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 #ifndef __XB_NDX_H__
00042 #define __XB_NDX_H__
00043
00044 #ifdef __GNU LesserG__
00045 #pragma interface
00046 #endif
00047
00048 #include <xbase64/xbase64.h>
00049 #include <string.h>
00050
00054
00055
00056
00057 #define XB_INLINE_GETDBFNO
00058
00059 #define XB_NDX_NODE_BASESIZE 24 // size of base header data
00060
00061 #define XB_VAR_NODESIZE // define to enable variable node sizes
00062
00063 #ifndef XB_VAR_NODESIZE
00064 #define XB_NDX_NODE_SIZE 2048
00065
00066 #else
00067 #define XB_DEFAULT_NDX_NODE_SIZE 512
00068 #define XB_MAX_NDX_NODE_SIZE 4096
00069 #define XB_NDX_NODE_SIZE NodeSize
00070 #define XB_NDX_NODE_MULTIPLE 512
00071 #endif // XB_VAR_NODESIZE
00072
00074
00077 struct XBDLLEXPORT xbNdxHeadNode {
00078 xbLong StartNode;
00079 xbLong TotalNodes;
00080 xbLong NoOfKeys;
00081
00082 xbUShort KeyLen;
00083 xbUShort KeysPerNode;
00084 xbUShort KeyType;
00085 xbLong KeySize;
00086 char Unknown2;
00087 char Unique;
00088
00089 #ifndef XB_VAR_NODESIZE
00090 char KeyExpression[XB_NDX_NODE_SIZE - 24];
00091 #else
00092 char KeyExpression[XB_MAX_NDX_NODE_SIZE - 24];
00093 #endif // XB_VAR_NODESIZE
00094 };
00095
00097
00100 struct XBDLLEXPORT xbNdxLeafNode {
00101 xbLong NoOfKeysThisNode;
00102 #ifndef XB_VAR_NODESIZE
00103 char KeyRecs[XB_NDX_NODE_SIZE-4];
00104 #else
00105 char KeyRecs[XB_MAX_NDX_NODE_SIZE - 4];
00106 #endif // XB_VAR_NODESIZE
00107 };
00108
00110
00113 struct XBDLLEXPORT xbNdxNodeLink {
00114 xbNdxNodeLink * PrevNode;
00115 xbNdxNodeLink * NextNode;
00116 xbLong CurKeyNo;
00117 xbLong NodeNo;
00118 struct xbNdxLeafNode Leaf;
00119 };
00120
00122
00125 class XBDLLEXPORT xbNdx : public xbIndex
00126 {
00127 public:
00128 xbNdx();
00129 xbNdx(xbDbf *);
00130 virtual ~xbNdx();
00131
00132
00133
00134
00135 xbShort CreateIndex( const char *IxName, const char *Exp,
00136 xbShort Unique, xbShort OverLay );
00137 xbLong GetTotalNodes();
00138 xbULong GetCurDbfRec() { return CurDbfRec; }
00139 xbShort CreateKey( xbShort, xbShort );
00140 xbShort GetCurrentKey(char *key);
00141 xbShort AddKey( xbLong );
00142 xbShort UniqueIndex() { return HeadNode.Unique; }
00143 xbShort DeleteKey( xbLong );
00144 xbShort KeyWasChanged();
00145 xbShort FindKey( const char *Key );
00146 xbShort FindKey();
00147 xbShort FindKey( xbDouble );
00148 #ifdef XBASE_DEBUG
00149 void DumpHdrNode( xbShort Option );
00150 void DumpNodeRec( xbLong NodeNo );
00151 void DumpNodeChain();
00152 xbShort CheckIndexIntegrity( xbShort Option );
00153 #endif
00155
00157 xbShort GetNextKey() { return GetNextKey( 1 ); }
00159
00161 xbShort GetLastKey() { return GetLastKey( 0, 1 ); }
00163
00165 xbShort GetFirstKey() { return GetFirstKey( 1 ); }
00167
00169 xbShort GetPrevKey() { return GetPrevKey( 1 ); }
00170 xbShort ReIndex(void (*statusFunc)(xbLong itemNum, xbLong numItems) = 0);
00171 xbShort KeyExists( const char * Key ) { return FindKey( Key, strlen( Key ), 0 ); }
00172 xbShort KeyExists( xbDouble );
00173
00174 virtual void SetNodeSize(xbShort size);
00175
00176 virtual void GetExpression(char *buf, int len);
00177 virtual const char* GetExtWithDot(bool lower);
00178
00179 protected:
00180 virtual xbUShort GetKeyLen();
00181 virtual const char* GetKeyExpression();
00182 virtual void FreeNodesMemory();
00183
00184 protected:
00185 xbNdxHeadNode HeadNode;
00186 xbNdxLeafNode LeafNode;
00187 xbLong xbNodeLinkCtr;
00188 xbLong ReusedxbNodeLinks;
00189
00190 #ifndef XB_VAR_NODESIZE
00191 char Node[XB_NDX_NODE_SIZE];
00192 #else
00193 char Node[XB_MAX_NDX_NODE_SIZE];
00194 #endif // XB_VAR_NODESIZE
00195
00196 xbNdxNodeLink * NodeChain;
00197 xbNdxNodeLink * FreeNodeChain;
00198 xbNdxNodeLink * CurNode;
00199 xbNdxNodeLink * DeleteChain;
00200
00201
00202
00203 xbLong GetLeftNodeNo( xbShort, xbNdxNodeLink * );
00204
00205
00206
00208
00210 inline xbShort CompareKey( const char *Key1, const char *Key2, xbShort Klen )
00211 {
00212 xbDouble d1, d2;
00213 int c;
00214
00215 if(!( Key1 && Key2 )) return -1;
00216
00217 if( Klen > HeadNode.KeyLen ) Klen = HeadNode.KeyLen;
00218
00219 if( HeadNode.KeyType == 0 )
00220 {
00221 c = memcmp(Key1, Key2, Klen);
00222 if(c < 0)
00223 return 2;
00224 else if(c > 0)
00225 return 1;
00226 return 0;
00227 }
00228 else
00229 {
00230 d1 = dbf->xbase->GetDouble( Key1 );
00231 d2 = dbf->xbase->GetDouble( Key2 );
00232 if( d1 == d2 ) return 0;
00233 else if( d1 > d2 ) return 1;
00234 else return 2;
00235 }
00236 }
00237
00238 #ifndef XB_INLINE_GETDBFNO
00239 xbLong GetDbfNo( xbShort, xbNdxNodeLink * );
00240 #else
00242
00244 inline xbLong GetDbfNo( xbShort RecNo, xbNdxNodeLink *n )
00245 {
00246 xbNdxLeafNode *temp;
00247 char *p;
00248 if( !n ) return 0L;
00249 temp = &n->Leaf;
00250 if( RecNo < 0 || RecNo > ( temp->NoOfKeysThisNode - 1 )) return 0L;
00251 p = temp->KeyRecs + 4;
00252 p += RecNo * ( 8 + HeadNode.KeyLen );
00253 return( dbf->xbase->GetLong( p ));
00254 }
00255 #endif
00256 char * GetKeyData( xbShort, xbNdxNodeLink * );
00257 xbUShort GetKeysPerNode();
00258 virtual xbShort GetHeadNode();
00259 xbShort GetLeafNode( xbLong, xbShort );
00260 xbNdxNodeLink * GetNodeMemory();
00261 void ReleaseNodeMemory(xbNdxNodeLink *n, xbBool doFree = false);
00262 xbShort BSearchNode(const char *key, xbShort klen,
00263 const xbNdxNodeLink *node, xbShort *comp);
00264 xbLong GetLeafFromInteriorNode( const char *Tkey, xbShort Klen );
00265 xbShort CalcKeyLen();
00266 xbShort PutKeyData( xbShort, xbNdxNodeLink * );
00267 xbShort PutLeftNodeNo( xbShort, xbNdxNodeLink *, xbLong );
00268 xbShort PutLeafNode( xbLong, xbNdxNodeLink * );
00269 xbShort PutHeadNode( xbNdxHeadNode *, FILE *, xbShort );
00270 xbShort PutDbfNo( xbShort, xbNdxNodeLink *, xbLong );
00271 xbShort PutKeyInNode( xbNdxNodeLink *, xbShort, xbLong, xbLong, xbShort );
00272 xbShort SplitLeafNode( xbNdxNodeLink *, xbNdxNodeLink *, xbShort, xbLong );
00273 xbShort SplitINode( xbNdxNodeLink *, xbNdxNodeLink *, xbLong );
00274 xbShort AddToIxList();
00275 xbShort RemoveFromIxList();
00276 xbShort RemoveKeyFromNode( xbShort, xbNdxNodeLink * );
00277 xbShort FindKey( const char *Tkey, xbShort Klen, xbShort RetrieveSw );
00278 xbShort UpdateParentKey( xbNdxNodeLink * );
00279 xbShort GetFirstKey( xbShort );
00280 xbShort GetNextKey( xbShort );
00281 xbShort GetLastKey( xbLong, xbShort );
00282 xbShort GetPrevKey( xbShort );
00283 void UpdateDeleteList( xbNdxNodeLink * );
00284 void ProcessDeleteList();
00285 xbNdxNodeLink * LeftSiblingHasSpace( xbNdxNodeLink * );
00286 xbNdxNodeLink * RightSiblingHasSpace( xbNdxNodeLink * );
00287 xbShort DeleteSibling( xbNdxNodeLink * );
00288 xbShort MoveToLeftNode( xbNdxNodeLink *, xbNdxNodeLink * );
00289 xbShort MoveToRightNode( xbNdxNodeLink *, xbNdxNodeLink * );
00290 xbShort FindKey( const char *Tkey, xbLong DbfRec );
00291 };
00292 #endif