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;
      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;
      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  }