Page MenuHomePhorge
Files F27033626

splay.c
No OneTemporary
Actions

Authored By
Unknown
Size
9 KB
Referenced Files
None
Subscribers
None

splay.c
View Options

/* splay.c - code for splay trees Version of August 18, 2001.
* Author: Brendan McKay bdm@cs.anu.edu.au
This file is not meant to be compiled separately, but to be
#included into other programs. Use it like this:
1. Define a node type SPLAYNODE. It must be a structure that
contains at least the pointer fields left, right and parent of
type SPLAYNODE*.
Also define a macro SPLAYNODESIZE giving the size of an object
of type SPLAYNODE, unless sizeof(SPLAYNODE) is adequate.
2. Declare a variable of type SPLAYNODE* to point to the root
of the tree, and initialise it to NULL.
3. Declare SCAN_ARGS to be the additional arguments needed for
splay_scan(), including a leading comma.
4. Declare ACTION(p) for what splay_scan() should do for node p.
5. Declare INSERT_ARGS to be the additional arguments needed
for splay_insert(), including a leading comma.
6. Declare COMPARE(p) to compare INSERT_ARGS or LOOKUP_ARGS to the
contents of node p. <0, 0, >0 if INSERT_ARGS is greater, equal,
less, than p. This has to be an expression with a value, so you will
need to make it a procedure call if the comparison is complicated.
If you are using something like strcmp, the correct order is
strcmp( INSERT_ARGS, p ).
7. Declare PRESENT(p) for what to do if INSERT_ARGS is already
present, in node p. There is a spare int variable i available.
Typically, this might update some data in the node p.
8. Declare NOT_PRESENT(p) for what to do if INSERT_ARGS is not
in the tree and p is a fresh node to hold it. No need to set
the left, right, and parent fields. Use i here too if you like.
Typically, this might initialise the data in node p.
PRESENT(p) and NOT_PRESENT(p) should not manipulate the
tree pointers. However, each of them can include a
return if you don't want to change the tree. In the
case of NOT_PRESENT(p), do free(p) before returning.
In the case of PRESENT(p), it is also legal to delete the
node from the tree using SCAN_DELETE(to_root,p). In that
case you MUST return immediately afterwards.
9. Declare LOOKUP_ARGS to be the additional arguments needed
for splay_lookup(), including a leading comma. The default
for LOOKUP_ARGS is to be the same as INSERT_ARGS.
10. #include "splay.c"
Calls:
Suppose "root" is name of the variable described in step 2.
There is no need to initialise the tree. Step 2 did that already.
To insert something in the tree:
splay_insert(&root, ...stuff...)
where "stuff" is the stuff you want to insert, declared as INSERT_ARGS.
If the key (some part of the stuff decided by you) is present in an
existing tree node p, PRESENT(p) is executed. Otherwise, a new tree
node p is created and NOT_PRESENT(p) is executed.
To look up something in the tree:
splay_lookup(&root, ...stuff...)
where "stuff" is the stuff you want to find, declared as LOOKUP_ARGS.
It will return a pointer to the tree node with the right key, or NULL
if there is no such tree node.
To do something for each node of the tree:
splay_scan(root, ...stuff...)
where "stuff" is anything you like (including nothing). This will
execute ACTION(p) for each node p in inorder.
To delete the node p (which MUST be in the tree:
splay_delete(&root, p)
Nothing happens if p is NULL, so you can use
splay_delete(&root, splay_lookup(&root, ...stuff...))
to delete a node, if any, containing stuff.
It is possible to have splay trees of several types in the same
program. Just include "splay.c" several times, with the procedure
names SPLAY, SPLAY_SCAN, SPLAY_LOOKUP, SPLAY_INSERT, SPLAY_DELETE
defined to distinct names. You have to redefine them all even if
you aren't using them all.
*/
#define S_A 0
#define S_L 1
#define S_R 2
#define S_LL 3
#define S_LR 4
#define S_RL 5
#define S_RR 6
#ifndef SPLAYNODESIZE
#define SPLAYNODESIZE sizeof(SPLAYNODE)
#endif
#ifndef LOOKUP_ARGS
#define LOOKUP_ARGS INSERT_ARGS
#endif
#ifndef SPLAY
#define SPLAY splay
#define SPLAY_SCAN splay_scan
#define SPLAY_LOOKUP splay_lookup
#define SPLAY_INSERT splay_insert
#define SPLAY_DELETE splay_delete
#endif
/*********************************************************************/
void
SPLAY_SCAN(SPLAYNODE *root SCAN_ARGS)
/* Do ACTION(p) for each node of the tree, in inorder. Nonrecursive! */
{
int code;
SPLAYNODE *p;
p = root;
code = S_A;
while (p)
{
switch (code) /* deliberate flow-ons */
{
case S_A:
if (p->left)
{
p = p->left;
break;
}
case S_L:
ACTION(p);
if (p->right)
{
p = p->right;
code = S_A;
break;
}
case S_R:
if (p->parent && p->parent->left == p) code = S_L;
else code = S_R;
p = p->parent;
break;
}
}
}
/*********************************************************************/
static void
SPLAY(SPLAYNODE *p)
/* Splay the node p. It becomes the new root. */
{
SPLAYNODE *q,*r,*s;
SPLAYNODE *a,*b,*c;
int code;
#define LCHILD(x,y) {(x)->left = y; if (y) (y)->parent = x;}
#define RCHILD(x,y) {(x)->right = y; if (y) (y)->parent = x;}
while (p->parent)
{
a = p->left;
b = p->right;
q = p->parent;
if (q->left == p)
{
code = S_L;
c = q->right;
}
else
{
code = S_R;
c = q->left;
}
r = q->parent;
if (r)
{
if (r->left == q) code = (code == S_L ? S_LL : S_LR);
else code = (code == S_L ? S_RL : S_RR);
s = r->parent;
p->parent = s;
if (s)
{
if (s->left == r) s->left = p;
else s->right = p;
}
}
else
{
p->parent = NULL;
}
switch (code)
{
case S_L:
RCHILD(p,q);
LCHILD(q,b);
break;
case S_R:
LCHILD(p,q);
RCHILD(q,a);
break;
case S_LL:
RCHILD(p,q);
RCHILD(q,r);
LCHILD(q,b);
LCHILD(r,c);
break;
case S_RR:
LCHILD(p,q);
LCHILD(q,r);
RCHILD(r,c);
RCHILD(q,a);
break;
case S_LR:
LCHILD(p,q);
RCHILD(p,r);
RCHILD(q,a);
LCHILD(r,b);
break;
case S_RL:
LCHILD(p,r);
RCHILD(p,q);
RCHILD(r,a);
LCHILD(q,b);
break;
}
}
}
/*********************************************************************/
void
SPLAY_INSERT(SPLAYNODE **to_root INSERT_ARGS)
/* Do insertion operation. On return, the object being inserted
is at the root of the tree regardless of whether a new node
needed to be created for it. */
{
int i,cmp;
SPLAYNODE *p,*ppar,*new_node;
p = *to_root;
cmp = 0;
while (p != NULL)
{
cmp = COMPARE(p);
if (cmp == 0)
{
PRESENT(p);
SPLAY(p);
*to_root = p;
return;
}
else if (cmp < 0)
{
ppar = p;
p = p->left;
}
else
{
ppar = p;
p = p->right;
}
}
if ((new_node = (SPLAYNODE*)malloc(SPLAYNODESIZE)) == NULL)
{
fprintf(stderr,">E malloc failed in splay_insert()\n");
exit(1);
}
NOT_PRESENT(new_node);
new_node->left = new_node->right = NULL;
if (cmp == 0)
{
*to_root = new_node;
new_node->parent = NULL;
}
else if (cmp < 0)
{
ppar->left = new_node;
new_node->parent = ppar;
}
else
{
ppar->right = new_node;
new_node->parent = ppar;
}
SPLAY(new_node);
*to_root = new_node;
}
/*********************************************************************/
SPLAYNODE*
SPLAY_LOOKUP(SPLAYNODE **to_root LOOKUP_ARGS)
/* Do a look-up operation. If found, return a pointer to the
node containing it. If not, return NULL. */
{
int i,cmp; /* i is available for COMPARE */
SPLAYNODE *p;
p = *to_root;
cmp = 0;
while (p != NULL)
{
cmp = COMPARE(p);
if (cmp == 0)
{
SPLAY(p);
*to_root = p;
return p;
}
else if (cmp < 0)
p = p->left;
else
p = p->right;
}
return NULL;
}
/*********************************************************************/
void
SPLAY_DELETE(SPLAYNODE **to_root, SPLAYNODE *p)
/* Remove node p from the tree and free it. */
{
SPLAYNODE *q;
if (p == NULL) return;
SPLAY(p);
*to_root = p;
/* Now we have to delete the root. */
/* No right child (includes no children). */
if (!p->right)
{
*to_root = p->left;
if (p->left) p->left->parent = NULL;
free(p);
return;
}
/* right child but no left child */
if (!p->left)
{
*to_root = p->right;
p->right->parent = NULL;
free(p);
return;
}
/* both children exist */
for (q = p->left; q->right; q = q->right) {}
if (q->left) q->left->parent = q->parent;
if (q->parent == p) q->parent->left = q->left;
else q->parent->right = q->left;
q->left = p->left;
q->right = p->right;
q->parent = NULL;
if (p->left) p->left->parent = q;
if (p->right) p->right->parent = q;
*to_root = q;
free(p);
}
/*********************************************************************/
/* The following shows the tree structure for debugging purposes.
If you define SPLAY_DUMP you must also define DUMP_ARGS,
DUMP_LEFT, DUMP_RIGHT and DUMP_ACTION(p). */
#ifdef SPLAY_DUMP
void
SPLAY_DUMP(SPLAYNODE *p DUMP_ARGS)
{
int i;
if (p == NULL) return;
if (p->right && p->right->parent != p)
fprintf(stderr,"parent misaligned at %p-%p ************\n",p,p->right);
if (p->left && p->left->parent != p)
fprintf(stderr,"parent misaligned at %p-%p ************\n",p,p->left);
SPLAY_DUMP(p->right DUMP_RIGHT);
DUMP_ACTION(p);
SPLAY_DUMP(p->left DUMP_LEFT);
}
#endif

File Metadata

Mime Type
text/x-c
Expires
Tue, Oct 27, 4:40 PM (1 d, 10 h)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
407994
Default Alt Text
splay.c (9 KB)

Event Timeline