bintree
["Little Useful Bits" Library]

This interface provides a facility which enables a client to order and access a set of arbitary data in a binary "tree". More...

Data Structures

struct  lub_bintree_node_s
struct  lub_bintree_key_s
struct  lub_bintree_s
struct  lub_bintree_iterator_s

Defines

#define lub_bintree_MAX_KEY_STORAGE   (80)

Typedefs

typedef lub_bintree_node_s lub_bintree_node_t
typedef int lub_bintree_compare_fn (const void *clientnode, const void *clientkey)
typedef lub_bintree_key_s lub_bintree_key_t
typedef void lub_bintree_getkey_fn (const void *clientnode, lub_bintree_key_t *key)
typedef lub_bintree_s lub_bintree_t
typedef lub_bintree_iterator_s lub_bintree_iterator_t

Functions

void lub_bintree_init (lub_bintree_t *tree, size_t node_offset, lub_bintree_compare_fn compareFn, lub_bintree_getkey_fn getkeyFn)
void lub_bintree_node_init (lub_bintree_node_t *node)
int lub_bintree_insert (lub_bintree_t *tree, void *clientnode)
void lub_bintree_remove (lub_bintree_t *tree, void *clientnode)
void * lub_bintree_findfirst (lub_bintree_t *tree)
void * lub_bintree_findlast (lub_bintree_t *tree)
void * lub_bintree_find (lub_bintree_t *tree, const void *key)
void * lub_bintree_findnext (lub_bintree_t *tree, const void *key)
void * lub_bintree_findprevious (lub_bintree_t *tree, const void *key)
void lub_bintree_iterator_init (lub_bintree_iterator_t *iter, lub_bintree_t *tree, const void *clientnode)
void * lub_bintree_iterator_next (lub_bintree_iterator_t *iter)
void * lub_bintree_iterator_previous (lub_bintree_iterator_t *iter)

Detailed Description

This interface provides a facility which enables a client to order and access a set of arbitary data in a binary "tree".

Each "tree" is defined by a number of "clientnodes" which are ordered according to a client defined "key".

A "clientkey" is a client specific entity which can be compared with a "clientnode" to determine which is the "greatest". In order to do this the client needs provide a comparison function for comparing a "clientnode" with a "clientkey", and a function to convert a "clientnode" into a "clientkey".

The client is responsible for providing each "clientnode" in a tree. This will typically contain some client specific data, but will also need to contain a bintree "node" which is used to structurally relate each node to one another in the tree. A specific "node" may only belong to one tree at a time, but an individual "clientnode" may contain multiple of these if necessary.

Implementation
The implementation of this interface uses a top-down splaying algorithm.
"Splay trees", or "self-adjusting search trees" are a simple and efficient data structure for storing an ordered set. The data structure consists of a binary tree, without parent pointers, and no additional fields. It allows searching, insertion, deletion, deletemin, deletemax, splitting, joining, and many other operations, all with amortized logarithmic performance. Since the trees adapt to the sequence of requests, their performance on real access patterns is typically even better. Splay trees are described in a number of texts and papers [1,2,3,4,5].
The code here is adapted from simple top-down splay, at the bottom of page 669 of [3]. It can be obtained via anonymous ftp from spade.pc.cs.cmu.edu in directory /usr/sleator/public.
The chief modification here is that the splay operation works even if the item being splayed is not in the tree, and even if the tree root of the tree is NULL. So the line:
t = splay(i, t);
causes it to search for item with key i in the tree rooted at t. If it's there, it is splayed to the root. If it isn't there, then the node put at the root is the last one before NULL that would have been reached in a normal binary search for i. (It's a neighbor of i in the tree.) This allows many other operations to be easily implemented.
[1] "Fundamentals of data structures in C", Horowitz, Sahni, and Anderson-Freed, Computer Science Press, pp 542-547.
[2] "Data Structures and Their Algorithms", Lewis and Denenberg, Harper Collins, 1991, pp 243-251.
[3] "Self-adjusting Binary Search Trees" Sleator and Tarjan, JACM Volume 32, No 3, July 1985, pp 652-686.
[4] "Data Structure and Algorithm Analysis", Mark Weiss, Benjamin Cummins, 1992, pp 119-130.
[5] "Data Structures, Algorithms, and Performance", Derick Wood, Addison-Wesley, 1993, pp 367-375.
The splay function is based on one written by Daniel Sleator, which is released in the public domain.
Author:
Graeme McKerrell
Date:
Created On : Fri Jan 23 12:50:18 2004
Version:
TESTED

Define Documentation

#define lub_bintree_MAX_KEY_STORAGE   (80)
 

This is used to size the key storage area for an opaque key. If any client requires a greater storage size then this will need to be increased.

Typedef Documentation

typedef int lub_bintree_compare_fn(const void *clientnode, const void *clientkey)
 

This type defines a callback function which will compare two "keys" with each other

Parameters:
clientnode the client node to compare
clientkey the key to compare with a node
Returns:
<0 if clientnode < clientkey; 0 if clientnode == clientkey; >0 if clientnode > clientkey

typedef void lub_bintree_getkey_fn(const void *clientnode, lub_bintree_key_t *key)
 

This type defines a callback function which will convert a client's "node" into a search "key"

Parameters:
clientnode the node from which to derive a key
key a reference to the key to fill out
Returns:
A "key" which corresponds the "node" in this view

typedef struct lub_bintree_iterator_s lub_bintree_iterator_t
 

This is used to perform iterations of a tree

typedef struct lub_bintree_key_s lub_bintree_key_t
 

This is used to declare an opaque key structure Typically a client would declare their own non-opaque structure which they would fill out appropriately

typedef struct lub_bintree_node_s lub_bintree_node_t
 

This type represents a bintree "node". Typically the client will have a "clientnode" structure which contains it's data. A bintree "node" is made one of the data elements of that structure. When the tree is initialised the client provides the offset into the structure of the "node" which is to be used for that tree.

typedef struct lub_bintree_s lub_bintree_t
 

This type represents an binary tree instance

Function Documentation

void* lub_bintree_find (  lub_bintree_t *  tree,
const void *  key
) 
 

This operation searches the specified "tree" for a "clientnode" which matches the specified "key"

Precondition:
The tree must be initialised
Returns:
"clientnode" instance or NULL if no node is found.
Parameters:
tree  the "tree" instance to invoke this operation upon
key  the "key" to search with

void* lub_bintree_findfirst (  lub_bintree_t *  tree  ) 
 

This operation returns the first "clientnode" present in the specified "tree"

Precondition:
The tree must be initialised
Returns:
"clientnode" instance or NULL if no nodes are present in this tree.
Parameters:
tree  the "tree" instance to invoke this operation upon

void* lub_bintree_findlast (  lub_bintree_t *  tree  ) 
 

This operation returns the last "clientnode" present in the specified "tree"

Precondition:
The tree must be initialised
Returns:
"clientnode" instance or NULL if no nodes are present in this tree.
Parameters:
tree  the "tree" instance to invoke this operation upon

void* lub_bintree_findnext (  lub_bintree_t *  tree,
const void *  key
) 
 

This operation searches the specified "tree" for a "clientnode" which is the one which logically follows the specified "key"

A "clientnode" with the specified "key" doesn't need to be in the tree.

Precondition:
The tree must be initialised
Returns:
"clientnode" instance or NULL if no node is found.
Parameters:
tree  the "tree" instance to invoke this operation upon
key  the "key" to search with

void* lub_bintree_findprevious (  lub_bintree_t *  tree,
const void *  key
) 
 

This operation searches the specified "tree" for a "clientnode" which is the one which logically preceeds the specified "key"

A "clientnode" with the specified "key" doesn't need to be in the tree.

Precondition:
The tree must be initialised
Returns:
"clientnode" instance or NULL if no node is found.
Parameters:
tree  the "tree" instance to invoke this operation upon
key  the "key" to search with

void lub_bintree_init (  lub_bintree_t *  tree,
size_t  node_offset,
lub_bintree_compare_fn  compareFn,
lub_bintree_getkey_fn  getkeyFn
) 
 

This operation initialises an instance of a binary tree.

Precondition:
none
Postcondition:
The tree is ready to have client nodes inserted.
Parameters:
tree  the "tree" instance to initialise
node_offset  the offset of the bintree "node" structure within the "clientnode" structure. This is typically passed using the offsetof() macro.
compareFn  a comparison function for comparing a "clientnode" with a "clientkey"
getkeyFn  a function which will fill out a "key" from a clientnode

int lub_bintree_insert (  lub_bintree_t *  tree,
void *  clientnode
) 
 

This operation adds a client node to the specified tree.

Precondition:
The tree must be initialised

The clientnode must be initialised

Returns:
0 if the "clientnode" is added correctly to the tree. If another "clientnode" already exists in the tree with the same key, then -1 is returned, and the tree remains unchanged.
Postcondition:
If the bintree "node" is already part of a tree, then an assert will fire.
Parameters:
tree  the "tree" instance to invoke this operation upon
clientnode  a pointer to a client node. NB the tree can find the necessary lub_BintreeNodeT from it's stored offset.

void lub_bintree_iterator_init (  lub_bintree_iterator_t *  iter,
lub_bintree_t *  tree,
const void *  clientnode
) 
 

This operation initialises an iterator. This can then be subsequently used for iterating through a tree. This will work even if the "clientnode" which defined the current iterator has been removed before the next iterator operation.

Precondition:
The tree must be initialised

The clientnode must be initialised and valid at the time of this call

Postcondition:
The interator instance will be updated to reference the position in the tree for the clientnode.
Parameters:
iter  the iterator instance to initialise
tree  the tree to associate with this iterator
clientnode  the starting point for the iteration

void* lub_bintree_iterator_next (  lub_bintree_iterator_t *  iter  ) 
 

This operation returns the next "clientnode" in an iteration.

Precondition:
The interator instance must have been initialised
Returns:
"clientnode" instance or NULL if the iteration has reached the end of the tree.
Postcondition:
The interator instance will be updated to reference the position in the tree for the returned value.
Parameters:
iter  the iterator instance to invoke this operation upon.

void* lub_bintree_iterator_previous (  lub_bintree_iterator_t *  iter  ) 
 

This operation returns the previous "clientnode" in an iteration.

Precondition:
The interator instance must have been initialised
Returns:
"clientnode" instance or NULL if the iteration has reached the beginning of the tree.
Postcondition:
The interator instance will be updated to reference the position in the tree for the returned value.
Parameters:
iter  the iterator instance to invoke this operation upon.

void lub_bintree_node_init (  lub_bintree_node_t *  node  ) 
 

This operation is called to initialise a "clientnode" ready for insertion into a tree. This is only required once after the memory for a node has been allocated.

Precondition:
none
Postcondition:
The node is ready to be inserted into a tree.
Parameters:
node  the bintree node to initialise

void lub_bintree_remove (  lub_bintree_t *  tree,
void *  clientnode
) 
 

This operation removes a "clientnode" from the specified "tree"

Precondition:
The tree must be initialised

The clientnode must be initialised

Postcondition:
The "clientnode" will no longer be part of the specified tree, and will be made available for re-insertion

If the clientnode is not present in the specified tree, then an assert will fire.

Parameters:
tree  the "tree" instance to invoke this operation upon
clientnode  the node to remove

Generated on Fri Jun 2 10:49:38 2006 for CLISH by  doxygen 1.4.6