Ingres CL SP
From Ingres Community Wiki
|
Ingres Compatability Library |
General Library Specification - SP
Abstract
This is the specification of the SP facility provided by the general library for access to splay trees, an efficient, mostly balanced, in-memory tree structure.
Revision 1.2, 06-Jun-2008
Document History
- Revision 1.2, 06-Jun-2008
- Brought up-to-date and cleaned up.
- Revision 1.1, 15-Nov-1997
- Converted to HTML.
- Revision 1.0, 30-Jul-94
- Created from proposal approved on 30-oct-92.
Specification
Introduction
The splay tree (SP) factiliy provides access to a very efficient in-memory tree structure suitable for symbol tables, lookup tables, dictionaries, event-sets, and priority-queues.
Splay trees are also called "self-adjusting search trees". They are similar to avl-trees, but are not concerned with keeping the tree strictly balanced. Instead, the tree is dynamically reorganized in a simple way that yields a good amortized bound at the expense of worst case performance.
In performance, splay trees are of order n log2 n, like many other tree algorithms, but have good "K" characteristics for some applications. They are often better, because skewed access patterns drive the tree to a shape that favors the most recently accessed over the least recently touched. This makes them very good for the delete-min operation on a priority queue, where there are random insertions and a lot of delete-min operatons. In this case, the min object is almost always at the root, reducing to nearly O(1) actual performance.
A splay tree may not be a good sorter for an array (just use qsort) but may be good if you already have node-oriented objects.
Splay trees have a complicating property running on a threaded system: All access must be locked, since lookup traversals modify the shape of the tree.
Library
GL
Concepts
A splay tree is like other trees in that there are nodes go up, left, and right. However, they do not rigorously keep the tree balanced at insert time. Instead, operations on the tree do continuous partial reorganizations. Over time, these drive the tree into reasonable shape. The reorganization pulls recently accessed nodes towards the top of the tree, so one can also picture it as a caching tree.
Client code must provide its own structures and key comparison routines. In practice, it is probably easiest to encapsulate the SPBLK node structure inside a larger unit that also contains the real keys, pointing the SPBLK key field at either the whole structure or the real key part.
Splay Algorithm
The SPsplay function is used by most of the other splay tree functions, so it is presented here. The function descriptions often use the term splay as a verb, as in "is splayed", "has been splayed", or "avoiding splaying".
- SPsplay - reorganize tree t around node n
The tree is reorganized so that n is the root of the splay tree t; t is split from n up to the old root, with all nodes to the left of n (that is, with key values less than or equal to the key of n) ending up in the left subtree, and all nodes to the right of n (having key values greater than the key of n) ending up in the right subtree. The left branch of the right subtree and the right branch of the left subtree are shortened in the process
The algorithm assumes that n is not NULL and is in t. Results are unpredictable if n is not in t to start with.
SP functions
The following executable interfaces are provided.
Click on the name of a function to see detailed information.
| Name | Description |
|---|---|
| SPdelete | delete node by key. |
| SPdeq | dequeue head node. |
| SPenq | enqueue node after nodes with same key. |
| SPfhead | fast-find the head of the tree. |
| SPfnext | fast-find next. |
| SPfprev | fast-find previous. |
| SPftail | fast-find tail |
| SPhead | find head |
| SPinit | initialize a splay tree. |
| SPinstall | install node, no duplicates. |
| SPlookup | locate node by key. |
| SPnext | find next node. |
| SPprev | find previous node. |
| SPsplay | reorganize tree around node. |
The SP routines apply no interpretation on the data elements in the blocks. They rely on user-supplied comparison routines. They do not do any memory allocation, which is completely up to the client.
References
Splay trees were first described in Self Adjusting Binary Trees, by D. D. Sleator and R. E. Tarjan, Proc. ACM SIGACT Symposium on Theory of Computing (Boston, Apr 1983) 235-245. A more accessible article is Algorithm Design, Robert Tarjan's Turing Award Lecture reprinted in Comm. ACM 28, 3 (Mar. 1987) 204-212. Their performance characteristics were examined in An Empirical Comparison of Priority-Queue and Event-Set Implementations", by Douglas W. Jones, Comm. ACM 29, 4 (Apr. 1986) 300-311. The current implementation is derived from a C translation of the code used by Jones, available as Comp.sources.unix archive v14i087.
A more recent version can be found in Software Solutions in C, edited by Dale Schumacher, Academic Press Professional 1994 ISBN 0-12-632360-7. This comes with a disk.
Header file <sp.h>
SPBLK structure - a node in a tree
typedef struct _spblk SPBLK;
{
struct _spblk; /* clients should not look at these */
SPBLK *leftlink;
SPBLK *rightlink;
SPBLK *uplink; /* visible to clients */
PTR key;
}
SPTREE structure - tree definition
This structure is first filled in with a call to SPinit. Statistics are kept by the routines to see how effective the reorganization is. The number of lkpcmps/lookups and enqcmps/enqs estimation the effective tree depth.
typedef struct
{
SPBLK *root; /* root node */
SP_COMPARE_FUNC *compare; /* key comparison function */
/* Statistics, not strictly necessary, but handy for tuning */
i4 lookups; /* number of SPlookup()s */
i4 lkpcmps; /* number of lookup comparisons */
i4 enqs; /* number of SPenq()s */
i4 enqcmps; /* compares in SPenq */
i4 splays; /* number of splays */
i4 splayloops; /* number of loops inside splays */
} SPTREE;
SP_COMPARE_FUNC - function used to compare keys
This compares keys pointed to by the key field in SPBLKs. The function is called by the SP functions to compare keys during many of the splay tree operations. The compare function should return:
| -1 | if key1 < key2 |
| 0 | if key1 == key2 |
| +1 | if key1 < key2 |
typedef i4 SP_COMPARE_FUNC( PTR key1, PTR key2 );
Executable Interface
The following functions are provided.
SPdelete - delete node by key
The node is deleted from the tree. The resulting splay tree has been splayed around its new root, which is the successor of the node.
Inputs:
| n | the node to delete |
| t | the tree containing the node. |
Outputs:
| None |
Returns:
| none |
Definition:
VOID SPdelete(SPBLK *n, SPTREE *t);
SPdeq - dequeue head node
Remove and return the head node from a subtree; this deletes (and returns) the leftmost node from subtree, replacing it with its right subtree (if there is one). On the way to the leftmost node, rotations are performed to shorten the left branch of the tree.
Inputs:
| np | pointer to a variable holding the root of the subtree |
Outputs:
| none |
Returns:
| the leftmost node in the subtree, or NULL if the tree is empty |
Definition:
SPBLK *SPdeq(SPBLK **np);
Example:
SPBLK *
treedeq( SPTREE *t )
{
return( SPdeq( &t->root ) );
}
SPenq - enqueue node after nodes with same key
Put node n in tree t after all other nodes with the same key. When this is done, n will be the root of the splay tree representing t, all nodes in t with keys less than or equal to that of n will be in the left subtree, and all with greater keys will be in the right subtree. The tree is split into these subtrees from the top down, with rotations performed along the way to shorten the left branch of the right subtree and the right branch of the left subtree.
Inputs:
| n | node to add to the tree |
| t | tree to insert into |
Outputs:
| none |
Returns:
| the inserted node |
Definition:
SPBLK *SPenq(SPBLK *n, SPTREE *t);
SPfhead - fast-find the head of the tree
Returns a reference to the head event in the tree, avoiding splaying. Excessive use of this may leave the tree under-balanced. It just searches for and returns a pointer to the bottom of the left branch.
Inputs:
| t | pointer to the splay tree |
Outputs:
| none |
Returns:
| the first node in the tree, or NULL if the tree is empty |
Definition:
SPBLK *SPfhead(SPTREE *t);
SPfnext - fast-find next node
Return the successor of n. This is a fast (on average) version that does not splay, but which may leave the tree under-balanced.
Inputs:
| n | current node |
Outputs:
| none |
Returns:
| the node following n, or NULL if n is the tail |
Definition:
SPBLK *SPfnext(SPBLK *n);
SPfprev - fast-find previous node
Return the predecessor of n. This is a fast (on average) version that does not splay, but which may leave the tree under-balanced.
Inputs:
| n | the current node |
Outputs:
| none |
Returns:
| the previous node, or NULL if n is the head |
Definition:
SPBLK *SPfprev(SPBLK *n);
SPftail - fast-find tail
Return the last node in a tree, without reorganizing. This may leave the tree under-balanced.
Inputs:
| t | pointer to the splay tree |
Outputs:
| none |
Returns:
| the last node in the tree, or NULL if the tree is empty |
Definition:
SPBLK *SPfhead(SPTREE *t);
SPhead - find head
Returns the head node in tree t; t->root ends up pointing to the head node, and the old left branch of t is shortened, as if t had been splayed about the head element. This is done by dequeueing the head and then making the resulting tree the right child of the head returned by SPdeq.
SPfhead is faster but does not help the amortized performance.
Inputs:
| t | pointer to the splay tree |
Outputs:
| none |
Returns:
| the first node in the tree, or NULL if the tree is empty |
Definition:
SPBLK *SPhead(SPTREE *t);
SPinit - initialize tree
Initialize a splay tree, including a pointer to the comparison function to be used for ordering the tree.
Inputs:
| t | pointer to the tree to be initialized |
| compare | pointer to comparison function to be used for ordering the tree |
Outputs:
| none |
Returns:
| a pointer to the initialized tree |
Definition:
SPTREE *SPinit( SPTREE *t, SP_COMPARE_FUNC *compare );
See SP_COMPAR_FUNC for the definition of the compare function.
SPinstall - install node, checking for duplicates
Insert a node into a tree if one with the same key does not already exist. Returns either the inserted node or the old node with the same key. The tree is splayed around n such that n becomes the root of the tree.
Inputs:
| n | a node not currently in the tree with a key to be inserted |
| t | the destination tree |
Outputs:
| none |
Returns:
| Either an existing node with the same key, or the input node |
Definition:
SPBLK *SPinstall(SPBLK *n, SPTREE *t);
SPlookup - locate node by key
Locate a node in the tree containing the same key as that in the supplied node. The returned node is splayed to the root of the tree.
Inputs:
| n | a node, probably not in the tree, containing a key to be located |
| t | the tree to search |
Outputs:
| none |
Returns:
| the node containing the key, or NULL if not found. |
Definition:
SPBLK *SPlookup(SPBLK *n, SPTREE *t );
SPnext - find next node
If n is not at the tail of t, return the successor of n; the tree is splayed so that the successor becomes the root of the tree. If n is the tail, return NULL.
Inputs:
| n | the current node |
| t | the tree containing n |
Outputs:
| none |
Returns:
| the successor node to n, or NULL if it is the tail |
Definition:
SPBLK *SPnext(SPBLK *n, SPTREE *t);
SPprev - find previous node
If n is not the head of t, return the predecessor of n; the tree is splayed so that the predecessor becomes the root of the tree. If n is the head, return NULL.
Inputs:
| n | the current node |
| t | the tree containing n |
Outputs:
| none |
Returns:
| the predecessor to n, or NULL if n is the head |
Definition:
SPBLK *SPprev(SPBLK *n, SPTREE *t);
SPsplay - reorganize tree around node
The tree is reorganized so that n is the root of the splay tree t; t is split from n up to the old root, with all nodes to the left of n (that is, with key values less than or equal to the key of n) ending up in the left subtree, and all nodes to the right of n (having key values greater than the key of n) ending up in the right subtree. The left branch of the right subtree and the right branch of the left subtree are shortened in the process.
The algorithm assumes that n is not NULL and is in t. Results are unpredictable if n is not in t to start with.
Inputs:
| n | the node to be made the root |
| t | the tree containing n |
Outputs:
| none |
Returns:
| none |
Definition:
VOID SPsplay(SPBLK *n, SPTREE *t);
MO Examples
typedef struct
{
char *key;
char *data;
} MY_STUFF;
typedef struct
{
SPBLK treenode; MY_STUFF stuff;
} MY_NODE;
i4 mycompare( PTR a, PTR b )
{
MY_STUFF *one = (MY_STUFF *)a;
MY_STUFF *two = (MY_STUFF *)a;
return( STcompare( one->key, two->key );
}
SPTREE *Tree; SPTREE RealTree;
/* set up a tree */
init() { Tree = &RealTree; SPinit( Tree, mycompare ); }
/* optimistic add -- allocates before checking */
addnode( char *name, char *data )
{
MY_NODE *np; MY_NODE *rp;
/* get and setup a node */
np = (MY_NODE *)malloc( sizeof(*np) );
np->treenode.key = (PTR)&np->stuff;
np->stuff.key = name;
np->stuff.data = data;
/* handle duplicate insertion */
if( np != (rp = SPinstall( np, Tree ) ) )
{
rp->stuff.data = data; free( np );
}
}
/* return the stuff for the name */
MY_STUFF * get_stuff( char *name )
{
MY_NODE node; SPBLK *sp;
node.stuff.key = name;
node.treenode.key = &node.stuff;
if( (sp = SPlookup( &node, Tree ) ) )
return( (MY_STUFF *)sp->key );
return( NULL );
}
/* delete a node */
delnode( char *name )
{
MY_NODE node;
node.stuff.key = name;
node.treenode.key = &node.stuff;
SPdelete( &node, Tree );
}
|
Ingres Compatability Library |
