14710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* "Rotating trees" (Armin Rigo) 24710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * 34710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * Google "splay trees" for the general idea. 44710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * 54710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * It's a dict-like data structure that works best when accesses are not 64710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * random, but follow a strong pattern. The one implemented here is for 74710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * access patterns where the same small set of keys is looked up over 84710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * and over again, and this set of keys evolves slowly over time. 94710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#include <stdlib.h> 124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define EMPTY_ROTATING_TREE ((rotating_node_t *)NULL) 144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtypedef struct rotating_node_s rotating_node_t; 164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtypedef int (*rotating_tree_enum_fn) (rotating_node_t *node, void *arg); 174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstruct rotating_node_s { 194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm void *key; 204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rotating_node_t *left; 214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rotating_node_t *right; 224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm}; 234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmvoid RotatingTree_Add(rotating_node_t **root, rotating_node_t *node); 254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmrotating_node_t* RotatingTree_Get(rotating_node_t **root, void *key); 264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmint RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn, 274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm void *arg); 28