| // Note: This file is obtained from |
| // http://www.cs.utk.edu/~cs140/spring-2005/notes/Splay/ |
| // FIXME: This may not be the most efficient version of splay implementation |
| // This may be updated with a different splay implementation in near future |
| #ifndef _SPLAY_ |
| #define SPLAY |
| |
| typedef unsigned long Jval ; |
| |
| /* Node identities */ |
| |
| #define SPLAY_SENTINEL 0 |
| #define SPLAY_OTHER 1 |
| |
| typedef struct splay { |
| Jval key; |
| Jval val; |
| int is_sentinel; |
| struct splay *left; |
| struct splay *right; |
| struct splay *flink; |
| struct splay *blink; |
| struct splay *parent; |
| } Splay; |
| |
| extern "C" { |
| Splay *new_splay(); |
| void free_splay(Splay *); |
| Splay *splay_insert_ptr(Splay *tree, unsigned long key, Jval val); |
| Splay *splay_find_ptr(Splay *tree, unsigned long key); |
| Splay *splay_find_gte_ptr(Splay *tree, unsigned long key, int *found); |
| |
| Splay *splay_root(Splay *tree); |
| Splay *splay_first(Splay *tree); |
| Splay *splay_last(Splay *tree); |
| Splay *splay_next(Splay *node); |
| Splay *splay_prev(Splay *node); |
| Splay *splay_nil(Splay *tree); |
| |
| void splay_delete_node(Splay *node); |
| } |
| |
| #define splay_traverse(ptr, list) \ |
| for (ptr = splay_first(list); ptr != splay_nil(list); ptr = splay_next(ptr)) |
| #define splay_rtraverse(ptr, list) \ |
| for (ptr = splay_last(list); ptr != splay_nil(list); ptr = splay_prev(ptr)) |
| |
| #endif |