Advanced C 1992

Part II • Managing Data in C

Listing 10.6. continued

#include <stdlib.h>	// For standard functions
#include <stdio.h>	// Make includes first part of file
#include <string.h>	// For string functions
#include <process.h>	// For exit(), etc.
#include <malloc.h>	// For malloc(), calloc(), realloc(), free()
#include <search.h>	// For qsort()
#include <time.h>	// To initialize the random-number functions

/* B-tree search and add, find, and delete

*Adapted from

*ALGORITHMS+DATA STRUCTURES=PROGRAMS by N. Wirth

*	Implemented	for BDS	C by H. Katayose (JUG-CP/M No.179)
*	Implemented	for ANSI	C by P. Hipson (CUG)
*/
/* PAGE_SIZE is		better at 8 (less memory fragmentation) */
#define PAGE_SIZE			2
#define HALF_PAGE_SIZE			(PAGE_SIZE / 2)
#define PAGE			struct _page
#define ITEM			struct _item
#define ROOT		0
#define RIGHT		1
#define LEFT		2
#define TRUE		(1)
#define FALSE		(0)

/* Storage allocation structures used by malloc() */

struct _header
{
struct _header	*_ptr;
unsigned	_size;
};

396

Data Management: Sorts, Lists, and Indexes

struct	_header	_base;	/*	Declare	this external data to */
struct	_header	*_allocp;	/*	be used	by malloc() */

C C C

C10C C

C C C

/* B-tree structures */

struct	_item
{
int	nKeyValue;
PAGE	*RightReference;
int	nCount;
};
struct	_page
{
int	nItemCount;
PAGE	*LeftReference;
ITEM	Item[PAGE_SIZE];
};
/* Function prototypes */
int	Search(int nKeyValue, int * nLevelCount, PAGE *a, ITEM *v);
int	SearchAndAdd(int nKeyValue, PAGE *a, ITEM *v);
int	Insert(PAGE *a, int i, ITEM *u, ITEM *v);
int	CopyItem(ITEM *DestinationItem, ITEM *SourceItem);
int	NewItem(PAGE **Page);
int	TreePrint(PAGE *p, int l, int nRightLeft, int nPosition);
int	DeleteItem(int nKeyValue, PAGE *a);
int	UnderFlow(PAGE *c, PAGE *a, int s);
int	Delete(PAGE *p, PAGE *a, int k);
void	PrintHelp(void);
/* The main program */
int main()
{
int	i;
int	j;

continues

397

Part II • Managing Data in C

Listing 10.6. continued

int	nKeyValue;
int	h;
int	nLevelCount = 0;
char	chOperation;
char	szCommand[132];
PAGE	*q;
PAGE	*root;
ITEM	u;

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”);

root = NULL;

while (TRUE)

{

printf(“\n\nCommand ?”);

gets(szCommand);

sscanf(szCommand, “%c %d”, &chOperation, &nKeyValue);

switch(chOperation)

{

case ‘h’: case ‘H’:

PrintHelp();

break;

398

Data Management: Sorts, Lists, and Indexes

case ‘r’: case ‘R’:

printf(“ADDING %d NODES\n”, nKeyValue);

srand((unsigned)time(NULL));

if (nKeyValue > 2000)

{

nKeyValue = 2000;

}

for (i = 0; i < nKeyValue; i++)

{

j = rand();

if (SearchAndAdd(j, root, &u))

{

q = root; NewItem(&root); root->nItemCount = 1; root->LeftReference = q;

CopyItem(&root->Item[0], &u);

}

}

TreePrint(root, 0, ROOT, 0); break;

case ‘s’: case ‘S’:

nLevelCount = 0;

if ((Search(nKeyValue, &nLevelCount, root, &u)))

{

printf(“SEARCH KEY %d found by searching %d \ levels\n”,

nKeyValue,

nLevelCount);

}

else

{

C C C

C10C C

C C C

continues

399

Part II • Managing Data in C

Listing 10.6. continued

printf(“SEARCH KEY %d NOT FOUND searching %d \ levels\n”,

nKeyValue,

nLevelCount);

}

break;

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;

case ‘t’: case ‘T’:

printf(“PRINT TREE\n”);

TreePrint(root, 0, ROOT, 0);

break;

case ‘d’: case ‘D’:

printf(“DELETE KEY %d\n”, nKeyValue);

400

Data Management: Sorts, Lists, and Indexes

if (DeleteItem(nKeyValue, root))

{

if (root->nItemCount == 0)

{

q = root;

root = q->LeftReference;

}

}

TreePrint(root, 0, ROOT, 0);

break;

case ‘x’: case ‘X’:

printf(“Confirm exit, y|n:”);

scanf(“%c”, &chOperation);

if (chOperation == ‘y’ || chOperation == ‘Y’)

{

exit(0);

}

break;

default:

printf(“\aUnknown operation ‘%c’\n”, chOperation);

break;

}

}

return(0);

}

int Search(

int nKeyValue, int *nLevelCount,

C C C

C10C C

C C C

continues

401

Part II • Managing Data in C

Listing 10.6. continued

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; i++)

{

;

}

if (nKeyValue == a->Item[i].nKeyValue && i < a->nItemCount)

{

return(TRUE);

}

else

{

++(*nLevelCount);

return(Search(nKeyValue, nLevelCount,

i ? a->Item[i - 1].RightReference : a->LeftReference, &u));

}

}

int SearchAndAdd( int nKeyValue, PAGE *a, ITEM *v)

402

Data Management: Sorts, Lists, and Indexes	C C C
	10C
	C C C
	C C

{

int i;

ITEM u;

//printf(“SearchAndAdd()...\n”);

if (a == NULL)

{

v->nKeyValue = nKeyValue; v->nCount = 1; v->RightReference = NULL; return TRUE;

}

for (i = 0; i < a->nItemCount && nKeyValue > a->Item[i].nKeyValue; i++)

{

;

}

if (nKeyValue == a->Item[i].nKeyValue && i < a->nItemCount)

{

a->Item[i].nCount++;

}

else

{

if (SearchAndAdd(nKeyValue,

i ? a->Item[i - 1].RightReference : a->LeftReference, &u))

{

return (Insert(a, i, &u, v));

}

}

return FALSE;

}

int Insert( PAGE *a,

continues

403

Part II • Managing Data in C

Listing 10.6. continued

int i, ITEM *u, ITEM *v)

{
PAGE	*b;
int	j;
int	h;

//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)

{

CopyItem(v, u);

}

else

{

CopyItem(v, &a->Item[HALF_PAGE_SIZE - 1]);

404

Data Management: Sorts, Lists, and Indexes

for (j = HALF_PAGE_SIZE - 1; j >= i + 1; j--)

{

CopyItem(&a->Item[j], &a->Item[j - 1]);

}

C C C

C10C C

C C C

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;

}

else

{

a->nItemCount = HALF_PAGE_SIZE; b->nItemCount = HALF_PAGE_SIZE;

}

continues

405