00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
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
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
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 {
00090 xbLong StartNode;
00091 xbLong TotalNodes;
00092 xbLong NoOfKeys;
00093 xbUShort KeyLen;
00094 xbUShort KeysPerNode;
00095 xbUShort KeyType;
00096 xbLong KeySize;
00097 char Unknown2;
00098 char Unique;
00099
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 {
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 {
00125 xbNdxNodeLink * PrevNode;
00126 xbNdxNodeLink * NextNode;
00127 xbLong CurKeyNo;
00128 xbLong NodeNo;
00129 struct xbNdxLeafNode Leaf;
00130 };
00131
00133
00136 class XBDLLEXPORT xbNdx : public xbIndex
00137 {
00138
00139
00140 public:
00141 xbNdx() : xbIndex() {}
00142 xbNdx( xbDbf * );
00143
00144 ~xbNdx() {}
00145
00146
00147
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
00206
00207
00208 xbNdxNodeLink * NodeChain;
00209 xbNdxNodeLink * FreeNodeChain;
00210 xbNdxNodeLink * CurNode;
00211 xbNdxNodeLink * DeleteChain;
00212 xbNdxNodeLink * CloneChain;
00213 xbLong CurDbfRec;
00214 char *KeyBuf;
00215 char *KeyBuf2;
00216
00217
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
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 );
00311
00312 xbShort CloneNodeChain();
00313 xbShort UncloneNodeChain();
00314
00315
00316
00317
00318
00319
00320
00321 };
00322 #endif