Mercurial > cpython-lru_cache-weakref
annotate Modules/rotatingtree.c @ 58765:2ba7677bfa95 legacy-trunk
testCopysign was defined twice in test_math; combine the definitions
| author | Mark Dickinson <dickinsm@gmail.com> |
|---|---|
| date | Sat, 06 Feb 2010 23:11:25 +0000 |
| parents | db2fca9ea264 |
| children | fd25030223b0 |
| rev | line source |
|---|---|
| 36459 | 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; | |
|
36496
db2fca9ea264
randombits(): Stop compiler warning about mixing
Tim Peters <tim.peters@gmail.com>
parents:
36459
diff
changeset
|
18 if (random_stream < (1U << bits)) { |
| 36459 | 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 } |