Commit | Line | Data |
---|---|---|
805e021f CE |
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 | } |