home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C!T ROM 2
/
ctrom_ii_b.zip
/
ctrom_ii_b
/
PROGRAM
/
C
/
BPTREE
/
BPTREE.C
< prev
next >
Wrap
Text File
|
1992-09-04
|
10KB
|
272 lines
//-----------------------------------------------------------------
// BPTREE.C
//
// BPlus Tree management functions
//
//-----------------------------------------------------------------
#ifdef __WINMEM__
#include <windows.h>
#endif
#include "bptree.h"
//-----------------------------------------------------------------
// BPlus tree structure allocation and deallocation functions
//-----------------------------------------------------------------
TREENODEPTR LIBFUNC MakeINode( ) {
TREENODEPTR tNode;
tNode = (TREENODEPTR)Malloc( sizeof( TREENODE ) );
tNode->nodeType = BPT_INODE;
return( tNode );
}
void LIBFUNC FreeINode( TREENODEPTR tNode ) {
Free( tNode );
return;
}
TREENODEPTR LIBFUNC MakeLNode( ) {
TREENODEPTR tNode;
tNode = (TREENODEPTR)Malloc( sizeof( TREENODE ) );
tNode->nodeType = BPT_LNODE;
return( tNode );
}
void LIBFUNC FreeLNode( TREENODEPTR tNode ) {
Free( tNode );
return;
}
KEYPTR LIBFUNC MakeMemBuf( int size ) {
return( (KEYPTR)Malloc( size ) );
}
void LIBFUNC FreeMemBuf( KEYPTR szBuf ) {
Free( szBuf );
}
//-----------------------------------------------------------------
// Recursive node insertion routine
//-----------------------------------------------------------------
TREENODEPTR LIBFUNC InsertTreeNode( PTR2TREENODEPTR tree, KEYPTR key, DATAPTR data ) {
TREENODEPTR newINode, newLNode, tNode;
if ( (*tree)->nodeType == BPT_LNODE ) {
newINode = MakeINode( );
newLNode = MakeLNode( );
newLNode->lnode.keyValue = MakeMemBuf( StrLen( key ) + 1 );
StrCpy( newLNode->lnode.keyValue, key );
newLNode->lnode.data = data;
if ( StrCmp( key, (*tree)->lnode.keyValue ) >= 0 ) {
newINode->inode.left = *tree;
newINode->inode.right = newLNode;
newINode->inode.keyValue = MakeMemBuf( StrLen( key ) + 1 );
StrCpy( newINode->inode.keyValue, key );
(*tree)->lnode.next->lnode.prev = newLNode;
newLNode->lnode.next = (*tree)->lnode.next;
(*tree)->lnode.next = newLNode;
newLNode->lnode.prev = *tree;
} else {
newINode->inode.left = newLNode;
newINode->inode.right = *tree;
newINode->inode.keyValue = MakeMemBuf( StrLen( (*tree)->lnode.keyValue ) + 1 );
StrCpy( newINode->inode.keyValue, (*tree)->lnode.keyValue );
(*tree)->lnode.prev->lnode.next = newLNode;
newLNode->lnode.prev = (*tree)->lnode.prev;
(*tree)->lnode.prev = newLNode;
newLNode->lnode.next = *tree;
}
*tree = newINode;
return( newLNode );
} else {
if ( StrCmp( key, (*tree)->inode.keyValue ) >= 0 ) {
tNode = InsertTreeNode( (PTR2TREENODEPTR)(&((*tree)->inode.right)), key, data );
} else {
tNode = InsertTreeNode( (PTR2TREENODEPTR)(&((*tree)->inode.left)), key, data );
}
return( tNode );
}
}
//-----------------------------------------------------------------
// Recursive node deletion routine
//-----------------------------------------------------------------
DATAPTR LIBFUNC DeleteTreeNode( PTR2TREENODEPTR tree, KEYPTR key )
{
DATAPTR data;
TREENODEPTR newTree;
if ( StrCmp( key, (*tree)->inode.keyValue ) >= 0 ) {
if ( (*tree)->inode.right->nodeType == BPT_INODE ) {
data = DeleteTreeNode( (PTR2TREENODEPTR)&((*tree)->inode.right ), key );
return( data );
} else {
if ( StrCmp( (*tree)->inode.right->lnode.keyValue, key )== 0 ) {
data = (*tree)->inode.right->lnode.data;
(*tree)->inode.right->lnode.next->lnode.prev = (*tree)->inode.right->lnode.prev;
(*tree)->inode.right->lnode.prev->lnode.next = (*tree)->inode.right->lnode.next;
FreeLNode( (*tree)->inode.right );
newTree = (*tree)->inode.left;
FreeINode( *tree );
*tree = newTree;
return( data );
} else
return( NULL );
}
} else {
if ( (*tree)->inode.left->nodeType == BPT_INODE ) {
data = DeleteTreeNode( (PTR2TREENODEPTR)&((*tree)->inode.left ), key );
return( data );
} else {
if ( StrCmp( (*tree)->inode.left->lnode.keyValue, key ) == 0 ) {
data = (*tree)->inode.left->lnode.data;
(*tree)->inode.left->lnode.next->lnode.prev = (*tree)->inode.left->lnode.prev;
(*tree)->inode.left->lnode.prev->lnode.next = (*tree)->inode.left->lnode.next;
FreeLNode( (*tree)->inode.left );
newTree = (*tree)->inode.right;
FreeINode( *tree );
*tree = newTree;
return( data );
} else
return( NULL );
}
}
}
//-----------------------------------------------------------------
// Exported Function - Create a new tree
//-----------------------------------------------------------------
TREEPTR LIBFUNC NewTree( ) {
TREEPTR tree;
tree = (TREEPTR)Malloc( sizeof( TREE ) );
tree->tree = NULL;
tree->first.nodeType = BPT_LNODE;
tree->first.lnode.specialType = BPT_FIRST;
tree->first.lnode.prev = NULL;
tree->first.lnode.next = &(tree->last);
tree->last.nodeType = BPT_LNODE;
tree->last.lnode.specialType = BPT_LAST;
tree->last.lnode.next = NULL;
tree->last.lnode.prev = &(tree->first);
tree->curPointer = NULL;
return( tree );
}
//-----------------------------------------------------------------
// Exported Function - Insert a node in the tree
//-----------------------------------------------------------------
TREENODEPTR LIBFUNC InsertInTree( TREEPTR tree, KEYPTR key, DATAPTR data ) {
TREENODEPTR tNode;
if ( tree->tree == NULL ) {
tree->tree = MakeLNode( );
tree->tree->lnode.keyValue = MakeMemBuf( StrLen( key ) + 1 );
StrCpy( tree->tree->lnode.keyValue, key );
tree->tree->lnode.data = data;
tree->tree->lnode.next = &(tree->last);
tree->tree->lnode.prev = &(tree->first);
tree->first.lnode.next = tree->tree;
tree->last.lnode.prev = tree->tree;
tree->curPointer = tree->tree;
return( tree->tree );
} else {
tNode = InsertTreeNode( (PTR2TREENODEPTR)(&(tree->tree)), key, data );
tree->curPointer = tNode;
return( tNode );
}
}
//-----------------------------------------------------------------
// Exported Function - Delete a node from the tree
//-----------------------------------------------------------------
DATAPTR LIBFUNC DeleteFromTree( TREEPTR tree, KEYPTR key ) {
DATAPTR data;
if ( tree->tree == NULL ) return NULL;
if ( tree->tree->nodeType == BPT_LNODE ) {
tree->first.lnode.next = &(tree->last);
tree->last.lnode.prev = &(tree->first);
data = tree->tree->lnode.data;
FreeLNode( tree->tree );
return( data );
}
data = DeleteTreeNode( (PTR2TREENODEPTR)&(tree->tree), key );
return( data );
}
//-----------------------------------------------------------------
// Exported Functions - Sequential node access functions
//-----------------------------------------------------------------
TREENODEPTR LIBFUNC FirstInTree( TREEPTR tree ) {
if ( tree->first.lnode.next == &(tree->last) )
return( NULL );
else
return( tree->curPointer = tree->first.lnode.next );
}
TREENODEPTR LIBFUNC LastInTree( TREEPTR tree ) {
if ( tree->last.lnode.prev == &(tree->first) )
return( NULL );
else
return( tree->curPointer = tree->last.lnode.prev );
}
TREENODEPTR LIBFUNC NextInTree( TREEPTR tree ) {
if ( tree->curPointer == NULL )
return( NULL );
if ( tree->curPointer->lnode.next == &(tree->last) )
return( NULL );
else
return( tree->curPointer = tree->curPointer->lnode.next );
}
TREENODEPTR LIBFUNC PrevInTree( TREEPTR tree ) {
if ( tree->curPointer == NULL )
return( NULL );
if ( tree->curPointer->lnode.prev == &(tree->first) )
return( NULL );
else
return( tree->curPointer = tree->curPointer->lnode.prev );
}
//-----------------------------------------------------------------
// Exported Function - Keyed node access function
//-----------------------------------------------------------------
TREENODEPTR LIBFUNC FindInTree( TREEPTR tree, KEYPTR key ) {
TREENODEPTR currentNode;
if ( tree->tree == NULL )
return( NULL );
currentNode = tree->tree;
while( currentNode->nodeType != BPT_LNODE ) {
if ( StrCmp( key, currentNode->inode.keyValue ) >= 0 )
currentNode = currentNode->inode.right;
else
currentNode = currentNode->inode.left;
}
if ( StrCmp( key, currentNode->lnode.keyValue ) == 0 )
return( tree->curPointer = currentNode );
else
return( tree->curPointer = NULL );
}
//-----------------------------------------------------------------
// Exported Function - Data access functions
//-----------------------------------------------------------------
KEYPTR LIBFUNC NodeKeyValue( TREENODEPTR tNode ) {
if ( tNode->nodeType == BPT_INODE )
return( tNode->inode.keyValue );
else
return( tNode->lnode.keyValue );
}
DATAPTR LIBFUNC NodeDataValue( TREENODEPTR tNode ) {
if ( tNode->nodeType == BPT_INODE )
return( NULL );
else
return( tNode->lnode.data );