Part II • Managing Data in C
struct _header |
|
|
{ |
|
|
struct _header |
*_ptr; |
unsigned |
|
_size; |
}; |
|
|
struct _header |
_base; |
/* Declare this external data to */ |
struct _header |
*_allocp; /* be used by malloc() */ |
The next structure, called _item, contains information specific to each data item (node) in the B-tree. This is the structure that would contain your item-specific data, such as the node’s key (this is an integer in the example program, but it could be a character string as well), a pointer to a structure containing the item’s data, or an index into a file that would have the item’s data.
struct _item
{
int |
nKeyValue; |
PAGE |
*RightReference; |
int |
nCount; |
};
The third structure, _page, forms the building block for the B-tree. This structure contains a count of items (from 1 to PAGE_SIZE), the block’s left branch, and an array of PAGE_SIZE Items. The nItemCount variable indicates how many of the items are used.
struct _page
{
int |
nItemCount; |
PAGE |
*LeftReference; |
ITEM |
Item[PAGE_SIZE]; |
};
The majority of BTREE.C’s main function processes keyboard input. This code is similar to the code in other example programs, so this section describes only the three most important blocks. The first block is executed when the user searches for a record. The Search() function is called, and is passed parameters that include the key the user is searching for and the root node for the B-tree.
case ‘s’: case ‘S’:
nLevelCount = 0;
Data Management: Sorts, Lists, and Indexes
if ((Search(nKeyValue, &nLevelCount, root, &u)))
{
printf(“SEARCH KEY %d found by searching %d levels\n”, nKeyValue,
nLevelCount);
}
else
{
printf(“SEARCH KEY %d NOT FOUND searching %d levels\n”, nKeyValue,
nLevelCount);
}
break;
The SearchAndAdd() function searches for the item. If the item cannot be found, SearchAndAdd() adds the user’s key to the B-tree. This function returns TRUE if the item was not added because the B-tree does not exist yet. If the B-tree does not exist yet, the B-tree is created and the item is added as the root of the node.
case ‘a’: case ‘A’:
printf(“ADD KEY %d\n”, nKeyValue);
if (SearchAndAdd(nKeyValue, root, &u))
{
q = root; NewItem(&root); root->nItemCount = 1; root->LeftReference = q;
CopyItem(&root->Item[0], &u);
}
TreePrint(root, 0, ROOT, 0);
break;
The DeleteItem() function is called when the user wants to delete a key. If the item being deleted is the current root, DeleteItem() returns TRUE, signaling that a new root must be created from another node.
case ‘d’: case ‘D’:
Part II • Managing Data in C
printf(“DELETE KEY %d\n”, nKeyValue);
if (DeleteItem(nKeyValue, root))
{
if (root->nItemCount == 0)
{
q = root;
root = q->LeftReference;
}
}
TreePrint(root, 0, ROOT, 0);
break;
Let’s look at some of the functions that do the work in the BTREE program. The Search() function simply follows the tree, starting at the given node, until the specified key is found or it is known that the key is not in the B-tree. The Search() function works recursively: it calls itself each time it searches a node and does not find a match for the specified key. By calling itself, Search() can use a simple function to perform a search to any level:
int Search(
int |
nKeyValue, |
int |
*nLevelCount, |
PAGE |
*a, |
ITEM |
*v) |
{ |
|
int |
i; |
ITEM |
u; |
//printf(“Search()...\n”);
if (a == NULL)
{
return(FALSE);
}
for (i = 0; i < a->nItemCount && nKeyValue > a->Item[i].nKeyValue;
Data Management: Sorts, Lists, and Indexes |
C C C |
|
10C |
|
C C C |
|
C C |
i++)
{
;
}
if (nKeyValue == a->Item[i].nKeyValue && i < a->nItemCount)
{
return(TRUE);
}
Search uses a simple integer comparison to check for a match. If the key had been a character string, you could use a call to strcmp() or some other character comparison function.
The recursive call to Search() follows. The recursion is performed by using a comparison of the variable i and by passing the current node’s right or left node to search.
else
{
++(*nLevelCount);
return(Search(nKeyValue, nLevelCount,
i ? a->Item[i - 1].RightReference : a->LeftReference, &u));
}
}
The SearchAndAdd() function is similar to the Search() function. When Search() ends, however, it simply returns a flag showing that the key was not found. When SearchAndAdd() returns, it adds the key to the current B-tree.
int SearchAndAdd( int nKeyValue, PAGE *a, ITEM *v)
{
int i;
ITEM u;
//printf(“SearchAndAdd()...\n”);
Part II • Managing Data in C
If the function was passed a NULL pointer, the program is preparing to add this key to a node. Then SearchAndAdd() prepares to add the key as the node, and returns TRUE to tell the caller that a node has been created.
The root node is created in the main program because the root node is “owned” by the main program, not by the B-tree functions:
if (a == NULL)
{
v->nKeyValue = nKeyValue; v->nCount = 1; v->RightReference = NULL; return TRUE;
}
The following code, which is similar to the code in Search(), is used to find a match:
for (i = 0; i < a->nItemCount && nKeyValue > a->Item[i].nKeyValue; i++)
{
;
}
if (nKeyValue == a->Item[i].nKeyValue && i < a->nItemCount)
{
In the following code, if a match is found, a counter of matches is incremented. This allows our version of B-tree to have duplicate keys, with only one copy of the key kept in memory.
a->Item[i].nCount++;
}
else
{
if (SearchAndAdd(nKeyValue,
i ? a->Item[i - 1].RightReference : a->LeftReference, &u))
{
If the SearchAndAdd() function does not find the key, the Insert() function adds the key to the B-tree (in the correct place), as follows:
return (Insert(a, i, &u, v));
}
}
Data Management: Sorts, Lists, and Indexes |
C C C |
|
10C |
|
C C C |
|
C C |
return FALSE;
}
The Insert() function adds the current key value to the passed node by computing the number of items in the current block. If the block is too full, the function splits it into two blocks:
int Insert(
PAGE |
*a, |
int |
i, |
ITEM |
*u, |
ITEM |
*v) |
//printf(“Insert()...\n”);
if (a->nItemCount < PAGE_SIZE)
{
for (j = a->nItemCount; j >= i + 1; j—)
{
CopyItem(&a->Item[j], &a->Item[j - 1]);
}
++a->nItemCount;
CopyItem(&a->Item[i], u);
return(FALSE);
}
else
{/* Page a is full. Split it and assign the emerging item to v. */
NewItem(&b);
if (i <= HALF_PAGE_SIZE)
{
if (i == HALF_PAGE_SIZE)
{
Part II • Managing Data in C
CopyItem(v, u);
}
else
{
CopyItem(v, &a->Item[HALF_PAGE_SIZE - 1]);
for (j = HALF_PAGE_SIZE - 1; j >= i + 1; j--)
{
CopyItem(&a->Item[j], &a->Item[j - 1]);
}
CopyItem(&a->Item[i], u);
}
for (j = 0; j <= HALF_PAGE_SIZE - 1; j++)
{
CopyItem(&b->Item[j], &a->Item[j + HALF_PAGE_SIZE]);
}
}
else
{
i -= HALF_PAGE_SIZE;
CopyItem(v, &a->Item[HALF_PAGE_SIZE]);
for (j = 0; j <= i - 2; j++)
{
CopyItem(&b->Item[j], &a->Item[j + HALF_PAGE_SIZE + 1]);
}
CopyItem(&b->Item[i - 1], u);
for (j = i; j <= HALF_PAGE_SIZE - 1; j++)
{
CopyItem(&b->Item[j], &a->Item[j + HALF_PAGE_SIZE]);
}
}
if (HALF_PAGE_SIZE == 0)
{
a->nItemCount = 1; b->nItemCount = 1;
Data Management: Sorts, Lists, and Indexes |
C C C |
|
10C |
|
C C C |
|
C C |
}
else
{
a->nItemCount = HALF_PAGE_SIZE; b->nItemCount = HALF_PAGE_SIZE;
}
b->LeftReference = v->RightReference; v->RightReference = b;
}
return(TRUE);
}
The CopyItem() function copies information from the source item to the destination item. In the days of non-ANSI C, structures could not be assigned to each other. ANSI C supports structure assignments, however, so you could replace CopyItem() with assignment statements.
int CopyItem(
ITEM *DestinationItem, ITEM *SourceItem)
{ |
|
|
// |
printf(“CopyItem()...\n”); |
|
|
DestinationItem->nKeyValue |
= SourceItem->nKeyValue; |
|
DestinationItem->RightReference |
= SourceItem->RightReference; |
|
DestinationItem->nCount |
= SourceItem->nCount; |
|
return(0); |
|
} |
|
|
The NewItem() function is used to create a new node. NewItem() uses malloc() to allocate memory for the new node, then clears the memory.
int NewItem(
PAGE **Page)
{
Part II • Managing Data in C
//printf(“NewItem()...\n”);
if ((*Page = (PAGE *)malloc(sizeof(**Page))) == NULL)
{
fprintf(stderr, “Couldn’t allocate memory!\n”);
exit(16);
}
/* malloc() doesn’t initialize storage, so we do... */
memset(*Page, 0, sizeof(**Page));
return(0);
}
The TreePrint() function prints the B-tree. This function knows which level it is being called for and prints this information with the current node’s values.
int TreePrint(
PAGE |
*Page, |
int |
nLevel, |
int |
nRightLeft, |
int |
nPosition) |
{ |
|
int |
i; |
int |
j; |
If TreePrint()is called witha NULL node, itdoes nothing. Otherwise, TreePrint() prints the level, prints whether it is the left or right node of its parent, and indents the node’s numeric value (its key value) by four spaces for each level.
if (Page != NULL)
{
for (i = 0; i < Page->nItemCount; i++)
{
switch(nRightLeft)
{
case ROOT: /* Should have only one root */ printf(“\n”);
printf(“(ROOT %2d) “, nLevel); break;
Data Management: Sorts, Lists, and Indexes
case LEFT: /* Happens all |
the time */ |
printf(“(L %2d |
%2d) “, nLevel, nPosition); |
break; |
|
|
case RIGHT:/* Happens all the time */ |
printf(“(R %2d |
%2d) “, nLevel, nPosition); |
break; |
|
|
default: /* Should never happen */ printf(“ERROR “);
break;
}
for (j = 0; j < nLevel; j++)
{/* Adjust the starting column for the variable */ printf(“.....”);
}
After the necessary header information is displayed, the key value is printed. Remember, the key does not need to be an integer. If it was a character string, you would probably have to change the following line:
printf(“%5d \n”, Page->Item[i].nKeyValue);
After printing the key value, TreePrint(), like Search(), calls itself recursively, and is passed information on whether the right node or the left node is being followed:
if (Page->Item[i].RightReference != NULL)
{
TreePrint(Page->Item[i].RightReference, nLevel + 1, RIGHT, i + 1);
}
}
if (Page->LeftReference != NULL)
{
TreePrint(Page->LeftReference, nLevel + 1, LEFT, 0);
}
}
return(0);
}
