Armin Rigo | a871ef2 | 2006-02-08 12:53:56 +0000 | [diff] [blame] | 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 |
Thomas Wouters | 477c8d5 | 2006-05-27 19:21:47 +0000 | [diff] [blame] | 7 | * access patterns where the same small set of keys is looked up over |
Armin Rigo | a871ef2 | 2006-02-08 12:53:56 +0000 | [diff] [blame] | 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 { |
Serhiy Storchaka | 598ceae | 2017-11-28 17:56:10 +0200 | [diff] [blame] | 19 | void *key; |
| 20 | rotating_node_t *left; |
| 21 | rotating_node_t *right; |
Armin Rigo | a871ef2 | 2006-02-08 12:53:56 +0000 | [diff] [blame] | 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, |
Serhiy Storchaka | 598ceae | 2017-11-28 17:56:10 +0200 | [diff] [blame] | 27 | void *arg); |