1 /* "Rotating trees" (Armin Rigo) 2 * 3 * Google "splay trees" for the general idea. 4 * 5 * It's a dict-like data structure that works best when accesses are not 6 * random, but follow a strong pattern. The one implemented here is for 7 * access patterns where the same small set of keys is looked up over 8 * and over again, and this set of keys evolves slowly over time. 9 */ 10 11 #include <stdlib.h> 12 13 #define EMPTY_ROTATING_TREE ((rotating_node_t *)NULL) 14 15 typedef struct rotating_node_s rotating_node_t; 16 typedef int (*rotating_tree_enum_fn) (rotating_node_t *node, void *arg); 17 18 struct rotating_node_s { 19 void *key; 20 rotating_node_t *left; 21 rotating_node_t *right; 22 }; 23 24 void RotatingTree_Add(rotating_node_t **root, rotating_node_t *node); 25 rotating_node_t* RotatingTree_Get(rotating_node_t **root, void *key); 26 int RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn, 27 void *arg); 28
