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 |
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 |
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 * |
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 |
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 | |