summaryrefslogtreecommitdiffstats
path: root/Modules/rotatingtree.c
diff options
context:
space:
mode:
authorAntoine Pitrou <solipsis@pitrou.net>2010-05-09 15:52:27 (GMT)
committerAntoine Pitrou <solipsis@pitrou.net>2010-05-09 15:52:27 (GMT)
commitf95a1b3c53bdd678b64aa608d4375660033460c3 (patch)
treea8bee40b1b14e28ff5978ea519f3035a3c399912 /Modules/rotatingtree.c
parentbd250300191133d276a71b395b6428081bf825b8 (diff)
downloadcpython-f95a1b3c53bdd678b64aa608d4375660033460c3.zip
cpython-f95a1b3c53bdd678b64aa608d4375660033460c3.tar.gz
cpython-f95a1b3c53bdd678b64aa608d4375660033460c3.tar.bz2
Recorded merge of revisions 81029 via svnmerge from
svn+ssh://pythondev@svn.python.org/python/trunk ........ r81029 | antoine.pitrou | 2010-05-09 16:46:46 +0200 (dim., 09 mai 2010) | 3 lines Untabify C files. Will watch buildbots. ........
Diffstat (limited to 'Modules/rotatingtree.c')
-rw-r--r--Modules/rotatingtree.c160
1 files changed, 80 insertions, 80 deletions
diff --git a/Modules/rotatingtree.c b/Modules/rotatingtree.c
index 39c6dd5..07e08bc 100644
--- a/Modules/rotatingtree.c
+++ b/Modules/rotatingtree.c
@@ -14,14 +14,14 @@ static unsigned int random_stream = 0;
static int
randombits(int bits)
{
- int result;
- if (random_stream < (1U << bits)) {
- random_value *= 1082527;
- random_stream = random_value;
- }
- result = random_stream & ((1<<bits)-1);
- random_stream >>= bits;
- return result;
+ int result;
+ if (random_stream < (1U << bits)) {
+ random_value *= 1082527;
+ random_stream = random_value;
+ }
+ result = random_stream & ((1<<bits)-1);
+ random_stream >>= bits;
+ return result;
}
@@ -30,15 +30,15 @@ randombits(int bits)
void
RotatingTree_Add(rotating_node_t **root, rotating_node_t *node)
{
- while (*root != NULL) {
- if (KEY_LOWER_THAN(node->key, (*root)->key))
- root = &((*root)->left);
- else
- root = &((*root)->right);
- }
- node->left = NULL;
- node->right = NULL;
- *root = node;
+ while (*root != NULL) {
+ if (KEY_LOWER_THAN(node->key, (*root)->key))
+ root = &((*root)->left);
+ else
+ root = &((*root)->right);
+ }
+ node->left = NULL;
+ node->right = NULL;
+ *root = node;
}
/* Locate the node with the given key. This is the most complicated
@@ -47,57 +47,57 @@ RotatingTree_Add(rotating_node_t **root, rotating_node_t *node)
rotating_node_t *
RotatingTree_Get(rotating_node_t **root, void *key)
{
- if (randombits(3) != 4) {
- /* Fast path, no rebalancing */
- rotating_node_t *node = *root;
- while (node != NULL) {
- if (node->key == key)
- return node;
- if (KEY_LOWER_THAN(key, node->key))
- node = node->left;
- else
- node = node->right;
- }
- return NULL;
- }
- else {
- rotating_node_t **pnode = root;
- rotating_node_t *node = *pnode;
- rotating_node_t *next;
- int rotate;
- if (node == NULL)
- return NULL;
- while (1) {
- if (node->key == key)
- return node;
- rotate = !randombits(1);
- if (KEY_LOWER_THAN(key, node->key)) {
- next = node->left;
- if (next == NULL)
- return NULL;
- if (rotate) {
- node->left = next->right;
- next->right = node;
- *pnode = next;
- }
- else
- pnode = &(node->left);
- }
- else {
- next = node->right;
- if (next == NULL)
- return NULL;
- if (rotate) {
- node->right = next->left;
- next->left = node;
- *pnode = next;
- }
- else
- pnode = &(node->right);
- }
- node = next;
- }
- }
+ if (randombits(3) != 4) {
+ /* Fast path, no rebalancing */
+ rotating_node_t *node = *root;
+ while (node != NULL) {
+ if (node->key == key)
+ return node;
+ if (KEY_LOWER_THAN(key, node->key))
+ node = node->left;
+ else
+ node = node->right;
+ }
+ return NULL;
+ }
+ else {
+ rotating_node_t **pnode = root;
+ rotating_node_t *node = *pnode;
+ rotating_node_t *next;
+ int rotate;
+ if (node == NULL)
+ return NULL;
+ while (1) {
+ if (node->key == key)
+ return node;
+ rotate = !randombits(1);
+ if (KEY_LOWER_THAN(key, node->key)) {
+ next = node->left;
+ if (next == NULL)
+ return NULL;
+ if (rotate) {
+ node->left = next->right;
+ next->right = node;
+ *pnode = next;
+ }
+ else
+ pnode = &(node->left);
+ }
+ else {
+ next = node->right;
+ if (next == NULL)
+ return NULL;
+ if (rotate) {
+ node->right = next->left;
+ next->left = node;
+ *pnode = next;
+ }
+ else
+ pnode = &(node->right);
+ }
+ node = next;
+ }
+ }
}
/* Enumerate all nodes in the tree. The callback enumfn() should return
@@ -105,17 +105,17 @@ RotatingTree_Get(rotating_node_t **root, void *key)
A non-zero value is directly returned by RotatingTree_Enum(). */
int
RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn,
- void *arg)
+ void *arg)
{
- int result;
- rotating_node_t *node;
- while (root != NULL) {
- result = RotatingTree_Enum(root->left, enumfn, arg);
- if (result != 0) return result;
- node = root->right;
- result = enumfn(root, arg);
- if (result != 0) return result;
- root = node;
- }
- return 0;
+ int result;
+ rotating_node_t *node;
+ while (root != NULL) {
+ result = RotatingTree_Enum(root->left, enumfn, arg);
+ if (result != 0) return result;
+ node = root->right;
+ result = enumfn(root, arg);
+ if (result != 0) return result;
+ root = node;
+ }
+ return 0;
}