Line data Source code
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 5308 : randombits(int bits) 16 : { 17 : int result; 18 5308 : if (random_stream < (1U << bits)) { 19 452 : random_value *= 1082527; 20 452 : random_stream = random_value; 21 : } 22 5308 : result = random_stream & ((1<<bits)-1); 23 5308 : random_stream >>= bits; 24 5308 : 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 540 : RotatingTree_Add(rotating_node_t **root, rotating_node_t *node) 32 : { 33 2307 : while (*root != NULL) { 34 1767 : if (KEY_LOWER_THAN(node->key, (*root)->key)) 35 709 : root = &((*root)->left); 36 : else 37 1058 : root = &((*root)->right); 38 : } 39 540 : node->left = NULL; 40 540 : node->right = NULL; 41 540 : *root = node; 42 540 : } 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 3872 : RotatingTree_Get(rotating_node_t **root, void *key) 49 : { 50 3872 : if (randombits(3) != 4) { 51 : /* Fast path, no rebalancing */ 52 3504 : rotating_node_t *node = *root; 53 13834 : while (node != NULL) { 54 13354 : if (node->key == key) 55 3024 : return node; 56 10330 : if (KEY_LOWER_THAN(key, node->key)) 57 4466 : node = node->left; 58 : else 59 5864 : node = node->right; 60 : } 61 480 : return NULL; 62 : } 63 : else { 64 368 : rotating_node_t **pnode = root; 65 368 : rotating_node_t *node = *pnode; 66 : rotating_node_t *next; 67 : int rotate; 68 368 : if (node == NULL) 69 17 : return NULL; 70 : while (1) { 71 1744 : if (node->key == key) 72 308 : return node; 73 1436 : rotate = !randombits(1); 74 1436 : if (KEY_LOWER_THAN(key, node->key)) { 75 663 : next = node->left; 76 663 : if (next == NULL) 77 13 : return NULL; 78 650 : if (rotate) { 79 335 : node->left = next->right; 80 335 : next->right = node; 81 335 : *pnode = next; 82 : } 83 : else 84 315 : pnode = &(node->left); 85 : } 86 : else { 87 773 : next = node->right; 88 773 : if (next == NULL) 89 30 : return NULL; 90 743 : if (rotate) { 91 382 : node->right = next->left; 92 382 : next->left = node; 93 382 : *pnode = next; 94 : } 95 : else 96 361 : pnode = &(node->right); 97 : } 98 1393 : 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 1589 : RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn, 108 : void *arg) 109 : { 110 : int result; 111 : rotating_node_t *node; 112 2732 : while (root != NULL) { 113 1143 : result = RotatingTree_Enum(root->left, enumfn, arg); 114 1143 : if (result != 0) return result; 115 1143 : node = root->right; 116 1143 : result = enumfn(root, arg); 117 1143 : if (result != 0) return result; 118 1143 : root = node; 119 : } 120 1589 : return 0; 121 : }