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