summaryrefslogtreecommitdiff
path: root/xbase64/xbndx.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'xbase64/xbndx.cpp')
-rwxr-xr-xxbase64/xbndx.cpp2402
1 files changed, 2402 insertions, 0 deletions
diff --git a/xbase64/xbndx.cpp b/xbase64/xbndx.cpp
new file mode 100755
index 0000000..e89bc7a
--- /dev/null
+++ b/xbase64/xbndx.cpp
@@ -0,0 +1,2402 @@
+/* xbndx.cpp
+
+ Xbase64 project source code
+
+ NDX indexing routines for X-Base
+
+ Copyright (C) 1997,2003,2004 Gary A Kunkel
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ Contact:
+
+ Email:
+
+ xdb-devel@lists.sourceforge.net
+ xdb-users@lists.sourceforge.net
+
+ Regular Mail:
+
+ XBase Support
+ 149C South Main St
+ Keller Texas, 76248
+ USA
+
+*/
+
+#ifdef __GNU LesserG__
+ #pragma implementation "xbndx.h"
+#endif
+
+#ifdef __WIN32__
+#include <xbase64/xbwincfg.h>
+#else
+#include <xbase64/xbconfig.h>
+#endif
+
+#include <xbase64/xbase64.h>
+#include <iostream>
+
+#ifdef XB_INDEX_NDX
+
+#ifdef HAVE_IO_H
+#include <io.h>
+#endif
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+//#include <xbase64/xbexcept.h>
+
+/*! \file xbndx.cpp
+*/
+
+/***********************************************************************/
+//! Short description
+/*!
+*/
+/* This routine dumps the node chain to stdout */
+#ifdef XBASE_DEBUG
+void xbNdx::DumpNodeChain()
+{
+ xbNdxNodeLink *n;
+ std::cout << std::endl << "*************************" << std::endl;
+ std::cout << "xbNodeLinkCtr = " << xbNodeLinkCtr << std::endl;
+ std::cout << "Reused = " << ReusedxbNodeLinks << std::endl;
+
+ n = NodeChain;
+ while(n){
+ std::cout << "xbNodeLink Chain ->" << n->NodeNo << std::endl;
+ std::cout << " CurKeyNo ->" << n->CurKeyNo << std::endl;
+ n = n->NextNode;
+ }
+ n = FreeNodeChain;
+ while(n){
+ std::cout << "FreexbNodeLink Chain " << n->NodeNo << std::endl;
+ n = n->NextNode;
+ }
+ n = DeleteChain;
+ while(n){
+ std::cout << "DeleteLink Chain " << n->NodeNo << std::endl;
+ n = n->NextNode;
+ }
+}
+#endif
+/***********************************************************************/
+//! Short description
+/*!
+ \param n
+*/
+/* This routine returns a chain of one or more index nodes back to the */
+/* free node chain */
+
+void xbNdx::ReleaseNodeMemory(xbNdxNodeLink *n, xbBool doFree)
+{
+ xbNdxNodeLink *temp;
+
+ if(doFree){
+ while(n){
+ temp = n->NextNode;
+ free(n);
+ n = temp;
+ }
+ } else {
+ if( !FreeNodeChain )
+ FreeNodeChain = n;
+ else { /* put this list at the end */
+ temp = FreeNodeChain;
+ while( temp->NextNode )
+ temp = temp->NextNode;
+ temp->NextNode = n;
+ }
+ }
+}
+/***********************************************************************/
+//! Short description
+/*!
+*/
+/* This routine returns a node from the free chain if available, */
+/* otherwise it allocates new memory for the requested node */
+
+xbNdxNodeLink * xbNdx::GetNodeMemory()
+{
+ xbNdxNodeLink * temp;
+ if( FreeNodeChain ){
+ temp = FreeNodeChain;
+ FreeNodeChain = temp->NextNode;
+ ReusedxbNodeLinks++;
+ } else {
+ temp = (xbNdxNodeLink *) malloc( sizeof( xbNdxNodeLink ));
+ xbNodeLinkCtr++;
+ }
+ memset( temp, 0x00, sizeof( xbNdxNodeLink ));
+ return temp;
+}
+/***********************************************************************/
+//! Short description
+/*!
+*/
+#ifdef XBASE_DEBUG
+void xbNdx::DumpHdrNode( xbShort opt )
+{
+ if( opt ){
+ FILE * log;
+ if(( log = fopen( "xbase64.log", "a+t" )) == NULL ) return;
+ fprintf( log, "Index Header Node for %s\n", GetFileName().getData());
+ fprintf( log, "--------------------------------\n" );
+ fprintf( log, "Start node = %ld\n", HeadNode.StartNode );
+ fprintf( log, "Total nodes = %ld\n", HeadNode.TotalNodes );
+ fprintf( log, "No of keys = %ld\n", HeadNode.NoOfKeys );
+ fprintf( log, "Key Length = %d\n", HeadNode.KeyLen );
+ fprintf( log, "Keys Per Node = %d\n", HeadNode.KeysPerNode );
+ fprintf( log, "Key type = %d\n", HeadNode.KeyType );
+ fprintf( log, "Key size = %ld\n", HeadNode.KeySize );
+ fprintf( log, "Unknown 2 = %d\n", HeadNode.Unknown2 );
+ fprintf( log, "Unique = %d\n", HeadNode.Unique );
+ fprintf( log, "KeyExpression = %s\n", HeadNode.KeyExpression );
+ fclose( log );
+ }
+ else
+ {
+ std::cout << "Start node = " << HeadNode.StartNode << std::endl;
+ std::cout << "Total nodes = " << HeadNode.TotalNodes << std::endl;
+ std::cout << "No of keys = " << HeadNode.NoOfKeys << std::endl;
+ std::cout << "Key Length = " << HeadNode.KeyLen << std::endl;
+ std::cout << "Keys Per Node = " << HeadNode.KeysPerNode << std::endl;
+ std::cout << "Key type = " << HeadNode.KeyType << std::endl;
+ std::cout << "Key size = " << HeadNode.KeySize << std::endl;
+ std::cout << "Unknown 2 = " << HeadNode.Unknown2 << std::endl;
+ std::cout << "Unique = " << HeadNode.Unique << std::endl;
+ std::cout << "KeyExpression = " << HeadNode.KeyExpression << std::endl;
+#ifdef XB_VAR_NODESIZE
+ std::cout << "NodeSize = " << NodeSize << std::endl;
+#endif // XB_VAR_NODESIZE
+ std::cout << std::endl;
+ }
+}
+#endif
+
+/***********************************************************************/
+//! Constructor
+/*!
+ \param pdbf
+*/
+xbNdx::xbNdx() : xbIndex()
+{
+}
+
+/***********************************************************************/
+//! Constructor
+/*!
+ \param pdbf
+*/
+xbNdx::xbNdx(xbDbf *pdbf) : xbIndex(pdbf) {
+#ifndef XB_VAR_NODESIZE
+ memset( Node, 0x00, XB_NDX_NODE_SIZE );
+#else
+ memset( Node, 0x00, XB_MAX_NDX_NODE_SIZE );
+#endif
+ memset( &HeadNode, 0x00, sizeof( xbNdxHeadNode ));
+ NodeChain = NULL;
+ FreeNodeChain = NULL;
+ DeleteChain = NULL;
+ CurNode = NULL;
+ xbNodeLinkCtr = 0L;
+ ReusedxbNodeLinks = 0L;
+#ifndef XB_VAR_NODESIZE
+ NodeSize = XB_NDX_NODE_SIZE;
+#else
+ NodeSize = XB_DEFAULT_NDX_NODE_SIZE;
+#endif // XB_VAR_NODESIZE
+}
+
+/***********************************************************************/
+//! Destructor
+/*!
+*/
+xbNdx::~xbNdx()
+{
+ CloseIndex();
+}
+
+/***********************************************************************/
+//! Short description
+/*!
+*/
+xbShort xbNdx::GetHeadNode( void )
+{
+ char *p, *q;
+ xbShort i;
+
+ if( !IsOpen() )
+ return XB_NOT_OPEN;
+
+ if( _fseek( indexfp, 0, SEEK_SET ))
+ return XB_SEEK_ERROR;
+
+ if(( fread( Node, XB_NDX_NODE_SIZE, 1, indexfp )) != 1 )
+ return XB_READ_ERROR;
+
+ /* load the head node structure */
+ p = Node;
+ HeadNode.StartNode = dbf->xbase->GetLong ( p ); p+=4;
+ HeadNode.TotalNodes = dbf->xbase->GetLong ( p ); p+=4;
+ HeadNode.NoOfKeys = dbf->xbase->GetLong ( p ); p+=4;
+ HeadNode.KeyLen = dbf->xbase->GetShort( p ); p+=2;
+ HeadNode.KeysPerNode = dbf->xbase->GetShort( p ); p+=2;
+ HeadNode.KeyType = dbf->xbase->GetShort( p ); p+=2;
+ HeadNode.KeySize = dbf->xbase->GetLong ( p ); p+=4;
+ HeadNode.Unknown2 = *p++;
+ HeadNode.Unique = *p++;
+
+#ifdef XB_VAR_NODESIZE
+ //
+ // Automagically determine the node size. Note the (2 * sizeof(xbLong))
+ // is taken directly from CreateIndex(). I don't understand it exactly,
+ // but this is the value used to calculate the number of keys per node.
+ // DTB.
+ //
+ NodeSize = (2 * sizeof(xbLong)) + HeadNode.KeySize * HeadNode.KeysPerNode;
+ if(NodeSize % XB_NDX_NODE_MULTIPLE)
+ NodeSize = ((NodeSize + XB_NDX_NODE_MULTIPLE) / XB_NDX_NODE_MULTIPLE) *
+ XB_NDX_NODE_MULTIPLE;
+#endif
+
+ q = HeadNode.KeyExpression;
+ for( i = XB_NDX_NODE_BASESIZE; i < XB_NDX_NODE_SIZE && *p; i++ )
+ *q++ = *p++;
+
+ return 0;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param NodeNo
+ \param SetNodeChain
+*/
+/* This routine reads a leaf node from disk */
+/* */
+/* If SetNodeChain 2, then the node is not appended to the node chain */
+/* but the CurNode pointer points to the node read */
+/* If SetNodeChain 1, then the node is appended to the node chain */
+/* If SetNodeChain 0, then record is only read to Node memory */
+
+xbShort xbNdx::GetLeafNode( xbLong NodeNo, xbShort SetNodeChain )
+{
+ xbNdxNodeLink *n;
+
+ if( !IsOpen() )
+ return XB_NOT_OPEN;
+
+ if( _fseek( indexfp, (xbOffT)NodeNo * XB_NDX_NODE_SIZE, SEEK_SET ))
+ return XB_SEEK_ERROR;
+
+ if(( fread( Node, XB_NDX_NODE_SIZE, 1, indexfp )) != 1 )
+ return XB_READ_ERROR;
+
+ if( !SetNodeChain ) return 0;
+
+ if(( n = GetNodeMemory()) == NULL )
+ return XB_NO_MEMORY;
+
+ n->NodeNo = NodeNo;
+ n->CurKeyNo = 0L;
+ n->NextNode = NULL;
+ n->Leaf.NoOfKeysThisNode = dbf->xbase->GetLong( Node );
+ memcpy( n->Leaf.KeyRecs, Node+4, XB_NDX_NODE_SIZE - 4 );
+
+ /* put the node in the chain */
+ if( SetNodeChain == 1 ){
+ if( NodeChain == NULL ){ /* first one ? */
+ NodeChain = n;
+ CurNode = n;
+ CurNode->PrevNode = NULL;
+ } else {
+ n->PrevNode = CurNode;
+ CurNode->NextNode = n;
+ CurNode = n;
+ }
+ }
+ else
+ CurNode = n;
+ return 0;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param n
+*/
+#ifdef XBASE_DEBUG
+void xbNdx::DumpNodeRec( xbLong n )
+{
+ char *p;
+ xbLong NoOfKeys, LeftBranch, RecNo, NodeType;
+ xbShort i,j;
+ FILE * log;
+
+ if(( log = fopen( "xbase64.log", "a+t" )) == NULL ) return;
+ GetLeafNode( n, 0 );
+ NoOfKeys = dbf->xbase->GetLong( Node );
+ p = Node + 4; /* go past no of keys */
+
+ fprintf( log, "----------------------------------------------------\n" );
+ fprintf( log, "Node # %ld\n", n );
+ fprintf( log, "Number of keys = %ld\n", NoOfKeys );
+ fprintf( log, " Key Left Dbf Rec Key\n" );
+ fprintf( log, "Number Branch Number Data\n" );
+
+ NodeType = 0;
+ for( i = 0; i < (NoOfKeys+NodeType); i++ ){
+ LeftBranch = dbf->xbase->GetLong( p );
+ if( i == 0 && LeftBranch ){
+ NodeType = 1; /* print one extra entry for interior nodes */
+ fprintf( log, "Interior node\n" );
+ }
+
+ p+=4;
+ RecNo = dbf->xbase->GetLong( p );
+ p+=4;
+
+ fprintf( log, " %3d %9ld %9ld ", i, LeftBranch, RecNo );
+
+ if( NodeType == 1 && i == NoOfKeys )
+ fprintf( log, "...\n" );
+
+ else if( !HeadNode.KeyType ){
+ for( j = 0; j < HeadNode.KeyLen; j++ )
+ fputc( *p++, log );
+ fputc( '\n', log );
+ }
+
+ else {
+ fprintf( log, "??????\n" /*, dbf->xbase->GetDouble( p )*/ );
+ p += 8;
+ }
+ }
+ fclose( log );
+}
+#endif
+/***********************************************************************/
+#ifndef XB_INLINE_GETDBFNO
+xbLong xbNdx::GetDbfNo( xbShort RecNo, xbNdxNodeLink * n )
+{
+ xbNdxLeafNode *temp;
+ char *p;
+ if( !n ) return 0L;
+ temp = &n->Leaf;
+ if( RecNo < 0 || RecNo > ( temp->NoOfKeysThisNode - 1 )) return 0L;
+ p = temp->KeyRecs + 4;
+ p += RecNo * ( 8 + HeadNode.KeyLen );
+ return( dbf->xbase->GetLong( p ));
+}
+#endif
+/***********************************************************************/
+//! Short description
+/*!
+ \param RecNo
+ \param n
+*/
+xbLong xbNdx::GetLeftNodeNo( xbShort RecNo, xbNdxNodeLink * n )
+{
+ xbNdxLeafNode *temp;
+ char *p;
+ if( !n ) return 0L;
+ temp = &n->Leaf;
+ if( RecNo < 0 || RecNo > temp->NoOfKeysThisNode ) return 0L;
+ p = temp->KeyRecs;
+ p += RecNo * ( 8 + HeadNode.KeyLen );
+ return( dbf->xbase->GetLong( p ));
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param RecNo
+ \param n
+*/
+char * xbNdx::GetKeyData( xbShort RecNo, xbNdxNodeLink * n )
+{
+ xbNdxLeafNode *temp;
+ char *p;
+ if( !n ) return 0L;
+ temp = &n->Leaf;
+ if( RecNo < 0 || RecNo > ( temp->NoOfKeysThisNode - 1 )) return 0L;
+ p = temp->KeyRecs + 8;
+ p += RecNo * ( 8 + HeadNode.KeyLen );
+ return( p );
+}
+/***********************************************************************/
+//! Short description
+/*!
+*/
+xbLong xbNdx::GetTotalNodes( void )
+{
+ if( &HeadNode )
+ return HeadNode.TotalNodes;
+ else
+ return 0L;
+}
+/***********************************************************************/
+//! Short description
+/*!
+*/
+xbUShort xbNdx::GetKeysPerNode( void )
+{
+ if( &HeadNode )
+ return HeadNode.KeysPerNode;
+ else
+ return 0L;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param RetrieveSw
+*/
+xbShort xbNdx::GetFirstKey( xbShort RetrieveSw )
+{
+/* This routine returns 0 on success and sets CurDbfRec to the record */
+/* corresponding to the first index pointer */
+
+ xbLong TempNodeNo;
+ xbShort rc;
+
+ /* initialize the node chain */
+ if( NodeChain ){
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = NULL;
+ }
+
+ if(( rc = GetHeadNode()) != 0 ){
+ CurDbfRec = 0L;
+ return rc;
+ }
+
+ /* get a node and add it to the link */
+ if(( rc = GetLeafNode( HeadNode.StartNode, 1 )) != 0 ){
+ return rc;
+ }
+
+/* traverse down the left side of the tree */
+ while( GetLeftNodeNo( 0, CurNode )){
+ TempNodeNo = GetLeftNodeNo( 0, CurNode );
+ if(( rc = GetLeafNode( TempNodeNo, 1 )) != 0 ){
+ CurDbfRec = 0L;
+ return rc;
+ }
+ CurNode->CurKeyNo = 0;
+ }
+ CurDbfRec = GetDbfNo( 0, CurNode );
+ if( RetrieveSw )
+ return dbf->GetRecord( CurDbfRec );
+ else
+ return XB_NO_ERROR;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param RetrieveSw
+*/
+xbShort xbNdx::GetNextKey( xbShort RetrieveSw )
+{
+/* This routine returns 0 on success and sets CurDbfRec to the record */
+/* corresponding to the next index pointer */
+
+ xbNdxNodeLink * TempxbNodeLink;
+ xbLong TempNodeNo;
+ xbShort rc;
+
+ if( !IsOpen() ){
+ CurDbfRec = 0L;
+ return XB_NOT_OPEN;
+ }
+
+ if( !CurNode ){
+ rc = GetFirstKey( RetrieveSw );
+ return rc;
+ }
+
+ /* more keys on this node ? */
+ if(( CurNode->Leaf.NoOfKeysThisNode-1) > CurNode->CurKeyNo ){
+ CurNode->CurKeyNo++;
+ CurDbfRec = GetDbfNo( CurNode->CurKeyNo, CurNode );
+ if( RetrieveSw )
+ return dbf->GetRecord( CurDbfRec );
+ else
+ return XB_NO_ERROR;
+ }
+
+ /* if head node we are at eof */
+ if( CurNode->NodeNo == HeadNode.StartNode ) {
+ return XB_EOF;
+ }
+
+ /* this logic assumes that interior nodes have n+1 left node no's where */
+ /* n is the number of keys in the node */
+
+ /* pop up one node to the interior node level & free the leaf node */
+
+ TempxbNodeLink = CurNode;
+ CurNode = CurNode->PrevNode;
+ CurNode->NextNode = NULL;
+ ReleaseNodeMemory( TempxbNodeLink );
+
+ /* while no more right keys && not head node, pop up one node */
+ while(( CurNode->CurKeyNo >= CurNode->Leaf.NoOfKeysThisNode ) &&
+ ( CurNode->NodeNo != HeadNode.StartNode )){
+ TempxbNodeLink = CurNode;
+ CurNode = CurNode->PrevNode;
+ CurNode->NextNode = NULL;
+ ReleaseNodeMemory( TempxbNodeLink );
+ }
+
+ /* if head node && right most key, return end-of-file */
+ if(( HeadNode.StartNode == CurNode->NodeNo ) &&
+ ( CurNode->CurKeyNo >= CurNode->Leaf.NoOfKeysThisNode )) {
+ return XB_EOF;
+ }
+
+ /* move one to the right */
+ CurNode->CurKeyNo++;
+ TempNodeNo = GetLeftNodeNo( CurNode->CurKeyNo, CurNode );
+
+ if(( rc = GetLeafNode( TempNodeNo, 1 )) != 0 ){
+ return rc;
+ }
+
+/* traverse down the left side of the tree */
+ while( GetLeftNodeNo( 0, CurNode )){
+ TempNodeNo = GetLeftNodeNo( 0, CurNode );
+ if(( rc = GetLeafNode( TempNodeNo, 1 )) != 0 ){
+ CurDbfRec = 0L;
+ return rc;
+ }
+ CurNode->CurKeyNo = 0;
+ }
+ CurDbfRec = GetDbfNo( 0, CurNode );
+ if( RetrieveSw )
+ return dbf->GetRecord( CurDbfRec );
+ else
+ return XB_NO_ERROR;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param NodeNo
+ \param RetrieveSw
+*/
+xbShort xbNdx::GetLastKey( xbLong NodeNo, xbShort RetrieveSw )
+{
+/* This routine returns 0 on success and sets CurDbfRec to the record */
+/* corresponding to the last index pointer */
+
+/* If NodeNo = 0, start at head node, otherwise start at NodeNo */
+
+ xbLong TempNodeNo;
+ xbShort rc;
+
+ if( NodeNo < 0 || NodeNo > HeadNode.TotalNodes )
+ return XB_INVALID_NODE_NO;
+
+ /* initialize the node chain */
+ if( NodeChain ){
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = NULL;
+ }
+ if( NodeNo == 0L )
+ if(( rc = GetHeadNode()) != 0 ){
+ CurDbfRec = 0L;
+ return rc;
+ }
+
+ /* get a node and add it to the link */
+ if( NodeNo == 0L ){
+ if(( rc = GetLeafNode( HeadNode.StartNode, 1 )) != 0 ){
+ CurDbfRec = 0L;
+ return rc;
+ }
+ } else {
+ if(( rc = GetLeafNode( NodeNo, 1 )) != 0 ) {
+ CurDbfRec = 0L;
+ return rc;
+ }
+ }
+ CurNode->CurKeyNo = CurNode->Leaf.NoOfKeysThisNode;
+
+/* traverse down the right side of the tree */
+ while( GetLeftNodeNo( CurNode->Leaf.NoOfKeysThisNode, CurNode )){
+ TempNodeNo = GetLeftNodeNo( CurNode->Leaf.NoOfKeysThisNode, CurNode );
+ if(( rc = GetLeafNode( TempNodeNo, 1 )) != 0 ){
+ CurDbfRec = 0L;
+ return rc;
+ }
+ CurNode->CurKeyNo = CurNode->Leaf.NoOfKeysThisNode;
+ }
+ CurNode->CurKeyNo--; /* leaf node has one fewer ix recs */
+ CurDbfRec = GetDbfNo( CurNode->Leaf.NoOfKeysThisNode-1, CurNode );
+ if( RetrieveSw )
+ return dbf->GetRecord( CurDbfRec );
+ else
+ return XB_NO_ERROR;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param RetrieveSw
+*/
+xbShort xbNdx::GetPrevKey( xbShort RetrieveSw )
+{
+/* This routine returns 0 on success and sets CurDbfRec to the record */
+/* corresponding to the previous index pointer */
+
+ xbNdxNodeLink * TempxbNodeLink;
+ xbLong TempNodeNo;
+ xbShort rc;
+
+ if( !IsOpen() ){
+ CurDbfRec = 0L;
+ return XB_NOT_OPEN;
+ }
+
+ if( !CurNode ){
+ CurDbfRec = 0L;
+ return GetFirstKey( RetrieveSw );
+ }
+
+ /* more keys on this node ? */
+ if( CurNode->CurKeyNo > 0 ){
+ CurNode->CurKeyNo--;
+ CurDbfRec = GetDbfNo( CurNode->CurKeyNo, CurNode );
+ if( RetrieveSw )
+ return dbf->GetRecord( CurDbfRec );
+ else
+ return XB_NO_ERROR;
+ }
+
+ /* this logic assumes that interior nodes have n+1 left node no's where */
+ /* n is the number of keys in the node */
+ /* pop up one node to the interior node level & free the leaf node */
+
+ if( !CurNode->PrevNode ) { /* michael - make sure prev node exists */
+ return XB_EOF;
+ }
+
+ TempxbNodeLink = CurNode;
+ CurNode = CurNode->PrevNode;
+ CurNode->NextNode = NULL;
+ ReleaseNodeMemory( TempxbNodeLink );
+
+ /* while no more left keys && not head node, pop up one node */
+ while(( CurNode->CurKeyNo == 0 ) &&
+ ( CurNode->NodeNo != HeadNode.StartNode )) {
+ TempxbNodeLink = CurNode;
+ CurNode = CurNode->PrevNode;
+ CurNode->NextNode = NULL;
+ ReleaseNodeMemory( TempxbNodeLink );
+ }
+
+ /* if head node && left most key, return beginning-of-file */
+ if(( HeadNode.StartNode == CurNode->NodeNo ) &&
+ ( CurNode->CurKeyNo == 0 )) {
+ return XB_BOF;
+ }
+
+ /* move one to the left */
+ CurNode->CurKeyNo--;
+ TempNodeNo = GetLeftNodeNo( CurNode->CurKeyNo, CurNode );
+
+ if(( rc = GetLeafNode( TempNodeNo, 1 )) != 0 ) {
+ return rc;
+ }
+
+ if( GetLeftNodeNo( 0, CurNode )) /* if interior node */
+ CurNode->CurKeyNo = CurNode->Leaf.NoOfKeysThisNode;
+ else /* leaf node */
+ CurNode->CurKeyNo = CurNode->Leaf.NoOfKeysThisNode - 1;
+
+/* traverse down the right side of the tree */
+ while( GetLeftNodeNo( 0, CurNode )){ /* while interior node */
+ TempNodeNo = GetLeftNodeNo( CurNode->Leaf.NoOfKeysThisNode, CurNode );
+ if(( rc = GetLeafNode( TempNodeNo, 1 )) != 0 ){
+ CurDbfRec = 0L;
+ return rc;
+ }
+ if( GetLeftNodeNo( 0, CurNode )) /* if interior node */
+ CurNode->CurKeyNo = CurNode->Leaf.NoOfKeysThisNode;
+ else /* leaf node */
+ CurNode->CurKeyNo = CurNode->Leaf.NoOfKeysThisNode - 1;
+ }
+ CurDbfRec = GetDbfNo( CurNode->Leaf.NoOfKeysThisNode - 1, CurNode );
+ if( RetrieveSw )
+ return dbf->GetRecord( CurDbfRec );
+ else
+ return XB_NO_ERROR;
+}
+/**************************************************************************/
+//! Short description
+/*!
+ \param key
+ \param klen
+ \param node
+ \param comp
+*/
+/*
+** This is a pretty basic binary search with two exceptions: 1) it will
+** find the first of duplicate key values and 2) will return the index
+** and the value of the last comparision even if it doesn't find a
+** match.
+*/
+xbShort
+xbNdx::BSearchNode(const char *key, xbShort klen, const xbNdxNodeLink *node,
+ xbShort *comp)
+{
+ xbShort c, p, start = 0, end = node->Leaf.NoOfKeysThisNode - 1;
+
+ if(start > end){
+ *comp = 2;
+ return 0;
+ }
+
+ do {
+ p = (start + end) / 2;
+ c = CompareKey(key, GetKeyData(p, (xbNdxNodeLink *)node), klen);
+ switch(c){
+
+ case 1 : /* greater than */
+ start = p + 1;
+ break;
+
+ case 2 : /* less than */
+ end = p - 1;
+ break;
+ }
+ } while(start <= end && c);
+
+
+ if(c == 1)
+ while(p < node->Leaf.NoOfKeysThisNode &&
+ (c = CompareKey(key, GetKeyData(p, (xbNdxNodeLink *)node), klen)) == 1)
+ p++;
+
+ *comp = c;
+
+ if(!c)
+ while(p > 0 && !CompareKey(key, GetKeyData(p - 1, (xbNdxNodeLink *)node), klen))
+ p--;
+
+ return p;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param Tkey
+ \param Klen
+*/
+xbLong xbNdx::GetLeafFromInteriorNode( const char * Tkey, xbShort Klen )
+{
+ /* This function scans an interior node for a key and returns the */
+ /* correct interior leaf node no */
+
+ xbShort p, c;
+
+ /* if Tkey > any keys in node, return right most key */
+ p = CurNode->Leaf.NoOfKeysThisNode - 1;
+ if( CompareKey( Tkey, GetKeyData( p, CurNode ), Klen ) == 1 ) {
+ CurNode->CurKeyNo = CurNode->Leaf.NoOfKeysThisNode;
+ return GetLeftNodeNo( CurNode->Leaf.NoOfKeysThisNode, CurNode );
+ }
+
+ p = BSearchNode(Tkey, Klen, CurNode, &c);
+ CurNode->CurKeyNo = p;
+ return GetLeftNodeNo( p, CurNode );
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param d
+*/
+xbShort xbNdx::KeyExists( xbDouble d )
+{
+ char buf[9];
+ memset( buf, 0x00, 9 );
+ dbf->xbase->PutDouble( buf, d );
+ return FindKey( buf, 8, 0 );
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param d
+*/
+xbShort xbNdx::FindKey( xbDouble d )
+{
+ char buf[9];
+ memset( buf, 0x00, 9 );
+ dbf->xbase->PutDouble( buf, d );
+ return FindKey( buf, 8, 1 );
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param Key
+*/
+xbShort xbNdx::FindKey( const char * Key )
+{
+ return FindKey( Key, strlen( Key ), 1 );
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param Tkey
+ \param DbfRec
+*/
+xbShort xbNdx::FindKey( const char * Tkey, xbLong DbfRec )
+{
+ /* find a key with a specifc DBF record number */
+ xbShort rc;
+
+ xbLong CurDbfRecNo;
+ xbLong CurNdxDbfNo;
+
+ /* if we are already on the correct key, return XB_FOUND */
+ if( CurNode ) {
+ CurDbfRecNo = dbf->GetCurRecNo();
+ CurNdxDbfNo = GetDbfNo( CurNode->CurKeyNo, CurNode );
+ if( CurDbfRecNo == CurNdxDbfNo &&
+ (strncmp(Tkey, GetKeyData( CurNode->CurKeyNo, CurNode ),
+ HeadNode.KeyLen ) == 0 )) {
+ return XB_FOUND;
+ }
+ }
+ rc = FindKey( Tkey, HeadNode.KeyLen, 0 );
+
+ while( rc == 0 || rc == XB_FOUND ) {
+ if( strncmp( Tkey, GetKeyData( CurNode->CurKeyNo, CurNode ),
+ HeadNode.KeyLen ) == 0 ){
+ if( DbfRec == GetDbfNo( CurNode->CurKeyNo, CurNode )) {
+ return XB_FOUND;
+ }
+ else
+ rc = GetNextKey( 0 );
+ } else {
+ return XB_NOT_FOUND;
+ }
+ }
+ return XB_NOT_FOUND;
+}
+/***********************************************************************/
+//! Short description
+/*!
+*/
+xbShort xbNdx::FindKey( void )
+{
+ /* if no paramaters given, use KeyBuf */
+ return( FindKey( KeyBuf, HeadNode.KeyLen, 0 ));
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param Tkey
+ \param Klen
+ \param RetrieveSw
+*/
+xbShort xbNdx::FindKey( const char * Tkey, xbShort Klen, xbShort RetrieveSw )
+{
+ /* This routine sets the current key to the found key */
+ /* if RetrieveSw is true, the method positions the dbf record */
+ xbShort rc,i;
+ xbLong TempNodeNo;
+
+ if( NodeChain ) {
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = NULL;
+ }
+
+ if(( rc = GetHeadNode()) != 0 ){
+ CurDbfRec = 0L;
+ return rc;
+ }
+
+ /* load first node */
+ if(( rc = GetLeafNode( HeadNode.StartNode, 1 )) != 0 ){
+ CurDbfRec = 0L;
+ return rc;
+ }
+
+ /* traverse down the tree until it hits a leaf */
+ while( GetLeftNodeNo( 0, CurNode )){ /* while interior node */
+ TempNodeNo = GetLeafFromInteriorNode( Tkey, Klen );
+ if(( rc = GetLeafNode( TempNodeNo, 1 )) != 0 ){
+ CurDbfRec = 0L;
+ return rc;
+ }
+ }
+
+ i = BSearchNode(Tkey, Klen, CurNode, &rc);
+ switch(rc) {
+ case 0 : /* found! */
+ CurNode->CurKeyNo = i;
+ CurDbfRec = GetDbfNo( i, CurNode );
+ if( RetrieveSw )
+ dbf->GetRecord(CurDbfRec);
+ return XB_FOUND;
+
+ case 1 : /* less than */
+// if(i < CurNode->Leaf.NoOfKeysThisNode)
+ break;
+// i++;
+
+ case 2 : /* greater than */
+ CurNode->CurKeyNo = i;
+ CurDbfRec = GetDbfNo( i, CurNode );
+ if( RetrieveSw )
+ dbf->GetRecord(CurDbfRec);
+ return XB_NOT_FOUND;
+ }
+
+ CurNode->CurKeyNo = i;
+ if(i >= CurNode->Leaf.NoOfKeysThisNode){
+ CurDbfRec = 0;
+ return XB_EOF;
+ }
+
+ CurDbfRec = GetDbfNo( i, CurNode );
+ if((RetrieveSw) && (CurDbfRec > 0))
+ dbf->GetRecord( CurDbfRec );
+
+ return XB_NOT_FOUND;
+}
+/***********************************************************************/
+//! Short description
+/*!
+*/
+xbShort xbNdx::CalcKeyLen()
+{
+ xbShort rc;
+ xbExpNode * TempNode;
+ char FieldName[11];
+ char Type;
+
+ TempNode = IxExp->GetFirstTreeNode();
+
+ if( !TempNode )
+ return 0;
+
+ if( TempNode->Type == 'd' ) return -8;
+ if( TempNode->Type == 'D' ){
+ memset( FieldName, 0x00, 11 );
+ memcpy( FieldName, TempNode->NodeText, TempNode->Len );
+ Type = dbf->GetFieldType( dbf->GetFieldNo( FieldName ));
+ if( Type == 'N' || Type == 'F' )
+ return -8;
+ }
+
+ if(( rc = IxExp->ProcessExpression()) != XB_NO_ERROR )
+ return 0;
+
+ TempNode = (xbExpNode *) IxExp->Pop();
+ if( !TempNode )
+ return 0;
+ rc = TempNode->DataLen;
+
+ if( !TempNode->InTree )
+ delete TempNode;
+
+ return rc;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param IxName
+ \param Exp
+ \param Unique
+ \param Overlay
+*/
+xbShort xbNdx::CreateIndex(const char * IxName, const char * Exp,
+ xbShort Unique, xbShort Overlay )
+{
+ xbShort i, KeyLen, rc;
+
+ if( IsOpen()) CloseIndex();
+ if( strlen( Exp ) > 488 )
+ return XB_INVALID_KEY_EXPRESSION;
+
+ if( dbf->GetDbfStatus() == 0 )
+ return XB_NOT_OPEN;
+
+ /* Get the index file name and store it in the class */
+ SetFileName(IxName);
+
+ /* check if the file already exists */
+ if (((indexfp = fopen( GetFileName(), "r" )) != NULL ) && !Overlay ) {
+ fclose( indexfp );
+ return XB_FILE_EXISTS;
+ }
+
+ if (indexfp)
+ fclose(indexfp);
+
+ if(( indexfp = fopen( GetFileName(), "w+b" )) == NULL )
+ return XB_OPEN_ERROR;
+
+#ifdef XB_LOCKING_ON
+ /*
+ ** Must turn off buffering when multiple programs may be accessing
+ ** index files.
+ */
+ setbuf( indexfp, NULL );
+#endif
+
+ /* parse the expression */
+ IxExp = new xbExpn( dbf->xbase );
+ if(( rc = IxExp->BuildExpressionTree( Exp, strlen( Exp ), dbf )) != XB_NO_ERROR )
+ return rc;
+
+ /* build the header record */
+ memset( &HeadNode, 0x00, sizeof( xbNdxHeadNode ));
+ HeadNode.StartNode = 1L;
+ HeadNode.TotalNodes = 2L;
+ HeadNode.NoOfKeys = 1L;
+ KeyLen = CalcKeyLen();
+
+ if( KeyLen == 0 || KeyLen > 100 ) /* 100 byte key length limit */
+ return XB_INVALID_KEY;
+ else if( KeyLen == -8 ){
+ HeadNode.KeyType = 1; /* numeric key */
+ HeadNode.KeyLen = 8;
+ } else {
+ HeadNode.KeyType = 0; /* character key */
+ HeadNode.KeyLen = KeyLen;
+ }
+
+// HeadNode.KeysPerNode = (xbUShort) ( XB_NDX_NODE_SIZE - (2*sizeof( xbLong ))) /
+// (HeadNode.KeyLen + 8 );
+// HeadNode.KeySize = HeadNode.KeyLen + 8;
+// while(( HeadNode.KeySize % 4 ) != 0 ) HeadNode.KeySize++; /* multiple of 4*/
+
+/* above code replaced with following by Paul Koufalis pkoufalis@cogicom.com */
+// while(( HeadNode.KeyLen % 4 ) != 0 ) HeadNode.KeyLen++; /* multiple of 4*/
+// HeadNode.KeySize = HeadNode.KeyLen + 8;
+
+
+/* above two lines commented out by gary 4/14/99 and replaced w/ following
+ For compatibility with other Xbase tools
+ KeyLen is the length of the key data
+ KeySize = KeyLen+8, rounded up until divisible by 4
+*/
+
+ HeadNode.KeySize = HeadNode.KeyLen + 8;
+ while(( HeadNode.KeySize % 4 ) != 0 ) HeadNode.KeySize++; /* multiple of 4*/
+
+ HeadNode.KeysPerNode = (xbUShort)
+ (XB_NDX_NODE_SIZE - (2*sizeof( xbLong ))) / HeadNode.KeySize;
+
+ HeadNode.Unique = Unique;
+ strncpy( HeadNode.KeyExpression, Exp, 488 );
+ KeyBuf = (char *) malloc( HeadNode.KeyLen + 1 );
+ KeyBuf2 = (char *) malloc( HeadNode.KeyLen + 1 );
+ memset( KeyBuf, 0x00, HeadNode.KeyLen + 1 );
+ memset( KeyBuf2, 0x00, HeadNode.KeyLen + 1 );
+
+ if(( rc = PutHeadNode( &HeadNode, indexfp, 0 )) != 0 ){
+ return rc;
+ }
+ /* write node #1 all 0x00 */
+ for( i = 0; i < XB_NDX_NODE_SIZE; i++ ){
+ if ((fwrite("\x00", 1, 1, indexfp)) != 1){
+ fclose( indexfp );
+ return XB_WRITE_ERROR;
+ }
+ }
+// IndexStatus = XB_OPEN;
+ return dbf->AddIndexToIxList( index, GetFileName() );
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param RecNo
+ \param n
+ \param NodeNo
+*/
+xbShort xbNdx::PutLeftNodeNo( xbShort RecNo, xbNdxNodeLink *n, xbLong NodeNo )
+{
+ /* This routine sets n node's leftnode number */
+ xbNdxLeafNode *temp;
+ char *p;
+ if( !n )
+ return XB_INVALID_NODELINK;
+
+ temp = &n->Leaf;
+ if( RecNo < 0 || RecNo > HeadNode.KeysPerNode)
+ return XB_INVALID_KEY;
+
+ p = temp->KeyRecs;
+ p+= RecNo * ( 8 + HeadNode.KeyLen );
+ dbf->xbase->PutLong( p, NodeNo );
+ return XB_NO_ERROR;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param RecNo
+ \param n
+ \param DbfNo
+*/
+xbShort xbNdx::PutDbfNo( xbShort RecNo, xbNdxNodeLink *n, xbLong DbfNo )
+{
+ /* This routine sets n node's dbf number */
+ xbNdxLeafNode *temp;
+ char *p;
+ if( !n )
+ return XB_INVALID_NODELINK;
+
+ temp = &n->Leaf;
+ if( RecNo < 0 || RecNo > (HeadNode.KeysPerNode-1))
+ return XB_INVALID_KEY;
+
+ p = temp->KeyRecs + 4;
+ p+= RecNo * ( 8 + HeadNode.KeyLen );
+ dbf->xbase->PutLong( p, DbfNo );
+ return XB_NO_ERROR;
+}
+/************************************************************************/
+//! Short description
+/*!
+ \param l
+ \param n
+*/
+xbShort xbNdx::PutLeafNode( xbLong l, xbNdxNodeLink *n )
+{
+ if ((_fseek(indexfp, (xbOffT)l * XB_NDX_NODE_SIZE , SEEK_SET)) != 0) {
+ fclose( indexfp );
+ return XB_SEEK_ERROR;
+ }
+ dbf->xbase->PutLong( Node, n->Leaf.NoOfKeysThisNode );
+
+ if(( fwrite( Node, 4, 1, indexfp )) != 1 ){
+ fclose( indexfp );
+ return XB_WRITE_ERROR;
+ }
+ if(( fwrite( &n->Leaf.KeyRecs, XB_NDX_NODE_SIZE-4, 1, indexfp )) != 1 ){
+ fclose( indexfp );
+ return XB_WRITE_ERROR;
+ }
+ return 0;
+}
+/************************************************************************/
+//! Short description
+/*!
+ \param Head
+ \param f
+ \param UpdateOnly
+*/
+xbShort xbNdx::PutHeadNode( xbNdxHeadNode * Head, FILE * f, xbShort UpdateOnly )
+{
+ char buf[4];
+
+ if(( _fseek( f, 0L, SEEK_SET )) != 0 ){
+ fclose( f );
+ return XB_SEEK_ERROR;
+ }
+ memset( buf, 0x00, 4 );
+ dbf->xbase->PutLong( buf, Head->StartNode );
+ if(( fwrite( &buf, 4, 1, f )) != 1 ){
+ fclose( f );
+ return XB_WRITE_ERROR;
+ }
+ memset( buf, 0x00, 4 );
+ dbf->xbase->PutLong( buf, Head->TotalNodes );
+ if(( fwrite( &buf, 4, 1, f )) != 1 ){
+ fclose( f );
+ return XB_WRITE_ERROR;
+ }
+ memset( buf, 0x00, 4 );
+ dbf->xbase->PutLong( buf, Head->NoOfKeys );
+ if(( fwrite( &buf, 4, 1, f )) != 1 ){
+ fclose( f );
+ return XB_WRITE_ERROR;
+ }
+ if( UpdateOnly )
+ return XB_NO_ERROR;
+ memset( buf, 0x00, 2 );
+ dbf->xbase->PutLong( buf, Head->KeyLen );
+ if(( fwrite( &buf, 2, 1, f )) != 1 ){
+ fclose( f );
+ return XB_WRITE_ERROR;
+ }
+ memset( buf, 0x00, 2 );
+ dbf->xbase->PutLong( buf, Head->KeysPerNode );
+ if(( fwrite( &buf, 2, 1, f )) != 1 ){
+ fclose( f );
+ return XB_WRITE_ERROR;
+ }
+ memset( buf, 0x00, 2 );
+ dbf->xbase->PutLong( buf, Head->KeyType );
+ if(( fwrite( &buf, 2, 1, f )) != 1 ){
+ fclose( f );
+ return XB_WRITE_ERROR;
+ }
+ memset( buf, 0x00, 4 );
+ dbf->xbase->PutLong( buf, Head->KeySize );
+ if(( fwrite( &buf, 4, 1, f )) != 1 ){
+ fclose( f );
+ return XB_WRITE_ERROR;
+ }
+ if(( fwrite( &Head->Unknown2, XB_NDX_NODE_SIZE - 22, 1, f )) != 1 ){
+ fclose( f );
+ return XB_WRITE_ERROR;
+ }
+ return 0;
+}
+/************************************************************************/
+//! Short description
+/*!
+ \param RecNo
+ \param n
+*/
+xbShort xbNdx::PutKeyData( xbShort RecNo, xbNdxNodeLink *n )
+{
+ /* This routine copies the KeyBuf data into xbNdxNodeLink n */
+ xbNdxLeafNode *temp;
+ char *p;
+ xbShort i;
+ if( !n )
+ return XB_INVALID_NODELINK;
+
+ temp = &n->Leaf;
+ if( RecNo < 0 || RecNo > (HeadNode.KeysPerNode-1))
+ return XB_INVALID_KEY;
+
+ p = temp->KeyRecs + 8;
+ p+= RecNo * ( 8 + HeadNode.KeyLen );
+ for( i = 0; i < HeadNode.KeyLen; i++ ) {
+ *p = KeyBuf[i];
+ p++;
+ }
+ return XB_NO_ERROR;
+}
+/************************************************************************/
+//! Short description
+/*!
+ \param n
+ \param pos
+ \param d
+ \param l
+ \param w
+*/
+xbShort xbNdx::PutKeyInNode( xbNdxNodeLink * n, xbShort pos, xbLong d,
+ xbLong l, xbShort w )
+{
+ xbShort i;
+
+ /* check the node */
+ if (!n)
+ return XB_INVALID_NODELINK;
+
+ if(pos < 0 || pos > HeadNode.KeysPerNode)
+ return XB_INVALID_RECORD;
+
+ if(n->Leaf.NoOfKeysThisNode >= HeadNode.KeysPerNode)
+ return XB_NODE_FULL;
+
+ /* if key movement, save the original key */
+ if( pos < n->Leaf.NoOfKeysThisNode )
+ memcpy( KeyBuf2, KeyBuf, HeadNode.KeyLen + 1);
+
+ /* if interior node, handle the right most left node no */
+ if( GetLeftNodeNo( 0, n ))
+ PutLeftNodeNo( n->Leaf.NoOfKeysThisNode+1, n,
+ GetLeftNodeNo( n->Leaf.NoOfKeysThisNode, n ));
+
+ for( i = n->Leaf.NoOfKeysThisNode; i > pos; i-- ){
+ memcpy( KeyBuf, GetKeyData(i-1,n), HeadNode.KeyLen );
+ PutKeyData( i, n );
+ PutDbfNo( i, n, GetDbfNo(i-1,n));
+ PutLeftNodeNo(i, n, GetLeftNodeNo(i-1,n));
+ }
+
+ /* put new key in node */
+ if( pos < n->Leaf.NoOfKeysThisNode )
+ memcpy( KeyBuf, KeyBuf2, HeadNode.KeyLen + 1);
+
+ PutKeyData( pos, n );
+ PutDbfNo( pos, n, d );
+ PutLeftNodeNo( pos, n, l );
+ n->Leaf.NoOfKeysThisNode++;
+ if( w )
+ return PutLeafNode( n->NodeNo, n );
+ else
+ return 0;
+}
+/************************************************************************/
+//! Short description
+/*!
+ \param curNode Current Node
+ \param newNode New Empty Node
+ \param pos Position of new key in current node
+ \param d dbf record number
+*/
+/* This function splits a full index leaf node into two parts
+ as of 2/13/04, this split logic was modified to cause an
+ even split in order to keep the index tree balanced
+
+*/
+
+xbShort xbNdx::SplitLeafNode( xbNdxNodeLink *curNode,
+ xbNdxNodeLink *newNode, xbShort pos, xbLong d )
+{
+ xbShort curNodeNewSize;
+ xbShort newNodeSize;
+ xbShort i,j,rc,startPos;
+
+ curNodeNewSize = (curNode->Leaf.NoOfKeysThisNode + 1) / 2;
+ newNodeSize = curNode->Leaf.NoOfKeysThisNode + 1 - curNodeNewSize;
+
+ /* save off the current key buffer */
+ memcpy( KeyBuf2, KeyBuf, HeadNode.KeyLen + 1 );
+ if( pos < curNodeNewSize ){ /* new key goes in current node */
+
+ /* copy second half of current node to beginning of new node */
+ /* memcpy( dst, src, len ); */
+ startPos = curNode->Leaf.NoOfKeysThisNode - newNodeSize;
+
+ for( i = startPos, j = 0; i < CurNode->Leaf.NoOfKeysThisNode; i++, j++){
+ memcpy( KeyBuf, GetKeyData( i, curNode ), HeadNode.KeyLen );
+ PutKeyData( j, newNode );
+ PutDbfNo( j, newNode, GetDbfNo( i, curNode ));
+ }
+
+ /* make a hole for the new key */
+ for( i = curNodeNewSize - 1; i > pos; i-- ){
+ memcpy( KeyBuf, GetKeyData( i-1, curNode ), HeadNode.KeyLen );
+ PutKeyData( i, curNode );
+ PutDbfNo( i, curNode, GetDbfNo( i-1, curNode ));
+ }
+
+ /* insert key appropriately */
+ memcpy( KeyBuf, KeyBuf2, HeadNode.KeyLen + 1 );
+ PutKeyData( pos, curNode );
+ PutDbfNo( pos, curNode, d );
+ }
+ else
+ {
+ pos -= curNodeNewSize;
+
+ /* do part one of the key migration */
+ if( pos ){
+
+/* was originally
+
+ startPos = curNode->Leaf.NoOfKeysThisNode - curNodeNewSize + 1;
+
+
+ then was changed to
+*/
+
+/*
+ if( ((pos + curNodeNewSize) == HeadNode.KeysPerNode) &&
+ (pos == newNodeSize) ){ // off the right end
+ startPos = curNode->Leaf.NoOfKeysThisNode - curNodeNewSize;
+ }
+ else
+ {
+ startPos = curNode->Leaf.NoOfKeysThisNode - curNodeNewSize + 1;
+ }
+
+*/
+
+/*
+ and this didn't work
+
+
+ startPos = curNode->Leaf.NoOfKeysThisNode - curNodeNewSize;
+
+*/
+
+ startPos = curNodeNewSize;
+ for( i = startPos, j = 0;
+ j < pos && i < curNode->Leaf.NoOfKeysThisNode; i++, j++){
+ memcpy( KeyBuf, GetKeyData( i, curNode ), HeadNode.KeyLen );
+ PutKeyData( j, newNode );
+ PutDbfNo( j, newNode, GetDbfNo( i, curNode ));
+ }
+ }
+
+ /* insert new key appropriately */
+ memcpy( KeyBuf, KeyBuf2, HeadNode.KeyLen + 1 );
+ PutKeyData( pos, newNode );
+ PutDbfNo( pos, newNode, d );
+
+ /* Load the remainder of the keys on the new node past the new key */
+ if( pos < (newNodeSize-1) ){
+
+// startPos = curNode->Leaf.NoOfKeysThisNode - curNodeNewSize + pos + 1;
+
+ startPos = curNodeNewSize + pos;
+ for( i = startPos, j = pos+1; j < newNodeSize; i++, j++){
+ memcpy( KeyBuf, GetKeyData( i, curNode ), HeadNode.KeyLen );
+ PutKeyData( j, newNode );
+ PutDbfNo( j, newNode, GetDbfNo( i, curNode ));
+ }
+ }
+ }
+
+ curNode->Leaf.NoOfKeysThisNode = curNodeNewSize;
+ newNode->Leaf.NoOfKeysThisNode = newNodeSize;
+
+ /* write the new nodes to disk */
+ if(( rc = PutLeafNode( curNode->NodeNo, curNode )) != 0 )
+ return rc;
+ if(( rc = PutLeafNode( newNode->NodeNo, newNode )) != 0 )
+ return rc;
+
+ return 0;
+}
+/************************************************************************/
+//! Short description
+/*!
+ \param nodeToSplit Interior node to split
+ \param newNode New empty node to use
+ \param dscNodeNo Descendant node number
+*/
+/* This routine splits an interior node */
+
+xbShort xbNdx::SplitINode( xbNdxNodeLink *nodeToSplit,
+ xbNdxNodeLink *newNode, xbLong dscNodeNo )
+{
+ xbShort i,j,rc;
+ xbNdxNodeLink * SaveNodeChain;
+ xbNdxNodeLink * SaveCurNode;
+ xbLong newNodeToSplitSize;
+ xbLong newNodeSize;
+ xbShort pos, startPos, offset;
+
+ newNodeToSplitSize = (nodeToSplit->Leaf.NoOfKeysThisNode + 2 ) / 2;
+ newNodeSize = nodeToSplit->Leaf.NoOfKeysThisNode + 2 - newNodeToSplitSize;
+ pos = nodeToSplit->CurKeyNo;
+
+ if( pos < (newNodeToSplitSize-1) ){
+ /* copy second half of nodeToSplit to newNode */
+ startPos = nodeToSplit->Leaf.NoOfKeysThisNode - newNodeSize +1;
+ for(i=startPos, j=0; i <= nodeToSplit->Leaf.NoOfKeysThisNode; i++, j++ ){
+ if( i < nodeToSplit->Leaf.NoOfKeysThisNode ){
+ memcpy( KeyBuf, GetKeyData( i, nodeToSplit ), HeadNode.KeyLen );
+ PutKeyData( j, newNode );
+ }
+ PutLeftNodeNo( j, newNode, GetLeftNodeNo( i, nodeToSplit ));
+ }
+
+ /* make a hole for the new key */
+ for( i = newNodeToSplitSize; i > pos; i-- ){
+ memcpy( KeyBuf, GetKeyData( i-1, nodeToSplit ), HeadNode.KeyLen );
+ PutKeyData( i, nodeToSplit );
+ PutLeftNodeNo( i, nodeToSplit, GetLeftNodeNo( i-1, nodeToSplit ));
+ }
+
+ /* load new high key value into current position on nodeToSplit */
+ if( pos < (newNodeToSplitSize - 1 )){
+ SaveNodeChain = NodeChain;
+ NodeChain = NULL;
+ SaveCurNode = CurNode;
+ GetLastKey( GetLeftNodeNo( pos, nodeToSplit ), 0 );
+ memcpy( KeyBuf, GetKeyData( CurNode->CurKeyNo, CurNode ), HeadNode.KeyLen );
+ PutKeyData( pos, nodeToSplit );
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = SaveNodeChain;
+ CurNode = SaveCurNode;
+ }
+ PutLeftNodeNo( pos+1, nodeToSplit, dscNodeNo );
+ }
+
+/*************/
+/* part b */
+/*************/
+
+ else
+ {
+ pos -= newNodeToSplitSize-1;
+ /* do part one of the key migration */
+ if( pos ){
+// startPos = nodeToSplit->Leaf.NoOfKeysThisNode - newNodeToSplitSize + 2;
+
+// 5/29/04 gak changed the following line for index probs
+// startPos = nodeToSplit->Leaf.NoOfKeysThisNode - newNodeToSplitSize + 1;
+
+ if( HeadNode.KeysPerNode % 2 )
+ offset = 2;
+ else
+ offset = 1;
+
+ startPos = nodeToSplit->Leaf.NoOfKeysThisNode - newNodeToSplitSize + offset;
+
+ for( i = startPos, j = 0; j < pos; i++, j++ ){
+ if( i < nodeToSplit->Leaf.NoOfKeysThisNode && j < (pos-1)){
+ memcpy( KeyBuf, GetKeyData( i, nodeToSplit ), HeadNode.KeyLen );
+ PutKeyData( j, newNode );
+ }
+ else
+ {
+ SaveNodeChain = NodeChain;
+ NodeChain = NULL;
+ SaveCurNode = CurNode;
+ GetLastKey( GetLeftNodeNo( i, nodeToSplit ), 0 );
+ memcpy(KeyBuf,GetKeyData(CurNode->CurKeyNo,CurNode),HeadNode.KeyLen);
+ PutKeyData( j, newNode );
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = SaveNodeChain;
+ CurNode = SaveCurNode;
+ }
+ PutLeftNodeNo( j, newNode, GetLeftNodeNo( i, nodeToSplit ));
+ }
+ }
+
+ /* insert new key appropriately */
+ if( pos < (newNodeSize - 1)){
+ SaveNodeChain = NodeChain;
+ NodeChain = NULL;
+ SaveCurNode = CurNode;
+ GetLastKey( dscNodeNo, 0 );
+ memcpy(KeyBuf,GetKeyData(CurNode->CurKeyNo,CurNode),HeadNode.KeyLen);
+ PutKeyData( pos, newNode );
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = SaveNodeChain;
+ CurNode = SaveCurNode;
+ }
+ PutLeftNodeNo( pos, newNode, dscNodeNo );
+
+ /* load remainder of the keys */
+ if( pos < (newNodeSize - 1)){
+
+
+// startPos=nodeToSplit->Leaf.NoOfKeysThisNode-newNodeToSplitSize+pos+2;
+// 5/29/04 gak changed the following line for index probs
+
+ startPos=nodeToSplit->Leaf.NoOfKeysThisNode-newNodeToSplitSize+pos+offset;
+
+ for( i = startPos, j = pos+1; j < newNodeSize; i++, j++ ){
+ if( i < nodeToSplit->Leaf.NoOfKeysThisNode ){
+ memcpy( KeyBuf, GetKeyData( i, nodeToSplit ), HeadNode.KeyLen );
+ PutKeyData( j, newNode );
+ }
+ PutLeftNodeNo( j, newNode, GetLeftNodeNo( i, nodeToSplit ));
+ }
+ }
+ }
+
+ nodeToSplit->Leaf.NoOfKeysThisNode = newNodeToSplitSize - 1;
+ newNode->Leaf.NoOfKeysThisNode = newNodeSize - 1;
+
+ if((rc = PutLeafNode( nodeToSplit->NodeNo, nodeToSplit )) != 0) return rc;
+ if((rc = PutLeafNode( newNode->NodeNo, newNode )) != 0) return rc;
+ return 0;
+}
+/************************************************************************/
+//! Short description
+/*!
+ \param RecBufSw
+ \param KeyBufSw
+*/
+xbShort xbNdx::CreateKey( xbShort RecBufSw, xbShort KeyBufSw )
+{
+ /* RecBufSw 0 Use RecBuf */
+ /* 1 Use RecBuf2 */
+ /* KeyBufSw 0 Use KeyBuf */
+ /* 1 Use KeyBuf2 */
+
+ xbShort rc;
+ xbExpNode * TempNode;
+
+ if(( rc = IxExp->ProcessExpression( RecBufSw )) != XB_NO_ERROR )
+ return rc;
+ TempNode = (xbExpNode *) IxExp->Pop();
+ if( !TempNode )
+ return XB_INVALID_KEY;
+
+ if( KeyBufSw ){
+ if( HeadNode.KeyType == 1 ) /* numeric key */
+ dbf->xbase->PutDouble( KeyBuf2, TempNode->DoubResult );
+ else{ /* character key */
+ memset( KeyBuf2, 0x00, HeadNode.KeyLen + 1 );
+ memcpy( KeyBuf2, TempNode->StringResult, XB_MIN(HeadNode.KeyLen + 1, TempNode->DataLen) );
+ }
+ } else {
+ if( HeadNode.KeyType == 1 ) /* numeric key */
+ dbf->xbase->PutDouble( KeyBuf, TempNode->DoubResult );
+ else { /* character key */
+ memset( KeyBuf, 0x00, HeadNode.KeyLen + 1 );
+ memcpy( KeyBuf, TempNode->StringResult.c_str(), XB_MIN(HeadNode.KeyLen + 1, TempNode->DataLen) );
+ }
+ }
+// if( !TempNode->InTree ) dbf->xbase->FreeExpNode( TempNode );
+ if( !TempNode->InTree ) delete TempNode;
+ return 0;
+}
+/************************************************************************/
+//! Short description
+/*!
+ \param key
+*/
+xbShort
+xbNdx::GetCurrentKey(char *key)
+{
+ CreateKey(0, 0);
+ if(HeadNode.KeyType == 1)
+ memcpy(key, KeyBuf, 8);
+ else
+ memcpy(key, KeyBuf, HeadNode.KeyLen + 1);
+ return 0;
+}
+/************************************************************************/
+//! Short description
+/*!
+ \param DbfRec
+*/
+xbShort xbNdx::AddKey( xbLong DbfRec )
+{
+ /* This routine assumes KeyBuf contains the contents of the index to key */
+
+ char *p;
+ xbShort i,rc;
+ xbNdxNodeLink * TempNode;
+ xbNdxNodeLink * Tparent;
+ xbLong TempNodeNo; /* new, unattached leaf node no */
+ xbNdxNodeLink * SaveNodeChain;
+ xbNdxNodeLink * SaveCurNode;
+
+ /* find node key belongs in */
+ rc = FindKey( KeyBuf, HeadNode.KeyLen, 0 );
+ if( rc == XB_FOUND && HeadNode.Unique )
+ return XB_KEY_NOT_UNIQUE;
+
+ if( CurNode->Leaf.NoOfKeysThisNode > 0 && rc == XB_FOUND ){
+ rc = 0;
+ while( rc == 0 ){
+ if(( p = GetKeyData( CurNode->CurKeyNo, CurNode )) == NULL )
+ rc = -1;
+ else {
+ rc = CompareKey( KeyBuf, p, HeadNode.KeyLen );
+ if( rc == 0 && DbfRec >= GetDbfNo( CurNode->CurKeyNo, CurNode )){
+ if((rc = GetNextKey(0)) == XB_EOF) {
+ if((rc = GetLastKey(0, 0)) != XB_NO_ERROR)
+ return rc;
+ CurNode->CurKeyNo++;
+ }
+ }
+ else
+ rc = -1;
+ }
+ }
+ }
+
+ /* update header node */
+ HeadNode.NoOfKeys++;
+ /************************************************/
+ /* section A - if room in node, add key to node */
+ /************************************************/
+
+ if( CurNode->Leaf.NoOfKeysThisNode < HeadNode.KeysPerNode ){
+ if(( rc = PutKeyInNode( CurNode,CurNode->CurKeyNo,DbfRec,0L,1)) != 0)
+ return rc;
+ if(( rc = PutHeadNode( &HeadNode, indexfp, 1 )) != 0)
+ return rc;
+ return XB_NO_ERROR;
+ }
+
+ /***********************************************************************/
+ /* section B - split leaf node if full and put key in correct position */
+ /***********************************************************************/
+
+ TempNode = GetNodeMemory();
+ TempNode->NodeNo = HeadNode.TotalNodes++;
+ rc = SplitLeafNode( CurNode, TempNode, CurNode->CurKeyNo, DbfRec );
+ if( rc )
+ return rc;
+
+ TempNodeNo = TempNode->NodeNo;
+ ReleaseNodeMemory( TempNode );
+
+ /*****************************************************/
+ /* section C go up tree splitting nodes as necessary */
+ /*****************************************************/
+ Tparent = CurNode->PrevNode;
+
+ while( Tparent &&
+ Tparent->Leaf.NoOfKeysThisNode >= HeadNode.KeysPerNode-1) {
+
+ TempNode = GetNodeMemory();
+
+ if( !TempNode )
+ return XB_NO_MEMORY;
+ TempNode->NodeNo = HeadNode.TotalNodes++;
+
+ rc = SplitINode( Tparent, TempNode, TempNodeNo );
+ if( rc ) return rc;
+
+ TempNodeNo = TempNode->NodeNo;
+ ReleaseNodeMemory( TempNode );
+ ReleaseNodeMemory( CurNode );
+ CurNode = Tparent;
+ CurNode->NextNode = NULL;
+ Tparent = CurNode->PrevNode;
+ }
+
+ /************************************************************/
+ /* Section D if CurNode is split root, create new root */
+ /************************************************************/
+
+ /* at this point
+ CurNode = The node that was just split
+ TempNodeNo = The new node split off from CurNode */
+
+ if(CurNode->NodeNo == HeadNode.StartNode ){
+ TempNode = GetNodeMemory();
+ if( !TempNode )
+ return XB_NO_MEMORY;
+
+ SaveNodeChain = NodeChain;
+ NodeChain = NULL;
+ SaveCurNode = CurNode;
+ GetLastKey( CurNode->NodeNo, 0 );
+ memcpy( KeyBuf, GetKeyData( CurNode->CurKeyNo,CurNode ),HeadNode.KeyLen );
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = SaveNodeChain;
+ CurNode = SaveCurNode;
+ PutKeyData( 0, TempNode );
+ PutLeftNodeNo( 0, TempNode, CurNode->NodeNo );
+ PutLeftNodeNo( 1, TempNode, TempNodeNo );
+ TempNode->NodeNo = HeadNode.TotalNodes++;
+ TempNode->Leaf.NoOfKeysThisNode++;
+ HeadNode.StartNode = TempNode->NodeNo;
+ rc = PutLeafNode( TempNode->NodeNo, TempNode );
+ if( rc ) return rc;
+ rc = PutHeadNode( &HeadNode, indexfp, 1 );
+ if( rc ) return rc;
+ ReleaseNodeMemory( TempNode );
+ return XB_NO_ERROR;
+ }
+ /**********************************/
+ /* Section E make room in parent */
+ /**********************************/
+ for( i = Tparent->Leaf.NoOfKeysThisNode; i > Tparent->CurKeyNo; i-- ){
+ memcpy( KeyBuf, GetKeyData( i-1, Tparent ), HeadNode.KeyLen );
+ PutKeyData( i, Tparent );
+ PutLeftNodeNo( i+1, Tparent, GetLeftNodeNo( i, Tparent ));
+ }
+
+ /* put key in parent */
+ SaveNodeChain = NodeChain;
+ NodeChain = NULL;
+ SaveCurNode = CurNode;
+ GetLastKey( CurNode->NodeNo, 0 );
+ memcpy( KeyBuf,GetKeyData( CurNode->CurKeyNo, CurNode ), HeadNode.KeyLen );
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = SaveNodeChain;
+ CurNode = SaveCurNode;
+ PutKeyData( i, Tparent );
+ PutLeftNodeNo( i+1, Tparent, TempNodeNo );
+ Tparent->Leaf.NoOfKeysThisNode++;
+ rc = PutLeafNode( Tparent->NodeNo, Tparent );
+ if( rc ) return rc;
+ rc = PutHeadNode( &HeadNode, indexfp, 1 );
+ if( rc ) return rc;
+ return XB_NO_ERROR;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param pos
+ \param n
+*/
+xbShort xbNdx::RemoveKeyFromNode( xbShort pos, xbNdxNodeLink *n )
+{
+ xbShort i;
+ /* check the node */
+ if( !n )
+ return XB_INVALID_NODELINK;
+
+ if( pos < 0 || pos > HeadNode.KeysPerNode )
+ return XB_INVALID_KEY;
+
+ for( i = pos; i < n->Leaf.NoOfKeysThisNode-1; i++ ){
+ memcpy( KeyBuf, GetKeyData( i+1, n), HeadNode.KeyLen );
+ PutKeyData( i, n );
+ PutDbfNo( i, n, GetDbfNo( i+1, n ));
+ PutLeftNodeNo( i, n, GetLeftNodeNo( i+1, n ));
+ }
+ PutLeftNodeNo( i, n, GetLeftNodeNo( i+1, n ));
+ n->Leaf.NoOfKeysThisNode--;
+ /* if last key was deleted, decrement CurKeyNo */
+ if( n->CurKeyNo > n->Leaf.NoOfKeysThisNode )
+ n->CurKeyNo--;
+ return PutLeafNode( n->NodeNo, n );
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param n
+*/
+xbShort xbNdx::UpdateParentKey( xbNdxNodeLink * n )
+{
+/* this routine goes backwards thru the node chain looking for a parent
+ node to update */
+
+ xbNdxNodeLink * TempNode;
+ if( !n )
+ return XB_INVALID_NODELINK;
+
+ if( !GetDbfNo( 0, n ))
+ return XB_NOT_LEAFNODE;
+
+ TempNode = n->PrevNode;
+ while( TempNode ){
+ if( TempNode->CurKeyNo < TempNode->Leaf.NoOfKeysThisNode ){
+ memcpy(KeyBuf,GetKeyData(n->Leaf.NoOfKeysThisNode-1,n),HeadNode.KeyLen);
+ PutKeyData( TempNode->CurKeyNo, TempNode );
+ return PutLeafNode( TempNode->NodeNo, TempNode );
+ }
+ TempNode = TempNode->PrevNode;
+ }
+ return XB_NO_ERROR;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param n
+*/
+/* This routine queues up a list of nodes which have been emptied */
+void xbNdx::UpdateDeleteList( xbNdxNodeLink *n )
+{
+ n->NextNode = DeleteChain;
+ DeleteChain = n;
+}
+/***********************************************************************/
+//! Short description
+/*!
+*/
+/* Delete nodes from the node list - for now we leave the empty nodes */
+/* dangling in the file. Eventually we will remove nodes from the file */
+
+void xbNdx::ProcessDeleteList( void )
+{
+ if( DeleteChain ){
+ ReleaseNodeMemory( DeleteChain );
+ DeleteChain = NULL;
+ }
+}
+/***********************************************************************/
+//! Short description
+/*!
+*/
+xbShort xbNdx::KeyWasChanged( void )
+{
+ CreateKey( 0, 0 ); /* use KeyBuf, RecBuf */
+ CreateKey( 1, 1 ); /* use KeyBuf2, RecBuf2 */
+ if( CompareKey( KeyBuf, KeyBuf2, HeadNode.KeyLen ) != 0 )
+ return 1;
+ else
+ return 0;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param n
+*/
+xbNdxNodeLink * xbNdx::LeftSiblingHasSpace( xbNdxNodeLink * n )
+{
+ xbNdxNodeLink * TempNode;
+ xbNdxNodeLink * SaveCurNode;
+
+ /* returns a Nodelink to xbNdxNodeLink n's left sibling if it has space */
+ /* if left most node in parent return NULL */
+ if( n->PrevNode->CurKeyNo == 0 )
+ return NULL;
+
+ SaveCurNode = CurNode;
+ GetLeafNode( GetLeftNodeNo( n->PrevNode->CurKeyNo-1, n->PrevNode ), 2 );
+ if( CurNode->Leaf.NoOfKeysThisNode < HeadNode.KeysPerNode ){
+ TempNode = CurNode;
+ CurNode = SaveCurNode;
+ TempNode->PrevNode = n->PrevNode;
+ return TempNode;
+ } else { /* node is already full */
+ ReleaseNodeMemory( CurNode );
+ CurNode = SaveCurNode;
+ return NULL;
+ }
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param n
+*/
+xbNdxNodeLink * xbNdx::RightSiblingHasSpace( xbNdxNodeLink * n )
+{
+ /* returns a Nodelink to xbNdxNodeLink n's right sibling if it has space */
+
+ xbNdxNodeLink * TempNode;
+ xbNdxNodeLink * SaveCurNode;
+
+ /* if left most node in parent return NULL */
+ if( n->PrevNode->CurKeyNo >= n->PrevNode->Leaf.NoOfKeysThisNode )
+ return NULL;
+ SaveCurNode = CurNode;
+ /* point curnode to right sib*/
+ GetLeafNode( GetLeftNodeNo( n->PrevNode->CurKeyNo+1, n->PrevNode ), 2 );
+ if( CurNode->Leaf.NoOfKeysThisNode < HeadNode.KeysPerNode ){
+ TempNode = CurNode;
+ CurNode = SaveCurNode;
+ TempNode->PrevNode = n->PrevNode;
+ return TempNode;
+ } else { /* node is already full */
+ ReleaseNodeMemory( CurNode );
+ CurNode = SaveCurNode;
+ return NULL;
+ }
+}
+/*************************************************************************/
+//! Short description
+/*!
+ \param n
+ \param Right
+*/
+xbShort xbNdx::MoveToRightNode( xbNdxNodeLink * n, xbNdxNodeLink * Right )
+{
+ xbShort j;
+ xbNdxNodeLink * TempNode;
+ xbNdxNodeLink * SaveCurNode;
+ xbNdxNodeLink * SaveNodeChain;
+
+ if( n->CurKeyNo == 0 ){
+ j = 1;
+ SaveNodeChain = NodeChain;
+ SaveCurNode = CurNode;
+ NodeChain = NULL;
+ GetLastKey( n->NodeNo, 0 );
+ memcpy( KeyBuf, GetKeyData( CurNode->CurKeyNo, CurNode),HeadNode.KeyLen);
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = SaveNodeChain;
+ CurNode = SaveCurNode;
+ } else {
+ j = 0;
+ memcpy( KeyBuf, GetKeyData( j, n ), HeadNode.KeyLen);
+ }
+ PutKeyInNode( Right, 0, 0L, GetLeftNodeNo( j, n ), 1 );
+ ReleaseNodeMemory( Right );
+ TempNode = n;
+ CurNode = n->PrevNode;
+ n = n->PrevNode;
+ n->NextNode = NULL;
+ UpdateDeleteList( TempNode );
+ DeleteSibling( n );
+ return XB_NO_ERROR;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param n
+ \param Left
+*/
+xbShort xbNdx::MoveToLeftNode( xbNdxNodeLink * n, xbNdxNodeLink * Left )
+{
+ xbShort j, rc;
+ xbNdxNodeLink * SaveNodeChain;
+ xbNdxNodeLink * TempNode;
+
+ if( n->CurKeyNo == 0 )
+ j = 1;
+ else
+ j = 0;
+
+ /* save the original node chain */
+ SaveNodeChain = NodeChain;
+ NodeChain = NULL;
+
+ /* determine new right most key for left node */
+ GetLastKey( Left->NodeNo, 0 );
+ memcpy( KeyBuf, GetKeyData( CurNode->CurKeyNo, CurNode ), HeadNode.KeyLen);
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = NULL; /* for next GetLastKey */
+ PutKeyData( Left->Leaf.NoOfKeysThisNode, Left);
+ PutLeftNodeNo( Left->Leaf.NoOfKeysThisNode+1, Left, GetLeftNodeNo( j,n ));
+ Left->Leaf.NoOfKeysThisNode++;
+ Left->CurKeyNo = Left->Leaf.NoOfKeysThisNode;
+ if(( rc = PutLeafNode( Left->NodeNo, Left )) != 0 )
+ return rc;
+ n->PrevNode->NextNode = NULL;
+ UpdateDeleteList( n );
+
+ /* get the new right most key for left to update parents */
+ GetLastKey( Left->NodeNo, 0 );
+
+ /* assemble the chain */
+ TempNode = Left->PrevNode;
+ TempNode->CurKeyNo--;
+ NodeChain->PrevNode = Left->PrevNode;
+ UpdateParentKey( CurNode );
+ ReleaseNodeMemory( NodeChain );
+ ReleaseNodeMemory( Left );
+ CurNode = TempNode;
+ NodeChain = SaveNodeChain;
+ TempNode->CurKeyNo++;
+ DeleteSibling( TempNode );
+ return XB_NO_ERROR;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param n
+*/
+xbShort xbNdx::DeleteSibling( xbNdxNodeLink * n )
+{
+ xbNdxNodeLink * Left;
+ xbNdxNodeLink * Right;
+ xbNdxNodeLink * SaveCurNode;
+ xbNdxNodeLink * SaveNodeChain;
+ xbNdxNodeLink * TempNode;
+ xbShort rc;
+
+ /* this routine deletes sibling CurRecNo out of xbNodeLink n */
+ if( n->Leaf.NoOfKeysThisNode > 1 ){
+ RemoveKeyFromNode( n->CurKeyNo, n );
+ if( n->CurKeyNo == n->Leaf.NoOfKeysThisNode ){
+ SaveNodeChain = NodeChain;
+ SaveCurNode = CurNode;
+ NodeChain = NULL;
+ GetLastKey( n->NodeNo, 0 );
+ /* assemble the node chain */
+ TempNode = NodeChain->NextNode;
+ NodeChain->NextNode = NULL;
+ ReleaseNodeMemory( NodeChain );
+ TempNode->PrevNode = n;
+ UpdateParentKey( CurNode );
+ /* take it back apart */
+ ReleaseNodeMemory( TempNode );
+ NodeChain = SaveNodeChain;
+ CurNode = SaveCurNode;
+ }
+ } else if( n->NodeNo == HeadNode.StartNode ) {
+ /* get here if root node and only one child remains */
+ /* make remaining node the new root */
+ if( n->CurKeyNo == 0 )
+ HeadNode.StartNode = GetLeftNodeNo( 1, n );
+ else
+ HeadNode.StartNode = GetLeftNodeNo( 0, n );
+ UpdateDeleteList( n );
+ NodeChain = NULL;
+ CurNode = NULL;
+ }
+ else if (( Left = LeftSiblingHasSpace( n )) != NULL )
+ return MoveToLeftNode( n, Left );
+ else if (( Right = RightSiblingHasSpace( n )) != NULL )
+ return MoveToRightNode( n, Right );
+ /* else if left sibling exists */
+ else if( n->PrevNode->CurKeyNo > 0 ) {
+ /* move right branch from left sibling to this node */
+ SaveCurNode = CurNode;
+ SaveNodeChain = NodeChain;
+ NodeChain = NULL;
+ GetLeafNode( GetLeftNodeNo( n->PrevNode->CurKeyNo-1, n->PrevNode ), 2 );
+ Left = CurNode;
+ Left->PrevNode = SaveCurNode->PrevNode;
+ GetLastKey( Left->NodeNo, 0 );
+ strncpy( KeyBuf, GetKeyData( CurNode->CurKeyNo,CurNode),HeadNode.KeyLen );
+ if( n->CurKeyNo == 1 )
+ PutLeftNodeNo( 1, n, GetLeftNodeNo( 0, n ));
+ PutKeyData( 0, n );
+ PutLeftNodeNo( 0, n, GetLeftNodeNo( Left->Leaf.NoOfKeysThisNode, Left ));
+ if(( rc = PutLeafNode( n->NodeNo, n )) != XB_NO_ERROR ) return rc;
+ SaveCurNode = n->PrevNode;
+ SaveCurNode->NextNode = NULL;
+ ReleaseNodeMemory( n );
+ Left->Leaf.NoOfKeysThisNode--;
+ if(( rc = PutLeafNode( Left->NodeNo, Left )) != XB_NO_ERROR ) return rc;
+ /* rebuild left side of tree */
+ GetLastKey( Left->NodeNo, 0 );
+ NodeChain->PrevNode = SaveCurNode;
+ SaveCurNode->CurKeyNo--;
+ UpdateParentKey( CurNode );
+ ReleaseNodeMemory( NodeChain );
+ ReleaseNodeMemory( Left );
+ CurNode = SaveCurNode;
+ NodeChain = SaveNodeChain;
+ }
+ /* right sibling must exist */
+ else if( n->PrevNode->CurKeyNo <= n->PrevNode->Leaf.NoOfKeysThisNode ){
+ /* move left branch from left sibling to this node */
+ SaveCurNode = CurNode;
+ SaveNodeChain = NodeChain;
+ NodeChain = NULL;
+
+ /* move the left node number one to the left if necessary */
+ if( n->CurKeyNo == 0 ){
+ PutLeftNodeNo( 0, n, GetLeftNodeNo( 1, n ));
+ GetLastKey( GetLeftNodeNo( 0, n ), 0 );
+ memcpy(KeyBuf,GetKeyData(CurNode->CurKeyNo,CurNode),HeadNode.KeyLen);
+ PutKeyData( 0, n );
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = NULL;
+ }
+ GetLeafNode( GetLeftNodeNo( n->PrevNode->CurKeyNo+1, n->PrevNode ), 2 );
+ /* put leftmost node number from right node in this node */
+ PutLeftNodeNo( 1, n, GetLeftNodeNo( 0, CurNode ));
+ if(( rc = PutLeafNode( n->NodeNo, n )) != XB_NO_ERROR ) return rc;
+
+ /* remove the key from the right node */
+ RemoveKeyFromNode( 0, CurNode );
+ if(( rc = PutLeafNode( CurNode->NodeNo, CurNode )) != XB_NO_ERROR )
+ return rc;
+ ReleaseNodeMemory( CurNode );
+
+ /* update new parent key value */
+ GetLastKey( n->NodeNo, 0 );
+ NodeChain->PrevNode = n->PrevNode;
+ UpdateParentKey( CurNode );
+ ReleaseNodeMemory( NodeChain );
+ NodeChain = SaveNodeChain;
+ CurNode = SaveCurNode;
+ } else {
+ /* this should never be true-but could be if 100 byte limit is ignored*/
+ std::cout << "Fatal index error" << std::endl;
+ exit(0);
+ }
+ return XB_NO_ERROR;
+}
+/***********************************************************************/
+//! Short description
+/*!
+ \param DbfRec
+*/
+xbShort xbNdx::DeleteKey( xbLong DbfRec )
+{
+/* this routine assumes the key to be deleted is in KeyBuf */
+
+ xbNdxNodeLink * TempNode;
+ xbShort rc;
+
+#if 0
+ // Not sure why this check is here, but it prevents numeric keys
+ // from being deleted (and thus index updates will also fail).
+ // I have removed it for now. Derry Bryson
+ if( HeadNode.KeyType != 0x00 )
+ xb_error(XB_INVALID_KEY_TYPE);
+#endif
+
+ if(( rc = FindKey( KeyBuf, DbfRec )) != XB_FOUND )
+ return rc;
+
+ /* found the record to delete at this point */
+ HeadNode.NoOfKeys--;
+
+ /* delete the key from the node */
+ if(( rc = RemoveKeyFromNode( CurNode->CurKeyNo, CurNode )) != 0 )
+ return rc;
+
+ /* if root node, we are done */
+ if( !( CurNode->NodeNo == HeadNode.StartNode )){
+ /* if leaf node now empty */
+ if( CurNode->Leaf.NoOfKeysThisNode == 0 ){
+ TempNode = CurNode->PrevNode;
+ TempNode->NextNode = NULL;
+ UpdateDeleteList( CurNode );
+ CurNode = TempNode;
+ DeleteSibling( CurNode );
+ ProcessDeleteList();
+ }
+
+ /* if last key of leaf updated, update key in parent node */
+ /* this logic updates the correct parent key */
+
+ else if( CurNode->CurKeyNo == CurNode->Leaf.NoOfKeysThisNode )
+ UpdateParentKey( CurNode );
+ }
+
+ if(CurNode)
+ CurDbfRec = GetDbfNo( CurNode->CurKeyNo, CurNode );
+ else
+ CurDbfRec = 0;
+
+ if(( rc = PutHeadNode( &HeadNode, indexfp, 1 )) != 0 )
+ return rc;
+ return XB_NO_ERROR;
+}
+/************************************************************************/
+//! Short description
+/*!
+ \param option
+*/
+#ifdef XBASE_DEBUG
+xbShort xbNdx::CheckIndexIntegrity( const xbShort option )
+{
+ /* if option = 1, print out some stats */
+ xbShort rc;
+ xbLong ctr = 1L;
+ while( ctr <= dbf->NoOfRecords()){
+ if( option ) std::cout << "Checking Record " << ctr << std::endl;
+ if(( rc = dbf->GetRecord(ctr++)) != XB_NO_ERROR )
+ return rc;
+ if(!dbf->RecordDeleted()){
+ CreateKey( 0, 0 );
+ rc = FindKey( KeyBuf, dbf->GetCurRecNo());
+ if( rc != XB_FOUND ){
+ if( option ){
+ std::cout << "Record number " << dbf->GetCurRecNo()
+ << " Not Found" << std::endl;
+ std::cout << "Key = " << KeyBuf << std::endl;
+ }
+ return rc;
+ }
+ }
+ }
+ if( option )
+ std::cout << std::endl << "Total records checked = "
+ << ctr - 1 << std::endl;
+ return XB_NO_ERROR;
+}
+#endif
+/***********************************************************************/
+//! Short description
+/*!
+ \param statusFunc
+*/
+xbShort xbNdx::ReIndex(void (*statusFunc)(xbLong itemNum, xbLong numItems))
+{
+ /* this method assumes the index has been locked in exclusive mode */
+ xbLong l;
+ xbShort rc, i, saveAutoLock;
+ xbNdxHeadNode TempHead;
+ FILE *t;
+ xbString TempName;
+ memcpy( &TempHead, &HeadNode, sizeof( struct xbNdxHeadNode ));
+ TempHead.NoOfKeys = 1L;
+ TempHead.TotalNodes = 2L;
+ TempHead.StartNode = 1L;
+ rc = dbf->xbase->DirectoryExistsInName( GetFileName() );
+ if( rc ){
+ TempName.assign(GetFileName(), 0, rc);
+ TempName += "TEMPFILE.NDX";
+ } else
+ TempName = "TEMPFILE.NDX";
+
+ if(( t = fopen( TempName, "w+b" )) == NULL )
+ return XB_OPEN_ERROR;
+
+ if(( rc = PutHeadNode( &TempHead, t, 0 )) != 0 ){
+ fclose( t );
+ remove(TempName);
+ return rc;
+ }
+
+ for( i = 0; i < XB_NDX_NODE_SIZE; i++ ){
+ if(( fwrite( "\x00", 1, 1, t )) != 1 ){
+ fclose( t );
+ remove(TempName);
+ return XB_WRITE_ERROR;
+ }
+ }
+ if( fclose( indexfp ) != 0 )
+ return XB_CLOSE_ERROR;
+ if( fclose( t ) != 0 )
+ return XB_CLOSE_ERROR;
+ if( remove( GetFileName() ) != 0 )
+ return XB_CLOSE_ERROR;
+ if( rename(TempName, GetFileName() ) != 0 )
+ return XB_WRITE_ERROR;
+ if(( indexfp = fopen( GetFileName(), "r+b" )) == NULL )
+ return XB_OPEN_ERROR;
+
+ saveAutoLock = dbf->GetAutoLock();
+ dbf->AutoLockOff();
+ for( l = 1; l <= dbf->PhysicalNoOfRecords(); l++ ){
+ if(statusFunc && (l == 1 || !(l % 100) || l == dbf->PhysicalNoOfRecords()))
+ statusFunc(l, dbf->PhysicalNoOfRecords());
+ if(( rc = dbf->GetRecord(l)) != XB_NO_ERROR ){
+ if(saveAutoLock)
+ dbf->AutoLockOn();
+ return rc;
+ }
+
+ if(!dbf->GetRealDelete() || !dbf->RecordDeleted()){
+ /* Create the key */
+ CreateKey( 0, 0 );
+ /* add key to index */
+ if(( rc = AddKey( l )) != XB_NO_ERROR ){
+ if(saveAutoLock)
+ dbf->AutoLockOn();
+ return rc;
+ }
+ }
+ }
+ return rc;
+}
+
+/***********************************************************************/
+//! Short description
+/*!
+ \param size
+*/
+void xbNdx::SetNodeSize(xbShort size)
+{
+#ifdef XB_VAR_NODESIZE
+ if(size >= XB_DEFAULT_NDX_NODE_SIZE)
+ {
+ if(size % XB_NDX_NODE_MULTIPLE)
+ NodeSize = ((size + XB_NDX_NODE_MULTIPLE) / XB_NDX_NODE_MULTIPLE) *
+ XB_NDX_NODE_MULTIPLE;
+ else
+ NodeSize = size;
+ }
+ else
+ NodeSize = XB_DEFAULT_NDX_NODE_SIZE;
+#endif
+}
+
+/***********************************************************************/
+//! Short description
+/*!
+ \param buf
+ \param len
+*/
+void xbNdx::GetExpression(char *buf, int len)
+{
+ memcpy(buf, HeadNode.KeyExpression,
+ len < XB_NDX_NODE_SIZE ? len : XB_NDX_NODE_SIZE - XB_NDX_NODE_BASESIZE);
+}
+
+const char* xbNdx::GetExtWithDot(bool lower)
+{
+ return lower? ".ndx": ".NDX";
+}
+
+xbUShort xbNdx::GetKeyLen()
+{
+ return HeadNode.KeyLen;
+}
+
+const char* xbNdx::GetKeyExpression()
+{
+ return HeadNode.KeyExpression;
+}
+
+void xbNdx::FreeNodesMemory()
+{
+ ReleaseNodeMemory(NodeChain, true);
+ NodeChain = 0;
+// ReleaseNodeMemory(CloneChain, true);
+// CloneChain = 0;
+ ReleaseNodeMemory(FreeNodeChain, true);
+ FreeNodeChain = 0;
+ ReleaseNodeMemory(DeleteChain, true);
+ DeleteChain = 0;
+}
+
+#endif /* XB_INDEX_NDX */
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-30 09:31:16 +0000