Main Page | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members

ndx.h

Go to the documentation of this file.
00001 /*  $Id: ndx.h,v 1.6 2000/11/10 19:04:17 dbryson Exp $
00002 
00003     Xbase project source code
00004 
00005     This file contains a header file for the xbNdx object, which is used
00006     for handling NDX type indices.
00007 
00008     Copyright (C) 1997  StarTech, Gary A. Kunkel   
00009 
00010     This library is free software; you can redistribute it and/or
00011     modify it under the terms of the GNU Lesser General Public
00012     License as published by the Free Software Foundation; either
00013     version 2.1 of the License, or (at your option) any later version.
00014 
00015     This library is distributed in the hope that it will be useful,
00016     but WITHOUT ANY WARRANTY; without even the implied warranty of
00017     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018     Lesser General Public License for more details.
00019 
00020     You should have received a copy of the GNU Lesser General Public
00021     License along with this library; if not, write to the Free Software
00022     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00023 
00024     Contact:
00025 
00026       Mail:
00027 
00028         Technology Associates, Inc.
00029         XBase Project
00030         1455 Deming Way #11
00031         Sparks, NV 89434
00032         USA
00033 
00034       Email:
00035 
00036         xbase@techass.com
00037 
00038       See our website at:
00039 
00040         xdb.sourceforge.net
00041 
00042 
00043     V 1.0   10/10/97   - Initial release of software
00044     V 1.02  10/25/97   - Index performance enhancements
00045     V 1.3   11/30/97   - Moved GetLong and GetShort to DBF class for memos
00046     V 1.5   1/2/98     - Added Dbase IV memo field support
00047     V 1.6a  4/1/98     - Added expression support
00048     V 1.6b  4/8/98     - umeric index support
00049     V 1.9   4/12/99    - Bug fix w/ AddKey and code cleanup
00050 */
00051 
00052 #ifndef __XB_NDX_H__
00053 #define __XB_NDX_H__
00054 
00055 #ifdef __GNUG__
00056 #pragma interface
00057 #endif
00058 
00059 #include <xbase/xbase.h>
00060 #include <string.h>
00061 
00065 //
00066 // Define the following to use inline versions of the respective methods.
00067 //
00068 #define XB_INLINE_COMPAREKEY
00069 #define XB_INLINE_GETDBFNO
00070 
00071 #define XB_NDX_NODE_BASESIZE            24      // size of base header data
00072 
00073 #define XB_VAR_NODESIZE                 // define to enable variable node sizes
00074 
00075 #ifndef XB_VAR_NODESIZE
00076 #define XB_NDX_NODE_SIZE 2048
00077 //#define XB_NDX_NODE_SIZE 512          // standard dbase node size
00078 #else
00079 #define XB_DEFAULT_NDX_NODE_SIZE        512
00080 #define XB_MAX_NDX_NODE_SIZE            4096
00081 #define XB_NDX_NODE_SIZE                NodeSize
00082 #define XB_NDX_NODE_MULTIPLE            512
00083 #endif // XB_VAR_NODESIZE
00084 
00086 
00089 struct XBDLLEXPORT xbNdxHeadNode {        /* ndx header on disk */
00090    xbLong   StartNode;                    /* header node is node 0 */
00091    xbLong   TotalNodes;                   /* includes header node */
00092    xbLong   NoOfKeys;                     /* actual count + 1 */
00093    xbUShort KeyLen;                       /* length of key data */
00094    xbUShort KeysPerNode;
00095    xbUShort KeyType;                      /* 00 = Char, 01 = Numeric */
00096    xbLong   KeySize;                      /* key len + 8 bytes */
00097    char   Unknown2;
00098    char   Unique;
00099 //   char   KeyExpression[488];
00100 #ifndef XB_VAR_NODESIZE
00101    char   KeyExpression[XB_NDX_NODE_SIZE - 24];
00102 #else
00103    char   KeyExpression[XB_MAX_NDX_NODE_SIZE - 24];
00104 #endif // XB_VAR_NODESIZE
00105 };
00106 
00108 
00111 struct XBDLLEXPORT xbNdxLeafNode {        /* ndx node on disk */
00112    xbLong   NoOfKeysThisNode;
00113 #ifndef XB_VAR_NODESIZE
00114    char   KeyRecs[XB_NDX_NODE_SIZE-4];
00115 #else
00116    char     KeyRecs[XB_MAX_NDX_NODE_SIZE - 4];
00117 #endif // XB_VAR_NODESIZE
00118 };
00119 
00121 
00124 struct XBDLLEXPORT xbNdxNodeLink {        /* ndx node memory */
00125    xbNdxNodeLink * PrevNode;
00126    xbNdxNodeLink * NextNode;
00127    xbLong       CurKeyNo;                 /* 0 - KeysPerNode-1 */
00128    xbLong       NodeNo;
00129    struct xbNdxLeafNode Leaf;
00130 };
00131 
00133 
00136 class XBDLLEXPORT xbNdx : public xbIndex
00137 {
00138 //   xbExpNode * ExpressionTree;    /* Expression tree for index */
00139 
00140 public:
00141    xbNdx() : xbIndex() {}
00142    xbNdx( xbDbf * );
00143 
00144    ~xbNdx() {}
00145 
00146 /* don't uncomment next line - it causes seg faults for some undiagnosed reason*/
00147 //   ~NDX() { if( NdxStatus ) CloseIndex(); }  
00148 
00149    xbShort  OpenIndex ( const char * FileName );
00150    xbShort  CloseIndex();
00151    xbShort  CreateIndex( const char *IxName, const char *Exp,
00152                          xbShort Unique, xbShort OverLay );
00153    xbLong   GetTotalNodes();
00154    xbLong   GetCurDbfRec() { return CurDbfRec; }
00155    xbShort  CreateKey( xbShort, xbShort );
00156    xbShort  GetCurrentKey(char *key);
00157    xbShort  AddKey( xbLong );
00158    xbShort  UniqueIndex() { return HeadNode.Unique; }
00159    xbShort  DeleteKey( xbLong );
00160    xbShort  KeyWasChanged();
00161    xbShort  FindKey( const char *Key );
00162    xbShort  FindKey();
00163    xbShort  FindKey( xbDouble );
00164 #ifdef XBASE_DEBUG
00165    void     DumpHdrNode();
00166    void     DumpNodeRec( xbLong NodeNo ); 
00167    void     DumpNodeChain();
00168    xbShort  CheckIndexIntegrity( const xbShort Option );
00169 #endif
00170 
00171 
00173    xbShort  GetNextKey()  { return GetNextKey( 1 ); }
00175 
00177    xbShort  GetLastKey()  { return GetLastKey( 0, 1 ); }
00179 
00181    xbShort  GetFirstKey() { return GetFirstKey( 1 ); }
00183 
00185    xbShort  GetPrevKey()  { return GetPrevKey( 1 ); }
00186    xbShort  ReIndex(void (*statusFunc)(xbLong itemNum, xbLong numItems) = 0);
00187    xbShort  KeyExists( const char * Key ) { return FindKey( Key, strlen( Key ), 0 ); }
00188    xbShort  KeyExists( xbDouble );
00189 
00190    virtual void SetNodeSize(xbShort size);
00191 
00192    virtual void GetExpression(char *buf, int len);
00193 
00194 protected:
00195    xbNdxHeadNode HeadNode;
00196    xbNdxLeafNode LeafNode;
00197    xbLong xbNodeLinkCtr;
00198    xbLong ReusedxbNodeLinks;
00199    xbString IndexName;
00200 #ifndef XB_VAR_NODESIZE
00201    char  Node[XB_NDX_NODE_SIZE];
00202 #else
00203    char  Node[XB_MAX_NDX_NODE_SIZE];
00204 #endif // XB_VAR_NODESIZE
00205 //   FILE  *ndxfp;
00206 //   int   NdxStatus;                /* 0 = closed, 1 = open */
00207 
00208    xbNdxNodeLink * NodeChain;     /* pointer to node chain of index nodes */
00209    xbNdxNodeLink * FreeNodeChain; /* pointer to chain of free index nodes */
00210    xbNdxNodeLink * CurNode;       /* pointer to current node              */
00211    xbNdxNodeLink * DeleteChain;   /* pointer to chain to delete           */
00212    xbNdxNodeLink * CloneChain;    /* pointer to node chain copy (add dup) */
00213    xbLong  CurDbfRec;             /* current Dbf record number */
00214    char  *KeyBuf;                 /* work area key buffer */
00215    char  *KeyBuf2;                /* work area key buffer */
00216 
00217 /* private functions */
00218    xbLong     GetLeftNodeNo( xbShort, xbNdxNodeLink * );
00219 #ifndef XB_INLINE_COMPAREKEY
00220    xbShort    CompareKey( const char *Key1, const char *Key2, xbShort Klen );
00221 #else
00222 
00223 
00225    inline xbShort    CompareKey( const char *Key1, const char *Key2, xbShort Klen )
00226    {
00227 #if 0
00228      const  char *k1, *k2;
00229      xbShort  i;
00230 #endif
00231      xbDouble d1, d2;
00232      int c;
00233 
00234      if(!( Key1 && Key2 )) return -1;
00235 
00236      if( Klen > HeadNode.KeyLen ) Klen = HeadNode.KeyLen;
00237 
00238      if( HeadNode.KeyType == 0 )
00239      {
00240        c = memcmp(Key1, Key2, Klen);
00241        if(c < 0)
00242          return 2;
00243        else if(c > 0)
00244          return 1;
00245        return 0;
00246      }
00247      else      /* key is numeric */
00248      {
00249         d1 = dbf->xbase->GetDouble( Key1 );
00250         d2 = dbf->xbase->GetDouble( Key2 );
00251         if( d1 == d2 ) return 0;
00252         else if( d1 > d2 ) return 1;
00253         else return 2;
00254      }
00255    }
00256 #endif
00257 #ifndef XB_INLINE_GETDBFNO
00258    xbLong     GetDbfNo( xbShort, xbNdxNodeLink * );
00259 #else
00260 
00261 
00263    inline xbLong     GetDbfNo( xbShort RecNo, xbNdxNodeLink *n )
00264    {
00265      xbNdxLeafNode *temp;
00266      char *p;
00267      if( !n ) return 0L;
00268      temp = &n->Leaf;
00269      if( RecNo < 0 || RecNo > ( temp->NoOfKeysThisNode - 1 )) return 0L;
00270      p = temp->KeyRecs + 4;
00271      p += RecNo * ( 8 + HeadNode.KeyLen );
00272      return( dbf->xbase->GetLong( p ));
00273    }
00274 #endif
00275    char *     GetKeyData( xbShort, xbNdxNodeLink * );
00276    xbUShort   GetKeysPerNode();
00277    xbShort    GetHeadNode();
00278    xbShort    GetLeafNode( xbLong, xbShort );
00279    xbNdxNodeLink * GetNodeMemory();
00280    void       ReleaseNodeMemory( xbNdxNodeLink * );
00281    xbShort    BSearchNode(const char *key, xbShort klen,
00282                           const xbNdxNodeLink *node,
00283                           xbShort *comp);
00284    xbLong     GetLeafFromInteriorNode( const char *Tkey, xbShort Klen );
00285    xbShort    CalcKeyLen();
00286    xbShort    PutKeyData( xbShort, xbNdxNodeLink * );
00287    xbShort    PutLeftNodeNo( xbShort, xbNdxNodeLink *, xbLong );
00288    xbShort    PutLeafNode( xbLong, xbNdxNodeLink * );
00289    xbShort    PutHeadNode( xbNdxHeadNode *, FILE *, xbShort );
00290    xbShort    PutDbfNo( xbShort, xbNdxNodeLink *, xbLong );
00291    xbShort    PutKeyInNode( xbNdxNodeLink *, xbShort, xbLong, xbLong, xbShort );
00292    xbShort    SplitLeafNode( xbNdxNodeLink *, xbNdxNodeLink *, xbShort, xbLong ); 
00293    xbShort    SplitINode( xbNdxNodeLink *, xbNdxNodeLink *, xbLong );
00294    xbShort    AddToIxList();
00295    xbShort    RemoveFromIxList();
00296    xbShort    RemoveKeyFromNode( xbShort, xbNdxNodeLink * );
00297    xbShort    FindKey( const char *Tkey, xbShort Klen, xbShort RetrieveSw );      
00298    xbShort    UpdateParentKey( xbNdxNodeLink * );
00299    xbShort    GetFirstKey( xbShort );
00300    xbShort    GetNextKey( xbShort );
00301    xbShort    GetLastKey( xbLong, xbShort );
00302    xbShort    GetPrevKey( xbShort ); 
00303    void       UpdateDeleteList( xbNdxNodeLink * );
00304    void       ProcessDeleteList();
00305    xbNdxNodeLink * LeftSiblingHasSpace( xbNdxNodeLink * );
00306    xbNdxNodeLink * RightSiblingHasSpace( xbNdxNodeLink * );
00307    xbShort    DeleteSibling( xbNdxNodeLink * );
00308    xbShort    MoveToLeftNode( xbNdxNodeLink *, xbNdxNodeLink * );
00309    xbShort    MoveToRightNode( xbNdxNodeLink *, xbNdxNodeLink * );
00310    xbShort    FindKey( const char *Tkey, xbLong DbfRec );   /* for a specific dbf no */
00311 
00312    xbShort    CloneNodeChain();          
00313    xbShort    UncloneNodeChain();        
00314    
00315 //#ifdef XB_LOCKING_ON
00316 //   xbShort  LockIndex( const xbShort, const xbShort ) const;
00317 //#else
00318 //   xbShort  LockIndex( const xbShort, const xbShort ) const { return NO_ERROR; }
00319 //#endif
00320 
00321 };
00322 #endif      /* __XB_NDX_H__ */

Generated on Sun Jun 4 09:51:01 2006 for Xbase Class Library by  doxygen 1.4.4