1 #include "rotatingtree.h"
3 #define KEY_LOWER_THAN(key1, key2) ((char*)(key1) < (char*)(key2))
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.
11 static unsigned int random_value
= 1;
12 static unsigned int random_stream
= 0;
18 if (random_stream
< (1<<bits
)) {
19 random_value
*= 1082527;
20 random_stream
= random_value
;
22 result
= random_stream
& ((1<<bits
)-1);
23 random_stream
>>= bits
;
28 /* Insert a new node into the tree.
29 (*root) is modified to point to the new root. */
31 RotatingTree_Add(rotating_node_t
**root
, rotating_node_t
*node
)
33 while (*root
!= NULL
) {
34 if (KEY_LOWER_THAN(node
->key
, (*root
)->key
))
35 root
= &((*root
)->left
);
37 root
= &((*root
)->right
);
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. */
48 RotatingTree_Get(rotating_node_t
**root
, void *key
)
50 if (randombits(3) != 4) {
51 /* Fast path, no rebalancing */
52 rotating_node_t
*node
= *root
;
53 while (node
!= NULL
) {
56 if (KEY_LOWER_THAN(key
, node
->key
))
64 rotating_node_t
**pnode
= root
;
65 rotating_node_t
*node
= *pnode
;
66 rotating_node_t
*next
;
73 rotate
= !randombits(1);
74 if (KEY_LOWER_THAN(key
, node
->key
)) {
79 node
->left
= next
->right
;
84 pnode
= &(node
->left
);
91 node
->right
= next
->left
;
96 pnode
= &(node
->right
);
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(). */
107 RotatingTree_Enum(rotating_node_t
*root
, rotating_tree_enum_fn enumfn
,
111 rotating_node_t
*node
;
112 while (root
!= NULL
) {
113 result
= RotatingTree_Enum(root
->left
, enumfn
, arg
);
114 if (result
!= 0) return result
;
116 result
= enumfn(root
, arg
);
117 if (result
!= 0) return result
;