1 #ifndef _SPLAY_TREE_H_ 2 #define _SPLAY_TREE_H_ 3 #include "first.h" 4 5 typedef struct tree_node { 6 struct tree_node * left, * right; 7 int key; 8 int size; /* maintained to be the number of nodes rooted here */ 9 10 void *data; 11 } splay_tree; 12 13 14 splay_tree * splaytree_splay (splay_tree *t, int key); 15 splay_tree * splaytree_insert(splay_tree *t, int key, void *data); 16 splay_tree * splaytree_delete(splay_tree *t, int key); 17 splay_tree * splaytree_size(splay_tree *t); 18 19 #define splaytree_size(x) (((x)==NULL) ? 0 : ((x)->size)) 20 /* This macro returns the size of a node. Unlike "x->size", */ 21 /* it works even if x=NULL. The test could be avoided by using */ 22 /* a special version of NULL which was a real node with size 0. */ 23 24 25 #include "algo_md.h" 26 27 __attribute_pure__ 28 static inline int32_t splaytree_djbhash(const char *str, const uint32_t len); 29 static inline int32_t splaytree_djbhash(const char *str, const uint32_t len) 30 { 31 /* strip highest bit of hash value for splaytree */ 32 return (int32_t)(djbhash(str,len,DJBHASH_INIT) & ~(((uint32_t)1) << 31)); 33 } 34 35 36 #endif 37