Part II • Managing Data in C
Listing 10.6. continued
b->LeftReference = v->RightReference; v->RightReference = b;
}
return(TRUE);
}
int CopyItem(
ITEM *DestinationItem, ITEM *SourceItem)
{ |
|
|
// |
printf(“CopyItem()...\n”); |
|
|
DestinationItem->nKeyValue |
= SourceItem->nKeyValue; |
|
DestinationItem->RightReference |
= SourceItem->RightReference; |
|
DestinationItem->nCount |
= SourceItem->nCount; |
|
return(0); |
|
} |
|
|
int NewItem(
PAGE **Page)
{
//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. */
Part II • Managing Data in C
Listing 10.6. continued
for (j = 0; j < nLevel; j++)
{/* Adjust the starting column for the variable */ printf(“.....”);
}
printf(“%5d \n”, Page->Item[i].nKeyValue);
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);
}
int DeleteItem( int nKeyValue, PAGE *a)
{ |
|
int |
i; |
int |
k; |
int |
l; |
int |
r; |
PAGE |
*q; |
Data Management: Sorts, Lists, and Indexes
//printf(“DeleteItem()...\n”);
if (a == NULL)
{
printf(“Key is not in tree! Cannot delete this key.\n”); return FALSE;
}
else
{/* Binary array search */
for (l = 0, r = a->nItemCount - 1; l <= r; )
{
k = (l + r) / 2;
if (nKeyValue <= a->Item[k].nKeyValue)
{
r = k - 1;
}
if (nKeyValue >= a->Item[k].nKeyValue)
{
l = k + 1;
}
}
q = (r == -1) ? a->LeftReference : a->Item[r].RightReference;
if (l - r > 1)
{/* Found; now delete Item[k] */
if (q |
== |
NULL) |
{/* a |
is |
a terminal page */ |
—(a->nItemCount);
for (i = k; i < a->nItemCount; i++)
{
CopyItem(&a->Item[i], &a->Item[i + 1]);
}
return (a->nItemCount < HALF_PAGE_SIZE);
}
else
{
if (Delete(q, a, k))
{
continues
Part II • Managing Data in C
Listing 10.6. continued
return(UnderFlow(a, q, r));
}
}
}
else
{
if (DeleteItem(nKeyValue, q))
{
return UnderFlow(a, q, r);
|
} |
|
} |
} |
|
} |
|
int UnderFlow( |
PAGE |
*c, |
PAGE |
*a, |
int |
s) |
{ |
|
PAGE |
*b; |
int |
i; |
int |
k; |
int |
mb; |
int |
mc; |
// |
printf(“UnderFlow()...\n”); |
|
mc = c->nItemCount; |
|
if (s < mc - 1) |
|
{ |
++s;
b = c->Item[s].RightReference; mb = b->nItemCount;
Data Management: Sorts, Lists, and Indexes |
C C C |
|
10C |
|
C C C |
|
C C |
k = (mb - HALF_PAGE_SIZE + 1) / 2;
CopyItem(&a->Item[HALF_PAGE_SIZE - 1], &c->Item[s]);
a->Item[HALF_PAGE_SIZE - 1].RightReference = b->LeftReference;
if (k > 0)
{
for(i = 0; i < k - 1; i++)
{
CopyItem(&a->Item[i + HALF_PAGE_SIZE], &b->Item[i]);
}
CopyItem(&c->Item[s], &b->Item[k - 1]); c->Item[s].RightReference = b;
b->LeftReference = b->Item[k - 1].RightReference; mb -= k;
for (i = 0; i < mb; i++)
{
CopyItem(&b->Item[i], &b->Item[i + k]);
}
b->nItemCount = mb;
a->nItemCount = HALF_PAGE_SIZE - 1 + k;
return(FALSE);
}
else
{
for (i = 0; i < HALF_PAGE_SIZE; i++)
{
CopyItem(&a->Item[i + HALF_PAGE_SIZE], &b->Item[i]);
}
for (i = s; i < mc; i++)
{
CopyItem(&c->Item[i], &c->Item[i + 1]);
}
continues
Part II • Managing Data in C
Listing 10.6. continued
a->nItemCount = PAGE_SIZE; c->nItemCount = mc - 1;
}
}
else
{
b = (s == 0) ? c->LeftReference : c->Item[s - 1].RightReference; mb = b->nItemCount + 1;
k = (mb - HALF_PAGE_SIZE) / 2;
if (k > 0)
{
for(i = HALF_PAGE_SIZE - 2; i >= 0; i--)
{
CopyItem(&a->Item[i + k], &a->Item[i]);
}
CopyItem(&a->Item[k - 1], &c->Item[s]);
a->Item[k - 1].RightReference = a->LeftReference; mb -= k;
for (i = k - 2; i >= 0; i--)
{
CopyItem(&a->Item[i], &b->Item[i + mb]);
}
a->LeftReference = b->Item[mb].RightReference; CopyItem(&c->Item[s], &b->Item[mb - 1]); c->Item[s].RightReference = a;
b->nItemCount = mb - 1;
a->nItemCount = HALF_PAGE_SIZE - 1 + k;
return(FALSE);
}
else
{
CopyItem(&b->Item[mb], &c->Item[s]); b->Item[mb].RightReference = a->LeftReference;
Part II • Managing Data in C
Listing 10.6. continued
void PrintHelp()
{
printf(
“\n\nBTREE: Demo program for B-trees\n” “\n”
“Command are:\n”
“A # - Adds key # (integer 0 - 32767).\n”
“D # - Deletes key # (integer 0 - 32767).\n”
“S # - Searches for key # (integer 0 - 32767).\n”
“R # - Adds # random keys (integer 0 - 2000).\n”
“H - Prints a help screen.\n”
“T - Prints the current B-tree structure.\n”
“X - Exits, after a confirming prompt.\n\n”);
printf(“\n”
“All keys (the items that are placed in the tree) are \ integers,\n”
“ranging from 0 to 32767. Each item is added to the tree when \ the\n”
“Add command is issued.\n”);
printf(“\n”
“A new key is added with the Add command. Enter an A and an\n” “integer value.\n”);
printf(“\n”
“An existing key can be deleted by using the Delete command.\n” “Enter a D followed by an integer key value. If the value \
entered\n”
“is not a valid key, the program will tell you so.\n”);
printf(“\n”
“When you search for a key, the tree is traversed. If the key\n” “is found, the level where it was found is provided. If the \
key\n”
“is not found, a message is printed.\n”);
Data Management: Sorts, Lists, and Indexes |
C C C |
|
10C |
|
C C C |
|
C C |
printf(“\n”
“The Repeat command is used to build a table of random keys. \ The\n”
“rand() function is called the specified number of times. No\n” “test for duplicates is made, but duplicates for random-number\n” “counts of less than several hundred are infrequent.\n”);
printf(“\n”
“To print the entire tree structure, use the Tree command. \ This\n”
“command is entered as a T. There are no parameters for “ “this command.\n”);
printf(“\n”
“To end the program, use the Exit command. Enter an X, with no\n” “parameters. You will be prompted to confirm that you want to\n” “exit.\n”);
printf(“\n”
“If you don’t enter the key (or count for Repeat), the \ previous\n”
“value for the count is used.\n”);
}
The BTREE program arranges its tree in a way that you might not expect. The memory allocation functions could be called for each node, but this would be inefficient. Rather, each allocated block has from two to eight nodes. (You could have more than eight, but the B-tree’s performance might suffer.) I chose a block that would contain two data items (or nodes).
/* PAGE_SIZE is better at 8 (less memory fragmentation).*/
#define |
PAGE_SIZE |
2 |
#define |
HALF_PAGE_SIZE |
(PAGE_SIZE / 2) |
Three structures are created for the B-tree. First, a structure is created for the malloc() function:
/* Storage allocation structures used by malloc() */
