splay.h File Reference

#include "common.h"
#include "collection.h"
#include "vector.h"
#include "mempool.h"

Go to the source code of this file.

Data Structures

struct  _cp_splaynode
struct  _cp_splaytree
#define cp_splaytree_rdlock(tree)   (cp_splaytree_lock((tree), COLLECTION_LOCK_READ))
#define cp_splaytree_wrlock(tree)   (cp_splaytree_lock((tree), COLLECTION_LOCK_WRITE))
typedef CPROPS_DLL struct
typedef CPROPS_DLL struct
CPROPS_DLL cp_splaynode * cp_splaynode_create (void *key, void *value, cp_mempool *pool)
CPROPS_DLL void cp_splaytree_destroy_node (struct _cp_splaytree *tree, cp_splaynode *node)
CPROPS_DLL void cp_splaytree_destroy_node_deep (struct _cp_splaytree *owner, cp_splaynode *node)
CPROPS_DLL cp_splaytree * cp_splaytree_create (cp_compare_fn cmp)
CPROPS_DLL cp_splaytree * cp_splaytree_create_by_option (int mode, cp_compare_fn cmp, cp_copy_fn key_copy, cp_destructor_fn key_dtr, cp_copy_fn val_copy, cp_destructor_fn val_dtr)
CPROPS_DLL void cp_splaytree_destroy (cp_splaytree *tree)
CPROPS_DLL void cp_splaytree_destroy_custom (cp_splaytree *tree, cp_destructor_fn key_dtr, cp_destructor_fn val_dtr)
CPROPS_DLL void * cp_splaytree_insert (cp_splaytree *tree, void *key, void *value)
CPROPS_DLL void * cp_splaytree_get (cp_splaytree *tree, void *key)
CPROPS_DLL void * cp_splaytree_find (cp_splaytree *tree, void *key, cp_op op)
CPROPS_DLL int cp_splaytree_contains (cp_splaytree *tree, void *key)
CPROPS_DLL void * cp_splaytree_delete (cp_splaytree *tree, void *key)
CPROPS_DLL int cp_splaytree_callback_preorder (cp_splaytree *tree, cp_callback_fn callback, void *prm)
CPROPS_DLL int cp_splaytree_callback (cp_splaytree *tree, cp_callback_fn callback, void *prm)
CPROPS_DLL int cp_splaytree_callback_postorder (cp_splaytree *tree, cp_callback_fn callback, void *prm)
CPROPS_DLL int cp_splaytree_count (cp_splaytree *tree)
CPROPS_DLL int cp_splaytree_lock (cp_splaytree *tree, int type)
CPROPS_DLL int cp_splaytree_unlock (cp_splaytree *tree)
CPROPS_DLL int cp_splaytree_get_mode (cp_splaytree *tree)
CPROPS_DLL int cp_splaytree_set_mode (cp_splaytree *tree, int mode)
CPROPS_DLL int cp_splaytree_unset_mode (cp_splaytree *tree, int mode)
CPROPS_DLL void cp_splaytree_dump (cp_splaytree *tree)
CPROPS_DLL int cp_splaytree_use_mempool (cp_splaytree *tree, cp_mempool *pool)
CPROPS_DLL int cp_splaytree_share_mempool (cp_splaytree *tree, cp_shared_mempool *pool)

Detailed Description

splay tree definitions

splay trees move the node last accessed to the root of the tree as part of every operation. This makes tree operations slower than in AVL or red-black trees. A natural application for splay trees would be in implementing a cache, where a small number of keys out of a large search space are expected to be accessed at a significantly higher probability than average.

The splay tree was introduced by Daniel D. Sleator and Robert E. Tarjan in an article titled Self-Adjusting Binary Search Trees, 1985

Definition in file splay.h.

Generated on Mon Dec 5 23:00:22 2011 for cprops by  doxygen 1.4.7