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 }