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   (200)
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)
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

---

Define 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:

	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_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:

tree	the "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:

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

---