14710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#include "rotatingtree.h" 24710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 34710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define KEY_LOWER_THAN(key1, key2) ((char*)(key1) < (char*)(key2)) 44710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 54710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* The randombits() function below is a fast-and-dirty generator that 64710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * is probably irregular enough for our purposes. Note that it's biased: 74710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * I think that ones are slightly more probable than zeroes. It's not 84710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * important here, though. 94710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic unsigned int random_value = 1; 124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic unsigned int random_stream = 0; 134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmrandombits(int bits) 164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int result; 184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (random_stream < (1U << bits)) { 194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm random_value *= 1082527; 204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm random_stream = random_value; 214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = random_stream & ((1<<bits)-1); 234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm random_stream >>= bits; 244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Insert a new node into the tree. 294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (*root) is modified to point to the new root. */ 304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmvoid 314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmRotatingTree_Add(rotating_node_t **root, rotating_node_t *node) 324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (*root != NULL) { 344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (KEY_LOWER_THAN(node->key, (*root)->key)) 354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm root = &((*root)->left); 364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else 374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm root = &((*root)->right); 384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm node->left = NULL; 404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm node->right = NULL; 414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm *root = node; 424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Locate the node with the given key. This is the most complicated 454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm function because it occasionally rebalances the tree to move the 464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm resulting node closer to the root. */ 474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmrotating_node_t * 484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmRotatingTree_Get(rotating_node_t **root, void *key) 494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (randombits(3) != 4) { 514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Fast path, no rebalancing */ 524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rotating_node_t *node = *root; 534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (node != NULL) { 544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (node->key == key) 554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return node; 564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (KEY_LOWER_THAN(key, node->key)) 574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm node = node->left; 584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else 594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm node = node->right; 604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else { 644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rotating_node_t **pnode = root; 654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rotating_node_t *node = *pnode; 664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rotating_node_t *next; 674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rotate; 684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (node == NULL) 694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (1) { 714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (node->key == key) 724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return node; 734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rotate = !randombits(1); 744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (KEY_LOWER_THAN(key, node->key)) { 754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm next = node->left; 764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (next == NULL) 774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rotate) { 794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm node->left = next->right; 804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm next->right = node; 814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm *pnode = next; 824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else 844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm pnode = &(node->left); 854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else { 874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm next = node->right; 884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (next == NULL) 894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rotate) { 914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm node->right = next->left; 924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm next->left = node; 934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm *pnode = next; 944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else 964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm pnode = &(node->right); 974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm node = next; 994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 1024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Enumerate all nodes in the tree. The callback enumfn() should return 1044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm zero to continue the enumeration, or non-zero to interrupt it. 1054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm A non-zero value is directly returned by RotatingTree_Enum(). */ 1064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmint 1074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmRotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn, 1084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm void *arg) 1094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 1104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int result; 1114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rotating_node_t *node; 1124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (root != NULL) { 1134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = RotatingTree_Enum(root->left, enumfn, arg); 1144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result != 0) return result; 1154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm node = root->right; 1164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = enumfn(root, arg); 1174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result != 0) return result; 1184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm root = node; 1194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 1214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 122