Ignore:
Timestamp:
Mar 19, 2014, 11:11:30 AM (11 years ago)
Author:
dmik
Message:

python: Update vendor to 2.7.6.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • python/vendor/current/Modules/rotatingtree.c

    r2 r388  
    1515randombits(int bits)
    1616{
    17         int result;
    18         if (random_stream < (1U << bits)) {
    19                 random_value *= 1082527;
    20                 random_stream = random_value;
    21         }
    22         result = random_stream & ((1<<bits)-1);
    23         random_stream >>= bits;
    24         return result;
     17    int result;
     18    if (random_stream < (1U << bits)) {
     19        random_value *= 1082527;
     20        random_stream = random_value;
     21    }
     22    result = random_stream & ((1<<bits)-1);
     23    random_stream >>= bits;
     24    return result;
    2525}
    2626
    … …  
    3131RotatingTree_Add(rotating_node_t **root, rotating_node_t *node)
    3232{
    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;
     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;
    4242}
    4343
    … …  
    4848RotatingTree_Get(rotating_node_t **root, void *key)
    4949{
    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         }
     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    }
    101101}
    102102
    … …  
    106106int
    107107RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn,
    108                   void *arg)
     108                  void *arg)
    109109{
    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;
     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;
    121121}
Note: See TracChangeset for help on using the changeset viewer.