smj@ssl-macc.co.uk (Steve Jefferson) (08/19/86)
This article consists of a set of C sources to implement a B-tree
algorithm and several accompanying tests. It was derived from a single
program obtained from net.sources some time ago but has been revised and
extended somewhat since then.
The code builds to 2 executables:
(1) btree.fe - an interactive front-end to the main B-tree system
this implements a simple set of commands
<number> : insert given key value into the tree
i<number> : ditto
d<number> : delete given key value from tree
l<number> : locate a given key in tree
p : print current tree
s : set up a default tree
x : exit from program
(2) btree.test - a series of tests for the B-tree system - typically this
should be run after any significant change to the B-tree
code.
- 3 tests are performed as follows (a test will only
proceed if the previous test succeeded):
(i) Perform a series of random inserts, deletes
and searches, maintaining an external checklist
and checking the shape of the tree after every
action
(ii) Insert a fixed number of keys in ascending order
then delete them in ascending order
(iii) As (ii) but everything is in descending order
Limitations:
(1) The B-tree is implemented as a series of *struct*s in
memory - explicit reads and writes of (disc) blocks would
be more useful.
(2) The current system only allows for unique key values
and not data with identical key values which can then be
distinguished by the actual information content of the data.
If anyone has any suggestions or modifications for this code, or indeed has
any B-tree code of their own which they are willing to release, I would most
interested.
Steve Jefferson
(smj@uk.co.ssl-macc or smj@sslvax.UUCP)
--------------------------------- cut here -----------------------------------
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
#
# btree.c - the main B-tree code, organised as a set of
# procedures returning error/ success codes
# btree.h - error codes for btree.c
# btree.fe.c - the B-tree "front-end" system
# btree.fe.h - the real code of the front-end system
# btree.test.c - the B-tree test system
# btree.test.h - various constants used by the tests
# btree.prt.h - routines used for printing out B-trees
# used by both the front-end and the tests
# btree.fe.M - makefile for constructing the btree front-end
# btree.test.M - makefile for constructing the btree test
#
# 4. Upon completion, execute
# (i) 'make -f btree.fe.M' to build the front-end system
# (executable 'btree.fe').
# (ii) 'make -f btree.test.M' to build the test system
# (executable 'btree.test').
#
# This archive created: Mon Aug 18 16:11:03 1986
#
echo shar: "extracting btree.c"
if test -f 'btree.c'
then
echo shar: "will not over-write existing file 'btree.c'"
else
cat << \SHAR_EOF > 'btree.c'
/********************************************************************
*********************************************************************
Module Name: btree.c
============
Function: Provide a library of routines for creating
========= and manipulating B-Trees.
The "order" of the B-Tree is controlled by a
manifest constant.
Description:
============
Main btree code Insert, Delete, Search etc.
Interface Routines:
-------------------
int Insert(*tree, dtm)
Insert DATUM dtm into B-tree "tree",
returns an error/success code.
int Delete(*tree, key)
Remove the entry associated with "key" from the B-Tree
returns an error/success code.
int Search(tree, key, dtmptr)
Look for key "key" in B-tree "tree".
Set "dtmptr" to point to matching DATUM or to NULL.
Return an error/success code.
Libraries Used:
---------------
stdio.h
btree.h
****************************************************************************
****************************************************************************/
static char btreeprog[] = "@(#)btree.c 1.7 7/17/86";
#include <stdio.h>
#include "btree.h"
#define TRUE 1 /* A couple of useful constants */
#define FALSE 0
#define M 2 /* This constant defines the order of the B-tree */
/************** Global types and data structures **************/
typedef int KEY; /* Define the key field type */
typedef int INFO; /* and define the type of the information field
associated with this key */
typedef struct /* Define a structure (DATUM) consisting of a key */
{ /* and an information field */
KEY key;
INFO inf;
} DATUM;
/* The following is the structure used for defining
B-trees and their nodes */
typedef struct btnode
{
int t_active; /* # of active keys */
DATUM t_dat[2*M]; /* Keys + Data */
struct btnode *t_ptr[2*M+1]; /* Subtree ptrs */
} NODE, *BTREE;
/**********************************************************************
* INSERTION ROUTINES
**********************************************************************/
static BTREE splittree; /*
A global variable used by "InternalInsert"
to return the right hand portion of a tree
which has been bisected .
*/
/*
** INSERT
** ======
**
** Purpose: Enter the given key into the B-tree.
**
** Parameters: dtm = DATUM to be inserted into tree
** tree = B-tree to insert into
**
** Returns: An error/success code which will be one of:
** SUCCESS
** KEY_EXISTS_ERROR
** In addition the tree "tree" is updated.
**
** Description: This is the "front end" of the insertion routine
** - most of the work is done by "InternalInsert".
**
*/
int Insert(treeptr, dtm)
BTREE *treeptr;
DATUM dtm;
{
int status;
int InternalInsert();
BTREE MkNode();
/*
Invoke the main insertion routine, let it do the guts of the
insertions, then let it return a final status code.
*/
status = InternalInsert(*treeptr, &dtm);
/*
Now examine the returned status code - there are 3 cases:
(1) NODE_SPLIT
The root node was split - then stitch the tree together by
creating a new root node containing dtm only and link 'tree'
to the left-hand link and 'splittree' to the right-hand link
(2) SUCCESS
The tree has already been reassembled into a consistent state
so just return a success code
(3) KEY_EXISTS_ERROR
The given key already exists - the tree should already be unchanged
- just exit with this error code
*/
if (status==NODE_SPLIT)
{
*treeptr = MkNode(dtm, *treeptr, splittree);
return SUCCESS;
}
else
return status;
}
/*
** INTERNALINSERT
** ==============
**
** Purpose: This routine performs the major part of key insertion
**
** Parameters: tree = B-tree to use.
** dtmptr = Pointer to the datum to be inserted into the tree
** on exit this should contain any datum to be passed
** back up the tree as a result of splitting.
**
** Returns: An error/success/information code which will be one of:
** SUCCESS: Tree is okay, no split occurred dtmptr will not
** point at anything meaningful and splittree will be
** NULL.
** NODE_SPLIT:
** Top level node has been split - dtmptr and splittree
** are now meaningful.
** KEY_EXISTS_ERROR:
** The key to be inserted already exists - the tree is
** unchanged.
**
** Description: This routine works in a recursive manner under the following
** algorithm:
** 1) Scan down the tree for a place to insert the new datum
** - this should be a leaf unless the datum itself is found
** (in which case return an error code)
** 2) Try to insert the new datum in the located node
** - if it will fit, then slot it into the node and exit with
** a success code.
** - if the node is already full, split it into 2 separate
** nodes (one for the lowest M keys, one for the highest M
** keys) and return the NODE_SPLIT code and everything
** associated with it
**
*/
int InternalInsert(tree, dtmptr)
DATUM *dtmptr;
BTREE tree;
{
int index,
j;
int SearchNode();
int status;
BTREE tmp;
BTREE MkNode();
if (tree == (BTREE) NULL)
{
/*
If current tree is NULL then we're at a leaf, so we can't insert the
datum here - the procedure is to act as if we've just split a node
and are returning a datum to be slotted in further up the tree - the
only difference is that splittree is set to NULL.
*/
splittree = (BTREE) NULL;
return NODE_SPLIT;
}
else
{
/*
Tree is not null - now search for occurence of datum's key
in the current top-level node - return its position (or index
of pointer to subtree) as a by-product.
*/
if (SearchNode(tree, (*dtmptr).key, &index))
/*
If key has been found then return an error code
*/
return KEY_EXISTS_ERROR;
/*
If not found the try to insert datum in next level of tree -
this action will then return a status code and possibly a
splittree.
*/
status = InternalInsert(tree->t_ptr[index],dtmptr);
/*
If we have had a successful insertion (with tree in good order)
or we have had a key insertion error, then return with this
status code without further ado.
*/
if (status != NODE_SPLIT)
return status;
/*
We've now had a split node at the level below with dtmptr now
pointing to a datum throw back up from it and splittree
pointing to the right-hand part of the split node
Next stage is to try to insert things here and tidy up the tree
once and for all - so check to see whether current top level
node is full or not (ie. can it support an insertion ?).
*/
if (tree->t_active < 2*M)
{
/*
If there is room then everything's hunky dory
*/
InsInNode(tree, *dtmptr, splittree);
return SUCCESS;
}
/*
Current top-level node is full - so split it into two
- set left-hand half to contain lower M keys and leave it
attached to main tree.
- set splittree to point to right-hand half (which contains
the highest M keys).
- set dtmptr to point to central key value
*/
if (index <= M)
{
/*
If datum should go in a left-hand or central position
of current top-level node then shift right-element out
Note that we need a temporary B-tree here just to do
the swap of datums
*/
tmp = MkNode(tree->t_dat[2*M-1], (BTREE)NULL, tree->t_ptr[2*M]);
tree->t_active--;
InsInNode(tree, *dtmptr, splittree);
}
else
/*
If datum is definitely part of right-hand half of
the 2M+1 keys then transfer it to (what will be)
splittree immediately.
*/
tmp = MkNode(*dtmptr, (BTREE)NULL, splittree);
/*
Final part is to move right hand half of current top level node
out into (whta is about to become) the new splittree
and then mode central (Mth) key of current top-level node into
*dtmptr
*/
for (j = M+1; j < 2*M; j++)
InsInNode(tmp, tree->t_dat[j], tree->t_ptr[j+1]);
*dtmptr = tree->t_dat[M];
tree->t_active = M;
tmp->t_ptr[0] = tree->t_ptr[M+1];
splittree = tmp;
/*
Finally return NODE_SPLIT code
*/
return NODE_SPLIT;
}
}
/*
** INSINNODE
** =========
**
** Purpose: Add a datum into a B-tree node working on the assumption
** that there is room for it.
**
** Parameters: nodeptr = Ptr to the node,
** dtm = Datum to enter,
** ptr = "Greater than" link to subordinate node.
**
** Returns: None.
**
** Description: The workings of this routine are pretty straightforward - just
** sort out where the key should go, shift all greater keys
** right one position and then insert the key and pointer.
*/
InsInNode(nodeptr, dtm, ptr)
BTREE nodeptr,
ptr;
DATUM dtm;
{
int index;
int KeyCmp();
for (index = nodeptr->t_active; index>0 && KeyCmp(dtm.key, nodeptr->t_dat[index-1].key)<0; index--)
{
nodeptr->t_dat[index] = nodeptr->t_dat[index-1];
nodeptr->t_ptr[index+1] = nodeptr->t_ptr[index];
}
nodeptr->t_active++;
nodeptr->t_dat[index] = dtm;
nodeptr->t_ptr[index+1] = ptr;
}
/*************************************************************************
* DELETION ROUTINES
*************************************************************************/
/*
** DELETE
** ======
**
** Purpose: Remove the data associated with a given key from a B-tree.
**
** Parameters: tree = B-tree to update
** key = Key to use,
**
** Returns: An error/success code
** SUCCESS / KEY_NOT_FOUND_ERROR / TREE_CORRUPTED_ERROR
**
** Description: The real work to do with deletion is performed by RealDelete()
** this routine only checks that RealDelete has actually done
** a deletion and tidies things up afterwards.
**
*/
int Delete(treeptr, key)
BTREE *treeptr;
KEY key;
{
int status;
int RealDelete();
BTREE savetree;
/*
Do the main deletion then check whether it managed to find anything
to delete. If it didn't - return an error code.
*/
status = RealDelete(*treeptr, key);
if (status != SUCCESS)
return status;
/*
Now check to see whether the previous root node has now
been superceded.
*/
else if ((*treeptr)->t_active == 0)
{
/*
If so then deallocate the space that was set aside for the
root node and make its leftmost child the new root node.
*/
savetree = (*treeptr)->t_ptr[0];
Dispose(*treeptr);
*treeptr = savetree;
}
return SUCCESS;
}
/*
** REALDELETE
** ==========
**
** Purpose: Remove a key from a tree
**
** Parameters: tree = B-tree to be updated
** key = Key to use,
**
** Returns: Returns an error/success code (SUCCESS/KEY_NOT_FOUND_ERROR)
**
** Description: This routine operates recursively in the following manner:
** 1) Locate the required key within the tree.
** 2) If it's in a leaf then remove it and rebalance the tree
** otherwise replace it by the next key in the tree (in
** ascending order), then delete that key from its node
** (which must be a leaf).
*/
int RealDelete(tree, key)
BTREE tree;
KEY key;
{
int index;
int status;
int SearchNode();
KEY nextkey;
if (tree == (BTREE)NULL)
/*
If now trying to scan down a non-existant link,
mark required key as not found and exit
*/
return KEY_NOT_FOUND_ERROR;
/*
First stage is to search for key within current top-level node
If it's not there then we must continue down the tree looking
for it.
*/
if (! SearchNode(tree, key, &index))
{
/*
If required key not found in current top-level node
then try deleting it from the next node down
*/
status = RealDelete(tree->t_ptr[index], key);
if (status==SUCCESS)
Balance(tree,index);
return status;
}
/*
If the key was found, then check whether this is
a leaf
*/
if (tree->t_ptr[index] == (BTREE)NULL)
{
/*
If this is a leaf, then just remove the required key for now
- the tree will be rebalanced on the way back up
*/
Remove(tree,index);
return SUCCESS;
}
else
{
/*
If this isn't a leaf, the rule is to replace the key by
the next highest in the tree, deleting that key from its
node and rebalancing the tree
*/
nextkey = Succ(tree, index);
status = RealDelete(tree->t_ptr[index+1],nextkey);
if (status==SUCCESS)
{
Balance(tree,index+1);
return status;
}
else
return TREE_CORRUPTED_ERROR;
}
}
/*
** REMOVE
** ======
**
** Purpose: Remove a single datum
**
** Parameters: tree = Ptr to the B-tree node,
** pos = Index of the key to be removed.
**
** Returns: None.
**
** Description: Remove a datum from a B-tree node and fill the gap left
** by the deletion by shuffling across the other DATUMs and
** pointers.
**
*/
Remove(tree, pos)
BTREE tree;
int pos;
{
int i;
/*
This is all pretty trivial - just shuffle everything to the
right of the deleted key, left by one.
*/
for (i=pos; i<((tree->t_active)-1); ++i)
{
tree->t_dat[i] = tree->t_dat[i+1];
tree->t_ptr[i+1] = tree->t_ptr[i+2];
}
/*
Finally decrement the number of valid keys in the node
*/
tree->t_active--;
}
/*
** SUCC
** ====
**
** Purpose: Replace a key by its successor
**
** Parameters: tree = Ptr to a B-tree node,
** pos = Index of the key to be succ'ed.
**
** Returns: Returns the successor key
**
** Description: Using the natural ordering, replace a key with its successor
** (ie the next key in the tree in ascending order).
** This routine relies on the fact that the successor of a key
** will be the leftmost key in the leftmost leaf of the
** "greater than" subtree of the key to be deleted.
**
*/
KEY Succ(tree, pos)
BTREE tree;
int pos;
{
BTREE ltree;
DATUM successor;
/*
Using the "greater than" branch the key chain down to leftmost node
below it.
*/
for (ltree = tree->t_ptr[pos+1]; ltree->t_ptr[0] != (BTREE)NULL; ltree = ltree->t_ptr[0])
; /* NULL BODY */
successor = ltree->t_dat[0];
tree->t_dat[pos] = successor;
return successor.key;
}
/*
** BALANCE
** =======
**
** Purpose: Restore balance to a potentially unbalanced B-tree
**
** Parameters: parent = Ptr to the parent node of a B-tree structure,
** pos = Index of the out-of-balance point within the
** parent node.
**
** Returns: None.
**
** Description: After removing an item from a B-tree we must restore
** the balance to the tree.
** In this routine we consider the DATUM in t->t_dat[pos-1]
** and the DATUMs in its immediate children (and there should
** be children for this routine to be called).
** The rules are:
** (1) If total number of DATUMs <= 2M then we can combine
** them into a single node
** (2) Otherwise if the difference in numbers between the 2
** children is greater than 1, then we must shuffle
** DATUM(s) out of the fullest node, through the parent
** and into the emptiest node
**
*/
Balance(parent, pos)
BTREE parent;
int pos;
{
int lchildindex, rchildindex;
int lchildlen, rchildlen;
/*
Firstly decide where the children are - this pretty obvious
- t_ptr[pos] and t_ptr[pos+1] - unless pos=tree->t_active
when we have t_ptr[t_active-1] & t_ptr[t_active]
*/
if (pos==parent->t_active)
rchildindex = parent->t_active;
else
rchildindex = pos+1;
lchildindex = rchildindex - 1;
/*
Now find out how many valid DATUMs reside in each of the children
*/
lchildlen = (parent->t_ptr[lchildindex])->t_active;
rchildlen = (parent->t_ptr[rchildindex])->t_active;
/*
Check total number of DATUMs involved
*/
if ((lchildlen + rchildlen + 1) <= 2*M)
/*
If <=2M then combine into 1 node
*/
Combine(parent,rchildindex);
/*
Otherwise if difference in sizes of children is >1 then shift
DATUMs one way or the other
*/
else if ((lchildlen-rchildlen)>1)
MoveRight(parent,lchildindex);
else if ((rchildlen-lchildlen)>1)
MoveLeft(parent,rchildindex);
}
/*
** COMBINE
** =======
**
** Purpose: Coalesce two nodes of a B-tree when they have too many DATUMs.
**
** Parameters: parent = Ptr to parent B-tree node,
** rindex = Index of the right-hand of the 2 nodes to be combined.
**
** Returns: None.
**
** Description: This all pretty simple - just move parent DATUM, followed by
** DATUMs from right-hand child into left-hand child. Then throw
** away right-hand child, delete parent DATUM and close the gap in
** the parent node.
*/
Combine(parent, rindex)
BTREE parent;
int rindex;
{
int i;
BTREE ltree,
rtree;
/*
Set up pointers to the 2 child trees
*/
ltree = parent->t_ptr[rindex-1];
rtree = parent->t_ptr[rindex];
/*
We are going to combine the 2 trees into the left-hand tree
so first thing is to tag parent datum onto end of this left-hand
child node
*/
ltree->t_active++;
ltree->t_dat[(ltree->t_active)-1] = parent->t_dat[rindex-1];
/*
Now set right-hand link from this left-hand child to be the left-hand
link right-hand child
*/
ltree->t_ptr[ltree->t_active] = rtree->t_ptr[0];
/*
Now tag all of right-hand child onto end of left-hand child
*/
for (i = 1; i <= rtree->t_active; ++i)
{
ltree->t_active++;
ltree->t_dat[ltree->t_active-1] = rtree->t_dat[i-1];
ltree->t_ptr[ltree->t_active] = rtree->t_ptr[i];
}
/*
Finally, remove parent DATUM from parent node by shifting
contents of parent node left as necessary
*/
for (i = rindex; i <= parent->t_active-1; ++i)
{
parent->t_dat[i-1] = parent->t_dat[i];
parent->t_ptr[i] = parent->t_ptr[i+1];
}
parent->t_active--;
Dispose(rtree);
}
/*
** MOVERIGHT
** =========
**
** Purpose: Move DATUMs right out of one child into its right-hand
** brother.
**
** Parameters: parent = Ptr to the parent B-tree node,
** lindex = Index of the link to the left-hand child
** from the parent node.
**
** Returns: None.
**
** Description: Main thing to note is that we only need to shift 1 DATUM
** because the current imbalance was caused by a deletion from
** the right-hand child and, prior to that, things were okay (the
** tree was balanced last time around).
*/
MoveRight(parent, lindex)
BTREE parent;
int lindex;
{
int i;
BTREE ltree,
rtree;
/*
Set up pointers to 2 trees concerned
*/
ltree = parent->t_ptr[lindex];
rtree = parent->t_ptr[lindex+1];
/*
First stage is to shift contents of right-hand child right by one
in order to accommodate the incoming DATUM from the parent node
*/
rtree->t_active++;
for (i = rtree->t_active; i >= 1; i--)
{
rtree->t_dat[i] = rtree->t_dat[i-1];
rtree->t_ptr[i+1] = rtree->t_ptr[i];
}
rtree->t_ptr[1] = rtree->t_ptr[0];
/*
Now copy parent DATUM into r-hand child
*/
rtree->t_dat[0] = parent->t_dat[lindex];
/*
Finally move rhand DATUM of lhand child into parent node
*/
rtree->t_ptr[0] = ltree->t_ptr[ltree->t_active];
parent->t_dat[lindex] = ltree->t_dat[(ltree->t_active)-1];
ltree->t_active--;
}
/*
** MOVELEFT
** ========
**
** Purpose: Move DATUM left from a right-hand child, through its parent
** DATUM and into a left-hand child.
**
** Parameters: parent = Ptr to the parent B-tree node,
** rindex = Index of the right-hand child within the
** parent node.
**
** Returns: None.
**
** Description: As with MoveRight (above) the main thing to note is that we
** only have to shift 1 DATUM.
*/
MoveLeft(parent, rindex)
BTREE parent;
int rindex;
{
int i;
BTREE ltree,
rtree;
/*
Set up pointers to 2 children
*/
ltree = parent->t_ptr[rindex-1];
rtree = parent->t_ptr[rindex];
/*
First stage is to shift DATUM from parent node onto end of
lhand child
*/
ltree->t_active++;
ltree->t_dat[(ltree->t_active)-1] = parent->t_dat[rindex-1];
/*
Now move lhand link from rhand child to be rhand link from
lhand child
*/
ltree->t_ptr[ltree->t_active] = rtree->t_ptr[0];
/*
Next, shift lhand DATUM of rhand node into parent node
*/
parent->t_dat[rindex-1] = rtree->t_dat[0];
/*
Finally shift contents of rhand child left by one
*/
rtree->t_ptr[0] = rtree->t_ptr[1];
for (i = 1; i <= rtree->t_active; ++i)
{
rtree->t_dat[i-1] = rtree->t_dat[i];
rtree->t_ptr[i] = rtree->t_ptr[i+1];
}
rtree->t_active--;
}
/*****************************************************************************
* SEARCH ROUTINE
*****************************************************************************/
/*
** SEARCH
** ======
**
** Purpose: Look for a key in a tree.
**
** Parameters: tree = Tree to look in
** key = key to look for
** dtmptr = pointer to found datum
**
** Returns: A success/error code (SUCCESS/KEY_NOT_FOUND_ERROR)
**
** Description:
**
*/
int Search(tree, key, dtmptr)
BTREE tree;
KEY key;
DATUM *dtmptr;
{
DATUM dtm;
int index;
int SearchNode();
while (tree != (BTREE)NULL)
{
/*
For each node just check to see whether the requd key value
is there - if not, go down 1 more level ...
*/
if (SearchNode(tree, key, &index))
{
dtm = (tree->t_dat[index]);
*dtmptr = dtm;
return SUCCESS;
}
tree = tree->t_ptr[index];
}
dtmptr = (DATUM *)NULL;
return KEY_NOT_FOUND_ERROR;
}
/**************************************************************************
* MISCELLANEOUS ROUTINES
**************************************************************************/
/*
** SEARCHNODE
** ==========
**
** Purpose: Look for a key in a single B-tree node.
**
** Parameters: nodeptr = Ptr to B-tree node,
** key = Key to look for,
** pindex = Pointer to integer vbl in which to place
** index position of key within node
**
** Returns: TRUE/FALSE result indicating whether key was in the node
**
** Description: The workings of this routine are pretty trivial -see code.
*/
int SearchNode(nodeptr, key, pindex)
BTREE nodeptr;
KEY key;
int *pindex;
{
int i;
int cmp;
int KeyCmp();
/*
Scan down the node from highest to lowest key value - stop when
a key <= 'key' is found
*/
for (i=(nodeptr->t_active)-1; i>=0; i--)
{
cmp = KeyCmp(key,(nodeptr->t_dat[i]).key);
if (cmp>=0)
{
*pindex = (cmp==0)? i: i+1;
return (cmp==0);
}
}
/*
If passed through loop unscathed then 'key' must be less than
everything in the node - so act accordingly
*/
*pindex = 0;
return FALSE;
}
/*
** KEYCMP
** ======
**
** Purpose: To compare two key values
**
** Parameters: key1 = First key,
** key2 = Second key.
**
** Returns: -1 if key1 < key2;
** 0 if key1 = key2;
** 1 if key1 > key2;
**
** Description: The contents of this routine are dependent upon the type of
** key being used - as long as it accepts the same parameters
** and returns the same results, any key type can be used.
*/
int KeyCmp(key1, key2)
KEY key1,
key2;
{
return key1<key2 ? -1 : key1==key2 ? 0 : 1;
}
/*
** MKNODE
** ======
**
** Purpose: Allocate storage for a new B-tree node and copy in an
** initial datum and two pointers from it.
**
** Parameters: dtm = Initial datum for new node
** ptr0 = "less than" pointer from dtm
** ptr1 = "greater than" pointer from dtm
**
** Returns: Reference to the new node.
**
** Description: All pretty obvious...
*/
BTREE MkNode(dtm, ptr0, ptr1)
DATUM dtm;
BTREE ptr0,
ptr1;
{
char *malloc();
BTREE tree;
tree = (BTREE) malloc(sizeof(NODE));
tree->t_ptr[0] = ptr0;
tree->t_ptr[1] = ptr1;
tree->t_dat[0] = dtm;
tree->t_active = 1;
return tree;
}
/*
** DISPOSE
** =======
**
** Purpose: Return the storage occupied by a tree node to the pool.
**
** Parameters: nodeptr = Ptr to the tree node.
**
** Returns: None.
**
** Description: Another simple one ...
*/
Dispose(nodeptr)
BTREE nodeptr;
{
free((char *) nodeptr);
}
SHAR_EOF
fi
echo shar: "extracting btree.h"
if test -f 'btree.h'
then
echo shar: "will not over-write existing file 'btree.h'"
else
cat << \SHAR_EOF > 'btree.h'
/************************************************************************
*
* B-tree header file
*
* This just defines various error codes etc.
*
***********************************************************************/
static char btree_header[] = "@(#)btree.h 1.3 7/16/86";
#define NODE_SPLIT -1 /* Information code - used internally
within insertion code */
#define SUCCESS 0 /* Success code */
#define KEY_EXISTS_ERROR 1 /* Returned by insertion routines */
#define KEY_NOT_FOUND_ERROR 2 /* Returned by deletion & search */
#define TREE_CORRUPTED_ERROR 3 /* Returned by deletion */
SHAR_EOF
fi
echo shar: "extracting btree.fe.c"
if test -f 'btree.fe.c'
then
echo shar: "will not over-write existing file 'btree.fe.c'"
else
cat << \SHAR_EOF > 'btree.fe.c'
/********************************************************************
*********************************************************************
Module Name: btree.fe.c
============
Function: Front end for btree code ...
=========
Description:
============
Implements a front-end program for the btree code
Libraries:
stdio.h
btree.fe.h
btree.c (-> btree.h)
bree.prt.h
****************************************************************************
****************************************************************************/
static char btreefrontendc[] = "@(#)btree.fe.c 1.1 7/16/86";
#include <stdio.h>
#include "btree.c"
#include "btree.fe.h"
#include "btree.prt.h"
/*
** MAIN PROGRAM
** ============
**
** Purpose: Front panel type thing for btree code - allows interactive
** manipulation of tree
**
** Parameters: none
**
** Returns: none
**
*/
main()
{
frontend();
}
SHAR_EOF
fi
echo shar: "extracting btree.fe.h"
if test -f 'btree.fe.h'
then
echo shar: "will not over-write existing file 'btree.fe.h'"
else
cat << \SHAR_EOF > 'btree.fe.h'
/********************************************************************
*********************************************************************
Module Name: btree.fe.h
============
Function: Front end for btree code ...
=========
Description:
============
Implements a front-end program for the btree code
****************************************************************************
****************************************************************************/
static char btreefrontend[] = "@(#)btree.fe.h 1.2 8/18/86";
/*
** FRONTEND
** ========
**
** Purpose: Front panel type thing for btree code - allows interactive
** manipulation of tree
**
** Parameters: none
**
** Returns: none
**
** Description: The following 'commands' are implemented
** <n> Insert key 'n'
** i<n> ditto
** d<n> Delete key 'n'
** l<n> Locate key 'n'
** p<n> Print tree
** s Set up default tree
** x Exit from front end
*/
frontend()
{
int status;
BTREE tree;
DATUM dtm,
dtm2;
KEY key;
char buf[BUFSIZ];
tree = (BTREE)NULL;
printf("Command: "); fflush(stdout);
while (fgets(buf, sizeof buf, stdin) != NULL)
{
buf[strlen(buf) - 1] = '\0';
switch (buf[0])
{
default: /* Error case */
fprintf(stderr, "i, d, l, p, s or x please!\n");
break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
sscanf(buf, "%d", &dtm.key);
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
break;
case 's': /* Set up default tree */
tree = (BTREE)NULL;
dtm.key = 20;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 10;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 15;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 30;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 40;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 7;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 18;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 22;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 26;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 5;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 35;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 13;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 27;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 32;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 42;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 46;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 24;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 45;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
dtm.key = 25;
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
ShowTree(tree, 0);
break;
case 'i': /* Insert a key */
sscanf(buf+1, "%d", &dtm.key);
status = Insert(&tree, dtm);
if (status != SUCCESS)
btree_err(status);
break;
case 'd': /* Delete a key */
sscanf(buf+1, "%d", &dtm.key);
status = Delete(&tree, dtm.key);
if (status != SUCCESS)
btree_err(status);
break;
case 'l': /* Lookup a key */
sscanf(buf+1, "%d", &dtm.key);
status = Search(tree, dtm.key, &dtm2);
if (status != SUCCESS)
btree_err(status);
printf("Found %d\n",dtm2.key);
break;
case 'p': /* Show the tree */
ShowTree(tree, 0);
break;
case 'x':
break;
}
if (buf[0]=='x')
break;
else
{
printf("Command: ");
fflush(stdout);
}
}
}
/*
** ERROR ROUTINE
** =============
**
** Purpose: Error message routine for btree front-end system
**
** Parameters: errcode = errcode
**
** Returns: none
**
** Description: Pretty simple...
*/
btree_err(errcode)
int errcode;
{
switch (errcode)
{
case KEY_EXISTS_ERROR:
fprintf(stderr,"Key already exists !\n");
break;
case KEY_NOT_FOUND_ERROR:
fprintf(stderr,"Key not found !\n");
break;
case TREE_CORRUPTED_ERROR:
fprintf(stderr,"Tree corrupted !\n");
break;
}
}
SHAR_EOF
fi
echo shar: "extracting btree.test.c"
if test -f 'btree.test.c'
then
echo shar: "will not over-write existing file 'btree.test.c'"
else
cat << \SHAR_EOF > 'btree.test.c'
/***************************************************************************
*
* Module Name: btree.test.c
* ============
*
* Function: BTREE TEST PROGRAM
* =========
*
* Description:
* ============
* -see main routine
* Libraries
* ----------
* stdio.h
* btree.c (--> btree.h)
* btree.test.h
* btree.prt.h
*
******************************************************************************/
static char btree_tests[] = "@(#)btree.test.c 1.1 7/16/86";
/*****************************************************************************
* INCLUDES and TEST PROGRAM PARAMETERS
*****************************************************************************/
#include <stdio.h>
#include "btree.c"
#include "btree.test.h"
#include "btree.prt.h"
/*
Number of key values to be used
*/
#define MAXKEYS 1500
/*
Values used by flag table (below)
*/
#define IN_TREE 1
#define NOT_IN_TREE 0
/*
Seed for random number generator
*/
static int seed;
/*
This array will contain boolean values -
if flag[i]=NOT_IN_TREE then key i is currently not in the tree
if flag[i]=IN_TREE then key i is currently in the tree.
*/
static int flag[MAXKEYS];
static int keytotal;
BTREE tree; /* Tree to be used */
/******************************************************************************
* MAIN TEST PROGRAM
******************************************************************************/
/*
** MAIN TEST PROGRAM
** =================
**
** Purpose: Test the B-tree routines
**
** Parameters: argv[1] = "" or a seed for the random tests
**
** Returns: A continuous set of diagnostic messages is sent to stdout
** This continues until the tests are successfully completed or
** until the first error occurs
**
** Description: There are 3 sets of tests performed
** (1) Random tests - a large number of random inserts, deletes
** and searches is performed.
** (2) All keys are inserted into the tree in ascending order
** then deleted in ascending order.
** (3) All keys are inserted into the tree in descending order
** then deleted in descending order.
** For the purposes of this test a limited range of keys is used
** - these are numbered 0 to MAXKEYS-1 (where MAXKEYS is #defined
** above) and a function getkey() returns the actual key value of
** a given key number - currently keys are integers so
** getkey(i) = i.
*/
main(argc,argv)
int argc;
char *argv[];
{
int statuscode;
int randomtest(), ascendingtest(), descendingtest();
/*
First thing to do is to check for a seed parameter
*/
if (argc != 0)
sscanf(argv[1],"%d",&seed);
else
seed = 0;
srandom(seed);
/*
Random test
*/
statuscode = randomtest();
if (statuscode != SUCCESS)
error(statuscode);
/*
Ascending test
*/
statuscode = ascendingtest();
if (statuscode != SUCCESS)
error(statuscode);
/*
Descending test
*/
statuscode = descendingtest();
if (statuscode != SUCCESS)
error(statuscode);
/*
Given message to say that it all worked
*/
printf("\n\n----> TESTS SUCCEEDED <----\n\n\n");
exit(1);
}
/****************************************************************************
* RANDOM INSERT/DELETE/SEARCH TEST
****************************************************************************/
/*
Number of inserts + deletes + searches for random tests.
*/
#define PASSES 2000
/*
Number of actions available to random test and the codes associated
with them.
*/
#define ACTIONS 3
#define SEARCH 0
#define INSERT 1
#define DELETE 2
/*
** RANDOMTEST
** ==========
** Purpose: Perform the random tests
**
** Parameters: None
**
** Returns: Diagnostic messages are continuously fed to stdout
** and upon completion/error a success/error code is returned
** SUCCESS: Everything went okay
** others : see routines testsearch(),
** testinsert(),
** testdelete().
**
** Description: For a given number of iterations (PASSES), generate a random
** key number and randomly select an insert, a delete or a search
** to do on the key corresponding to the key number.
*/
int randomtest()
{
int keynumber;
int pass,
status;
int randrange();
/*
Set up tree for new test
*/
inittree();
/*
Send start-of-test-banner
*/
printf("**************** RANDOM TESTS *****************\n\n");
/*
Now repeat the following process PASSES times:
1) Generate a random key value
2) Generate a random number to determine what action to perform
on that key
3) Perform the action and check the resulting tree.
*/
for (pass=1; pass<PASSES; pass++)
{
keynumber = randrange(MAXKEYS);
switch (randrange(ACTIONS))
{
case SEARCH:
status = testsearch(keynumber);
break;
case INSERT:
status = testinsert(keynumber);
break;
case DELETE:
status = testdelete(keynumber);
break;
}
if (status != SUCCESS)
return status;
}
return SUCCESS;
}
/*
** RANDRANGE
** =========
**
** Purpose: Generate a random integer within a given range
**
** Parameters: number_of_values = range of random int to be generated
**
** Returns: a random in in the range 0..(number_of_values-1)
**
** Description: Very simple - most of work done by a system routine.
*/
int randrange(number_of_values)
int number_of_values;
/*
Routine to generate a random number in a given range
*/
{
long random();
return (random() % number_of_values);
}
/*****************************************************************************
* ASCENDING KEY TEST
*****************************************************************************/
/*
** ASCENDINGTEST
** =============
**
** Purpose: Performs ascending key value test
**
** Parameters: None
**
** Returns: Sends continuous diagnostic stream to stdout
** Returns a success/error code at end of tests or if an error
** occurs.
**
** Description: Clear the tree, fill it with keys by adding them in ascending
** order, then delete them all in ascending key order.
*/
int ascendingtest()
{
int i;
int status;
/*
Set up tree for new test
*/
inittree();
/*
Print start-of-test banner
*/
printf("*************** ASCENDING TESTS ******************\n\n");
/*
Insert keys in order
*/
for (i=0; i<MAXKEYS; i++)
{
status = testinsert(i);
if (status != SUCCESS)
return(status);
}
/*
Delete keys in order
*/
for (i=0; i<MAXKEYS; i++)
{
status = testdelete(i);
if (status != SUCCESS)
return(status);
}
return SUCCESS;
}
/*****************************************************************************
* DESCENDING KEY TEST
*****************************************************************************/
/*
** DESCENDINGTEST
** ==============
**
** Purpose: Performs descending key value test
**
** Parameters: None
**
** Returns: Sends continuous diagnostic stream to stdout
** Returns a success/error code at end of tests or if an error
** occurs.
**
** Description: Clear the tree, fill it with keys by adding them in descending
** order, then delete them all in descending key order.
*/
descendingtest()
{
int i;
int status;
/*
Set up tree for new test
*/
inittree();
/*
Print start-of-test banner
*/
printf("*************** DESCENDING TESTS ******************\n\n");
/*
Insert keys in order
*/
for (i=MAXKEYS-1; i>=0; --i)
{
status = testinsert(i);
if (status != SUCCESS)
return(status);
}
/*
Delete keys in order
*/
for (i=MAXKEYS-1; i>=0; --i)
{
status = testdelete(i);
if (status != SUCCESS)
return(status);
}
return SUCCESS;
}
/*****************************************************************************
* TREE INITIALISATION
*****************************************************************************/
/*
** INITTREE
** ========
**
** Purpose: Set up tree & lookup tables ready for a new test
**
** Parameters: none.
**
** Returns: none.
**
** Description: trivial.
*/
inittree()
{
int i;
tree = (BTREE)NULL;
for (i=0; i<MAXKEYS; i++)
flag[i] = NOT_IN_TREE;
keytotal = 0;
}
/***********************************************************************
* TEST ROUTINES FOR SEARCH/INSERT/DELETE
***********************************************************************/
/*
** TESTSEARCH
** ==========
**
** Purpose: Test a search for a given key
**
** Parameters: keynumber = number of key to be located
**
** Returns: A diagnostic message is sent to stdout and upon completion
** an error/success code is returned:
** SUCCESS - everything worked
** FOUND_NON_EXISTANT_KEY
** - error - located a key when it wasn't in
** the tree
** NOT_FOUND_EXISTING_KEY
** - error - could locate a key which should be
** in the tree.
**
** Description: Basically, do the search and compare the result with the
** flag lookup table - also, if found successfully, check that
** the routine has returned a pointer to the correct keyed DATUM.
*/
int testsearch(keynumber)
int keynumber;
/*
Routine to test the search for a key within a tree
*/
{
KEY getkey();
KEY key;
DATUM dtm;
int i;
int status;
/*
Translate a key number into a key value
*/
key = getkey(keynumber);
/*
Send message to log file
*/
printf("Search\t");
printkey(key);
/*
Now attempt the search itself
*/
status = Search(tree,key,&dtm);
/*
Print out result of search
*/
if (status==SUCCESS)
printf("found \t");
else
printf("not found \t");
/*
We can get 2 sorts of error:
(1) A non-existant key was found
(2) An existing key could not be found
(3) 'dtm' doesn't point to the right key
*/
if ((status==SUCCESS) && (flag[i]==NOT_IN_TREE))
return FOUND_NON_EXISTANT_KEY;
if ((status==KEY_NOT_FOUND_ERROR) && (flag[i]==IN_TREE))
return NOT_FOUND_EXISTING_KEY;
if ((status==SUCCESS) && (dtm.key != key))
return FOUND_WRONG_KEY;
/*
Send final diagnostic message then exit successfully
*/
printf("CORRECT\n");
return SUCCESS;
}
/*
** TESTINSERT
** ==========
**
** Purpose: Test the insertion of a given key
**
** Parameters: keynumber = number of key to be inserted
**
** Returns: A diagnostic message is sent to stdout and upon completion
** an error/success code is returned:
** SUCCESS - everything worked
** INSERTED_EXISTING_KEY
** - error - successfully inserted a key which was
** already in the tree
** CANNOT_INSERT_KEY
** - error - could insert the key although it
** shouldn't be in the tree.
** also can get various errors from check_consistency()
**
** Description: Basically, do the insert, compare the result with the
** flag lookup table - if everything seems to be okay then
** update the lookup table and check the consistency of the
** new B-tree
*/
int testinsert(keynumber)
int keynumber;
{
DATUM dtm;
int status;
/*
Translate key index number into a key value
*/
dtm.key = getkey(keynumber);
/*
Send message to log file
*/
printf("Insert\t");
printkey(dtm.key);
/*
Now do the insert itself - can get two main errors:
(1) Successfully inserted a key which was already there
(2) Couldn't insert a key even though it wasn't there
*/
status = Insert(&tree,dtm);
/*
Now print out result of insert
*/
if (status==SUCCESS)
printf("inserted \t");
else
printf("not inserted\t");
/*
Check for error
*/
if ((status==SUCCESS) && (flag[keynumber]==IN_TREE))
return INSERTED_EXISTING_KEY;
if ((status==KEY_EXISTS_ERROR) && (flag[keynumber]==NOT_IN_TREE))
return CANNOT_INSERT_KEY;
/*
Update lookup table
*/
if (status==SUCCESS)
{
keytotal++;
flag[keynumber] = IN_TREE;
}
/*
Print 'no errors' message
*/
printf("CORRECT\t");
/*
Now check consistency of tree
*/
status = check_consistency();
if (status==SUCCESS)
printf("tree still okay\n");
return status;
}
/*
** TESTDELETE
** ==========
**
** Purpose: Test the deletion of a given key
**
** Parameters: keynumber = number of key to be deleted
**
** Returns: A diagnostic message is sent to stdout and upon completion
** an error/success code is returned:
** SUCCESS - everything worked
** TREE_CORRUPTED_ERROR
** - this is an error generated by Delete()
** itself when it thinks the tree has become
** corrupted
** DELETED_NON_EXISTANT_KEY
** - error - successfully deleted a key which
** should have been there in the first place
** CANNOT_DELETE_KEY
** - error - could delete a key which should have
** been in the tree
** also can get various errors from check_consistency()
**
** Description: Basically, do the delete, compare the result with the
** flag lookup table - if everything seems to be okay then
** update the lookup table and check the consistency of the
** new B-tree
*/
int testdelete(keynumber)
int keynumber;
{
KEY key;
int status;
/*
Translate key index number into a key value
*/
key = getkey(keynumber);
/*
Send message to log file
*/
printf("Delete\t");
printkey(key);
/*
Now do the delete itself - can get three main errors:
(1) Successfully deleted a key which wasn't there
(2) Couldn't delete a key even though it was there
(3) Delete detected a corrupted tree
*/
status = Delete(&tree,key);
/*
Print result of delete
*/
if (status==SUCCESS)
printf("deleted \t");
else
printf("not deleted \t");
/*
Check for errors
*/
if (status == TREE_CORRUPTED_ERROR)
return status;
if ((status==SUCCESS) && (flag[keynumber]==NOT_IN_TREE))
return DELETED_NON_EXISTANT_KEY;
if ((status==KEY_NOT_FOUND_ERROR) && (flag[keynumber]==IN_TREE))
return CANNOT_DELETE_KEY;
/*
Update lookup table
*/
if (status==SUCCESS)
{
flag[keynumber] = NOT_IN_TREE;
--keytotal;
}
/*
Print acknowledgement of success
*/
printf("CORRECT\t");
/*
Now check consistency of tree
*/
status = check_consistency();
if (status==SUCCESS)
printf("tree still okay\n");
return status;
}
/*********************************************************************
* CONSISTENCY CHECK ROUTINES
*********************************************************************/
/*
Total of number of keys found so far
*/
static int total;
/*
Depth of tree
*/
static int treedepth;
/*
** CHECKCONSISTENCY
** ================
**
** Purpose: Routine to check that a tree is in a consistent state
**
** Parameters: None
**
** Returns: One of the following error/success codes
** SUCCESS - all okay
** NODE_NOT_HALF_FULL
** - a node was found which was not half full and it
** wasn't the root.
** WRONG_KEY_IN_NODE
** - a node was found with a key value outside its
** specified range
** TREE_DEPTH_INCONSISTENT
** - the depth of the tree is not constant throughout
** KEY_TOTAL_MISMATCH
** - an external count of keys in the tree does not
** tally with a scan of the tree.
**
** Description: This routine fires off the 'performcheck' routine which
** is a recursive affair - upon return, any error from
** 'performcheck' is returned to the calling routine
** - otherwise the total number of keys in the tree is checked
** and this determines the final return code.
*/
int check_consistency()
{
KEY getkey();
int status;
/*
Set up initial total number of keys and depth of tree
*/
total = 0;
treedepth = 0;
/*
Now do the real consistency check
*/
status = performcheck(tree, 0, getkey(-1), getkey(MAXKEYS));
/*
if this gives any sort of error, return the error code
*/
if (status != SUCCESS)
return status;
/*
The only remaining check is the number of keys in the tree
- compare the test program running total (keytotal) with the
total from this tree scan (total)
*/
if (total != keytotal)
return KEY_TOTAL_MISMATCH;
return SUCCESS;
}
/*
** PERFORMCHECK
** ============
**
** Purpose: The main routine for checking consistency of a tree
**
** Parameters: tree = pointer to (sub-)tree to be checked
** thisdepth
** = depth of parent node (for root this is 0)
** lowkey = lower bound on range of key values in
** current top-level node
** highkey = upper bound on range of key values in
** current top-level node
**
** Returns: An error / success code
** SUCCESS - all okay
** TREE_DEPTH_INCONSISTENT
** - tree isn't of constant depth
** NODE_NOT_HALF_FULL
** - current top level node is not the root
** and is not 1/2 full
** WRONG_KEY_IN_NODE
** - a key (or keys) in this node does not
** lie in the correct key value range
** KEYS_NOT_IN_ORDER
** - at least 1 key of a node is not in order
**
** Description: This routine is a pretty complex affair and recursive to boot
** - the basic algorithm is:
** if we're at a root
** then check that depth agrees with system total
** else check size of node, range of keys in it and
** if these are okay, try all subtrees below here
*/
int performcheck(tree, thisdepth, lowkey, highkey)
BTREE tree;
int thisdepth;
KEY lowkey,
highkey;
{
int i;
int keys_in_node;
KEY lo,
hi,
upper;
int status;
/*
Update record of dpeth of current node
*/
thisdepth++;
/*
If current tree is null we've hit a leaf
- only check that can be performed is whether the depth is correct
*/
if (tree==(BTREE)NULL)
{
/*
Check the depth we've reached
*/
if (treedepth == 0)
{
/*
If overall depth is 0 then this is the first
leaf we've reached so no error
*/
treedepth = thisdepth;
return SUCCESS;
}
if (treedepth != thisdepth)
/*
if overall depth differs from current depth then
generate an error
*/
return TREE_DEPTH_INCONSISTENT;
return SUCCESS;
}
keys_in_node = tree->t_active;
/*
If not at a leaf, check whether this node is at least 1/2 full
- which is a prerequisite of all non-root nodes
*/
if ((keys_in_node<M) && (thisdepth != 1))
return NODE_NOT_HALF_FULL;
/*
Now update running total of keys found so far
*/
total += keys_in_node;
/*
Now check whether the keys in this node are between lowkey and
highkey - this only checks the left- and right- hand keys of the
node - a check for the order of keys in a node is done later.
*/
if ((KeyCmp(tree->t_dat[0].key, lowkey)<=0) ||
(KeyCmp(tree->t_dat[keys_in_node-1].key, highkey)>=0))
return WRONG_KEY_IN_NODE;
/*
If all's okay so far, go into the guts of the test - a recursive
consistency check of all nodes below here
*/
for (i=0; i<=keys_in_node; i++)
{
/*
Establish 3 quantities:
lo = lower bound on t_dat[i] and keys under t_ptr[i]
hi = upper bound on values in t_ptr[i]
upper = upper bound on t_dat[i]
*/
if (i==0)
lo = lowkey;
else
lo = tree->t_dat[i-1].key;
if (i==keys_in_node)
hi = highkey;
else
{
hi = tree->t_dat[i].key;
/*
The quantity 'upper' is only needed here
(where i<keys_in_node)
*/
if (i==(keys_in_node-1))
upper = highkey;
else
upper = tree->t_dat[i+1].key;
/*
Now check that t_dat[i] lies between 'lo' and 'upper'
*/
if ((KeyCmp(tree->t_dat[i].key,lo)<=0) ||
(KeyCmp(tree->t_dat[i].key,upper)>=0))
return KEYS_NOT_IN_ORDER;
}
/*
Do consistency check of subtree t_ptr[i]
*/
status = performcheck(tree->t_ptr[i],thisdepth,lo,hi);
/*
If a check of the subtree gave an error then bail out now
*/
if (status != SUCCESS)
break;
}
return status;
}
/*************************************************************************
* VARIOUS MISCELLANEOUS ROUTINES
*************************************************************************/
/*
** GETKEY
** ======
**
** Purpose: Routine to translate a key number into a key value
**
** Parameters: keynumber = number of key to be obtained
**
** Returns: Returns a key value
**
** Description: This routine is key dependent - it just returns a key value
** coresponding to a key number.
** Note that the routine must return keys with key values
** -1 ... MAXKEYS - where the 2 extremes are used in consistency
** checks for bounds on the key values in a tree.
*/
KEY getkey(keynumber)
int keynumber;
{
return keynumber;
}
/*
** PRINTKEY
** ========
**
** Purpose: Routine to print a key value
**
** Parameters: key = key value to be printed
**
** Returns: None
**
** Description: Mind-numbingly simple
*/
printkey(key)
KEY key;
{
printf("%d\t",key);
}
/*
** ERROR
** =====
**
** Purpose: Routine to convert an error number into an error message
**
** Parameters: errno = error number
**
** Returns: none.
**
** Description: Nothing particularly taxing about this one
*/
error(errno)
int errno;
{
printf("\n");
switch (errno)
{
case FOUND_NON_EXISTANT_KEY:
printf("!!! SEARCH found a key which should be in the tree\n");
break;
case NOT_FOUND_EXISTING_KEY:
printf("!!! SEARCH failed to find a key which should be in the tree\n");
break;
case FOUND_WRONG_KEY:
printf("!!! SEARCH located the wrong key\n");
break;
case INSERTED_EXISTING_KEY:
printf("!!! INSERT inserted a key into the tree when it was already there\n");
break;
case CANNOT_INSERT_KEY:
printf("!!! INSERT claimed that a key was already in the tree when it wasn't\n");
break;
case DELETED_NON_EXISTANT_KEY:
printf("!!! DELETE managed to delete a key which wasn't in the tree");
break;
case CANNOT_DELETE_KEY:
printf("!!! DELETE claimed that a key wasn't in the tree when it was\n");
break;
case TREE_CORRUPTED_ERROR:
printf("!!! TREE CORRUPTED\n");
break;
case NODE_NOT_HALF_FULL:
printf("!!! CONSISTENCY ERROR - a node was found to be less than half full\n");
break;
case WRONG_KEY_IN_NODE:
printf("!!! CONSISTENCY ERROR - a key was found in the wrong node\n");
break;
case TREE_DEPTH_INCONSISTENT:
printf("!!! CONSISTENCY ERROR - the tree is not of constant depth\n");
break;
case KEYS_NOT_IN_ORDER:
printf("!!! CONSISTENCY ERROR - the keys within a node are not in ascending order\n");
break;
case KEY_TOTAL_MISMATCH:
printf("!!! CONSISTENCY ERROR - the total number of keys in the tree is wrong\n");
break;
}
printf("\nThe tree is :-\n");
ShowTree(tree,0);
printf("\n\n ----> TEST ABORTED <----\n\n\n");
exit(0);
}
SHAR_EOF
fi
echo shar: "extracting btree.test.h"
if test -f 'btree.test.h'
then
echo shar: "will not over-write existing file 'btree.test.h'"
else
cat << \SHAR_EOF > 'btree.test.h'
**************************************************************************
Module Name: btree.test.h
============
Function: Defines various error codes used by btree.test.c
=========
Description:
============
Just defines a set of error codes
***************************************************************************
**************************************************************************/
static char btree_test_prog_hdr[] = "@(#)btree.test.h 1.1 7/15/86";
#define FOUND_NON_EXISTANT_KEY 100
#define NOT_FOUND_EXISTING_KEY 101
#define FOUND_WRONG_KEY 102
#define INSERTED_EXISTING_KEY 103
#define CANNOT_INSERT_KEY 104
#define DELETED_NON_EXISTANT_KEY 105
#define CANNOT_DELETE_KEY 106
#define NODE_NOT_HALF_FULL 107
#define WRONG_KEY_IN_NODE 108
#define TREE_DEPTH_INCONSISTENT 109
#define KEYS_NOT_IN_ORDER 110
#define KEY_TOTAL_MISMATCH 111
SHAR_EOF
fi
echo shar: "extracting btree.prt.h"
if test -f 'btree.prt.h'
then
echo shar: "will not over-write existing file 'btree.prt.h'"
else
cat << \SHAR_EOF > 'btree.prt.h'
/****************************************************************************
*****************************************************************************
**
** Module Name: btree.prt.h
** ============
**
** Function: routine for printing a tree
** =========
**
** Modification History
** --------------------
** Vers Date Mdfr Reason for Change
** ------------------------------------------------------
** 1.1 17/07/86 SMJ Adapted from btree.c v1.4
** -------------------------------------------------------
**
** Description:
** ============
** See for yourself
*/
static char btreeprt[] = "@(#)btree.prt.h 1.1 7/17/86";
/****************************************************************************
* TREE PRINTING ROUTINES
****************************************************************************/
/*
** SHOWTREE
** ========
**
** Purpose: Print the contents of a tree, showing the level of each node.
**
** Parameters: tree = Tree to print,
** level = Depth in tree.
**
** Returns: None.
**
** Description: Recursively scan down the tree, printing out the
** contents of each node in turn, indented in accordance with
** their depth in the tree.
** The 'level' parameter allows a limit to be set on the depth
** printout.
*/
ShowTree(tree, level)
BTREE tree;
int level;
{
int i;
if (tree != (BTREE)NULL)
{
for (i=0; i<level; ++i)
putchar(' ');
for (i=0; i<tree->t_active; ++i)
ShowDatum(tree->t_dat[i]);
putchar('\n');
for (i=0; i<=tree->t_active; ++i)
ShowTree(tree->t_ptr[i], 1+level);
}
}
/*
** SHOWDATUM
** =========
**
** Purpose: Routine to print the contents of a given datum
**
** Parameters: dtm = Datum to print.
**
** Returns: None.
**
*/
ShowDatum(dtm)
DATUM dtm;
{
printf("%d ", dtm.key);
}
SHAR_EOF
fi
echo shar: "extracting btree.fe.M"
if test -f 'btree.fe.M'
then
echo shar: "will not over-write existing file 'btree.fe.M'"
else
cat << \SHAR_EOF > 'btree.fe.M'
#*********************************************************************
#
# Title: btree.fe.M
#
# Function: btree front-end makefile
#
#*********************************************************************
#
# @(#)btree.fe.M 1.1 7/16/86
btree.fe: btree.fe.o btree.o btree.prt.h
cc -O -o btree.fe btree.fe.o
btree.fe.o: btree.fe.c btree.fe.h
cc -c -O btree.fe.c
btree.o: btree.c btree.h
cc -c -O btree.c
SHAR_EOF
fi
echo shar: "extracting btree.test.M"
if test -f 'btree.test.M'
then
echo shar: "will not over-write existing file 'btree.test.M'"
else
cat << \SHAR_EOF > 'btree.test.M'
#*********************************************************************
#
# Title: btree.test.M
#
# Function: btree test makefile
#
#*********************************************************************
#
# @(#)btree.test.M 1.1 7/16/86
btree.test: btree.test.o btree.o btree.prt.h
cc -O -o btree.test btree.test.o
btree.test.o: btree.test.c btree.test.h
cc -c -O btree.test.c
btree.o: btree.c btree.h
cc -c -O btree.c
SHAR_EOF
fi
echo "Done."tim@hoptoad.uucp (Tim Maroney) (08/21/86)
This may be fine as a spare-time programming exercise, but as one who has
hacked on the same original code I feel safe in saying that it is totally
worthless for any application. The translation from in-memory chained data
structures to relative in-file data structures invalidates all the code. It
took me literally months of full-time work to arrive at an actual database
file manager with reasonable performance and functionality. This took so
much time that my employer has quite reasonably insisted that the resulting
code, which is totally dissimilar to the original which I abandoned during
the first week of work, that it remain proprietary - sorry, guys. In case
you would like an estimate, after much trimming I got it down to 22K of
machine code on the 68000.
--
Tim Maroney, Electronic Village Idiot
{ihnp4,sun,well,ptsfa,lll-crg,frog}!hoptoad!tim (uucp)
hoptoad!tim@lll-crg (arpa)
I buy Playboy, but only to look at the pictures.