Xbase Class Library  2.0.0
ndx.h
Go to the documentation of this file.
1 /* $Id: ndx.h,v 1.6 2000/11/10 19:04:17 dbryson Exp $
2 
3  Xbase project source code
4 
5  This file contains a header file for the xbNdx object, which is used
6  for handling NDX type indices.
7 
8  Copyright (C) 1997 StarTech, Gary A. Kunkel
9 
10  This library is free software; you can redistribute it and/or
11  modify it under the terms of the GNU Lesser General Public
12  License as published by the Free Software Foundation; either
13  version 2.1 of the License, or (at your option) any later version.
14 
15  This library is distributed in the hope that it will be useful,
16  but WITHOUT ANY WARRANTY; without even the implied warranty of
17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18  Lesser General Public License for more details.
19 
20  You should have received a copy of the GNU Lesser General Public
21  License along with this library; if not, write to the Free Software
22  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 
24  Contact:
25 
26  Mail:
27 
28  Technology Associates, Inc.
29  XBase Project
30  1455 Deming Way #11
31  Sparks, NV 89434
32  USA
33 
34  Email:
35 
36  xbase@techass.com
37 
38  See our website at:
39 
40  xdb.sourceforge.net
41 
42 
43  V 1.0 10/10/97 - Initial release of software
44  V 1.02 10/25/97 - Index performance enhancements
45  V 1.3 11/30/97 - Moved GetLong and GetShort to DBF class for memos
46  V 1.5 1/2/98 - Added Dbase IV memo field support
47  V 1.6a 4/1/98 - Added expression support
48  V 1.6b 4/8/98 - umeric index support
49  V 1.9 4/12/99 - Bug fix w/ AddKey and code cleanup
50 */
51 
52 #ifndef __XB_NDX_H__
53 #define __XB_NDX_H__
54 
55 #ifdef __GNUG__
56 #pragma interface
57 #endif
58 
59 #include <xbase/xbase.h>
60 #include <string.h>
61 
65 //
66 // Define the following to use inline versions of the respective methods.
67 //
68 #define XB_INLINE_COMPAREKEY
69 #define XB_INLINE_GETDBFNO
70 
71 #define XB_NDX_NODE_BASESIZE 24 // size of base header data
72 
73 #define XB_VAR_NODESIZE // define to enable variable node sizes
74 
75 #ifndef XB_VAR_NODESIZE
76 #define XB_NDX_NODE_SIZE 2048
77 //#define XB_NDX_NODE_SIZE 512 // standard dbase node size
78 #else
79 #define XB_DEFAULT_NDX_NODE_SIZE 512
80 #define XB_MAX_NDX_NODE_SIZE 4096
81 #define XB_NDX_NODE_SIZE NodeSize
82 #define XB_NDX_NODE_MULTIPLE 512
83 #endif // XB_VAR_NODESIZE
84 
86 
89 struct XBDLLEXPORT xbNdxHeadNode { /* ndx header on disk */
90  xbLong StartNode; /* header node is node 0 */
91  xbLong TotalNodes; /* includes header node */
92  xbLong NoOfKeys; /* actual count + 1 */
93  xbUShort KeyLen; /* length of key data */
95  xbUShort KeyType; /* 00 = Char, 01 = Numeric */
96  xbLong KeySize; /* key len + 8 bytes */
97  char Unknown2;
98  char Unique;
99 // char KeyExpression[488];
100 #ifndef XB_VAR_NODESIZE
101  char KeyExpression[XB_NDX_NODE_SIZE - 24];
102 #else
103  char KeyExpression[XB_MAX_NDX_NODE_SIZE - 24];
104 #endif // XB_VAR_NODESIZE
105 };
106 
108 
111 struct XBDLLEXPORT xbNdxLeafNode { /* ndx node on disk */
113 #ifndef XB_VAR_NODESIZE
114  char KeyRecs[XB_NDX_NODE_SIZE-4];
115 #else
116  char KeyRecs[XB_MAX_NDX_NODE_SIZE - 4];
117 #endif // XB_VAR_NODESIZE
118 };
119 
121 
124 struct XBDLLEXPORT xbNdxNodeLink { /* ndx node memory */
127  xbLong CurKeyNo; /* 0 - KeysPerNode-1 */
129  struct xbNdxLeafNode Leaf;
130 };
131 
133 
136 class XBDLLEXPORT xbNdx : public xbIndex
137 {
138 // xbExpNode * ExpressionTree; /* Expression tree for index */
139 
140 public:
141  xbNdx() : xbIndex() {}
142  xbNdx( xbDbf * );
143 
144  ~xbNdx() {}
145 
146 /* don't uncomment next line - it causes seg faults for some undiagnosed reason*/
147 // ~NDX() { if( NdxStatus ) CloseIndex(); }
148 
149  xbShort OpenIndex ( const char * FileName );
151  xbShort CreateIndex( const char *IxName, const char *Exp,
152  xbShort Unique, xbShort OverLay );
156  xbShort GetCurrentKey(char *key);
157  xbShort AddKey( xbLong );
158  xbShort UniqueIndex() { return HeadNode.Unique; }
161  xbShort FindKey( const char *Key );
162  xbShort FindKey();
164 #ifdef XBASE_DEBUG
165  void DumpHdrNode();
166  void DumpNodeRec( xbLong NodeNo );
167  void DumpNodeChain();
168  xbShort CheckIndexIntegrity( const xbShort Option );
169 #endif
170 
173  xbShort GetNextKey() { return GetNextKey( 1 ); }
175 
177  xbShort GetLastKey() { return GetLastKey( 0, 1 ); }
179 
181  xbShort GetFirstKey() { return GetFirstKey( 1 ); }
183 
185  xbShort GetPrevKey() { return GetPrevKey( 1 ); }
186  xbShort ReIndex(void (*statusFunc)(xbLong itemNum, xbLong numItems) = 0);
187  xbShort KeyExists( const char * Key ) { return FindKey( Key, strlen( Key ), 0 ); }
189 
190  virtual void SetNodeSize(xbShort size);
191 
192  virtual void GetExpression(char *buf, int len);
193 
194 protected:
200 #ifndef XB_VAR_NODESIZE
201  char Node[XB_NDX_NODE_SIZE];
202 #else
204 #endif // XB_VAR_NODESIZE
205 // FILE *ndxfp;
206 // int NdxStatus; /* 0 = closed, 1 = open */
207 
208  xbNdxNodeLink * NodeChain; /* pointer to node chain of index nodes */
209  xbNdxNodeLink * FreeNodeChain; /* pointer to chain of free index nodes */
210  xbNdxNodeLink * CurNode; /* pointer to current node */
211  xbNdxNodeLink * DeleteChain; /* pointer to chain to delete */
212  xbNdxNodeLink * CloneChain; /* pointer to node chain copy (add dup) */
213  xbLong CurDbfRec; /* current Dbf record number */
214  char *KeyBuf; /* work area key buffer */
215  char *KeyBuf2; /* work area key buffer */
216 
217 /* private functions */
218  xbLong GetLeftNodeNo( xbShort, xbNdxNodeLink * );
219 #ifndef XB_INLINE_COMPAREKEY
220  xbShort CompareKey( const char *Key1, const char *Key2, xbShort Klen );
221 #else
222 
225  inline xbShort CompareKey( const char *Key1, const char *Key2, xbShort Klen )
226  {
227 #if 0
228  const char *k1, *k2;
229  xbShort i;
230 #endif
231  xbDouble d1, d2;
232  int c;
233 
234  if(!( Key1 && Key2 )) return -1;
235 
236  if( Klen > HeadNode.KeyLen ) Klen = HeadNode.KeyLen;
237 
238  if( HeadNode.KeyType == 0 )
239  {
240  c = memcmp(Key1, Key2, Klen);
241  if(c < 0)
242  return 2;
243  else if(c > 0)
244  return 1;
245  return 0;
246  }
247  else /* key is numeric */
248  {
249  d1 = dbf->xbase->GetDouble( Key1 );
250  d2 = dbf->xbase->GetDouble( Key2 );
251  if( d1 == d2 ) return 0;
252  else if( d1 > d2 ) return 1;
253  else return 2;
254  }
255  }
256 #endif
257 #ifndef XB_INLINE_GETDBFNO
258  xbLong GetDbfNo( xbShort, xbNdxNodeLink * );
259 #else
260 
263  inline xbLong GetDbfNo( xbShort RecNo, xbNdxNodeLink *n )
264  {
265  xbNdxLeafNode *temp;
266  char *p;
267  if( !n ) return 0L;
268  temp = &n->Leaf;
269  if( RecNo < 0 || RecNo > ( temp->NoOfKeysThisNode - 1 )) return 0L;
270  p = temp->KeyRecs + 4;
271  p += RecNo * ( 8 + HeadNode.KeyLen );
272  return( dbf->xbase->GetLong( p ));
273  }
274 #endif
275  char * GetKeyData( xbShort, xbNdxNodeLink * );
276  xbUShort GetKeysPerNode();
277  xbShort GetHeadNode();
278  xbShort GetLeafNode( xbLong, xbShort );
279  xbNdxNodeLink * GetNodeMemory();
280  void ReleaseNodeMemory( xbNdxNodeLink * );
281  xbShort BSearchNode(const char *key, xbShort klen,
282  const xbNdxNodeLink *node,
283  xbShort *comp);
284  xbLong GetLeafFromInteriorNode( const char *Tkey, xbShort Klen );
285  xbShort CalcKeyLen();
286  xbShort PutKeyData( xbShort, xbNdxNodeLink * );
287  xbShort PutLeftNodeNo( xbShort, xbNdxNodeLink *, xbLong );
288  xbShort PutLeafNode( xbLong, xbNdxNodeLink * );
289  xbShort PutHeadNode( xbNdxHeadNode *, FILE *, xbShort );
290  xbShort PutDbfNo( xbShort, xbNdxNodeLink *, xbLong );
291  xbShort PutKeyInNode( xbNdxNodeLink *, xbShort, xbLong, xbLong, xbShort );
292  xbShort SplitLeafNode( xbNdxNodeLink *, xbNdxNodeLink *, xbShort, xbLong );
293  xbShort SplitINode( xbNdxNodeLink *, xbNdxNodeLink *, xbLong );
294  xbShort AddToIxList();
295  xbShort RemoveFromIxList();
296  xbShort RemoveKeyFromNode( xbShort, xbNdxNodeLink * );
297  xbShort FindKey( const char *Tkey, xbShort Klen, xbShort RetrieveSw );
298  xbShort UpdateParentKey( xbNdxNodeLink * );
303  void UpdateDeleteList( xbNdxNodeLink * );
304  void ProcessDeleteList();
305  xbNdxNodeLink * LeftSiblingHasSpace( xbNdxNodeLink * );
306  xbNdxNodeLink * RightSiblingHasSpace( xbNdxNodeLink * );
307  xbShort DeleteSibling( xbNdxNodeLink * );
308  xbShort MoveToLeftNode( xbNdxNodeLink *, xbNdxNodeLink * );
309  xbShort MoveToRightNode( xbNdxNodeLink *, xbNdxNodeLink * );
310  xbShort FindKey( const char *Tkey, xbLong DbfRec ); /* for a specific dbf no */
311 
312  xbShort CloneNodeChain();
313  xbShort UncloneNodeChain();
314 
315 //#ifdef XB_LOCKING_ON
316 // xbShort LockIndex( const xbShort, const xbShort ) const;
317 //#else
318 // xbShort LockIndex( const xbShort, const xbShort ) const { return NO_ERROR; }
319 //#endif
320 
321 };
322 #endif /* __XB_NDX_H__ */
virtual xbShort GetCurrentKey(char *key)=0
virtual xbShort CreateIndex(const char *, const char *, xbShort, xbShort)=0
xbLong TotalNodes
Definition: ndx.h:91
double xbDouble
xbDouble type
Definition: xtypes.h:76
~xbNdx()
Definition: ndx.h:144
#define XB_NDX_NODE_SIZE
Definition: ndx.h:81
virtual xbShort OpenIndex(const char *)=0
xbString IndexName
Definition: ndx.h:199
xbNdx class
Definition: ndx.h:136
virtual xbShort KeyExists(xbDouble)=0
#define XBDLLEXPORT
Definition: xbase.h:101
xbLong ReusedxbNodeLinks
Definition: ndx.h:198
xbNdxNodeLink * FreeNodeChain
Definition: ndx.h:209
xbUShort KeyLen
Definition: ndx.h:93
xbLong KeySize
Definition: ndx.h:96
virtual void SetNodeSize(xbShort size)
Definition: index.h:133
xbLong GetDbfNo(xbShort RecNo, xbNdxNodeLink *n)
Short description.
Definition: ndx.h:263
char Unknown2
Definition: ndx.h:97
xbNdxNodeLink * CurNode
Definition: ndx.h:210
xbLong NoOfKeysThisNode
Definition: ndx.h:112
xbShort GetFirstKey()
Short description.
Definition: ndx.h:181
virtual xbShort GetLastKey()=0
char * KeyBuf2
Definition: ndx.h:215
char * KeyBuf
Definition: ndx.h:214
xbShort KeyExists(const char *Key)
Definition: ndx.h:187
virtual xbShort GetNextKey()=0
xbNdx()
Definition: ndx.h:141
xbString class
Definition: xbstring.h:69
virtual xbShort FindKey()=0
virtual xbShort ReIndex(void(*statusFunc)(xbLong itemNum, xbLong numItems)=0)=0
xbLong NoOfKeys
Definition: ndx.h:92
virtual xbShort KeyWasChanged()=0
xbNdxNodeLink * CloneChain
Definition: ndx.h:212
xbShort UniqueIndex()
Definition: ndx.h:158
xbIndex class
Definition: index.h:67
virtual xbShort GetFirstKey()=0
xbNdxHeadNode HeadNode
Definition: ndx.h:195
xbNdxLeafNode LeafNode
Definition: ndx.h:196
virtual xbShort AddKey(xbLong)=0
#define xbLong
Definition: xtypes.h:67
virtual xbShort CloseIndex()=0
short int xbShort
xbShort type
Definition: xtypes.h:65
xbUShort KeysPerNode
Definition: ndx.h:94
xbLong CurDbfRec
Definition: ndx.h:213
char Unique
Definition: ndx.h:98
virtual xbShort GetPrevKey()=0
#define XB_MAX_NDX_NODE_SIZE
Definition: ndx.h:80
xbNdxNodeLink * DeleteChain
Definition: ndx.h:211
xbLong StartNode
Definition: ndx.h:90
xbLong CurDbfRec
Definition: index.h:79
virtual xbShort CreateKey(xbShort, xbShort)=0
virtual xbShort DeleteKey(xbLong)=0
xbNdxLeafNode struct
Definition: ndx.h:111
xbNdxHeadnode struct
Definition: ndx.h:89
xbUShort KeyType
Definition: ndx.h:95
virtual xbLong GetTotalNodes()=0
xbShort GetLastKey()
Short description.
Definition: ndx.h:177
xbShort GetPrevKey()
Short description.
Definition: ndx.h:185
xbLong xbNodeLinkCtr
Definition: ndx.h:197
xbNdxNodeLink * NodeChain
Definition: ndx.h:208
xbMH struct
Definition: dbf.h:201
xbShort GetNextKey()
Short description.
Definition: ndx.h:173
unsigned short int xbUShort
xbUShort type
Definition: xtypes.h:61
virtual void GetExpression(char *buf, int len)=0
xbShort CompareKey(const char *Key1, const char *Key2, xbShort Klen)
Short description.
Definition: ndx.h:225
char KeyRecs[XB_MAX_NDX_NODE_SIZE-4]
Definition: ndx.h:116
xbLong GetCurDbfRec()
Definition: ndx.h:154