Clarification of Question by
74744-ga
on
09 Aug 2002 12:58 PDT
Two files are attached below. The first is a B-Tree header file. The
second is a sample program that uses the btree.h file to implement
the insertion technique of a B-tree. The header file
does not include deletion. The deletion function should be added to
the header file.
*****
/* CIS 15C Binary Tree Header File: This contains all data declar-
*/
/* ations and functions to support a B-Tree of order N.
*/
/*
*/
/* The BTREE Manager supports the following interfaces:
*/
/*
*/
/* 1) btree_init initializes a BTREE instance.
*/
/* 2) btree_insert inserts a node within a BTREE instance.
*/
/* 3) btree_delete deletes a node from a BTREE instance.
*/
/* 4) btree_find searches a BTREE instance by key for a node.
*/
/* 5) btree_enum enumerates all NODES within the BTREE instance.
*/
/* 6) btree_destroy collapses the BTREE instance.
*/
/*
*/
/**********************************************************************/
#define FOUND 0
#define NOTFOUND -1
#define BSIZE 2
#define BSIZE2 BSIZE*2
#define TRUE 1
#define FALSE 0
typedef struct page; /* forward declare page
*/
typedef struct node /* this is a declaration of the
*/
/* structure and definition of 2
*/
/* new types: 1) NODE and
*/
/* 2) pointer to NODEP
*/
{
struct page *child; /* pointer to child page
*/
int key; /* NODE key
*/
void *user; /* pointer to user data
*/
} NODE, *np;
typedef struct page /* this is a declaration of the
*/
/* structure and definition of 2
*/
/* new types: 1) PAGE and
*/
/* 2) pointer to PAGEP
*/
{
int num_nodes; /* number of NODES within page
*/
struct page *page0; /* pointer to page 0
*/
NODE data[BSIZE2]; /* array of pointers to nodes
*/
} PAGE, *pg_bt;
typedef struct btree /* this is a declaration of the
*/
/* structure and definition of 2
*/
/* new types: 1) BTREE
*/
/* 2) pointer to BTREE
*/
{
int user_size; /* sizeof(user data)
*/
pg_bt root; /* root page of BTREE instance
*/
} BTREE, *btp;
void btree_init (void **, /* btree_init prototype
*/
int);
void btree_insert (void *, /* btree_insert prototype
*/
int,
void *);
void btree_inserts(void *, /* btree_inserts prototype
*/
int ,
void *,
pg_bt ,
int *,
np );
void btree_add (pg_bt, /* btree_add prototype
*/
int ,
np ,
int *,
np );
int btree_find (void *, /* btree_find prototype
*/
int ,
void *,
int *);
int btree_finds(void *, /* btree_finds prototype
*/
int ,
pg_bt ,
void *,
int *);
void btree_enum (void *); /* btree_enum prototype
*/
void btree_visit (pg_bt, /* btree_visit prototype
*/
int *);
void btree_destroy (void **); /* btree_destroy prototype
*/
void btree_dealloc (pg_bt); /* btree_dealloc prototype
*/
/**********************************************************************/
/* Function btree_init allocates a BTREE insance and returns the
*/
/* address to the caller.
*/
/**********************************************************************/
void btree_init (void **btree,
int size)
{
btp bp = (btp) malloc (sizeof (BTREE)); /* allocate BTREE */
/* instance */
bp->root = NULL; /* set root page to NULL
*/
bp->user_size = size; /* set size of user data
*/
(*btree) = bp; /* return address of BTREE
*/
/* to caller
*/
return;
}
/**********************************************************************/
/*
*/
/* Function btree_insert invokes the recursive function
btree_inserts*/
/* to insert a new node within the BTREE instance.
*/
/*
*/
/**********************************************************************/
void btree_insert (void *btree,
int key,
void *user)
{
btp bp = (btp) btree; /* point to BTREE instance
*/
int split = FALSE; /* assume root does not
split*/
NODE add_node; /* local NODE returned if
the*/
/* root page is to be split
*/
(void) btree_inserts (btree,
key,
user,
bp->root,
&split,
&add_node);
if (split == TRUE) /* if page split of root
*/
{ /* allocate new root page
*/
pg_bt root = (pg_bt) malloc (sizeof(PAGE));
root->num_nodes = 1; /* new root has a single
NODE*/
root->page0 = bp->root; /* old root becomes child
*/
root->data[0] = add_node; /* page and copy merged up
*/
bp->root = root; /* NODE
*/
}
return;
}
/**********************************************************************/
/*
*/
/* Function btree_inserts inserts a NODE into the BTREE instance.
*/
/* It isolates the candidate page into which the NODE should be
*/
/* placed. If the page address is NULL a NODE is allocated and
*/
/* returned to the invoker. The insertion will occur at the parent
*/
/* page. If the key is not a candidate for the current page then
*/
/* this function is recursively called on the appropriate child
page.*/
/*
*/
/**********************************************************************/
void btree_inserts (void *btree, /* insert into BTREE instance
*/
int key,
void *user,
pg_bt root,
int *add,
np add_node)
{
btp bp = (btp) btree; /* point to BTREE instance
*/
void *v;
pg_bt p;
NODE node_a;
pg_bt child;
if (root == NULL) /* if no candidate page the
*/
{
(*add_node).key = key; /* copy key to NODE
*/
(*add_node).child = NULL; /* empty child page
*/
(*add_node).user = malloc (bp->user_size); /* allocate user area
*/
(void) memcpy ((*add_node).user,/* and copy user data
*/
user,
bp->user_size);
(*add) = TRUE; /* indicate to caller to add NODE
*/
}
else /* else have valid page
*/
{
int left = 0; /* perform binary search of page
*/
int right = root->num_nodes-1;
int mid;
do
{
mid = (left+right)/2; /* generate mid point
*/
if (root->data[mid].key >= key) /* if key is to left of mid
*/
right = (mid - 1); /* adjust mid value
*/
if (root->data[mid].key <= key) /* if key is to right of mid
*/
left = (mid + 1); /* adjust mid value
*/
} while (right >= left);
if (right == -1) /* if key preceeds all keys this
*/
child = root->page0; /* page then set child page0
*/
else /* else right has the child
*/
child = root->data[right].child; /* page pointer of all keys
*/
/* preceeding this key
*/
(void) btree_inserts (btree,
key,
user,
child,
add,
&node_a);
if ((*add) == TRUE) /* if the NODE is to be added
*/
btree_add (root, /* then append to page splitting
*/
right, /* pages as necessary
*/
&node_a,
add,
add_node);
}
return;
}
/**********************************************************************/
/* Function btree_add attempts to insert the node on the page
passed.*/
/* If there is no room, a page split occurs and the NODE whose key
*/
/* is in the middle of the (2*BSIZE+1) NODEs is returned to be in-
*/
/* serted at a higer level.
*/
/**********************************************************************/
void btree_add (pg_bt root, /* btree_add function
*/
int right,
np node_add,
int *add,
np add_node)
{
int i;
if (root->num_nodes < BSIZE2) /* if NODE will fit on page
*/
{
root->num_nodes++; /* increment NODE count this
page*/
(*add) = FALSE; /* no need to add so move all
*/
/* nodes one slot to the right
*/
for (i = root->num_nodes-1; i >= right + 2; i--)
root->data[i] = root->data[i-1];
root->data[right+1] = (*node_add);/* and insert NODE
*/
}
else /* otherwise page is full so
*/
{ /* must perform page split
*/
pg_bt pagep = (pg_bt) malloc (sizeof(PAGE)); /* allocate new
page*/
if ((right+1) <= BSIZE) /* if insert point is to left
*/
{ /* of the NODEs this page
*/
if ((right+1) == BSIZE) /* if key is in the middle
*/
(*add_node) = (*node_add); /* then insert NODE
*/
else /* otherwise move the middle
*/
{ /* NODE out to return to caller
*/
(*add_node) = root->data[BSIZE-1]; /* and move each NODE one
*/
for (i = BSIZE-1; i >= right+2; i--); /* slot to right
*/
root->data[i] = root->data[i-1];
root->data[right+1] = (*node_add); /* and insert NODE
*/
}
for (i = 0; i < BSIZE; i++); /* and move BSIZE nodes from
full*/
pagep->data[i] = pagep->data[i+BSIZE]; /* page to new page
*/
}
else /* else right > BSIZE
*/
{
right = (right - (BSIZE)); /* generate relative position
*/
(*add_node) = root->data[BSIZE]; /* extract the 1st NODE on
*/
/* right of middle key
*/
for (i = 0 ; i < (right); i++) /* and move all keys < insert
*/
pagep->data[i] = root->data[i+BSIZE+1]; /* key to new page
*/
pagep->data[right] = (*node_add); /* insert NODE in new page
*/
for (i = right+1; i <= BSIZE; i++) /* and move remaining NODEs
*/
pagep->data[i] = root->data[i+BSIZE]; /* from split page
*/
}
root->num_nodes = pagep->num_nodes = BSIZE; /* both split page
*/
pagep->page0 = (*add_node).child;
(*add_node).child = pagep;
}
return;
}
/**********************************************************************/
/* Function btree_enum invokes function btree_vist to recursively
*/
/* visit each page within the BTREE instance.
*/
/**********************************************************************/
void btree_enum (void *btree) /* btree enum function
*/
{
btp bp = (btp) btree; /* point to BTREE instance
*/
int level = 0;
(void) printf ("\n**** Begin Enumeration of BTREE.\n\n");
(void) btree_visit (bp->root, /* invoke recursive enumeration
*/
&level);
return;
}
/**********************************************************************/
/* Function btree_visit visits page0, then each NODE followed by
*/
/* the child page of ach NODE.
*/
/**********************************************************************/
void btree_visit (pg_bt root, /* recursive btree_visit
*/
int *level)
{
int i;
if (root != NULL) /* if non-NULL page passed
*/
{
(*level)++; /* increment level #
*/
(void) btree_visit (root->page0, /* visit page0
*/
level);
for (i = 0 ; i < root->num_nodes; i++) /* iterate all NODES this
*/
{ /* page
*/
(void) printf ("**** Node = %s at level = %d.\n",
root->data[i].user, (*level));
(void) btree_visit (root->data[i].child, /* then visit child
*/
level);
} /* page
*/
(*level)--; /* decrement level #
*/
}
return;
}
/**********************************************************************/
/*
*/
/* Function btree_find invokes the recursive function btree_finds
*/
/* to retrieve the NODE specified by the passed key.
*/
/*
*/
/**********************************************************************/
int btree_find (void *btree,
int key,
void *user,
int *count)
{
int res;
btp bp = (btp) btree; /* point to BTREE instance
*/
res = btree_finds (btree,
key,
bp->root,
user,
count);
return res;
}
/**********************************************************************/
/* Function btree_finds searches recursively for the NODE matching
*/
/* the passed key. If not found NOTFOUND is returned. If found, the
*/
/* user data is copied to the invoker and FOUND is returned.
*/
/**********************************************************************/
int btree_finds(void *btree, /* recursive btree_find
*/
int key,
pg_bt root,
void *user,
int *count)
{
btp bp = (btp) btree; /* point to BTREE instance
*/
pg_bt child;
int i;
int found = NOTFOUND;
if (root != NULL) /* if non-NULL page passed
*/
{
int left = 0; /* perform binary search of
page*/
int right = root->num_nodes-1;
int mid;
(*count)++; /* increment page count
*/
do
{
mid = (left+right)/2; /* generate mid point
*/
if (root->data[mid].key >= key) /* if key is to left of mid
*/
right = (mid - 1); /* adjust mid value
*/
if (root->data[mid].key <= key) /* if key is to right of mid
*/
left = (mid + 1); /* adjust mid value
*/
} while (right >= left);
if (left - right > 1) /* if NODE was found
*/
{
(void) memcpy (user, /* copy user data
*/
root->data[mid].user,
bp->user_size);
found = FOUND; /* indicate found NODE
*/
}
else
{
if (right == -1) /* if key preceeds all keys this
*/
child = root->page0; /* page then set child page0
*/
else /* else right has the child
*/
child = root->data[right].child; /* page pointer of all keys
*/
found = btree_finds (btree,
key,
child,
user,
count);
}
}
return found;
}
/**********************************************************************/
/* Function btree_destroy recursively invokes btree_dealloc to free
*/
/* all storage within the BTREE instance The caller's pointer var-
*/
/* iable is reset to NULL.
*/
/**********************************************************************/
void btree_destroy (void **btree)
{
btp bp = (btp) (*btree); /* point to BTREE instance
*/
(void) printf ("\n**** Deallocating BTREE storage\n");
(void) btree_dealloc (bp->root);
(void) free ((void *) bp); /* free BTREE instance
*/
(*btree) = NULL; /* reset caller's storage to
*/
/* NULL
*/
return;
}
/**********************************************************************/
/* Function btree_dealloc recursively call itslef on page0 and for
*/
/* each NODE within the page, frees the user data and then recur-
*/
/* sively calls itself to deallocate storage for the child page.
*/
/**********************************************************************/
void btree_dealloc (pg_bt root)
{
int i;
if (root != NULL) /* if non-null page
*/
{
(void) printf ("**** Page has %d NODEs.\n",
root->num_nodes);
for (i = 0; i < root->num_nodes; i++)
(void) printf ("**** Node # %d is %s.\n",
i, root->data[i].user);
(void) btree_dealloc (root->page0);/* deallocate storage for
page0*/
for (i = 0 ; i < root->num_nodes; i++) /* iterate all NODES this
*/
{ /* page
*/
(void) free (root->data[i].user); /* free user area
*/
(void) btree_dealloc (root->data[i].child);/* then deallocate
*/
} /* storage for child
*/
}
return;
}
/**********************************************************************/
/* Sample Program: Managing a BTREE instance via the
*/
/* BTREE services specified within "btree.h".
*/
/**********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "btree.h" /* Include BTREE Manager Services
*/
#define MAX_NAME 16
typedef struct part
{
char name[MAX_NAME];
int inventory;
} PART, *partp;
int main (void)
{
int i, res = 0;
int key, count = 0;
int page_count = 0;
void *vt;
char part_num [5];
PART P;
PART insert_part [30] = {
{ "PART0001", 25 } ,
{ "PART0002", 8 } ,
{ "PART0003", 86 } ,
{ "PART0004", 89 } ,
{ "PART0005", 9 } ,
{ "PART0006", 56 } ,
{ "PART0007", 24 } ,
{ "PART0008", 66 } ,
{ "PART0009", 54 } ,
{ "PART0010", 24 } ,
{ "PART0011", 31 } ,
{ "PART0012", 49 } ,
{ "PART0013", 98 } ,
{ "PART0014", 77 } ,
{ "PART0015", 32 } ,
{ "PART0016", 33 } ,
{ "PART0017", 41 } ,
{ "PART0018", 44 } ,
{ "PART0019", 26 } ,
{ "PART0020", 4 } ,
{ "PART0021", 12 } ,
{ "PART0022", 93 } ,
{ "PART0023", 68 } ,
{ "PART0024", 18 } ,
{ "PART0025", 88 } ,
{ "PART0026", 63 } ,
{ "PART0027", 72 } ,
{ "PART0028", 35 } ,
{ "PART0029", 11 } ,
{ "PART0030", 3 }
} ;
int find_part [10] = {
10,
1,
29,
15,
20,
8,
16,
22,
12,
30
} ;
(void) printf ("\n**** Entering Sample Program \n\n");
(void) btree_init (&vt, /* create BTREE instance
*/
sizeof(PART));
for (i = 0 ; i < 30 ; i++ ) /* populate BTREE instance
*/
{
(void) strcpy (part_num, &insert_part[i].name[4]);
key = atoi (part_num); /* generate key from part name
*/
(void) btree_insert (vt,
key,
(void *) &insert_part[i]);
(void) printf ("**** Part %s inserted.\n", insert_part[i].name);
}
(void) btree_enum (vt); /* enumerate parts within BTREE
*/
page_count = 0; /* initialize total page count
*/
(void) printf ("\n**** Begin FIND provessing of BTREE.\n\n");
for (i = 0 ; i < 10 ; i++ )
{
count = 0; /* initialize page count this key
*/
if ((res = btree_find (vt,
find_part[i],
&P,
&count)) == FOUND)
(void) printf ("**** BTREE page count for part %s with
inventory
= %d is %d.\n",
P.name,
P.inventory,
count);
else
(void) printf ("**** Part with key = %d not found.\n",
find_part[i]);
page_count += count; /* accumulate total page accesses
*/
}
(void) printf ("\n**** Average page count = %d\n",
(page_count/10));
(void) btree_destroy (&vt); /* collpase BTREE structures
*/
(void) printf ("\n**** Exiting Sample Program \n\n");
return res;
}
