SplayTree.h File Reference

#include <TargConfig.h>

Include dependency graph for SplayTree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	SplayTreeNode
	Intrusive tree node. More...
struct	SplayTree
	Self-adjusting tree of caller-owned nodes, with unique keys. More...

Macros
#define	SplayTreeNode_getKey(o)   (o)->key
	Read a node's key. More...
#define	SplayTree_constructor(o, compareCB)
	Initialize an empty tree without allocating storage. More...
#define	SplayTree_getRoot(o)   (o)->root
	Read the current root without reshaping the tree. More...

Typedefs
typedef const void *	SplayTreeKey
	Borrowed key interpreted by SplayTree_Compare. More...
typedef struct SplayTreeNode	SplayTreeNode
	Intrusive tree node. More...
typedef int(*	SplayTree_Compare) (SplayTreeNode *n, SplayTreeKey k)
	Compare a search key with a node's key. More...
typedef int(*	SplayTree_Iter) (void *o, SplayTreeNode *n)
	Visit a node during SplayTree_iterate. More...
typedef struct SplayTree	SplayTree
	Self-adjusting tree of caller-owned nodes, with unique keys. More...

Functions
BA_API void	SplayTreeNode_constructor (SplayTreeNode *o, SplayTreeKey key)
	Initialize a node without allocating storage. More...
BA_API int	SplayTree_insert (SplayTree *o, SplayTreeNode *n)
	Insert a node. More...
BA_API SplayTreeNode *	SplayTree_find (SplayTree *o, SplayTreeKey key)
	Search and adjust the tree, even when no matching key is found. More...
BA_API int	SplayTree_remove (SplayTree *o, SplayTreeNode *n)
	Unlink a node and clear its left and right links. More...
BA_API int	SplayTree_iterate (SplayTree *o, void *userObj, SplayTree_Iter i)
	Visit nodes in root-left-right order, not sorted key order. More...

Macro Definition Documentation

SplayTree_constructor

#define SplayTree_constructor	(		o,
			compareCB
	)

Value:

   do { \
   (o)->compare = compareCB; \
   (o)->root = 0; \
} while(0)

Initialize an empty tree without allocating storage.

Parameters

[out]	o	Caller-owned tree object. Existing linked nodes are not freed.
[in]	compareCB	Required callback used to compare keys.

SplayTree_getRoot

#define SplayTree_getRoot

(

o

)

(o)->root

Read the current root without reshaping the tree.

Parameters

[in]

o

Initialized tree.

Returns

Borrowed root node, or NULL for an empty tree.

SplayTreeNode_getKey

#define SplayTreeNode_getKey

(

o

)

(o)->key

Read a node's key.

Parameters

[in]

o

Initialized node.

Returns

The borrowed key.

Typedef Documentation

SplayTree

typedef struct SplayTree SplayTree

Self-adjusting tree of caller-owned nodes, with unique keys.

Searches, including unsuccessful searches, may change the root and links. The tree does not allocate or free nodes or keys.

SplayTree_Compare

typedef int(* SplayTree_Compare) (SplayTreeNode *n, SplayTreeKey k)

Compare a search key with a node's key.

Parameters

[in]	n	Existing node; do not modify its links or key.
[in]	k	Search or insertion key.

Returns

Negative if k is less than n's key, zero if equal, positive if greater. Use one consistent ordering for every operation on the tree.

SplayTree_Iter

typedef int(* SplayTree_Iter) (void *o, SplayTreeNode *n)

Visit a node during SplayTree_iterate.

Parameters

[in]	o	The userObj pointer passed to SplayTree_iterate; may be NULL.
[in]	n	Current node. Do not insert, remove, find or otherwise reshape the tree from this callback, or free a node still being visited.

Returns

Zero to continue; any nonzero value stops traversal.

SplayTreeKey

typedef const void* SplayTreeKey

Borrowed key interpreted by SplayTree_Compare.

Its representation and NULL handling are defined by the comparison callback.

SplayTreeNode

typedef struct SplayTreeNode SplayTreeNode

Intrusive tree node.

The caller owns the node and key and must keep both valid while the node is in a tree. Initialize before insertion and do not change its key while it is linked.

Function Documentation

SplayTree_find()

BA_API SplayTreeNode * SplayTree_find	(	SplayTree *	o,
		SplayTreeKey	key
	)

Search and adjust the tree, even when no matching key is found.

Parameters

[in,out]	o	Initialized tree.
[in]	key	Search key interpreted by the comparison callback.

Returns

Borrowed matching node, or NULL if no match exists.

SplayTree_insert()

BA_API int SplayTree_insert	(	SplayTree *	o,
		SplayTreeNode *	n
	)

Insert a node.

Parameters

[in,out]	o	Initialized tree.
[in,out]	n	Initialized, unlinked node whose key must remain valid.

Returns

Zero on insertion, -1 if an equal key exists. No storage is freed.

SplayTree_iterate()

BA_API int SplayTree_iterate	(	SplayTree *	o,
		void *	userObj,
		SplayTree_Iter	i
	)

Visit nodes in root-left-right order, not sorted key order.

Parameters

[in]	o	Initialized tree. Do not reshape it during traversal.
[in]	userObj	Opaque callback context; may be NULL.
[in]	i	Required callback invoked once for each visited node.

Returns

Zero when all nodes were visited (including an empty tree), or -1 when the callback stopped traversal. Its particular nonzero value is not propagated. Traversal uses recursion proportional to the tree depth.

SplayTree_remove()

BA_API int SplayTree_remove	(	SplayTree *	o,
		SplayTreeNode *	n
	)

Unlink a node and clear its left and right links.

Parameters

[in,out]	o	Initialized tree.
[in,out]	n	Node to remove. A different node with an equal key is not removed. The caller retains ownership of n and its key.

Returns

Zero on removal, -1 if the specified node is not in the tree.

SplayTreeNode_constructor()

BA_API void SplayTreeNode_constructor	(	SplayTreeNode *	o,
		SplayTreeKey	key
	)

Initialize a node without allocating storage.

Parameters

[out]	o	Caller-owned node to initialize; must not be linked in a tree.
[in]	key	Borrowed key stored without copying.