diff options
Diffstat (limited to 'xbase64/xbndx.cpp')
| -rwxr-xr-x | xbase64/xbndx.cpp | 2402 |
1 files changed, 0 insertions, 2402 deletions
diff --git a/xbase64/xbndx.cpp b/xbase64/xbndx.cpp deleted file mode 100755 index e89bc7a..0000000 --- a/xbase64/xbndx.cpp +++ /dev/null @@ -1,2402 +0,0 @@ -/* 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 */ |