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