Revert "Add some basic tests to check out fuse"
[openafs.git] / 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 }