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 */
94  xbUShort KeysPerNode;
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 */
112  xbLong NoOfKeysThisNode;
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 */
125  xbNdxNodeLink * PrevNode;
126  xbNdxNodeLink * NextNode;
127  xbLong CurKeyNo; /* 0 - KeysPerNode-1 */
128  xbLong NodeNo;
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 );
150  xbShort CloseIndex();
151  xbShort CreateIndex( const char *IxName, const char *Exp,
152  xbShort Unique, xbShort OverLay );
153  xbLong GetTotalNodes();
154  xbLong GetCurDbfRec() { return CurDbfRec; }
155  xbShort CreateKey( xbShort, xbShort );
156  xbShort GetCurrentKey(char *key);
157  xbShort AddKey( xbLong );
158  xbShort UniqueIndex() { return HeadNode.Unique; }
159  xbShort DeleteKey( xbLong );
160  xbShort KeyWasChanged();
161  xbShort FindKey( const char *Key );
162  xbShort FindKey();
163  xbShort FindKey( xbDouble );
164 #ifdef XBASE_DEBUG
165  void DumpHdrNode();
166  void DumpNodeRec( xbLong NodeNo );
167  void DumpNodeChain();
168  xbShort CheckIndexIntegrity( const xbShort Option );
169 #endif
170 
171 
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 ); }
188  xbShort KeyExists( xbDouble );
189 
190  virtual void SetNodeSize(xbShort size);
191 
192  virtual void GetExpression(char *buf, int len);
193 
194 protected:
195  xbNdxHeadNode HeadNode;
196  xbNdxLeafNode LeafNode;
197  xbLong xbNodeLinkCtr;
198  xbLong ReusedxbNodeLinks;
199  xbString IndexName;
200 #ifndef XB_VAR_NODESIZE
201  char Node[XB_NDX_NODE_SIZE];
202 #else
203  char Node[XB_MAX_NDX_NODE_SIZE];
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 
223 
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 
261 
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 * );
299  xbShort GetFirstKey( xbShort );
300  xbShort GetNextKey( xbShort );
301  xbShort GetLastKey( xbLong, xbShort );
302  xbShort GetPrevKey( xbShort );
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__ */
Generated by   doxygen 1.8.2