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