7 #include <tests/tap/basic.h>
10 #include <opr/rbtree.h>
13 struct opr_rbtree_node node;
17 int _checkTree(struct opr_rbtree_node *node)
19 struct opr_rbtree_node *left, *right;
28 /* Leaf nodes are always black */
29 if (node->red && ((left && left->red) || (right &&right->red))) {
30 printf("Consecutive red nodes\n");
34 /* XXX - Check ordering in nodes */
36 lheight = _checkTree(left);
37 rheight = _checkTree(right);
39 if (lheight !=0 && rheight !=0 && lheight != rheight) {
40 printf("Left and right branches have differing number of black nodes\n");
44 if (lheight !=0 && rheight !=0)
45 return node->red ? lheight : lheight+1;
51 checkTree(struct opr_rbtree *head) {
52 return _checkTree(head->root);
56 insertNode(struct opr_rbtree *head, int value) {
58 struct intnode *inode;
59 struct opr_rbtree_node *parent, **childptr;
61 inode = malloc(sizeof(struct intnode));
64 childptr = &head->root;
68 struct intnode *tnode;
70 tnode = opr_containerof(parent, struct intnode, node);
72 if (value < tnode->value)
73 childptr = &(*childptr)->left;
74 else if (value > tnode->value)
75 childptr = &(*childptr)->right;
79 opr_rbtree_insert(head, parent, childptr, &inode->node);
84 countNodes(struct opr_rbtree *head) {
85 struct opr_rbtree_node *node;
88 node = opr_rbtree_first(head);
93 while ((node = opr_rbtree_next(node)))
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
103 createTree(struct opr_rbtree *head)
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);
113 if (countNodes(head) != 1001 - counter ) {
114 printf("Tree has fewer nodes than inserted : %d", 1001 - counter);
121 /* Randomly remove nodes from the tree, this is really, really inefficient, but
125 destroyTree(struct opr_rbtree *head)
129 for (counter = 1000; counter>0; counter--) {
130 struct opr_rbtree_node *node;
133 remove = random() % counter;
134 node = opr_rbtree_first(head);
135 for (i=0; i<remove; i++)
136 node = opr_rbtree_next(node);
138 opr_rbtree_remove(head, node);
139 if (countNodes(head) != counter-1) {
140 printf("Tree has lost nodes after %d deletions", 1001 - counter);
144 if (!checkTree(head)) {
145 printf("Tree check failed at %d removals\n", 1001 - counter);
155 struct opr_rbtree head;
159 opr_rbtree_init(&head);
160 ok(1, "Initialising the tree works");
162 ok(createTree(&head), "Creating tree with 1000 nodes works");
163 ok(destroyTree(&head), "Tree retains consistency as nodes deleted");