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");