CLISH  0.7.3
Data Structures | Macros | Typedefs | Functions

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
 

Macros

#define lub_bintree_MAX_KEY_STORAGE   (200)
 

Typedefs

typedef struct lub_bintree_node_s lub_bintree_node_t
 
typedef int lub_bintree_compare_fn (const void *clientnode, const void *clientkey)
 
typedef struct lub_bintree_key_s lub_bintree_key_t
 
typedef void lub_bintree_getkey_fn (const void *clientnode, lub_bintree_key_t *key)
 
typedef struct lub_bintree_s lub_bintree_t
 
typedef struct
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)
 
void lub_bintree_dump (lub_bintree_t *tree)
 

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

Macro Definition Documentation

#define lub_bintree_MAX_KEY_STORAGE   (200)

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
clientnodethe client node to compare
clientkeythe 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
clientnodethe node from which to derive a key
keya reference to the key to fill out
Returns
A "key" which corresponds the "node" in this view

This is used to perform iterations of a tree

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

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_dump ( lub_bintree_t tree)

This operation dumps the node list of the specified tree to stdout

Precondition
The tree must be initialised
Postcondition
The structure of the tree will be unaltered.
Parameters
treethe "tree" instance to invoke this operation upon
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
treethe "tree" instance to invoke this operation upon
keythe "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
treethe "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
treethe "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
treethe "tree" instance to invoke this operation upon
keythe "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
treethe "tree" instance to invoke this operation upon
keythe "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
treethe "tree" instance to initialise
node_offsetthe offset of the bintree "node" structure within the "clientnode" structure. This is typically passed using the offsetof() macro.
compareFna comparison function for comparing a "clientnode" with a "clientkey"
getkeyFna 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
treethe "tree" instance to invoke this operation upon
clientnodea 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
iterthe iterator instance to initialise
treethe tree to associate with this iterator
clientnodethe 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
iterthe 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
iterthe 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
nodethe 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
treethe "tree" instance to invoke this operation upon
clientnodethe node to remove