1 : /**********************************************************************
2 : * $Id: mitab_indfile.cpp,v 1.13 2008/01/29 20:46:32 dmorissette Exp $
3 : *
4 : * Name: mitab_indfile.cpp
5 : * Project: MapInfo TAB Read/Write library
6 : * Language: C++
7 : * Purpose: Implementation of the TABINDFile class used to handle
8 : * access to .IND file (table field indexes) attached to a .DAT file
9 : * Author: Daniel Morissette, dmorissette@dmsolutions.ca
10 : *
11 : **********************************************************************
12 : * Copyright (c) 1999-2001, Daniel Morissette
13 : *
14 : * Permission is hereby granted, free of charge, to any person obtaining a
15 : * copy of this software and associated documentation files (the "Software"),
16 : * to deal in the Software without restriction, including without limitation
17 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
18 : * and/or sell copies of the Software, and to permit persons to whom the
19 : * Software is furnished to do so, subject to the following conditions:
20 : *
21 : * The above copyright notice and this permission notice shall be included
22 : * in all copies or substantial portions of the Software.
23 : *
24 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
25 : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
27 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
28 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
29 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
30 : * DEALINGS IN THE SOFTWARE.
31 : **********************************************************************
32 : *
33 : * $Log: mitab_indfile.cpp,v $
34 : * Revision 1.13 2008/01/29 20:46:32 dmorissette
35 : * Added support for v9 Time and DateTime fields (byg 1754)
36 : *
37 : * Revision 1.12 2007/12/11 03:43:03 dmorissette
38 : * Added reporting access mode to error message in TABINDFile::Open()
39 : * (GDAL changeset r12460, ticket 1620)
40 : *
41 : * Revision 1.11 2005/04/29 19:08:56 dmorissette
42 : * Produce an error if m_nSubtreeDepth > 255 when creating a .IND (OGR bug 839)
43 : *
44 : * Revision 1.10 2004/06/30 20:29:04 dmorissette
45 : * Fixed refs to old address danmo@videotron.ca
46 : *
47 : * Revision 1.9 2003/07/24 02:45:57 daniel
48 : * Fixed problem scanning node in TABINDNode::FindNext() - bug 2176, FW
49 : *
50 : * Revision 1.8 2001/05/01 03:38:23 daniel
51 : * Added update support (allows creating new index in existing IND files).
52 : *
53 : * Revision 1.7 2000/11/13 22:17:57 daniel
54 : * When a (child) node's first entry is replaced by InsertEntry() then make
55 : * sure that node's key is updated in its parent node.
56 : *
57 : * Revision 1.6 2000/03/01 00:32:00 daniel
58 : * Added support for float keys, and completed support for generating indexes
59 : *
60 : * Revision 1.5 2000/02/28 16:57:42 daniel
61 : * Added support for writing indexes
62 : *
63 : * Revision 1.4 2000/01/15 22:30:44 daniel
64 : * Switch to MIT/X-Consortium OpenSource license
65 : *
66 : * Revision 1.3 1999/12/14 05:52:05 daniel
67 : * Fixed compile error on Windows
68 : *
69 : * Revision 1.2 1999/12/14 02:19:42 daniel
70 : * Completed .IND support for simple TABViews
71 : *
72 : * Revision 1.1 1999/11/20 15:49:07 daniel
73 : * Initial version
74 : *
75 : **********************************************************************/
76 :
77 : #include "mitab.h"
78 : #include "mitab_utils.h"
79 :
80 : #include <ctype.h> /* toupper() */
81 :
82 : /*=====================================================================
83 : * class TABINDFile
84 : *====================================================================*/
85 :
86 : #define IND_MAGIC_COOKIE 24242424
87 :
88 : /**********************************************************************
89 : * TABINDFile::TABINDFile()
90 : *
91 : * Constructor.
92 : **********************************************************************/
93 9 : TABINDFile::TABINDFile()
94 : {
95 9 : m_fp = NULL;
96 9 : m_pszFname = NULL;
97 9 : m_eAccessMode = TABRead;
98 9 : m_numIndexes = 0;
99 9 : m_papoIndexRootNodes = NULL;
100 9 : m_papbyKeyBuffers = NULL;
101 9 : }
102 :
103 : /**********************************************************************
104 : * TABINDFile::~TABINDFile()
105 : *
106 : * Destructor.
107 : **********************************************************************/
108 9 : TABINDFile::~TABINDFile()
109 : {
110 9 : Close();
111 9 : }
112 :
113 : /**********************************************************************
114 : * TABINDFile::Open()
115 : *
116 : * Open a .IND file, read the header and the root nodes for all the
117 : * field indexes, and be ready to search the indexes.
118 : *
119 : * If the filename that is passed in contains a .DAT extension then
120 : * the extension will be changed to .IND before trying to open the file.
121 : *
122 : * Note that we pass a pszAccess flag, but only read access is supported
123 : * for now (and there are no plans to support write.)
124 : *
125 : * Set bTestOpenNoError=TRUE to silently return -1 with no error message
126 : * if the file cannot be opened because it does not exist.
127 : *
128 : * Returns 0 on success, -1 on error.
129 : **********************************************************************/
130 : int TABINDFile::Open(const char *pszFname, const char *pszAccess,
131 11 : GBool bTestOpenNoError /*=FALSE*/)
132 : {
133 : int nLen;
134 :
135 11 : if (m_fp)
136 : {
137 : CPLError(CE_Failure, CPLE_FileIO,
138 0 : "Open() failed: object already contains an open file");
139 0 : return -1;
140 : }
141 :
142 : /*-----------------------------------------------------------------
143 : * Validate access mode and make sure we use binary access.
144 : * Note that for write access, we actually need read/write access to
145 : * the file.
146 : *----------------------------------------------------------------*/
147 13 : if (EQUALN(pszAccess, "r", 1) && strchr(pszAccess, '+') != NULL)
148 : {
149 2 : m_eAccessMode = TABReadWrite;
150 2 : pszAccess = "rb+";
151 : }
152 9 : else if (EQUALN(pszAccess, "r", 1))
153 : {
154 7 : m_eAccessMode = TABRead;
155 7 : pszAccess = "rb";
156 : }
157 2 : else if (EQUALN(pszAccess, "w", 1))
158 : {
159 2 : m_eAccessMode = TABWrite;
160 2 : pszAccess = "wb+";
161 : }
162 : else
163 : {
164 : CPLError(CE_Failure, CPLE_FileIO,
165 0 : "Open() failed: access mode \"%s\" not supported", pszAccess);
166 0 : return -1;
167 : }
168 :
169 : /*-----------------------------------------------------------------
170 : * Change .DAT (or .TAB) extension to .IND if necessary
171 : *----------------------------------------------------------------*/
172 11 : m_pszFname = CPLStrdup(pszFname);
173 :
174 11 : nLen = strlen(m_pszFname);
175 11 : if (nLen > 4 && !EQUAL(m_pszFname+nLen-4, ".IND") )
176 7 : strcpy(m_pszFname+nLen-4, ".ind");
177 :
178 : #ifndef _WIN32
179 11 : TABAdjustFilenameExtension(m_pszFname);
180 : #endif
181 :
182 : /*-----------------------------------------------------------------
183 : * Open file
184 : *----------------------------------------------------------------*/
185 11 : m_fp = VSIFOpen(m_pszFname, pszAccess);
186 :
187 11 : if (m_fp == NULL)
188 : {
189 0 : if (!bTestOpenNoError)
190 : CPLError(CE_Failure, CPLE_FileIO,
191 0 : "Open() failed for %s (%s)", m_pszFname, pszAccess);
192 :
193 0 : CPLFree(m_pszFname);
194 0 : m_pszFname = NULL;
195 0 : return -1;
196 : }
197 :
198 : /*-----------------------------------------------------------------
199 : * Reset block manager to allocate first block at byte 512, after header.
200 : *----------------------------------------------------------------*/
201 11 : m_oBlockManager.Reset();
202 11 : m_oBlockManager.AllocNewBlock();
203 :
204 : /*-----------------------------------------------------------------
205 : * Read access: Read the header block
206 : * This will also alloc and init the array of index root nodes.
207 : *----------------------------------------------------------------*/
208 11 : if ((m_eAccessMode == TABRead || m_eAccessMode == TABReadWrite) &&
209 : ReadHeader() != 0)
210 : {
211 : // Failed reading header... CPLError() has already been called
212 0 : Close();
213 0 : return -1;
214 : }
215 :
216 : /*-----------------------------------------------------------------
217 : * Write access: Init class members and write a dummy header block
218 : *----------------------------------------------------------------*/
219 11 : if (m_eAccessMode == TABWrite)
220 : {
221 2 : m_numIndexes = 0;
222 :
223 2 : if (WriteHeader() != 0)
224 : {
225 : // Failed writing header... CPLError() has already been called
226 0 : Close();
227 0 : return -1;
228 : }
229 : }
230 :
231 11 : return 0;
232 : }
233 :
234 : /**********************************************************************
235 : * TABINDFile::Close()
236 : *
237 : * Close current file, and release all memory used.
238 : *
239 : * Returns 0 on success, -1 on error.
240 : **********************************************************************/
241 20 : int TABINDFile::Close()
242 : {
243 20 : if (m_fp == NULL)
244 9 : return 0;
245 :
246 : /*-----------------------------------------------------------------
247 : * In Write Mode, commit all indexes to the file
248 : *----------------------------------------------------------------*/
249 11 : if (m_eAccessMode == TABWrite || m_eAccessMode == TABReadWrite)
250 : {
251 4 : WriteHeader();
252 :
253 10 : for(int iIndex=0; iIndex<m_numIndexes; iIndex++)
254 : {
255 6 : if (m_papoIndexRootNodes &&
256 : m_papoIndexRootNodes[iIndex])
257 : {
258 6 : m_papoIndexRootNodes[iIndex]->CommitToFile();
259 : }
260 : }
261 : }
262 :
263 : /*-----------------------------------------------------------------
264 : * Free index nodes in memory
265 : *----------------------------------------------------------------*/
266 25 : for (int iIndex=0; iIndex<m_numIndexes; iIndex++)
267 : {
268 14 : if (m_papoIndexRootNodes && m_papoIndexRootNodes[iIndex])
269 14 : delete m_papoIndexRootNodes[iIndex];
270 14 : if (m_papbyKeyBuffers && m_papbyKeyBuffers[iIndex])
271 14 : CPLFree(m_papbyKeyBuffers[iIndex]);
272 : }
273 11 : CPLFree(m_papoIndexRootNodes);
274 11 : m_papoIndexRootNodes = NULL;
275 11 : CPLFree(m_papbyKeyBuffers);
276 11 : m_papbyKeyBuffers = NULL;
277 11 : m_numIndexes = 0;
278 :
279 : /*-----------------------------------------------------------------
280 : * Close file
281 : *----------------------------------------------------------------*/
282 11 : VSIFClose(m_fp);
283 11 : m_fp = NULL;
284 :
285 11 : CPLFree(m_pszFname);
286 11 : m_pszFname = NULL;
287 :
288 11 : return 0;
289 : }
290 :
291 :
292 : /**********************************************************************
293 : * TABINDFile::ReadHeader()
294 : *
295 : * (private method)
296 : * Read the header block and init all class members for read access.
297 : *
298 : * Returns 0 on success, -1 on error.
299 : **********************************************************************/
300 9 : int TABINDFile::ReadHeader()
301 : {
302 :
303 9 : CPLAssert(m_fp);
304 9 : CPLAssert(m_eAccessMode == TABRead || m_eAccessMode == TABReadWrite);
305 :
306 : /*-----------------------------------------------------------------
307 : * In ReadWrite mode, we need to init BlockManager with file size
308 : *----------------------------------------------------------------*/
309 : VSIStatBuf sStatBuf;
310 9 : if (m_eAccessMode == TABReadWrite && VSIStat(m_pszFname, &sStatBuf) != -1)
311 : {
312 2 : m_oBlockManager.SetLastPtr(((sStatBuf.st_size-1)/512)*512);
313 : }
314 :
315 : /*-----------------------------------------------------------------
316 : * Read the header block
317 : *----------------------------------------------------------------*/
318 : TABRawBinBlock *poHeaderBlock;
319 9 : poHeaderBlock = new TABRawBinBlock(m_eAccessMode, TRUE);
320 9 : if (poHeaderBlock->ReadFromFile(m_fp, 0, 512) != 0)
321 : {
322 : // CPLError() has already been called.
323 0 : delete poHeaderBlock;
324 0 : return -1;
325 : }
326 :
327 9 : poHeaderBlock->GotoByteInBlock(0);
328 9 : GUInt32 nMagicCookie = poHeaderBlock->ReadInt32();
329 9 : if (nMagicCookie != IND_MAGIC_COOKIE)
330 : {
331 : CPLError(CE_Failure, CPLE_FileIO,
332 : "%s: Invalid Magic Cookie: got %d, expected %d",
333 0 : m_pszFname, nMagicCookie, IND_MAGIC_COOKIE);
334 0 : delete poHeaderBlock;
335 0 : return -1;
336 : }
337 :
338 9 : poHeaderBlock->GotoByteInBlock(12);
339 9 : m_numIndexes = poHeaderBlock->ReadInt16();
340 9 : if (m_numIndexes < 1 || m_numIndexes > 29)
341 : {
342 : CPLError(CE_Failure, CPLE_FileIO,
343 : "Invalid number of indexes (%d) in file %s",
344 0 : m_numIndexes, m_pszFname);
345 0 : delete poHeaderBlock;
346 0 : return -1;
347 : }
348 :
349 : /*-----------------------------------------------------------------
350 : * Alloc and init the array of index root nodes.
351 : *----------------------------------------------------------------*/
352 : m_papoIndexRootNodes = (TABINDNode**)CPLCalloc(m_numIndexes,
353 9 : sizeof(TABINDNode*));
354 :
355 9 : m_papbyKeyBuffers = (GByte **)CPLCalloc(m_numIndexes, sizeof(GByte*));
356 :
357 : /* First index def. starts at byte 48 */
358 9 : poHeaderBlock->GotoByteInBlock(48);
359 :
360 19 : for(int iIndex=0; iIndex<m_numIndexes; iIndex++)
361 : {
362 : /*-------------------------------------------------------------
363 : * Read next index definition
364 : *------------------------------------------------------------*/
365 10 : GInt32 nRootNodePtr = poHeaderBlock->ReadInt32();
366 10 : poHeaderBlock->ReadInt16(); // skip... max. num of entries per node
367 10 : int nTreeDepth = poHeaderBlock->ReadByte();
368 10 : int nKeyLength = poHeaderBlock->ReadByte();
369 10 : poHeaderBlock->GotoByteRel(8); // skip next 8 bytes;
370 :
371 : /*-------------------------------------------------------------
372 : * And init root node for this index.
373 : * Note that if nRootNodePtr==0 then this means that the
374 : * corresponding index does not exist (i.e. has been deleted?)
375 : * so we simply do not allocate the root node in this case.
376 : * An error will be produced if the user tries to access this index
377 : * later during execution.
378 : *------------------------------------------------------------*/
379 10 : if (nRootNodePtr > 0)
380 : {
381 10 : m_papoIndexRootNodes[iIndex] = new TABINDNode(m_eAccessMode);
382 10 : if (m_papoIndexRootNodes[iIndex]->InitNode(m_fp, nRootNodePtr,
383 : nKeyLength, nTreeDepth,
384 : FALSE,
385 : &m_oBlockManager)!= 0)
386 : {
387 : // CPLError has already been called
388 0 : delete poHeaderBlock;
389 0 : return -1;
390 : }
391 :
392 : // Alloc a temporary key buffer for this index.
393 : // This buffer will be used by the BuildKey() method
394 : m_papbyKeyBuffers[iIndex] = (GByte *)CPLCalloc(nKeyLength+1,
395 10 : sizeof(GByte));
396 : }
397 : else
398 : {
399 0 : m_papoIndexRootNodes[iIndex] = NULL;
400 0 : m_papbyKeyBuffers[iIndex] = NULL;
401 : }
402 : }
403 :
404 : /*-----------------------------------------------------------------
405 : * OK, we won't need the header block any more... free it.
406 : *----------------------------------------------------------------*/
407 9 : delete poHeaderBlock;
408 :
409 9 : return 0;
410 : }
411 :
412 :
413 : /**********************************************************************
414 : * TABINDFile::WriteHeader()
415 : *
416 : * (private method)
417 : * Write the header block based on current index information.
418 : *
419 : * Returns 0 on success, -1 on error.
420 : **********************************************************************/
421 6 : int TABINDFile::WriteHeader()
422 : {
423 6 : CPLAssert(m_fp);
424 6 : CPLAssert(m_eAccessMode == TABWrite || m_eAccessMode == TABReadWrite);
425 :
426 : /*-----------------------------------------------------------------
427 : * Write the 48 bytes of file header
428 : *----------------------------------------------------------------*/
429 : TABRawBinBlock *poHeaderBlock;
430 6 : poHeaderBlock = new TABRawBinBlock(m_eAccessMode, TRUE);
431 6 : poHeaderBlock->InitNewBlock(m_fp, 512, 0);
432 :
433 6 : poHeaderBlock->WriteInt32( IND_MAGIC_COOKIE );
434 :
435 6 : poHeaderBlock->WriteInt16( 100 ); // ???
436 6 : poHeaderBlock->WriteInt16( 512 ); // ???
437 6 : poHeaderBlock->WriteInt32( 0 ); // ???
438 :
439 6 : poHeaderBlock->WriteInt16( m_numIndexes );
440 :
441 6 : poHeaderBlock->WriteInt16( 0x15e7); // ???
442 :
443 6 : poHeaderBlock->WriteInt16( 10 ); // ???
444 6 : poHeaderBlock->WriteInt16( 0x611d); // ???
445 :
446 6 : poHeaderBlock->WriteZeros( 28 );
447 :
448 : /*-----------------------------------------------------------------
449 : * The first index definition starts at byte 48
450 : *----------------------------------------------------------------*/
451 12 : for(int iIndex=0; iIndex<m_numIndexes; iIndex++)
452 : {
453 6 : TABINDNode *poRootNode = m_papoIndexRootNodes[iIndex];
454 :
455 6 : if (poRootNode)
456 : {
457 : /*---------------------------------------------------------
458 : * Write next index definition
459 : *--------------------------------------------------------*/
460 6 : poHeaderBlock->WriteInt32(poRootNode->GetNodeBlockPtr());
461 6 : poHeaderBlock->WriteInt16(poRootNode->GetMaxNumEntries());
462 6 : poHeaderBlock->WriteByte( poRootNode->GetSubTreeDepth());
463 6 : poHeaderBlock->WriteByte( poRootNode->GetKeyLength());
464 :
465 6 : poHeaderBlock->WriteZeros( 8 );
466 :
467 : /*---------------------------------------------------------
468 : * Look for overflow of the SubTreeDepth field (byte)
469 : *--------------------------------------------------------*/
470 6 : if (poRootNode->GetSubTreeDepth() > 255)
471 : {
472 : CPLError(CE_Failure, CPLE_AssertionFailed,
473 : "Index no %d is too large and will not be useable. "
474 : "(SubTreeDepth = %d, cannot exceed 255).",
475 0 : iIndex+1, poRootNode->GetSubTreeDepth());
476 0 : return -1;
477 : }
478 : }
479 : else
480 : {
481 : /*---------------------------------------------------------
482 : * NULL Root Node: This index has likely been deleted
483 : *--------------------------------------------------------*/
484 0 : poHeaderBlock->WriteZeros( 16 );
485 : }
486 : }
487 :
488 : /*-----------------------------------------------------------------
489 : * OK, we won't need the header block any more... write and free it.
490 : *----------------------------------------------------------------*/
491 6 : if (poHeaderBlock->CommitToFile() != 0)
492 0 : return -1;
493 :
494 6 : delete poHeaderBlock;
495 :
496 6 : return 0;
497 : }
498 :
499 : /**********************************************************************
500 : * TABINDFile::ValidateIndexNo()
501 : *
502 : * Private method to validate the index no parameter of some methods...
503 : * returns 0 if index no. is OK, or produces an error ands returns -1
504 : * if index no is not valid.
505 : **********************************************************************/
506 190 : int TABINDFile::ValidateIndexNo(int nIndexNumber)
507 : {
508 190 : if (m_fp == NULL)
509 : {
510 : CPLError(CE_Failure, CPLE_AssertionFailed,
511 0 : "TABINDFile: File has not been opened yet!");
512 0 : return -1;
513 : }
514 :
515 190 : if (nIndexNumber < 1 || nIndexNumber > m_numIndexes ||
516 : m_papoIndexRootNodes == NULL ||
517 : m_papoIndexRootNodes[nIndexNumber-1] == NULL)
518 : {
519 : CPLError(CE_Failure, CPLE_AssertionFailed,
520 : "No field index number %d in %s: Valid range is [1..%d].",
521 0 : nIndexNumber, m_pszFname, m_numIndexes);
522 0 : return -1;
523 : }
524 :
525 190 : return 0; // Index seems valid
526 : }
527 :
528 : /**********************************************************************
529 : * TABINDFile::SetIndexFieldType()
530 : *
531 : * Sets the field type for the specified index.
532 : * This information will then be used in building the key values, etc.
533 : *
534 : * Returns 0 on success, -1 on error.
535 : **********************************************************************/
536 0 : int TABINDFile::SetIndexFieldType(int nIndexNumber, TABFieldType eType)
537 : {
538 0 : if (ValidateIndexNo(nIndexNumber) != 0)
539 0 : return -1;
540 :
541 0 : return m_papoIndexRootNodes[nIndexNumber-1]->SetFieldType(eType);
542 : }
543 :
544 : /**********************************************************************
545 : * TABINDFile::SetIndexUnique()
546 : *
547 : * Indicate that an index's keys are unique. This allows for some
548 : * optimization with read access. By default, an index is treated as if
549 : * its keys could have duplicates.
550 : *
551 : * Returns 0 on success, -1 on error.
552 : **********************************************************************/
553 0 : int TABINDFile::SetIndexUnique(int nIndexNumber, GBool bUnique/*=TRUE*/)
554 : {
555 0 : if (ValidateIndexNo(nIndexNumber) != 0)
556 0 : return -1;
557 :
558 0 : m_papoIndexRootNodes[nIndexNumber-1]->SetUnique(bUnique);
559 :
560 0 : return 0;
561 : }
562 :
563 : /**********************************************************************
564 : * TABINDFile::BuildKey()
565 : *
566 : * Encode a field value in the form required to be compared with index
567 : * keys in the specified index.
568 : *
569 : * Note that index numbers are positive values starting at 1.
570 : *
571 : * Returns a reference to an internal buffer that is valid only until the
572 : * next call to BuildKey(). (should not be freed by the caller).
573 : * Returns NULL if field index is invalid.
574 : *
575 : * The first flavour of the function handles integer type of values, this
576 : * corresponds to MapInfo types: integer, smallint, logical and date
577 : **********************************************************************/
578 2 : GByte *TABINDFile::BuildKey(int nIndexNumber, GInt32 nValue)
579 : {
580 2 : if (ValidateIndexNo(nIndexNumber) != 0)
581 0 : return NULL;
582 :
583 2 : int nKeyLength = m_papoIndexRootNodes[nIndexNumber-1]->GetKeyLength();
584 :
585 : /*-----------------------------------------------------------------
586 : * Convert all int values to MSB using the right number of bytes
587 : * Note:
588 : * The most significant bit has to be unset for negative values,
589 : * and to be set for positive ones... that's the reverse of what it
590 : * should usually be. Adding 0x80 to the MSB byte will do the job.
591 : *----------------------------------------------------------------*/
592 2 : switch(nKeyLength)
593 : {
594 : case 1:
595 0 : m_papbyKeyBuffers[nIndexNumber-1][0] = (GByte)(nValue & 0xff)+0x80;
596 0 : break;
597 : case 2:
598 : m_papbyKeyBuffers[nIndexNumber-1][0] =
599 0 : (GByte)(nValue/0x100 & 0xff)+0x80;
600 0 : m_papbyKeyBuffers[nIndexNumber-1][1] = (GByte)(nValue & 0xff);
601 0 : break;
602 : case 4:
603 : m_papbyKeyBuffers[nIndexNumber-1][0] =
604 2 : (GByte)(nValue/0x1000000 &0xff)+0x80;
605 2 : m_papbyKeyBuffers[nIndexNumber-1][1] = (GByte)(nValue/0x10000 & 0xff);
606 2 : m_papbyKeyBuffers[nIndexNumber-1][2] = (GByte)(nValue/0x100 &0xff);
607 2 : m_papbyKeyBuffers[nIndexNumber-1][3] = (GByte)(nValue & 0xff);
608 2 : break;
609 : default:
610 : CPLError(CE_Failure, CPLE_AssertionFailed,
611 : "BuildKey(): %d bytes integer key length not supported",
612 0 : nKeyLength);
613 : break;
614 : }
615 :
616 2 : return m_papbyKeyBuffers[nIndexNumber-1];
617 : }
618 :
619 : /**********************************************************************
620 : * TABINDFile::BuildKey()
621 : *
622 : * BuildKey() for string fields
623 : **********************************************************************/
624 41 : GByte *TABINDFile::BuildKey(int nIndexNumber, const char *pszStr)
625 : {
626 41 : if (ValidateIndexNo(nIndexNumber) != 0 || pszStr == NULL)
627 0 : return NULL;
628 :
629 41 : int nKeyLength = m_papoIndexRootNodes[nIndexNumber-1]->GetKeyLength();
630 :
631 : /*-----------------------------------------------------------------
632 : * Strings keys are all in uppercase, and padded with '\0'
633 : *----------------------------------------------------------------*/
634 41 : int i=0;
635 348 : for (i=0; i<nKeyLength && pszStr[i] != '\0'; i++)
636 : {
637 307 : m_papbyKeyBuffers[nIndexNumber-1][i] = (GByte)toupper(pszStr[i]);
638 : }
639 :
640 : /* Pad the end of the buffer with '\0' */
641 390 : for( ; i<nKeyLength; i++)
642 : {
643 349 : m_papbyKeyBuffers[nIndexNumber-1][i] = '\0';
644 : }
645 :
646 41 : return m_papbyKeyBuffers[nIndexNumber-1];
647 : }
648 :
649 : /**********************************************************************
650 : * TABINDFile::BuildKey()
651 : *
652 : * BuildKey() for float and decimal fields
653 : **********************************************************************/
654 47 : GByte *TABINDFile::BuildKey(int nIndexNumber, double dValue)
655 : {
656 47 : if (ValidateIndexNo(nIndexNumber) != 0)
657 0 : return NULL;
658 :
659 47 : int nKeyLength = m_papoIndexRootNodes[nIndexNumber-1]->GetKeyLength();
660 47 : CPLAssert(nKeyLength == 8 && sizeof(double) == 8);
661 :
662 : /*-----------------------------------------------------------------
663 : * Convert double and decimal values...
664 : * Reverse the sign of the value, and convert to MSB
665 : *----------------------------------------------------------------*/
666 47 : dValue = -dValue;
667 :
668 : #ifndef CPL_MSB
669 47 : CPL_SWAPDOUBLE(&dValue);
670 : #endif
671 :
672 47 : memcpy(m_papbyKeyBuffers[nIndexNumber-1], (GByte*)(&dValue), nKeyLength);
673 :
674 47 : return m_papbyKeyBuffers[nIndexNumber-1];
675 : }
676 :
677 :
678 : /**********************************************************************
679 : * TABINDFile::FindFirst()
680 : *
681 : * Search one of the indexes for a key value.
682 : *
683 : * Note that index numbers are positive values starting at 1.
684 : *
685 : * Return value:
686 : * - the key's corresponding record number in the .DAT file (greater than 0)
687 : * - 0 if the key was not found
688 : * - or -1 if an error happened
689 : **********************************************************************/
690 10 : GInt32 TABINDFile::FindFirst(int nIndexNumber, GByte *pKeyValue)
691 : {
692 10 : if (ValidateIndexNo(nIndexNumber) != 0)
693 0 : return -1;
694 :
695 10 : return m_papoIndexRootNodes[nIndexNumber-1]->FindFirst(pKeyValue);
696 : }
697 :
698 : /**********************************************************************
699 : * TABINDFile::FindNext()
700 : *
701 : * Continue the Search for pKeyValue previously initiated by FindFirst().
702 : * NOTE: FindFirst() MUST have been previously called for this call to
703 : * work...
704 : *
705 : * Note that index numbers are positive values starting at 1.
706 : *
707 : * Return value:
708 : * - the key's corresponding record number in the .DAT file (greater than 0)
709 : * - 0 if the key was not found
710 : * - or -1 if an error happened
711 : **********************************************************************/
712 10 : GInt32 TABINDFile::FindNext(int nIndexNumber, GByte *pKeyValue)
713 : {
714 10 : if (ValidateIndexNo(nIndexNumber) != 0)
715 0 : return -1;
716 :
717 10 : return m_papoIndexRootNodes[nIndexNumber-1]->FindNext(pKeyValue);
718 : }
719 :
720 :
721 : /**********************************************************************
722 : * TABINDFile::CreateIndex()
723 : *
724 : * Create a new index with the specified field type and size.
725 : * Field size applies only to char field type... the other types have a
726 : * predefined key length.
727 : *
728 : * Key length is limited to 128 chars. char fields longer than 128 chars
729 : * will have their key truncated to 128 bytes.
730 : *
731 : * Note that a .IND file can contain only a maximum of 29 indexes.
732 : *
733 : * Returns the new field index on success (greater than 0), or -1 on error.
734 : **********************************************************************/
735 4 : int TABINDFile::CreateIndex(TABFieldType eType, int nFieldSize)
736 : {
737 4 : int i, nNewIndexNo = -1;
738 :
739 4 : if (m_fp == NULL ||
740 : (m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite))
741 0 : return -1;
742 :
743 : // __TODO__
744 : // We'll need more work in TABDATFile::WriteDateTimeField() before
745 : // we can support indexes on fields of type DateTime (see bug #1844)
746 4 : if (eType == TABFDateTime)
747 : {
748 : CPLError(CE_Failure, CPLE_AssertionFailed,
749 0 : "Index on fields of type DateTime not supported yet.");
750 0 : return -1;
751 : }
752 :
753 : /*-----------------------------------------------------------------
754 : * Look for an empty slot in the current array, if there is none
755 : * then extend the array.
756 : *----------------------------------------------------------------*/
757 6 : for(i=0; m_papoIndexRootNodes && i<m_numIndexes; i++)
758 : {
759 2 : if (m_papoIndexRootNodes[i] == NULL)
760 : {
761 0 : nNewIndexNo = i;
762 0 : break;
763 : }
764 : }
765 :
766 4 : if (nNewIndexNo == -1 && m_numIndexes >= 29)
767 : {
768 : CPLError(CE_Failure, CPLE_AppDefined,
769 : "Cannot add new index to %s. A dataset can contain only a "
770 0 : "maximum of 29 indexes.", m_pszFname);
771 0 : return -1;
772 : }
773 :
774 4 : if (nNewIndexNo == -1)
775 : {
776 : /*-------------------------------------------------------------
777 : * Add a slot for new index at the end of the nodes array.
778 : *------------------------------------------------------------*/
779 4 : m_numIndexes++;
780 : m_papoIndexRootNodes = (TABINDNode**)CPLRealloc( m_papoIndexRootNodes,
781 : m_numIndexes*
782 4 : sizeof(TABINDNode*));
783 :
784 : m_papbyKeyBuffers = (GByte **)CPLRealloc(m_papbyKeyBuffers,
785 4 : m_numIndexes*sizeof(GByte*));
786 :
787 4 : nNewIndexNo = m_numIndexes-1;
788 : }
789 :
790 : /*-----------------------------------------------------------------
791 : * Alloc and init new node
792 : * The call to InitNode() automatically allocates storage space for
793 : * the node in the file.
794 : * New nodes are created with a subtree_depth=1 since they start as
795 : * leaf nodes, i.e. their entries point directly to .DAT records
796 : *----------------------------------------------------------------*/
797 : int nKeyLength = ((eType == TABFInteger) ? 4:
798 : (eType == TABFSmallInt) ? 2:
799 : (eType == TABFFloat) ? 8:
800 : (eType == TABFDecimal) ? 8:
801 : (eType == TABFDate) ? 4:
802 : (eType == TABFTime) ? 4:
803 : (eType == TABFDateTime) ? 8:
804 4 : (eType == TABFLogical) ? 4: MIN(128,nFieldSize));
805 :
806 4 : m_papoIndexRootNodes[nNewIndexNo] = new TABINDNode(m_eAccessMode);
807 4 : if (m_papoIndexRootNodes[nNewIndexNo]->InitNode(m_fp, 0, nKeyLength,
808 : 1, // subtree depth=1
809 : FALSE, // not unique
810 : &m_oBlockManager,
811 : NULL, 0, 0)!= 0)
812 : {
813 : // CPLError has already been called
814 0 : return -1;
815 : }
816 :
817 : // Alloc a temporary key buffer for this index.
818 : // This buffer will be used by the BuildKey() method
819 : m_papbyKeyBuffers[nNewIndexNo] = (GByte *)CPLCalloc(nKeyLength+1,
820 4 : sizeof(GByte));
821 :
822 : // Return 1-based index number
823 4 : return nNewIndexNo+1;
824 : }
825 :
826 :
827 : /**********************************************************************
828 : * TABINDFile::AddEntry()
829 : *
830 : * Add an .DAT record entry for pKeyValue in the specified index.
831 : *
832 : * Note that index numbers are positive values starting at 1.
833 : * nRecordNo is the .DAT record number, record numbers start at 1.
834 : *
835 : * Returns 0 on success, -1 on error
836 : **********************************************************************/
837 80 : int TABINDFile::AddEntry(int nIndexNumber, GByte *pKeyValue, GInt32 nRecordNo)
838 : {
839 80 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
840 : ValidateIndexNo(nIndexNumber) != 0)
841 0 : return -1;
842 :
843 80 : return m_papoIndexRootNodes[nIndexNumber-1]->AddEntry(pKeyValue,nRecordNo);
844 : }
845 :
846 :
847 : /**********************************************************************
848 : * TABINDFile::Dump()
849 : *
850 : * Dump block contents... available only in DEBUG mode.
851 : **********************************************************************/
852 : #ifdef DEBUG
853 :
854 0 : void TABINDFile::Dump(FILE *fpOut /*=NULL*/)
855 : {
856 0 : if (fpOut == NULL)
857 0 : fpOut = stdout;
858 :
859 0 : fprintf(fpOut, "----- TABINDFile::Dump() -----\n");
860 :
861 0 : if (m_fp == NULL)
862 : {
863 0 : fprintf(fpOut, "File is not opened.\n");
864 : }
865 : else
866 : {
867 0 : fprintf(fpOut, "File is opened: %s\n", m_pszFname);
868 0 : fprintf(fpOut, " m_numIndexes = %d\n", m_numIndexes);
869 0 : for(int i=0; i<m_numIndexes && m_papoIndexRootNodes; i++)
870 : {
871 0 : if (m_papoIndexRootNodes[i])
872 : {
873 0 : fprintf(fpOut, " ----- Index # %d -----\n", i+1);
874 0 : m_papoIndexRootNodes[i]->Dump(fpOut);
875 : }
876 : }
877 :
878 : }
879 :
880 0 : fflush(fpOut);
881 0 : }
882 :
883 : #endif // DEBUG
884 :
885 :
886 :
887 :
888 :
889 : /*=====================================================================
890 : * class TABINDNode
891 : *====================================================================*/
892 :
893 : /**********************************************************************
894 : * TABINDNode::TABINDNode()
895 : *
896 : * Constructor.
897 : **********************************************************************/
898 14 : TABINDNode::TABINDNode(TABAccess eAccessMode /*=TABRead*/)
899 : {
900 14 : m_fp = NULL;
901 14 : m_poCurChildNode = NULL;
902 14 : m_nSubTreeDepth = 0;
903 14 : m_nKeyLength = 0;
904 14 : m_eFieldType = TABFUnknown;
905 14 : m_poDataBlock = NULL;
906 14 : m_numEntriesInNode = 0;
907 14 : m_nCurIndexEntry = 0;
908 14 : m_nPrevNodePtr = 0;
909 14 : m_nNextNodePtr = 0;
910 14 : m_poBlockManagerRef = NULL;
911 14 : m_poParentNodeRef = NULL;
912 14 : m_bUnique = FALSE;
913 :
914 14 : m_eAccessMode = eAccessMode;
915 14 : }
916 :
917 : /**********************************************************************
918 : * TABINDNode::~TABINDNode()
919 : *
920 : * Destructor.
921 : **********************************************************************/
922 14 : TABINDNode::~TABINDNode()
923 : {
924 14 : if (m_poCurChildNode)
925 0 : delete m_poCurChildNode;
926 :
927 14 : if (m_poDataBlock)
928 14 : delete m_poDataBlock;
929 14 : }
930 :
931 : /**********************************************************************
932 : * TABINDNode::InitNode()
933 : *
934 : * Init a node... this function can be used either to initialize a new
935 : * node, or to make it point to a new data block in the file.
936 : *
937 : * By default, this call will read the data from the file at the
938 : * specified location if necessary, and leave the object ready to be searched.
939 : *
940 : * In write access, if the block does not exist (i.e. nBlockPtr=0) then a
941 : * new one is created and initialized.
942 : *
943 : * poParentNode is used in write access in order to update the parent node
944 : * when this node becomes full and has to be split.
945 : *
946 : * Returns 0 on success, -1 on error.
947 : **********************************************************************/
948 : int TABINDNode::InitNode(FILE *fp, int nBlockPtr,
949 : int nKeyLength, int nSubTreeDepth,
950 : GBool bUnique,
951 : TABBinBlockManager *poBlockMgr /*=NULL*/,
952 : TABINDNode *poParentNode /*=NULL*/,
953 14 : int nPrevNodePtr /*=0*/, int nNextNodePtr /*=0*/)
954 : {
955 : /*-----------------------------------------------------------------
956 : * If the block already points to the right block, then don't do
957 : * anything here.
958 : *----------------------------------------------------------------*/
959 14 : if (m_fp == fp && nBlockPtr> 0 && m_nCurDataBlockPtr == nBlockPtr)
960 0 : return 0;
961 :
962 : // Keep track of some info
963 14 : m_fp = fp;
964 14 : m_nKeyLength = nKeyLength;
965 14 : m_nSubTreeDepth = nSubTreeDepth;
966 14 : m_nCurDataBlockPtr = nBlockPtr;
967 14 : m_bUnique = bUnique;
968 :
969 : // Do not overwrite the following values if we receive NULL (the defaults)
970 14 : if (poBlockMgr)
971 14 : m_poBlockManagerRef = poBlockMgr;
972 14 : if (poParentNode)
973 0 : m_poParentNodeRef = poParentNode;
974 :
975 : // Set some defaults
976 14 : m_numEntriesInNode = 0;
977 14 : m_nPrevNodePtr = nPrevNodePtr;
978 14 : m_nNextNodePtr = nNextNodePtr;
979 :
980 14 : m_nCurIndexEntry = 0;
981 :
982 : /*-----------------------------------------------------------------
983 : * Init RawBinBlock
984 : * The node's buffer has to be created with read/write access since
985 : * the index is a very dynamic structure!
986 : *----------------------------------------------------------------*/
987 14 : if (m_poDataBlock == NULL)
988 14 : m_poDataBlock = new TABRawBinBlock(TABReadWrite, TRUE);
989 :
990 18 : if ((m_eAccessMode == TABWrite || m_eAccessMode == TABReadWrite) &&
991 : nBlockPtr == 0 && m_poBlockManagerRef)
992 : {
993 : /*-------------------------------------------------------------
994 : * Write access: Create and init a new block
995 : *------------------------------------------------------------*/
996 4 : m_nCurDataBlockPtr = m_poBlockManagerRef->AllocNewBlock();
997 4 : m_poDataBlock->InitNewBlock(m_fp, 512, m_nCurDataBlockPtr);
998 :
999 4 : m_poDataBlock->WriteInt32( m_numEntriesInNode );
1000 4 : m_poDataBlock->WriteInt32( m_nPrevNodePtr );
1001 4 : m_poDataBlock->WriteInt32( m_nNextNodePtr );
1002 : }
1003 : else
1004 : {
1005 10 : CPLAssert(m_nCurDataBlockPtr > 0);
1006 : /*-------------------------------------------------------------
1007 : * Read the data block from the file, applies to read access, or
1008 : * to write access (to modify an existing block)
1009 : *------------------------------------------------------------*/
1010 10 : if (m_poDataBlock->ReadFromFile(m_fp, m_nCurDataBlockPtr, 512) != 0)
1011 : {
1012 : // CPLError() has already been called.
1013 0 : return -1;
1014 : }
1015 :
1016 10 : m_poDataBlock->GotoByteInBlock(0);
1017 10 : m_numEntriesInNode = m_poDataBlock->ReadInt32();
1018 10 : m_nPrevNodePtr = m_poDataBlock->ReadInt32();
1019 10 : m_nNextNodePtr = m_poDataBlock->ReadInt32();
1020 : }
1021 :
1022 : // m_poDataBlock is now positioned at the beginning of the key entries
1023 :
1024 14 : return 0;
1025 : }
1026 :
1027 :
1028 : /**********************************************************************
1029 : * TABINDNode::GotoNodePtr()
1030 : *
1031 : * Move to the specified node ptr, and read the new node data from the file.
1032 : *
1033 : * This is just a cover funtion on top of InitNode()
1034 : **********************************************************************/
1035 0 : int TABINDNode::GotoNodePtr(GInt32 nNewNodePtr)
1036 : {
1037 : // First flush current changes if any.
1038 0 : if ((m_eAccessMode == TABWrite || m_eAccessMode == TABReadWrite) &&
1039 : m_poDataBlock && m_poDataBlock->CommitToFile() != 0)
1040 0 : return -1;
1041 :
1042 0 : CPLAssert(nNewNodePtr % 512 == 0);
1043 :
1044 : // Then move to the requested location.
1045 : return InitNode(m_fp, nNewNodePtr, m_nKeyLength, m_nSubTreeDepth,
1046 0 : m_bUnique);
1047 : }
1048 :
1049 : /**********************************************************************
1050 : * TABINDNode::ReadIndexEntry()
1051 : *
1052 : * Read the key value and record/node ptr for the specified index entry
1053 : * inside the current node data.
1054 : *
1055 : * nEntryNo is the 0-based index of the index entry that we are interested
1056 : * in inside the current node.
1057 : *
1058 : * Returns the record/node ptr, and copies the key value inside the
1059 : * buffer pointed to by *pKeyValue... this assumes that *pKeyValue points
1060 : * to a buffer big enough to hold the key value (m_nKeyLength bytes).
1061 : * If pKeyValue == NULL, then this parameter is ignored and the key value
1062 : * is not copied.
1063 : **********************************************************************/
1064 10 : GInt32 TABINDNode::ReadIndexEntry(int nEntryNo, GByte *pKeyValue)
1065 : {
1066 10 : GInt32 nRecordPtr = 0;
1067 10 : if (nEntryNo >= 0 && nEntryNo < m_numEntriesInNode)
1068 : {
1069 10 : if (pKeyValue)
1070 : {
1071 0 : m_poDataBlock->GotoByteInBlock(12 + nEntryNo*(m_nKeyLength+4));
1072 0 : m_poDataBlock->ReadBytes(m_nKeyLength, pKeyValue);
1073 : }
1074 : else
1075 : {
1076 : m_poDataBlock->GotoByteInBlock(12 + nEntryNo*(m_nKeyLength+4)+
1077 10 : m_nKeyLength);
1078 : }
1079 :
1080 10 : nRecordPtr = m_poDataBlock->ReadInt32();
1081 : }
1082 :
1083 10 : return nRecordPtr;
1084 : }
1085 :
1086 : /**********************************************************************
1087 : * TABINDNode::IndexKeyCmp()
1088 : *
1089 : * Compare the specified index entry with the key value, and
1090 : * return 0 if equal, an integer less than 0 if key is smaller than
1091 : * index entry, and an integer greater than 0 if key is bigger than
1092 : * index entry.
1093 : *
1094 : * nEntryNo is the 0-based index of the index entry that we are interested
1095 : * in inside the current node.
1096 : **********************************************************************/
1097 1321 : int TABINDNode::IndexKeyCmp(GByte *pKeyValue, int nEntryNo)
1098 : {
1099 1321 : CPLAssert(pKeyValue);
1100 1321 : CPLAssert(nEntryNo >= 0 && nEntryNo < m_numEntriesInNode);
1101 :
1102 1321 : m_poDataBlock->GotoByteInBlock(12 + nEntryNo*(m_nKeyLength+4));
1103 :
1104 1321 : return memcmp(pKeyValue, m_poDataBlock->GetCurDataPtr(), m_nKeyLength);
1105 : }
1106 :
1107 : /**********************************************************************
1108 : * TABINDNode::SetFieldType()
1109 : *
1110 : * Sets the field type for the current index and recursively set all
1111 : * children as well.
1112 : * This information will then be used in building the key values, etc.
1113 : *
1114 : * Returns 0 on success, -1 on error.
1115 : **********************************************************************/
1116 0 : int TABINDNode::SetFieldType(TABFieldType eType)
1117 : {
1118 0 : if (m_fp == NULL)
1119 : {
1120 : CPLError(CE_Failure, CPLE_AssertionFailed,
1121 0 : "TABINDNode::SetFieldType(): File has not been opened yet!");
1122 0 : return -1;
1123 : }
1124 :
1125 : /*-----------------------------------------------------------------
1126 : * Validate field type with key length
1127 : *----------------------------------------------------------------*/
1128 0 : if ((eType == TABFInteger && m_nKeyLength != 4) ||
1129 : (eType == TABFSmallInt && m_nKeyLength != 2) ||
1130 : (eType == TABFFloat && m_nKeyLength != 8) ||
1131 : (eType == TABFDecimal && m_nKeyLength != 8) ||
1132 : (eType == TABFDate && m_nKeyLength != 4) ||
1133 : (eType == TABFTime && m_nKeyLength != 4) ||
1134 : (eType == TABFDateTime && m_nKeyLength != 8) ||
1135 : (eType == TABFLogical && m_nKeyLength != 4) )
1136 : {
1137 : CPLError(CE_Failure, CPLE_IllegalArg,
1138 : "Index key length (%d) does not match field type (%s).",
1139 0 : m_nKeyLength, TABFIELDTYPE_2_STRING(eType) );
1140 0 : return -1;
1141 : }
1142 :
1143 0 : m_eFieldType = eType;
1144 :
1145 : /*-----------------------------------------------------------------
1146 : * Pass the field type info to child nodes
1147 : *----------------------------------------------------------------*/
1148 0 : if (m_poCurChildNode)
1149 0 : return m_poCurChildNode->SetFieldType(eType);
1150 :
1151 0 : return 0;
1152 : }
1153 :
1154 : /**********************************************************************
1155 : * TABINDNode::FindFirst()
1156 : *
1157 : * Start a new search in this node and its children for a key value.
1158 : * If the index is not unique, then FindNext() can be used to return
1159 : * the other values that correspond to the key.
1160 : *
1161 : * Return value:
1162 : * - the key's corresponding record number in the .DAT file (greater than 0)
1163 : * - 0 if the key was not found
1164 : * - or -1 if an error happened
1165 : **********************************************************************/
1166 90 : GInt32 TABINDNode::FindFirst(GByte *pKeyValue)
1167 : {
1168 90 : if (m_poDataBlock == NULL)
1169 : {
1170 : CPLError(CE_Failure, CPLE_AssertionFailed,
1171 0 : "TABINDNode::Search(): Node has not been initialized yet!");
1172 0 : return -1;
1173 : }
1174 :
1175 : /*-----------------------------------------------------------------
1176 : * Unless something has been broken, this method will be called by our
1177 : * parent node after it has established that we are the best candidate
1178 : * to contain the first instance of the key value. So there is no
1179 : * need to look in the previous or next nodes in the chain... if the
1180 : * value is not found in the current node block then it is not present
1181 : * in the index at all.
1182 : *
1183 : * m_nCurIndexEntry will be used to keep track of the search pointer
1184 : * when FindNext() will be used.
1185 : *----------------------------------------------------------------*/
1186 90 : m_nCurIndexEntry = 0;
1187 :
1188 90 : if (m_nSubTreeDepth == 1)
1189 : {
1190 : /*-------------------------------------------------------------
1191 : * Leaf node level... we look for an exact match
1192 : *------------------------------------------------------------*/
1193 841 : while(m_nCurIndexEntry < m_numEntriesInNode)
1194 : {
1195 691 : int nCmpStatus = IndexKeyCmp(pKeyValue, m_nCurIndexEntry);
1196 691 : if (nCmpStatus > 0)
1197 : {
1198 : /* Not there yet... (pKey > IndexEntry) */
1199 661 : m_nCurIndexEntry++;
1200 : }
1201 30 : else if (nCmpStatus == 0)
1202 : {
1203 : /* Found it! Return the record number */
1204 10 : return ReadIndexEntry(m_nCurIndexEntry, NULL);
1205 : }
1206 : else
1207 : {
1208 : /* Item does not exist... return 0 */
1209 20 : return 0;
1210 : }
1211 : }
1212 : }
1213 : else
1214 : {
1215 : /*-------------------------------------------------------------
1216 : * Index Node: Find the child node that is the best candidate to
1217 : * contain the value
1218 : *
1219 : * In the index tree at the node level, for each node entry inside
1220 : * the parent node, the key value (in the parent) corresponds to
1221 : * the value of the first key that you will find when you access
1222 : * the corresponding child node.
1223 : *
1224 : * This means that to find the child that contains the searched
1225 : * key, we look for the first index key >= pKeyValue and the child
1226 : * node that we are looking for is the one that precedes it.
1227 : *
1228 : * If the first key in the list is >= pKeyValue then this means
1229 : * that the pKeyValue does not exist in our children and we just
1230 : * return 0. We do not bother searching the previous node at the
1231 : * same level since this is the responsibility of our parent.
1232 : *
1233 : * The same way if the last indexkey in this node is < pKeyValue
1234 : * we won't bother searching the next node since this should also
1235 : * be taken care of by our parent.
1236 : *------------------------------------------------------------*/
1237 0 : while(m_nCurIndexEntry < m_numEntriesInNode)
1238 : {
1239 0 : int nCmpStatus = IndexKeyCmp(pKeyValue, m_nCurIndexEntry);
1240 :
1241 0 : if (nCmpStatus > 0 && m_nCurIndexEntry+1 < m_numEntriesInNode)
1242 : {
1243 : /* Not there yet... (pKey > IndexEntry) */
1244 0 : m_nCurIndexEntry++;
1245 : }
1246 : else
1247 : {
1248 : /*-----------------------------------------------------
1249 : * We either found an indexkey >= pKeyValue or reached
1250 : * the last entry in this node... still have to decide
1251 : * what we're going to do...
1252 : *----------------------------------------------------*/
1253 0 : if (nCmpStatus < 0 && m_nCurIndexEntry == 0)
1254 : {
1255 : /*-------------------------------------------------
1256 : * First indexkey in block is > pKeyValue...
1257 : * the key definitely does not exist in our children.
1258 : * However, we still want to drill down the rest of the
1259 : * tree because this function is also used when looking
1260 : * for a node to insert a new value.
1261 : *-------------------------------------------------*/
1262 : // Nothing special to do... just continue processing.
1263 : }
1264 :
1265 : /*-----------------------------------------------------
1266 : * If we found an node for which pKeyValue < indexkey
1267 : * (or pKeyValue <= indexkey for non-unique indexes) then
1268 : * we access the preceding child node.
1269 : *
1270 : * Note that for indexkey == pKeyValue in non-unique indexes
1271 : * we also check in the preceding node because when keys
1272 : * are not unique then there are chances that the requested
1273 : * key could also be found at the end of the preceding node.
1274 : * In this case, if we don't find the key in the preceding
1275 : * node then we'll do a second search in the current node.
1276 : *----------------------------------------------------*/
1277 0 : int numChildrenToVisit=1;
1278 0 : if (m_nCurIndexEntry > 0 &&
1279 : (nCmpStatus < 0 || (nCmpStatus==0 && !m_bUnique)) )
1280 : {
1281 0 : m_nCurIndexEntry--;
1282 0 : if (nCmpStatus == 0)
1283 0 : numChildrenToVisit = 2;
1284 : }
1285 :
1286 : /*-----------------------------------------------------
1287 : * OK, now it's time to load/access the candidate child nodes.
1288 : *----------------------------------------------------*/
1289 0 : int nRetValue = 0;
1290 0 : for(int iChild=0; nRetValue==0 &&
1291 : iChild<numChildrenToVisit; iChild++)
1292 : {
1293 : // If we're doing a second pass then jump to next entry
1294 0 : if (iChild > 0)
1295 0 : m_nCurIndexEntry++;
1296 :
1297 0 : int nChildNodePtr = ReadIndexEntry(m_nCurIndexEntry, NULL);
1298 0 : if (nChildNodePtr == 0)
1299 : {
1300 : /* Invalid child node??? */
1301 0 : nRetValue = 0;
1302 0 : continue;
1303 : }
1304 0 : else if (m_poCurChildNode == NULL)
1305 : {
1306 : /* Child node has never been initialized...do it now!*/
1307 :
1308 0 : m_poCurChildNode = new TABINDNode(m_eAccessMode);
1309 0 : if ( m_poCurChildNode->InitNode(m_fp, nChildNodePtr,
1310 : m_nKeyLength,
1311 : m_nSubTreeDepth-1,
1312 : m_bUnique,
1313 : m_poBlockManagerRef,
1314 : this) != 0 ||
1315 : m_poCurChildNode->SetFieldType(m_eFieldType)!=0)
1316 : {
1317 : // An error happened... and was already reported
1318 0 : return -1;
1319 : }
1320 : }
1321 :
1322 0 : if (m_poCurChildNode->GotoNodePtr(nChildNodePtr) != 0)
1323 : {
1324 : // An error happened and has already been reported
1325 0 : return -1;
1326 : }
1327 :
1328 0 : nRetValue = m_poCurChildNode->FindFirst(pKeyValue);
1329 : }/*for iChild*/
1330 :
1331 0 : return nRetValue;
1332 :
1333 : }/*else*/
1334 :
1335 : }/*while numEntries*/
1336 :
1337 : // No node was found that contains the key value.
1338 : // We should never get here... only leaf nodes should return 0
1339 0 : CPLAssert(FALSE);
1340 0 : return 0;
1341 : }
1342 :
1343 60 : return 0; // Not found
1344 : }
1345 :
1346 : /**********************************************************************
1347 : * TABINDNode::FindNext()
1348 : *
1349 : * Continue the search previously started by FindFirst() in this node
1350 : * and its children for a key value.
1351 : *
1352 : * Return value:
1353 : * - the key's corresponding record number in the .DAT file (greater than 0)
1354 : * - 0 if the key was not found
1355 : * - or -1 if an error happened
1356 : **********************************************************************/
1357 10 : GInt32 TABINDNode::FindNext(GByte *pKeyValue)
1358 : {
1359 10 : if (m_poDataBlock == NULL)
1360 : {
1361 : CPLError(CE_Failure, CPLE_AssertionFailed,
1362 0 : "TABINDNode::Search(): Node has not been initialized yet!");
1363 0 : return -1;
1364 : }
1365 :
1366 : /*-----------------------------------------------------------------
1367 : * m_nCurIndexEntry is the index of the last item that has been
1368 : * returned by FindFirst()/FindNext().
1369 : *----------------------------------------------------------------*/
1370 :
1371 10 : if (m_nSubTreeDepth == 1)
1372 : {
1373 : /*-------------------------------------------------------------
1374 : * Leaf node level... check if the next entry is an exact match
1375 : *------------------------------------------------------------*/
1376 10 : m_nCurIndexEntry++;
1377 10 : if (m_nCurIndexEntry >= m_numEntriesInNode && m_nNextNodePtr > 0)
1378 : {
1379 : // We're at the end of a node ... continue with next node
1380 0 : GotoNodePtr(m_nNextNodePtr);
1381 0 : m_nCurIndexEntry = 0;
1382 : }
1383 :
1384 10 : if (m_nCurIndexEntry < m_numEntriesInNode &&
1385 : IndexKeyCmp(pKeyValue, m_nCurIndexEntry) == 0)
1386 : {
1387 : /* Found it! Return the record number */
1388 0 : return ReadIndexEntry(m_nCurIndexEntry, NULL);
1389 : }
1390 : else
1391 : {
1392 : /* No more items with that key... return 0 */
1393 10 : return 0;
1394 : }
1395 : }
1396 : else
1397 : {
1398 : /*-------------------------------------------------------------
1399 : * Index Node: just pass the search to this child node.
1400 : *------------------------------------------------------------*/
1401 0 : while(m_nCurIndexEntry < m_numEntriesInNode)
1402 : {
1403 0 : if (m_poCurChildNode != NULL)
1404 0 : return m_poCurChildNode->FindNext(pKeyValue);
1405 : }
1406 : }
1407 :
1408 : // No more nodes were found that contain the key value.
1409 0 : return 0;
1410 : }
1411 :
1412 :
1413 : /**********************************************************************
1414 : * TABINDNode::CommitToFile()
1415 : *
1416 : * For write access, write current block and its children to file.
1417 : *
1418 : * note: TABRawBinBlock::CommitToFile() does nothing unless the block has
1419 : * been modified. (it has an internal bModified flag)
1420 : *
1421 : * Returns 0 on success, -1 on error.
1422 : **********************************************************************/
1423 6 : int TABINDNode::CommitToFile()
1424 : {
1425 6 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
1426 : m_poDataBlock == NULL)
1427 0 : return -1;
1428 :
1429 6 : if (m_poCurChildNode)
1430 : {
1431 0 : if (m_poCurChildNode->CommitToFile() != 0)
1432 0 : return -1;
1433 :
1434 0 : m_nSubTreeDepth = m_poCurChildNode->GetSubTreeDepth() + 1;
1435 : }
1436 :
1437 6 : return m_poDataBlock->CommitToFile();
1438 : }
1439 :
1440 : /**********************************************************************
1441 : * TABINDNode::AddEntry()
1442 : *
1443 : * Add an .DAT record entry for pKeyValue in this index
1444 : *
1445 : * nRecordNo is the .DAT record number, record numbers start at 1.
1446 : *
1447 : * In order to insert a new value, the root node first does a FindFirst()
1448 : * that will load the whole tree branch up to the insertion point.
1449 : * Then AddEntry() is recursively called up to the leaf node level for
1450 : * the insertion of the actual value.
1451 : * If the leaf node is full then it will be split and if necessary the
1452 : * split will propagate up in the tree through the pointer that each node
1453 : * has on its parent.
1454 : *
1455 : * If bAddInThisNodeOnly=TRUE, then the entry is added only locally and
1456 : * we do not try to update the child node. This is used when the parent
1457 : * of a node that is being splitted has to be updated.
1458 : *
1459 : * bInsertAfterCurChild forces the insertion to happen immediately after
1460 : * the m_nCurIndexEntry. This works only when bAddInThisNodeOnly=TRUE.
1461 : * The default is to search the node for a an insertion point.
1462 : *
1463 : * Returns 0 on success, -1 on error
1464 : **********************************************************************/
1465 : int TABINDNode::AddEntry(GByte *pKeyValue, GInt32 nRecordNo,
1466 : GBool bAddInThisNodeOnly /*=FALSE*/,
1467 : GBool bInsertAfterCurChild /*=FALSE*/,
1468 80 : GBool bMakeNewEntryCurChild /*=FALSE*/)
1469 : {
1470 80 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
1471 : m_poDataBlock == NULL)
1472 0 : return -1;
1473 :
1474 : /*-----------------------------------------------------------------
1475 : * If I'm the root node, then do a FindFirst() to init all the nodes
1476 : * and to make all of them point ot the insertion point.
1477 : *----------------------------------------------------------------*/
1478 80 : if (m_poParentNodeRef == NULL && !bAddInThisNodeOnly)
1479 : {
1480 80 : if (FindFirst(pKeyValue) < 0)
1481 0 : return -1; // Error happened and has already been reported.
1482 : }
1483 :
1484 80 : if (m_poCurChildNode && !bAddInThisNodeOnly)
1485 : {
1486 0 : CPLAssert(m_nSubTreeDepth > 1);
1487 : /*-------------------------------------------------------------
1488 : * Propagate the call down to our children
1489 : * Note: this recursive call could result in new levels of nodes
1490 : * being added under our feet by SplitRootnode() so it is very
1491 : * important to return right after this call or we might not be
1492 : * able to recognize this node at the end of the call!
1493 : *------------------------------------------------------------*/
1494 0 : return m_poCurChildNode->AddEntry(pKeyValue, nRecordNo);
1495 : }
1496 : else
1497 : {
1498 : /*-------------------------------------------------------------
1499 : * OK, we're a leaf node... this is where the real work happens!!!
1500 : *------------------------------------------------------------*/
1501 80 : CPLAssert(m_nSubTreeDepth == 1 || bAddInThisNodeOnly);
1502 :
1503 : /*-------------------------------------------------------------
1504 : * First thing to do is make sure that there is room for a new
1505 : * entry in this node, and to split it if necessary.
1506 : *------------------------------------------------------------*/
1507 80 : if (GetNumEntries() == GetMaxNumEntries())
1508 : {
1509 0 : if (m_poParentNodeRef == NULL)
1510 : {
1511 : /*-----------------------------------------------------
1512 : * Splitting the root node adds one level to the tree, so
1513 : * after splitting we just redirect the call to our child.
1514 : *----------------------------------------------------*/
1515 0 : if (SplitRootNode() != 0)
1516 0 : return -1; // Error happened and has already been reported
1517 :
1518 0 : CPLAssert(m_poCurChildNode);
1519 0 : CPLAssert(m_nSubTreeDepth > 1);
1520 : return m_poCurChildNode->AddEntry(pKeyValue, nRecordNo,
1521 : bAddInThisNodeOnly,
1522 : bInsertAfterCurChild,
1523 0 : bMakeNewEntryCurChild);
1524 : }
1525 : else
1526 : {
1527 : /*-----------------------------------------------------
1528 : * Splitting a regular node will leave it 50% full.
1529 : *----------------------------------------------------*/
1530 0 : if (SplitNode() != 0)
1531 0 : return -1;
1532 : }
1533 : }
1534 :
1535 : /*-------------------------------------------------------------
1536 : * Insert new key/value at the right position in node.
1537 : *------------------------------------------------------------*/
1538 80 : if (InsertEntry(pKeyValue, nRecordNo,
1539 : bInsertAfterCurChild, bMakeNewEntryCurChild) != 0)
1540 0 : return -1;
1541 : }
1542 :
1543 80 : return 0;
1544 : }
1545 :
1546 : /**********************************************************************
1547 : * TABINDNode::InsertEntry()
1548 : *
1549 : * (private method)
1550 : *
1551 : * Insert a key/value pair in the current node buffer.
1552 : *
1553 : * Returns 0 on success, -1 on error
1554 : **********************************************************************/
1555 : int TABINDNode::InsertEntry(GByte *pKeyValue, GInt32 nRecordNo,
1556 : GBool bInsertAfterCurChild /*=FALSE*/,
1557 80 : GBool bMakeNewEntryCurChild /*=FALSE*/)
1558 : {
1559 80 : int iInsertAt=0;
1560 :
1561 80 : if (GetNumEntries() >= GetMaxNumEntries())
1562 : {
1563 : CPLError(CE_Failure, CPLE_AssertionFailed,
1564 0 : "Node is full! Cannot insert key!");
1565 0 : return -1;
1566 : }
1567 :
1568 : /*-----------------------------------------------------------------
1569 : * Find the spot where the key belongs
1570 : *----------------------------------------------------------------*/
1571 80 : if (bInsertAfterCurChild)
1572 : {
1573 0 : iInsertAt = m_nCurIndexEntry+1;
1574 : }
1575 : else
1576 : {
1577 760 : while(iInsertAt < m_numEntriesInNode)
1578 : {
1579 620 : int nCmpStatus = IndexKeyCmp(pKeyValue, iInsertAt);
1580 620 : if (nCmpStatus <= 0)
1581 : {
1582 20 : break;
1583 : }
1584 600 : iInsertAt++;
1585 : }
1586 : }
1587 :
1588 80 : m_poDataBlock->GotoByteInBlock(12 + iInsertAt*(m_nKeyLength+4));
1589 :
1590 : /*-----------------------------------------------------------------
1591 : * Shift all entries that follow in the array
1592 : *----------------------------------------------------------------*/
1593 80 : if (iInsertAt < m_numEntriesInNode)
1594 : {
1595 : // Since we use memmove() directly, we need to inform
1596 : // m_poDataBlock that the upper limit of the buffer will move
1597 : m_poDataBlock->GotoByteInBlock(12 + (m_numEntriesInNode+1)*
1598 20 : (m_nKeyLength+4));
1599 20 : m_poDataBlock->GotoByteInBlock(12 + iInsertAt*(m_nKeyLength+4));
1600 :
1601 : memmove(m_poDataBlock->GetCurDataPtr()+(m_nKeyLength+4),
1602 : m_poDataBlock->GetCurDataPtr(),
1603 20 : (m_numEntriesInNode-iInsertAt)*(m_nKeyLength+4));
1604 :
1605 : }
1606 :
1607 : /*-----------------------------------------------------------------
1608 : * Write new entry
1609 : *----------------------------------------------------------------*/
1610 80 : m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue);
1611 80 : m_poDataBlock->WriteInt32(nRecordNo);
1612 :
1613 80 : m_numEntriesInNode++;
1614 80 : m_poDataBlock->GotoByteInBlock(0);
1615 80 : m_poDataBlock->WriteInt32(m_numEntriesInNode);
1616 :
1617 80 : if (bMakeNewEntryCurChild)
1618 0 : m_nCurIndexEntry = iInsertAt;
1619 80 : else if (m_nCurIndexEntry >= iInsertAt)
1620 80 : m_nCurIndexEntry++;
1621 :
1622 : /*-----------------------------------------------------------------
1623 : * If we replaced the first entry in the node, then this node's key
1624 : * changes and we have to update the reference in the parent node.
1625 : *----------------------------------------------------------------*/
1626 80 : if (iInsertAt == 0 && m_poParentNodeRef)
1627 : {
1628 0 : if (m_poParentNodeRef->UpdateCurChildEntry(GetNodeKey(),
1629 : GetNodeBlockPtr()) != 0)
1630 0 : return -1;
1631 : }
1632 :
1633 80 : return 0;
1634 : }
1635 :
1636 :
1637 : /**********************************************************************
1638 : * TABINDNode::UpdateCurChildEntry()
1639 : *
1640 : * Update the key for the current child node. This method is called by
1641 : * the child when its first entry (defining its node key) is changed.
1642 : *
1643 : * Returns 0 on success, -1 on error
1644 : **********************************************************************/
1645 0 : int TABINDNode::UpdateCurChildEntry(GByte *pKeyValue, GInt32 nRecordNo)
1646 : {
1647 :
1648 : /*-----------------------------------------------------------------
1649 : * Update current child entry with the info for the first node.
1650 : *
1651 : * For some reason, the key for first entry of the first node of each
1652 : * level has to be set to 0 except for the leaf level.
1653 : *----------------------------------------------------------------*/
1654 0 : m_poDataBlock->GotoByteInBlock(12 + m_nCurIndexEntry*(m_nKeyLength+4));
1655 :
1656 0 : if (m_nCurIndexEntry == 0 && m_nSubTreeDepth > 1 && m_nPrevNodePtr == 0)
1657 : {
1658 0 : m_poDataBlock->WriteZeros(m_nKeyLength);
1659 : }
1660 : else
1661 : {
1662 0 : m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue);
1663 : }
1664 0 : m_poDataBlock->WriteInt32(nRecordNo);
1665 :
1666 0 : return 0;
1667 : }
1668 :
1669 :
1670 :
1671 : /**********************************************************************
1672 : * TABINDNode::UpdateSplitChild()
1673 : *
1674 : * Update the key and/or record ptr information corresponding to the
1675 : * current child node.
1676 : *
1677 : * Returns 0 on success, -1 on error
1678 : **********************************************************************/
1679 : int TABINDNode::UpdateSplitChild(GByte *pKeyValue1, GInt32 nRecordNo1,
1680 : GByte *pKeyValue2, GInt32 nRecordNo2,
1681 0 : int nNewCurChildNo /* 1 or 2 */)
1682 : {
1683 :
1684 : /*-----------------------------------------------------------------
1685 : * Update current child entry with the info for the first node.
1686 : *
1687 : * For some reason, the key for first entry of the first node of each
1688 : * level has to be set to 0 except for the leaf level.
1689 : *----------------------------------------------------------------*/
1690 0 : m_poDataBlock->GotoByteInBlock(12 + m_nCurIndexEntry*(m_nKeyLength+4));
1691 :
1692 0 : if (m_nCurIndexEntry == 0 && m_nSubTreeDepth > 1 && m_nPrevNodePtr == 0)
1693 : {
1694 0 : m_poDataBlock->WriteZeros(m_nKeyLength);
1695 : }
1696 : else
1697 : {
1698 0 : m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue1);
1699 : }
1700 0 : m_poDataBlock->WriteInt32(nRecordNo1);
1701 :
1702 : /*-----------------------------------------------------------------
1703 : * Add an entry for the second node after the current one and ask
1704 : * AddEntry() to update m_nCurIndexEntry if the new node should
1705 : * become the new current child.
1706 : *----------------------------------------------------------------*/
1707 0 : if (AddEntry(pKeyValue2, nRecordNo2,
1708 : TRUE, /* bInThisNodeOnly */
1709 : TRUE, /* bInsertAfterCurChild */
1710 : (nNewCurChildNo==2)) != 0)
1711 : {
1712 0 : return -1;
1713 : }
1714 :
1715 0 : return 0;
1716 : }
1717 :
1718 :
1719 : /**********************************************************************
1720 : * TABINDNode::SplitNode()
1721 : *
1722 : * (private method)
1723 : *
1724 : * Split a node, update the references in the parent node, etc.
1725 : * Note that Root Nodes cannot be split using this method... SplitRootNode()
1726 : * should be used instead.
1727 : *
1728 : * The node is split in a way that the current child stays inside this
1729 : * node object, and a new node is created for the other half of the
1730 : * entries. This way, the object references in this node's parent and in its
1731 : * current child all remain valid. The new node is not kept in memory,
1732 : * it is written to disk right away.
1733 : *
1734 : * Returns 0 on success, -1 on error
1735 : **********************************************************************/
1736 0 : int TABINDNode::SplitNode()
1737 : {
1738 0 : TABINDNode *poNewNode=NULL;
1739 : int numInNode1, numInNode2;
1740 :
1741 0 : CPLAssert(m_numEntriesInNode >= 2);
1742 0 : CPLAssert(m_poParentNodeRef); // This func. does not work for root nodes
1743 :
1744 : /*-----------------------------------------------------------------
1745 : * Prepare new node
1746 : *----------------------------------------------------------------*/
1747 0 : numInNode1 = (m_numEntriesInNode+1)/2;
1748 0 : numInNode2 = m_numEntriesInNode - numInNode1;
1749 :
1750 0 : poNewNode = new TABINDNode(m_eAccessMode);
1751 :
1752 0 : if (m_nCurIndexEntry < numInNode1)
1753 : {
1754 : /*-------------------------------------------------------------
1755 : * We will move the second half of the array to a new node.
1756 : *------------------------------------------------------------*/
1757 0 : if (poNewNode->InitNode(m_fp, 0, m_nKeyLength,
1758 : m_nSubTreeDepth, m_bUnique,
1759 : m_poBlockManagerRef, m_poParentNodeRef,
1760 : GetNodeBlockPtr(), m_nNextNodePtr)!= 0 ||
1761 : poNewNode->SetFieldType(m_eFieldType) != 0 )
1762 : {
1763 0 : return -1;
1764 : }
1765 :
1766 : // We have to update m_nPrevNodePtr in the node that used to follow
1767 : // the current node and will now follow the new node.
1768 0 : if (m_nNextNodePtr)
1769 : {
1770 0 : TABINDNode *poTmpNode = new TABINDNode(m_eAccessMode);
1771 0 : if (poTmpNode->InitNode(m_fp, m_nNextNodePtr,
1772 : m_nKeyLength, m_nSubTreeDepth,
1773 : m_bUnique, m_poBlockManagerRef,
1774 : m_poParentNodeRef) != 0 ||
1775 : poTmpNode->SetPrevNodePtr(poNewNode->GetNodeBlockPtr()) != 0 ||
1776 : poTmpNode->CommitToFile() != 0)
1777 : {
1778 0 : return -1;
1779 : }
1780 0 : delete poTmpNode;
1781 : }
1782 :
1783 0 : m_nNextNodePtr = poNewNode->GetNodeBlockPtr();
1784 :
1785 : // Move half the entries to the new block
1786 0 : m_poDataBlock->GotoByteInBlock(12 + numInNode1*(m_nKeyLength+4));
1787 :
1788 0 : if (poNewNode->SetNodeBufferDirectly(numInNode2,
1789 : m_poDataBlock->GetCurDataPtr()) != 0)
1790 0 : return -1;
1791 :
1792 : #ifdef DEBUG
1793 : // Just in case, reset space previously used by moved entries
1794 0 : memset(m_poDataBlock->GetCurDataPtr(), 0, numInNode2*(m_nKeyLength+4));
1795 : #endif
1796 : // And update current node members
1797 0 : m_numEntriesInNode = numInNode1;
1798 :
1799 : // Update parent node with new children info
1800 0 : if (m_poParentNodeRef)
1801 : {
1802 0 : if (m_poParentNodeRef->UpdateSplitChild(GetNodeKey(),
1803 : GetNodeBlockPtr(),
1804 : poNewNode->GetNodeKey(),
1805 : poNewNode->GetNodeBlockPtr(), 1) != 0)
1806 0 : return -1;
1807 : }
1808 :
1809 : }
1810 : else
1811 : {
1812 : /*-------------------------------------------------------------
1813 : * We will move the first half of the array to a new node.
1814 : *------------------------------------------------------------*/
1815 0 : if (poNewNode->InitNode(m_fp, 0, m_nKeyLength,
1816 : m_nSubTreeDepth, m_bUnique,
1817 : m_poBlockManagerRef, m_poParentNodeRef,
1818 : m_nPrevNodePtr, GetNodeBlockPtr())!= 0 ||
1819 : poNewNode->SetFieldType(m_eFieldType) != 0 )
1820 : {
1821 0 : return -1;
1822 : }
1823 :
1824 : // We have to update m_nNextNodePtr in the node that used to precede
1825 : // the current node and will now precede the new node.
1826 0 : if (m_nPrevNodePtr)
1827 : {
1828 0 : TABINDNode *poTmpNode = new TABINDNode(m_eAccessMode);
1829 0 : if (poTmpNode->InitNode(m_fp, m_nPrevNodePtr,
1830 : m_nKeyLength, m_nSubTreeDepth,
1831 : m_bUnique, m_poBlockManagerRef,
1832 : m_poParentNodeRef) != 0 ||
1833 : poTmpNode->SetNextNodePtr(poNewNode->GetNodeBlockPtr()) != 0 ||
1834 : poTmpNode->CommitToFile() != 0)
1835 : {
1836 0 : return -1;
1837 : }
1838 0 : delete poTmpNode;
1839 : }
1840 :
1841 0 : m_nPrevNodePtr = poNewNode->GetNodeBlockPtr();
1842 :
1843 : // Move half the entries to the new block
1844 0 : m_poDataBlock->GotoByteInBlock(12 + 0);
1845 :
1846 0 : if (poNewNode->SetNodeBufferDirectly(numInNode1,
1847 : m_poDataBlock->GetCurDataPtr()) != 0)
1848 0 : return -1;
1849 :
1850 : // Shift the second half of the entries to beginning of buffer
1851 : memmove (m_poDataBlock->GetCurDataPtr(),
1852 : m_poDataBlock->GetCurDataPtr()+numInNode1*(m_nKeyLength+4),
1853 0 : numInNode2*(m_nKeyLength+4));
1854 :
1855 : #ifdef DEBUG
1856 : // Just in case, reset space previously used by moved entries
1857 : memset(m_poDataBlock->GetCurDataPtr()+numInNode2*(m_nKeyLength+4),
1858 0 : 0, numInNode1*(m_nKeyLength+4));
1859 : #endif
1860 :
1861 : // And update current node members
1862 0 : m_numEntriesInNode = numInNode2;
1863 0 : m_nCurIndexEntry -= numInNode1;
1864 :
1865 : // Update parent node with new children info
1866 0 : if (m_poParentNodeRef)
1867 : {
1868 0 : if (m_poParentNodeRef->UpdateSplitChild(poNewNode->GetNodeKey(),
1869 : poNewNode->GetNodeBlockPtr(),
1870 : GetNodeKey(),
1871 : GetNodeBlockPtr(), 2) != 0)
1872 0 : return -1;
1873 : }
1874 :
1875 : }
1876 :
1877 : /*-----------------------------------------------------------------
1878 : * Update current node header
1879 : *----------------------------------------------------------------*/
1880 0 : m_poDataBlock->GotoByteInBlock(0);
1881 0 : m_poDataBlock->WriteInt32(m_numEntriesInNode);
1882 0 : m_poDataBlock->WriteInt32(m_nPrevNodePtr);
1883 0 : m_poDataBlock->WriteInt32(m_nNextNodePtr);
1884 :
1885 : /*-----------------------------------------------------------------
1886 : * Flush and destroy temporary node
1887 : *----------------------------------------------------------------*/
1888 0 : if (poNewNode->CommitToFile() != 0)
1889 0 : return -1;
1890 :
1891 0 : delete poNewNode;
1892 :
1893 0 : return 0;
1894 : }
1895 :
1896 : /**********************************************************************
1897 : * TABINDNode::SplitRootNode()
1898 : *
1899 : * (private method)
1900 : *
1901 : * Split a Root Node.
1902 : * First, a level of nodes must be added to the tree, then the contents
1903 : * of what used to be the root node is moved 1 level down and then that
1904 : * node is split like a regular node.
1905 : *
1906 : * Returns 0 on success, -1 on error
1907 : **********************************************************************/
1908 0 : int TABINDNode::SplitRootNode()
1909 : {
1910 : /*-----------------------------------------------------------------
1911 : * Since a root note cannot be split, we add a level of nodes
1912 : * under it and we'll do the split at that level.
1913 : *----------------------------------------------------------------*/
1914 0 : TABINDNode *poNewNode = new TABINDNode(m_eAccessMode);
1915 :
1916 0 : if (poNewNode->InitNode(m_fp, 0, m_nKeyLength,
1917 : m_nSubTreeDepth, m_bUnique, m_poBlockManagerRef,
1918 : this, 0, 0)!= 0 ||
1919 : poNewNode->SetFieldType(m_eFieldType) != 0)
1920 : {
1921 0 : return -1;
1922 : }
1923 :
1924 : // Move all entries to the new child
1925 0 : m_poDataBlock->GotoByteInBlock(12 + 0);
1926 0 : if (poNewNode->SetNodeBufferDirectly(m_numEntriesInNode,
1927 : m_poDataBlock->GetCurDataPtr(),
1928 : m_nCurIndexEntry,
1929 : m_poCurChildNode) != 0)
1930 : {
1931 0 : return -1;
1932 : }
1933 :
1934 : #ifdef DEBUG
1935 : // Just in case, reset space previously used by moved entries
1936 : memset(m_poDataBlock->GetCurDataPtr(), 0,
1937 0 : m_numEntriesInNode*(m_nKeyLength+4));
1938 : #endif
1939 :
1940 : /*-----------------------------------------------------------------
1941 : * Rewrite current node. (the new root node)
1942 : *----------------------------------------------------------------*/
1943 0 : m_numEntriesInNode = 0;
1944 0 : m_nSubTreeDepth++;
1945 :
1946 0 : m_poDataBlock->GotoByteInBlock(0);
1947 0 : m_poDataBlock->WriteInt32(m_numEntriesInNode);
1948 :
1949 0 : InsertEntry(poNewNode->GetNodeKey(), poNewNode->GetNodeBlockPtr());
1950 :
1951 : /*-----------------------------------------------------------------
1952 : * Keep a reference to the new child
1953 : *----------------------------------------------------------------*/
1954 0 : m_poCurChildNode = poNewNode;
1955 0 : m_nCurIndexEntry = 0;
1956 :
1957 : /*-----------------------------------------------------------------
1958 : * And finally force the child to split itself
1959 : *----------------------------------------------------------------*/
1960 0 : return m_poCurChildNode->SplitNode();
1961 : }
1962 :
1963 : /**********************************************************************
1964 : * TABINDNode::SetNodeBufferDirectly()
1965 : *
1966 : * (private method)
1967 : *
1968 : * Set the key/value part of the nodes buffer and the pointers to the
1969 : * current child direclty. This is used when copying info to a new node
1970 : * in SplitNode() and SplitRootNode()
1971 : *
1972 : * Returns 0 on success, -1 on error
1973 : **********************************************************************/
1974 : int TABINDNode::SetNodeBufferDirectly(int numEntries, GByte *pBuf,
1975 : int nCurIndexEntry/*=0*/,
1976 0 : TABINDNode *poCurChild/*=NULL*/)
1977 : {
1978 0 : m_poDataBlock->GotoByteInBlock(0);
1979 0 : m_poDataBlock->WriteInt32(numEntries);
1980 :
1981 0 : m_numEntriesInNode = numEntries;
1982 :
1983 0 : m_poDataBlock->GotoByteInBlock(12);
1984 0 : if ( m_poDataBlock->WriteBytes(numEntries*(m_nKeyLength+4), pBuf) != 0)
1985 : {
1986 0 : return -1; // An error msg should have been reported already
1987 : }
1988 :
1989 0 : m_nCurIndexEntry = nCurIndexEntry;
1990 0 : m_poCurChildNode = poCurChild;
1991 0 : if (m_poCurChildNode)
1992 0 : m_poCurChildNode->m_poParentNodeRef = this;
1993 :
1994 0 : return 0;
1995 : }
1996 :
1997 : /**********************************************************************
1998 : * TABINDNode::GetNodeKey()
1999 : *
2000 : * Returns a reference to the key for the first entry in the node, which
2001 : * is also the key for this node at the level above it in the tree.
2002 : *
2003 : * Returns NULL if node is empty.
2004 : **********************************************************************/
2005 0 : GByte* TABINDNode::GetNodeKey()
2006 : {
2007 0 : if (m_poDataBlock == NULL || m_numEntriesInNode == 0)
2008 0 : return NULL;
2009 :
2010 0 : m_poDataBlock->GotoByteInBlock(12);
2011 :
2012 0 : return m_poDataBlock->GetCurDataPtr();
2013 : }
2014 :
2015 : /**********************************************************************
2016 : * TABINDNode::SetPrevNodePtr()
2017 : *
2018 : * Update the m_nPrevNodePtr member.
2019 : *
2020 : * Returns 0 on success, -1 on error.
2021 : **********************************************************************/
2022 0 : int TABINDNode::SetPrevNodePtr(GInt32 nPrevNodePtr)
2023 : {
2024 0 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
2025 : m_poDataBlock == NULL)
2026 0 : return -1;
2027 :
2028 0 : if (m_nPrevNodePtr == nPrevNodePtr)
2029 0 : return 0; // Nothing to do.
2030 :
2031 0 : m_poDataBlock->GotoByteInBlock(4);
2032 0 : return m_poDataBlock->WriteInt32(nPrevNodePtr);
2033 : }
2034 :
2035 : /**********************************************************************
2036 : * TABINDNode::SetNextNodePtr()
2037 : *
2038 : * Update the m_nNextNodePtr member.
2039 : *
2040 : * Returns 0 on success, -1 on error.
2041 : **********************************************************************/
2042 0 : int TABINDNode::SetNextNodePtr(GInt32 nNextNodePtr)
2043 : {
2044 0 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
2045 : m_poDataBlock == NULL)
2046 0 : return -1;
2047 :
2048 0 : if (m_nNextNodePtr == nNextNodePtr)
2049 0 : return 0; // Nothing to do.
2050 :
2051 0 : m_poDataBlock->GotoByteInBlock(8);
2052 0 : return m_poDataBlock->WriteInt32(nNextNodePtr);
2053 : }
2054 :
2055 :
2056 :
2057 : /**********************************************************************
2058 : * TABINDNode::Dump()
2059 : *
2060 : * Dump block contents... available only in DEBUG mode.
2061 : **********************************************************************/
2062 : #ifdef DEBUG
2063 :
2064 0 : void TABINDNode::Dump(FILE *fpOut /*=NULL*/)
2065 : {
2066 0 : if (fpOut == NULL)
2067 0 : fpOut = stdout;
2068 :
2069 0 : fprintf(fpOut, "----- TABINDNode::Dump() -----\n");
2070 :
2071 0 : if (m_fp == NULL)
2072 : {
2073 0 : fprintf(fpOut, "Node is not initialized.\n");
2074 : }
2075 : else
2076 : {
2077 0 : fprintf(fpOut, " m_numEntriesInNode = %d\n", m_numEntriesInNode);
2078 0 : fprintf(fpOut, " m_nCurDataBlockPtr = %d\n", m_nCurDataBlockPtr);
2079 0 : fprintf(fpOut, " m_nPrevNodePtr = %d\n", m_nPrevNodePtr);
2080 0 : fprintf(fpOut, " m_nNextNodePtr = %d\n", m_nNextNodePtr);
2081 0 : fprintf(fpOut, " m_nSubTreeDepth = %d\n", m_nSubTreeDepth);
2082 0 : fprintf(fpOut, " m_nKeyLength = %d\n", m_nKeyLength);
2083 : fprintf(fpOut, " m_eFieldtype = %s\n",
2084 0 : TABFIELDTYPE_2_STRING(m_eFieldType) );
2085 0 : if (m_nSubTreeDepth > 0)
2086 : {
2087 : GByte aKeyValBuf[255];
2088 : GInt32 nRecordPtr, nValue;
2089 0 : TABINDNode oChildNode;
2090 :
2091 0 : if (m_nKeyLength > 254)
2092 : {
2093 : CPLError(CE_Failure, CPLE_NotSupported,
2094 0 : "Dump() cannot handle keys longer than 254 chars.");
2095 0 : return;
2096 : }
2097 :
2098 0 : fprintf(fpOut, "\n");
2099 0 : for (int i=0; i<m_numEntriesInNode; i++)
2100 : {
2101 0 : if (m_nSubTreeDepth > 1)
2102 : {
2103 : fprintf(fpOut, " >>>> Child %d of %d <<<<<\n", i,
2104 0 : m_numEntriesInNode);
2105 : }
2106 : else
2107 : {
2108 : fprintf(fpOut, " >>>> Record (leaf) %d of %d <<<<<\n", i,
2109 0 : m_numEntriesInNode);
2110 : }
2111 :
2112 0 : if (m_eFieldType == TABFChar)
2113 : {
2114 0 : nRecordPtr = ReadIndexEntry(i, aKeyValBuf);
2115 0 : fprintf(fpOut, " nRecordPtr = %d\n", nRecordPtr);
2116 0 : fprintf(fpOut, " Char Val= \"%s\"\n", (char*)aKeyValBuf);
2117 : }
2118 0 : else if (m_nKeyLength != 4)
2119 : {
2120 0 : nRecordPtr = ReadIndexEntry(i, aKeyValBuf);
2121 0 : fprintf(fpOut, " nRecordPtr = %d\n", nRecordPtr);
2122 0 : fprintf(fpOut, " Int Value = %d\n", *(GInt32*)aKeyValBuf);
2123 0 : fprintf(fpOut, " Int16 Val= %d\n",*(GInt16*)(aKeyValBuf+2));
2124 0 : fprintf(fpOut, " Hex Val= 0x%8.8x\n",*(GUInt32*)aKeyValBuf);
2125 : }
2126 : else
2127 : {
2128 0 : nRecordPtr = ReadIndexEntry(i, (GByte*)&nValue);
2129 0 : fprintf(fpOut, " nRecordPtr = %d\n", nRecordPtr);
2130 0 : fprintf(fpOut, " Int Value = %d\n", nValue);
2131 0 : fprintf(fpOut, " Hex Value = 0x%8.8x\n",nValue);
2132 : }
2133 :
2134 0 : if (m_nSubTreeDepth > 1)
2135 : {
2136 : oChildNode.InitNode(m_fp, nRecordPtr, m_nKeyLength,
2137 0 : m_nSubTreeDepth - 1, FALSE);
2138 0 : oChildNode.SetFieldType(m_eFieldType);
2139 0 : oChildNode.Dump(fpOut);
2140 : }
2141 0 : }
2142 : }
2143 : }
2144 :
2145 0 : fflush(fpOut);
2146 : }
2147 :
2148 : #endif // DEBUG
|
