1 #include "rotatingtree.h"
2
3 #define KEY_LOWER_THAN(key1, key2) ((char*)(key1) < (char*)(key2))
4
5 /* The randombits() function below is a fast-and-dirty generator that
6 * is probably irregular enough for our purposes. Note that it's biased:
7 * I think that ones are slightly more probable than zeroes. It's not
8 * important here, though.
9 */
10
11 static unsigned int random_value = 1;
12 static unsigned int random_stream = 0;
13
14 static int
randombits(int bits)15 randombits(int bits)
16 {
17 int result;
18 if (random_stream < (1U << bits)) {
19 random_value *= 1082527;
20 random_stream = random_value;
21 }
22 result = random_stream & ((1<<bits)-1);
23 random_stream >>= bits;
24 return result;
25 }
26
27
28 /* Insert a new node into the tree.
29 (*root) is modified to point to the new root. */
30 void
RotatingTree_Add(rotating_node_t ** root,rotating_node_t * node)31 RotatingTree_Add(rotating_node_t **root, rotating_node_t *node)
32 {
33 while (*root != NULL) {
34 if (KEY_LOWER_THAN(node->key, (*root)->key))
35 root = &((*root)->left);
36 else
37 root = &((*root)->right);
38 }
39 node->left = NULL;
40 node->right = NULL;
41 *root = node;
42 }
43
44 /* Locate the node with the given key. This is the most complicated
45 function because it occasionally rebalances the tree to move the
46 resulting node closer to the root. */
47 rotating_node_t *
RotatingTree_Get(rotating_node_t ** root,void * key)48 RotatingTree_Get(rotating_node_t **root, void *key)
49 {
50 if (randombits(3) != 4) {
51 /* Fast path, no rebalancing */
52 rotating_node_t *node = *root;
53 while (node != NULL) {
54 if (node->key == key)
55 return node;
56 if (KEY_LOWER_THAN(key, node->key))
57 node = node->left;
58 else
59 node = node->right;
60 }
61 return NULL;
62 }
63 else {
64 rotating_node_t **pnode = root;
65 rotating_node_t *node = *pnode;
66 rotating_node_t *next;
67 int rotate;
68 if (node == NULL)
69 return NULL;
70 while (1) {
71 if (node->key == key)
72 return node;
73 rotate = !randombits(1);
74 if (KEY_LOWER_THAN(key, node->key)) {
75 next = node->left;
76 if (next == NULL)
77 return NULL;
78 if (rotate) {
79 node->left = next->right;
80 next->right = node;
81 *pnode = next;
82 }
83 else
84 pnode = &(node->left);
85 }
86 else {
87 next = node->right;
88 if (next == NULL)
89 return NULL;
90 if (rotate) {
91 node->right = next->left;
92 next->left = node;
93 *pnode = next;
94 }
95 else
96 pnode = &(node->right);
97 }
98 node = next;
99 }
100 }
101 }
102
103 /* Enumerate all nodes in the tree. The callback enumfn() should return
104 zero to continue the enumeration, or non-zero to interrupt it.
105 A non-zero value is directly returned by RotatingTree_Enum(). */
106 int
RotatingTree_Enum(rotating_node_t * root,rotating_tree_enum_fn enumfn,void * arg)107 RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn,
108 void *arg)
109 {
110 int result;
111 rotating_node_t *node;
112 while (root != NULL) {
113 result = RotatingTree_Enum(root->left, enumfn, arg);
114 if (result != 0) return result;
115 node = root->right;
116 result = enumfn(root, arg);
117 if (result != 0) return result;
118 root = node;
119 }
120 return 0;
121 }
122