tests/opr/rbtree-t.c

   1 #include <afsconfig.h>
   2 #include <afs/param.h>
   3
   4 #include <stdlib.h>
   5 #include <stdio.h>
   6
   7 #include <tests/tap/basic.h>
   8
   9 #include <afs/opr.h>
  10 #include <opr/rbtree.h>
  11
  12 struct intnode {
  13     struct opr_rbtree_node node;
  14     int value;
  15 };
  16
  17 int _checkTree(struct opr_rbtree_node *node)
  18 {
  19     struct opr_rbtree_node *left, *right;
  20     int lheight, rheight;
  21
  22     if (node == NULL)
  23         return 1;
  24
  25     left = node->left;
  26     right = node->right;
  27
  28     /* Leaf nodes are always black */
  29     if (node->red && ((left && left->red) || (right &&right->red))) {
  30         printf("Consecutive red nodes\n");
  31         return 0;
  32     }
  33
  34     /* XXX - Check ordering in nodes */
  35
  36     lheight = _checkTree(left);
  37     rheight = _checkTree(right);
  38
  39     if (lheight !=0 && rheight !=0 && lheight != rheight) {
  40         printf("Left and right branches have differing number of black nodes\n");
  41         return 0;
  42     }
  43
  44     if (lheight !=0 && rheight !=0)
  45         return node->red ? lheight : lheight+1;
  46     else
  47         return 0;
  48 }
  49
  50 int
  51 checkTree(struct opr_rbtree *head) {
  52     return _checkTree(head->root);
  53 }
  54
  55 int
  56 insertNode(struct opr_rbtree *head, int value) {
  57
  58     struct intnode *inode;
  59     struct opr_rbtree_node *parent, **childptr;
  60
  61     inode = malloc(sizeof(struct intnode));
  62     inode->value = value;
  63
  64     childptr = &head->root;
  65     parent = NULL;
  66
  67     while (*childptr) {
  68         struct intnode *tnode;
  69         parent = *childptr;
  70         tnode = opr_containerof(parent, struct intnode, node);
  71
  72         if (value < tnode->value)
  73             childptr = &(*childptr)->left;
  74         else if (value > tnode->value)
  75             childptr = &(*childptr)->right;
  76         else
  77             return -1;
  78     }
  79     opr_rbtree_insert(head, parent, childptr, &inode->node);
  80     return 0;
  81 }
  82
  83 int
  84 countNodes(struct opr_rbtree *head) {
  85     struct opr_rbtree_node *node;
  86     int count;
  87
  88     node = opr_rbtree_first(head);
  89     if (node == NULL)
  90         return 0;
  91
  92     count = 1;
  93     while ((node = opr_rbtree_next(node)))
  94         count++;
  95
  96     return count;
  97 }
  98
  99 /* Now, insert 1000 nodes into the tree, making sure with each insertion that
 100  * the tree is still valid, and has the correct number of nodes
 101  */
 102 int
 103 createTree(struct opr_rbtree *head)
 104 {
 105     int counter;
 106
 107     for (counter = 1000; counter>0; counter--) {
 108         while (insertNode(head, random())!=0);
 109         if (!checkTree(head)) {
 110            printf("Tree check failed at %d\n", 1001 - counter);
 111            return 0;
 112         }
 113         if (countNodes(head) != 1001 - counter ) {
 114            printf("Tree has fewer nodes than inserted : %d", 1001 - counter);
 115            return 0;
 116         }
 117     }
 118     return 1;
 119 }
 120
 121 /* Randomly remove nodes from the tree, this is really, really inefficient, but
 122  * hey
 123  */
 124 int
 125 destroyTree(struct opr_rbtree *head)
 126 {
 127     int counter;
 128
 129     for (counter = 1000; counter>0; counter--) {
 130         struct opr_rbtree_node *node;
 131         int remove, i;
 132
 133         remove = random() % counter;
 134         node = opr_rbtree_first(head);
 135         for (i=0; i<remove; i++)
 136             node = opr_rbtree_next(node);
 137
 138         opr_rbtree_remove(head, node);
 139         if (countNodes(head) != counter-1) {
 140             printf("Tree has lost nodes after %d deletions", 1001 - counter);
 141             return 0;
 142         }
 143
 144         if (!checkTree(head)) {
 145             printf("Tree check failed at %d removals\n", 1001 - counter);
 146             return 0;
 147         }
 148     }
 149     return 1;
 150 }
 151
 152 int
 153 main(void)
 154 {
 155     struct opr_rbtree head;
 156
 157     plan(3);
 158
 159     opr_rbtree_init(&head);
 160     ok(1, "Initialising the tree works");
 161
 162     ok(createTree(&head), "Creating tree with 1000 nodes works");
 163     ok(destroyTree(&head), "Tree retains consistency as nodes deleted");
 164
 165     return 0;
 166 }