blob: 39c6dd53ede34427b2fc0ebc9139755f17a5993d [file] [log] [blame]
Armin Rigoa871ef22006-02-08 12:53:56 +00001#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
11static unsigned int random_value = 1;
12static unsigned int random_stream = 0;
13
14static int
15randombits(int bits)
16{
17 int result;
Tim Peters219c1642006-02-15 03:01:30 +000018 if (random_stream < (1U << bits)) {
Armin Rigoa871ef22006-02-08 12:53:56 +000019 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. */
30void
31RotatingTree_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. */
47rotating_node_t *
48RotatingTree_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(). */
106int
107RotatingTree_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}