include/c++/util/tests/rbtree.cc

   1 #include <util/rbtree.h>
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4 #include <time.h>
   5
   6 using Util::RBTree;
   7
   8 struct Data;
   9 //struct Node;
  10 typedef RBTree<Data, unsigned int, unsigned int> RBType;
  11
  12 #if 0
  13 struct Node {
  14         unsigned int data;
  15
  16         bool operator < (Node &d)
  17         {
  18                 return data < d.data;
  19         }
  20
  21         bool operator < (int d)
  22         {
  23                 return data < d;
  24         }
  25
  26         bool operator > (int d)
  27         {
  28                 return data > d;
  29         }
  30 };
  31
  32 #endif
  33 struct Data {
  34         unsigned int magic;
  35         RBType::Node rbtree_node;
  36
  37         Data()
  38         {
  39                 magic = 0xdeadbeef;
  40         }
  41 };
  42
  43 static const unsigned int rbtree_size = 1000000;
  44
  45 Data data[rbtree_size];
  46
  47 int main(void)
  48 {
  49         RBType rbtree;
  50         srandom(time(NULL));
  51
  52         for (unsigned int i = 0; i < rbtree_size; i++) {
  53                 Data *d = &data[i];
  54                 unsigned int val;
  55
  56                 do {
  57                         val = random() & 0x7fffffff;
  58                 } while (rbtree.find(val));
  59
  60                 d->rbtree_node.value = val;
  61                 rbtree.add(d);
  62         }
  63
  64         for (unsigned int i = 0; i < rbtree_size; i++) {
  65                 unsigned int val = data[i].rbtree_node.value;
  66                 Data *d = rbtree.find(val);
  67                 assert(d);
  68                 assert(d->rbtree_node.value == val);
  69                 rbtree.del(d);
  70         }
  71
  72         printf("PASSED\n");
  73 }