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 35 : TABINDFile::TABINDFile()
42 : : m_pszFname(nullptr), m_fp(nullptr), m_eAccessMode(TABRead),
43 35 : m_numIndexes(0), m_papoIndexRootNodes(nullptr), m_papbyKeyBuffers(nullptr)
44 : {
45 35 : m_oBlockManager.SetName("IND");
46 35 : m_oBlockManager.SetBlockSize(512);
47 35 : }
48 :
49 : /**********************************************************************
50 : * TABINDFile::~TABINDFile()
51 : *
52 : * Destructor.
53 : **********************************************************************/
54 35 : TABINDFile::~TABINDFile()
55 : {
56 35 : Close();
57 35 : }
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 48 : int TABINDFile::Open(const char *pszFname, const char *pszAccess,
77 : GBool bTestOpenNoError /*=FALSE*/)
78 : {
79 48 : 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 48 : if (STARTS_WITH_CI(pszAccess, "r") && strchr(pszAccess, '+') != nullptr)
92 : {
93 13 : m_eAccessMode = TABReadWrite;
94 13 : pszAccess = "rb+";
95 : }
96 35 : else if (STARTS_WITH_CI(pszAccess, "r"))
97 : {
98 19 : m_eAccessMode = TABRead;
99 19 : 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 48 : m_pszFname = CPLStrdup(pszFname);
117 :
118 48 : const int nLen = static_cast<int>(strlen(m_pszFname));
119 48 : if (nLen > 4 && !EQUAL(m_pszFname + nLen - 4, ".IND"))
120 3 : strcpy(m_pszFname + nLen - 4, ".ind");
121 :
122 : #ifndef _WIN32
123 48 : TABAdjustFilenameExtension(m_pszFname);
124 : #endif
125 :
126 : /*-----------------------------------------------------------------
127 : * Open file
128 : *----------------------------------------------------------------*/
129 48 : m_fp = VSIFOpenL(m_pszFname, pszAccess);
130 :
131 48 : 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 48 : m_oBlockManager.Reset();
146 48 : 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 80 : if ((m_eAccessMode == TABRead || m_eAccessMode == TABReadWrite) &&
153 32 : 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 48 : 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 48 : 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 83 : int TABINDFile::Close()
186 : {
187 83 : if (m_fp == nullptr)
188 35 : return 0;
189 :
190 : /*-----------------------------------------------------------------
191 : * In Write Mode, commit all indexes to the file
192 : *----------------------------------------------------------------*/
193 48 : 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 120 : for (int iIndex = 0; iIndex < m_numIndexes; iIndex++)
211 : {
212 72 : if (m_papoIndexRootNodes && m_papoIndexRootNodes[iIndex])
213 72 : delete m_papoIndexRootNodes[iIndex];
214 72 : if (m_papbyKeyBuffers && m_papbyKeyBuffers[iIndex])
215 72 : CPLFree(m_papbyKeyBuffers[iIndex]);
216 : }
217 48 : CPLFree(m_papoIndexRootNodes);
218 48 : m_papoIndexRootNodes = nullptr;
219 48 : CPLFree(m_papbyKeyBuffers);
220 48 : m_papbyKeyBuffers = nullptr;
221 48 : m_numIndexes = 0;
222 :
223 : /*-----------------------------------------------------------------
224 : * Close file
225 : *----------------------------------------------------------------*/
226 48 : VSIFCloseL(m_fp);
227 48 : m_fp = nullptr;
228 :
229 48 : CPLFree(m_pszFname);
230 48 : m_pszFname = nullptr;
231 :
232 48 : 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 32 : int TABINDFile::ReadHeader()
244 : {
245 :
246 32 : CPLAssert(m_fp);
247 32 : 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 32 : 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 32 : TABRawBinBlock *poHeaderBlock = new TABRawBinBlock(m_eAccessMode, TRUE);
263 32 : 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 32 : poHeaderBlock->GotoByteInBlock(0);
271 32 : GUInt32 nMagicCookie = poHeaderBlock->ReadInt32();
272 32 : 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 32 : poHeaderBlock->GotoByteInBlock(12);
282 32 : m_numIndexes = poHeaderBlock->ReadInt16();
283 32 : 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 32 : m_papoIndexRootNodes = static_cast<TABINDNode **>(
296 32 : CPLCalloc(m_numIndexes, sizeof(TABINDNode *)));
297 :
298 32 : m_papbyKeyBuffers =
299 32 : static_cast<GByte **>(CPLCalloc(m_numIndexes, sizeof(GByte *)));
300 :
301 : /* First index def. starts at byte 48 */
302 32 : poHeaderBlock->GotoByteInBlock(48);
303 :
304 75 : for (int iIndex = 0; iIndex < m_numIndexes; iIndex++)
305 : {
306 : /*-------------------------------------------------------------
307 : * Read next index definition
308 : *------------------------------------------------------------*/
309 43 : GInt32 nRootNodePtr = poHeaderBlock->ReadInt32();
310 43 : poHeaderBlock->ReadInt16(); // skip... max. num of entries per node
311 43 : int nTreeDepth = poHeaderBlock->ReadByte();
312 43 : int nKeyLength = poHeaderBlock->ReadByte();
313 43 : 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 43 : if (nRootNodePtr > 0)
324 : {
325 43 : m_papoIndexRootNodes[iIndex] = new TABINDNode(m_eAccessMode);
326 43 : if (m_papoIndexRootNodes[iIndex]->InitNode(
327 : m_fp, nRootNodePtr, nKeyLength, nTreeDepth, FALSE,
328 43 : &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 86 : m_papbyKeyBuffers[iIndex] =
338 43 : 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 32 : delete poHeaderBlock;
351 :
352 32 : 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 1088 : int TABINDFile::ValidateIndexNo(int nIndexNumber)
451 : {
452 1088 : 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 1088 : if (nIndexNumber < 1 || nIndexNumber > m_numIndexes ||
460 1088 : m_papoIndexRootNodes == nullptr ||
461 1088 : 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 1088 : 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 2 : int TABINDFile::SetIndexFieldType(int nIndexNumber, TABFieldType eType)
481 : {
482 2 : if (ValidateIndexNo(nIndexNumber) != 0)
483 0 : return -1;
484 :
485 2 : 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 8 : GByte *TABINDFile::BuildKey(int nIndexNumber, double dValue)
605 : {
606 8 : if (ValidateIndexNo(nIndexNumber) != 0)
607 0 : return nullptr;
608 :
609 : const int nKeyLength =
610 8 : m_papoIndexRootNodes[nIndexNumber - 1]->GetKeyLength();
611 8 : CPLAssert(nKeyLength == 8 && sizeof(double) == 8);
612 :
613 : /*-----------------------------------------------------------------
614 : * Convert double and decimal values...
615 : * Reverse the sign of the value, and convert to MSB
616 : *----------------------------------------------------------------*/
617 8 : dValue = -dValue;
618 :
619 : #ifndef CPL_MSB
620 8 : CPL_SWAPDOUBLE(&dValue);
621 : #endif
622 :
623 8 : memcpy(m_papbyKeyBuffers[nIndexNumber - 1],
624 : reinterpret_cast<GByte *>(&dValue), nKeyLength);
625 :
626 8 : return m_papbyKeyBuffers[nIndexNumber - 1];
627 : }
628 :
629 : /**********************************************************************
630 : * TABINDFile::BuildKey()
631 : *
632 : * BuildKey() for LargeInt
633 : **********************************************************************/
634 0 : GByte *TABINDFile::BuildKey(int nIndexNumber, GInt64 nValue)
635 : {
636 0 : if (ValidateIndexNo(nIndexNumber) != 0)
637 0 : return nullptr;
638 :
639 : const int nKeyLength =
640 0 : m_papoIndexRootNodes[nIndexNumber - 1]->GetKeyLength();
641 0 : CPLAssert(nKeyLength == 8 && sizeof(double) == 8);
642 :
643 : #ifndef CPL_MSB
644 0 : CPL_SWAP64PTR(&nValue);
645 : #endif
646 :
647 0 : memcpy(m_papbyKeyBuffers[nIndexNumber - 1],
648 : reinterpret_cast<GByte *>(&nValue), nKeyLength);
649 :
650 0 : return m_papbyKeyBuffers[nIndexNumber - 1];
651 : }
652 :
653 : /**********************************************************************
654 : * TABINDFile::FindFirst()
655 : *
656 : * Search one of the indexes for a key value.
657 : *
658 : * Note that index numbers are positive values starting at 1.
659 : *
660 : * Return value:
661 : * - the key's corresponding record number in the .DAT file (greater than 0)
662 : * - 0 if the key was not found
663 : * - or -1 if an error happened
664 : **********************************************************************/
665 31 : GInt32 TABINDFile::FindFirst(int nIndexNumber, GByte *pKeyValue)
666 : {
667 31 : if (ValidateIndexNo(nIndexNumber) != 0)
668 0 : return -1;
669 :
670 31 : return m_papoIndexRootNodes[nIndexNumber - 1]->FindFirst(pKeyValue);
671 : }
672 :
673 : /**********************************************************************
674 : * TABINDFile::FindNext()
675 : *
676 : * Continue the Search for pKeyValue previously initiated by FindFirst().
677 : * NOTE: FindFirst() MUST have been previously called for this call to
678 : * work...
679 : *
680 : * Note that index numbers are positive values starting at 1.
681 : *
682 : * Return value:
683 : * - the key's corresponding record number in the .DAT file (greater than 0)
684 : * - 0 if the key was not found
685 : * - or -1 if an error happened
686 : **********************************************************************/
687 36 : GInt32 TABINDFile::FindNext(int nIndexNumber, GByte *pKeyValue)
688 : {
689 36 : if (ValidateIndexNo(nIndexNumber) != 0)
690 0 : return -1;
691 :
692 36 : return m_papoIndexRootNodes[nIndexNumber - 1]->FindNext(pKeyValue);
693 : }
694 :
695 : /**********************************************************************
696 : * TABINDFile::CreateIndex()
697 : *
698 : * Create a new index with the specified field type and size.
699 : * Field size applies only to char field type... the other types have a
700 : * predefined key length.
701 : *
702 : * Key length is limited to 128 chars. char fields longer than 128 chars
703 : * will have their key truncated to 128 bytes.
704 : *
705 : * Note that a .IND file can contain only a maximum of 29 indexes.
706 : *
707 : * Returns the new field index on success (greater than 0), or -1 on error.
708 : **********************************************************************/
709 29 : int TABINDFile::CreateIndex(TABFieldType eType, int nFieldSize)
710 : {
711 29 : int i, nNewIndexNo = -1;
712 :
713 29 : if (m_fp == nullptr ||
714 29 : (m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite))
715 0 : return -1;
716 :
717 : // __TODO__
718 : // We'll need more work in TABDATFile::WriteDateTimeField() before
719 : // we can support indexes on fields of type DateTime (see bug #1844)
720 29 : if (eType == TABFDateTime)
721 : {
722 0 : CPLError(CE_Failure, CPLE_AssertionFailed,
723 : "Index on fields of type DateTime not supported yet.");
724 0 : return -1;
725 : }
726 :
727 : /*-----------------------------------------------------------------
728 : * Look for an empty slot in the current array, if there is none
729 : * then extend the array.
730 : *----------------------------------------------------------------*/
731 42 : for (i = 0; m_papoIndexRootNodes && i < m_numIndexes; i++)
732 : {
733 13 : if (m_papoIndexRootNodes[i] == nullptr)
734 : {
735 0 : nNewIndexNo = i;
736 0 : break;
737 : }
738 : }
739 :
740 29 : if (nNewIndexNo == -1 && m_numIndexes >= 29)
741 : {
742 0 : CPLError(CE_Failure, CPLE_AppDefined,
743 : "Cannot add new index to %s. A dataset can contain only a "
744 : "maximum of 29 indexes.",
745 : m_pszFname);
746 0 : return -1;
747 : }
748 :
749 29 : if (nNewIndexNo == -1)
750 : {
751 : /*-------------------------------------------------------------
752 : * Add a slot for new index at the end of the nodes array.
753 : *------------------------------------------------------------*/
754 29 : m_numIndexes++;
755 58 : m_papoIndexRootNodes = static_cast<TABINDNode **>(CPLRealloc(
756 29 : m_papoIndexRootNodes, m_numIndexes * sizeof(TABINDNode *)));
757 :
758 29 : m_papbyKeyBuffers = static_cast<GByte **>(
759 29 : CPLRealloc(m_papbyKeyBuffers, m_numIndexes * sizeof(GByte *)));
760 :
761 29 : nNewIndexNo = m_numIndexes - 1;
762 : }
763 :
764 : /*-----------------------------------------------------------------
765 : * Alloc and init new node
766 : * The call to InitNode() automatically allocates storage space for
767 : * the node in the file.
768 : * New nodes are created with a subtree_depth=1 since they start as
769 : * leaf nodes, i.e. their entries point directly to .DAT records
770 : *----------------------------------------------------------------*/
771 44 : int nKeyLength = ((eType == TABFInteger) ? 4
772 30 : : (eType == TABFSmallInt) ? 2
773 30 : : (eType == TABFLargeInt) ? 8
774 29 : : (eType == TABFFloat) ? 8
775 28 : : (eType == TABFDecimal) ? 8
776 28 : : (eType == TABFDate) ? 4
777 28 : : (eType == TABFTime) ? 4
778 : :
779 : /*(eType == TABFDateTime) ? 8: */
780 28 : (eType == TABFLogical) ? 4
781 14 : : std::min(128, nFieldSize));
782 :
783 29 : m_papoIndexRootNodes[nNewIndexNo] = new TABINDNode(m_eAccessMode);
784 29 : if (m_papoIndexRootNodes[nNewIndexNo]->InitNode(m_fp, 0, nKeyLength,
785 : 1, // subtree depth=1
786 : FALSE, // not unique
787 : &m_oBlockManager, nullptr,
788 29 : 0, 0) != 0)
789 : {
790 : // CPLError has already been called
791 0 : return -1;
792 : }
793 :
794 : // Alloc a temporary key buffer for this index.
795 : // This buffer will be used by the BuildKey() method
796 58 : m_papbyKeyBuffers[nNewIndexNo] =
797 29 : static_cast<GByte *>(CPLCalloc(nKeyLength + 1, sizeof(GByte)));
798 :
799 : // Return 1-based index number
800 29 : return nNewIndexNo + 1;
801 : }
802 :
803 : /**********************************************************************
804 : * TABINDFile::AddEntry()
805 : *
806 : * Add an .DAT record entry for pKeyValue in the specified index.
807 : *
808 : * Note that index numbers are positive values starting at 1.
809 : * nRecordNo is the .DAT record number, record numbers start at 1.
810 : *
811 : * Returns 0 on success, -1 on error
812 : **********************************************************************/
813 494 : int TABINDFile::AddEntry(int nIndexNumber, GByte *pKeyValue, GInt32 nRecordNo)
814 : {
815 988 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
816 494 : ValidateIndexNo(nIndexNumber) != 0)
817 0 : return -1;
818 :
819 494 : return m_papoIndexRootNodes[nIndexNumber - 1]->AddEntry(pKeyValue,
820 494 : nRecordNo);
821 : }
822 :
823 : /**********************************************************************
824 : * TABINDFile::Dump()
825 : *
826 : * Dump block contents... available only in DEBUG mode.
827 : **********************************************************************/
828 : #ifdef DEBUG
829 :
830 0 : void TABINDFile::Dump(FILE *fpOut /*=NULL*/)
831 : {
832 0 : if (fpOut == nullptr)
833 0 : fpOut = stdout;
834 :
835 0 : fprintf(fpOut, "----- TABINDFile::Dump() -----\n");
836 :
837 0 : if (m_fp == nullptr)
838 : {
839 0 : fprintf(fpOut, "File is not opened.\n");
840 : }
841 : else
842 : {
843 0 : fprintf(fpOut, "File is opened: %s\n", m_pszFname);
844 0 : fprintf(fpOut, " m_numIndexes = %d\n", m_numIndexes);
845 0 : for (int i = 0; i < m_numIndexes && m_papoIndexRootNodes; i++)
846 : {
847 0 : if (m_papoIndexRootNodes[i])
848 : {
849 0 : fprintf(fpOut, " ----- Index # %d -----\n", i + 1);
850 0 : m_papoIndexRootNodes[i]->Dump(fpOut);
851 : }
852 : }
853 : }
854 :
855 0 : fflush(fpOut);
856 0 : }
857 :
858 : #endif // DEBUG
859 :
860 : /*=====================================================================
861 : * class TABINDNode
862 : *====================================================================*/
863 :
864 : /**********************************************************************
865 : * TABINDNode::TABINDNode()
866 : *
867 : * Constructor.
868 : **********************************************************************/
869 72 : TABINDNode::TABINDNode(TABAccess eAccessMode /*=TABRead*/)
870 : : m_fp(nullptr), m_eAccessMode(eAccessMode), m_poCurChildNode(nullptr),
871 : m_poParentNodeRef(nullptr), m_poBlockManagerRef(nullptr),
872 : m_nSubTreeDepth(0), m_nKeyLength(0), m_eFieldType(TABFUnknown),
873 : m_bUnique(FALSE), m_nCurDataBlockPtr(0), m_nCurIndexEntry(0),
874 : m_poDataBlock(nullptr), m_numEntriesInNode(0), m_nPrevNodePtr(0),
875 72 : m_nNextNodePtr(0)
876 : {
877 72 : }
878 :
879 : /**********************************************************************
880 : * TABINDNode::~TABINDNode()
881 : *
882 : * Destructor.
883 : **********************************************************************/
884 144 : TABINDNode::~TABINDNode()
885 : {
886 72 : if (m_poCurChildNode)
887 0 : delete m_poCurChildNode;
888 :
889 72 : if (m_poDataBlock)
890 72 : delete m_poDataBlock;
891 72 : }
892 :
893 : /**********************************************************************
894 : * TABINDNode::InitNode()
895 : *
896 : * Init a node... this function can be used either to initialize a new
897 : * node, or to make it point to a new data block in the file.
898 : *
899 : * By default, this call will read the data from the file at the
900 : * specified location if necessary, and leave the object ready to be searched.
901 : *
902 : * In write access, if the block does not exist (i.e. nBlockPtr=0) then a
903 : * new one is created and initialized.
904 : *
905 : * poParentNode is used in write access in order to update the parent node
906 : * when this node becomes full and has to be split.
907 : *
908 : * Returns 0 on success, -1 on error.
909 : **********************************************************************/
910 72 : int TABINDNode::InitNode(VSILFILE *fp, int nBlockPtr, int nKeyLength,
911 : int nSubTreeDepth, GBool bUnique,
912 : TABBinBlockManager *poBlockMgr /*=NULL*/,
913 : TABINDNode *poParentNode /*=NULL*/,
914 : int nPrevNodePtr /*=0*/, int nNextNodePtr /*=0*/)
915 : {
916 : /*-----------------------------------------------------------------
917 : * If the block already points to the right block, then don't do
918 : * anything here.
919 : *----------------------------------------------------------------*/
920 72 : if (m_fp == fp && nBlockPtr > 0 && m_nCurDataBlockPtr == nBlockPtr)
921 0 : return 0;
922 :
923 : // Keep track of some info
924 72 : m_fp = fp;
925 72 : m_nKeyLength = nKeyLength;
926 72 : m_nSubTreeDepth = nSubTreeDepth;
927 72 : m_nCurDataBlockPtr = nBlockPtr;
928 72 : m_bUnique = bUnique;
929 :
930 : // Do not overwrite the following values if we receive NULL (the defaults)
931 72 : if (poBlockMgr)
932 72 : m_poBlockManagerRef = poBlockMgr;
933 72 : if (poParentNode)
934 0 : m_poParentNodeRef = poParentNode;
935 :
936 : // Set some defaults
937 72 : m_numEntriesInNode = 0;
938 72 : m_nPrevNodePtr = nPrevNodePtr;
939 72 : m_nNextNodePtr = nNextNodePtr;
940 :
941 72 : m_nCurIndexEntry = 0;
942 :
943 : /*-----------------------------------------------------------------
944 : * Init RawBinBlock
945 : * The node's buffer has to be created with read/write access since
946 : * the index is a very dynamic structure!
947 : *----------------------------------------------------------------*/
948 72 : if (m_poDataBlock == nullptr)
949 72 : m_poDataBlock = new TABRawBinBlock(TABReadWrite, TRUE);
950 :
951 72 : if ((m_eAccessMode == TABWrite || m_eAccessMode == TABReadWrite) &&
952 29 : nBlockPtr == 0 && m_poBlockManagerRef)
953 : {
954 : /*-------------------------------------------------------------
955 : * Write access: Create and init a new block
956 : *------------------------------------------------------------*/
957 29 : m_nCurDataBlockPtr = m_poBlockManagerRef->AllocNewBlock();
958 29 : m_poDataBlock->InitNewBlock(m_fp, 512, m_nCurDataBlockPtr);
959 :
960 29 : m_poDataBlock->WriteInt32(m_numEntriesInNode);
961 29 : m_poDataBlock->WriteInt32(m_nPrevNodePtr);
962 29 : m_poDataBlock->WriteInt32(m_nNextNodePtr);
963 : }
964 : else
965 : {
966 43 : CPLAssert(m_nCurDataBlockPtr > 0);
967 : /*-------------------------------------------------------------
968 : * Read the data block from the file, applies to read access, or
969 : * to write access (to modify an existing block)
970 : *------------------------------------------------------------*/
971 43 : if (m_poDataBlock->ReadFromFile(m_fp, m_nCurDataBlockPtr, 512) != 0)
972 : {
973 : // CPLError() has already been called.
974 0 : return -1;
975 : }
976 :
977 43 : m_poDataBlock->GotoByteInBlock(0);
978 43 : m_numEntriesInNode = m_poDataBlock->ReadInt32();
979 43 : m_nPrevNodePtr = m_poDataBlock->ReadInt32();
980 43 : m_nNextNodePtr = m_poDataBlock->ReadInt32();
981 : }
982 :
983 : // m_poDataBlock is now positioned at the beginning of the key entries
984 :
985 72 : return 0;
986 : }
987 :
988 : /**********************************************************************
989 : * TABINDNode::GotoNodePtr()
990 : *
991 : * Move to the specified node ptr, and read the new node data from the file.
992 : *
993 : * This is just a cover function on top of InitNode()
994 : **********************************************************************/
995 0 : int TABINDNode::GotoNodePtr(GInt32 nNewNodePtr)
996 : {
997 : // First flush current changes if any.
998 0 : if ((m_eAccessMode == TABWrite || m_eAccessMode == TABReadWrite) &&
999 0 : m_poDataBlock && m_poDataBlock->CommitToFile() != 0)
1000 0 : return -1;
1001 :
1002 0 : CPLAssert(nNewNodePtr % 512 == 0);
1003 :
1004 : // Then move to the requested location.
1005 0 : return InitNode(m_fp, nNewNodePtr, m_nKeyLength, m_nSubTreeDepth,
1006 0 : m_bUnique);
1007 : }
1008 :
1009 : /**********************************************************************
1010 : * TABINDNode::ReadIndexEntry()
1011 : *
1012 : * Read the key value and record/node ptr for the specified index entry
1013 : * inside the current node data.
1014 : *
1015 : * nEntryNo is the 0-based index of the index entry that we are interested
1016 : * in inside the current node.
1017 : *
1018 : * Returns the record/node ptr, and copies the key value inside the
1019 : * buffer pointed to by *pKeyValue... this assumes that *pKeyValue points
1020 : * to a buffer big enough to hold the key value (m_nKeyLength bytes).
1021 : * If pKeyValue == NULL, then this parameter is ignored and the key value
1022 : * is not copied.
1023 : **********************************************************************/
1024 43 : GInt32 TABINDNode::ReadIndexEntry(int nEntryNo, GByte *pKeyValue)
1025 : {
1026 43 : GInt32 nRecordPtr = 0;
1027 43 : if (nEntryNo >= 0 && nEntryNo < m_numEntriesInNode)
1028 : {
1029 43 : if (pKeyValue)
1030 : {
1031 0 : m_poDataBlock->GotoByteInBlock(12 + nEntryNo * (m_nKeyLength + 4));
1032 0 : m_poDataBlock->ReadBytes(m_nKeyLength, pKeyValue);
1033 : }
1034 : else
1035 : {
1036 43 : m_poDataBlock->GotoByteInBlock(12 + nEntryNo * (m_nKeyLength + 4) +
1037 43 : m_nKeyLength);
1038 : }
1039 :
1040 43 : nRecordPtr = m_poDataBlock->ReadInt32();
1041 : }
1042 :
1043 43 : return nRecordPtr;
1044 : }
1045 :
1046 : /**********************************************************************
1047 : * TABINDNode::IndexKeyCmp()
1048 : *
1049 : * Compare the specified index entry with the key value, and
1050 : * return 0 if equal, an integer less than 0 if key is smaller than
1051 : * index entry, and an integer greater than 0 if key is bigger than
1052 : * index entry.
1053 : *
1054 : * nEntryNo is the 0-based index of the index entry that we are interested
1055 : * in inside the current node.
1056 : **********************************************************************/
1057 7429 : int TABINDNode::IndexKeyCmp(const GByte *pKeyValue, int nEntryNo)
1058 : {
1059 7429 : CPLAssert(pKeyValue);
1060 7429 : CPLAssert(nEntryNo >= 0 && nEntryNo < m_numEntriesInNode);
1061 :
1062 7429 : m_poDataBlock->GotoByteInBlock(12 + nEntryNo * (m_nKeyLength + 4));
1063 7429 : CPLAssert(m_nKeyLength <= 255);
1064 : GByte abyKey[255];
1065 7429 : if (m_poDataBlock->ReadBytes(m_nKeyLength, abyKey) != 0)
1066 0 : return -1;
1067 7429 : return memcmp(pKeyValue, abyKey, m_nKeyLength);
1068 : }
1069 :
1070 : /**********************************************************************
1071 : * TABINDNode::SetFieldType()
1072 : *
1073 : * Sets the field type for the current index and recursively set all
1074 : * children as well.
1075 : * This information will then be used in building the key values, etc.
1076 : *
1077 : * Returns 0 on success, -1 on error.
1078 : **********************************************************************/
1079 2 : int TABINDNode::SetFieldType(TABFieldType eType)
1080 : {
1081 2 : if (m_fp == nullptr)
1082 : {
1083 0 : CPLError(CE_Failure, CPLE_AssertionFailed,
1084 : "TABINDNode::SetFieldType(): File has not been opened yet!");
1085 0 : return -1;
1086 : }
1087 :
1088 : /*-----------------------------------------------------------------
1089 : * Validate field type with key length
1090 : *----------------------------------------------------------------*/
1091 2 : if ((eType == TABFInteger && m_nKeyLength != 4) ||
1092 2 : (eType == TABFSmallInt && m_nKeyLength != 2) ||
1093 2 : (eType == TABFLargeInt && m_nKeyLength != 8) ||
1094 2 : (eType == TABFFloat && m_nKeyLength != 8) ||
1095 2 : (eType == TABFDecimal && m_nKeyLength != 8) ||
1096 2 : (eType == TABFDate && m_nKeyLength != 4) ||
1097 2 : (eType == TABFTime && m_nKeyLength != 4) ||
1098 2 : (eType == TABFDateTime && m_nKeyLength != 8) ||
1099 0 : (eType == TABFLogical && m_nKeyLength != 4))
1100 : {
1101 0 : CPLError(CE_Failure, CPLE_IllegalArg,
1102 : "Index key length (%d) does not match field type (%s).",
1103 0 : m_nKeyLength, TABFIELDTYPE_2_STRING(eType));
1104 0 : return -1;
1105 : }
1106 :
1107 2 : m_eFieldType = eType;
1108 :
1109 : /*-----------------------------------------------------------------
1110 : * Pass the field type info to child nodes
1111 : *----------------------------------------------------------------*/
1112 2 : if (m_poCurChildNode)
1113 0 : return m_poCurChildNode->SetFieldType(eType);
1114 :
1115 2 : return 0;
1116 : }
1117 :
1118 : /**********************************************************************
1119 : * TABINDNode::FindFirst()
1120 : *
1121 : * Start a new search in this node and its children for a key value.
1122 : * If the index is not unique, then FindNext() can be used to return
1123 : * the other values that correspond to the key.
1124 : *
1125 : * Return value:
1126 : * - the key's corresponding record number in the .DAT file (greater than 0)
1127 : * - 0 if the key was not found
1128 : * - or -1 if an error happened
1129 : **********************************************************************/
1130 525 : GInt32 TABINDNode::FindFirst(const GByte *pKeyValue)
1131 : {
1132 1050 : std::set<int> oSetVisitedNodePtr;
1133 1050 : return FindFirst(pKeyValue, oSetVisitedNodePtr);
1134 : }
1135 :
1136 525 : GInt32 TABINDNode::FindFirst(const GByte *pKeyValue,
1137 : std::set<int> &oSetVisitedNodePtr)
1138 : {
1139 525 : if (m_poDataBlock == nullptr)
1140 : {
1141 0 : CPLError(CE_Failure, CPLE_AssertionFailed,
1142 : "TABINDNode::Search(): Node has not been initialized yet!");
1143 0 : return -1;
1144 : }
1145 :
1146 : /*-----------------------------------------------------------------
1147 : * Unless something has been broken, this method will be called by our
1148 : * parent node after it has established that we are the best candidate
1149 : * to contain the first instance of the key value. So there is no
1150 : * need to look in the previous or next nodes in the chain... if the
1151 : * value is not found in the current node block then it is not present
1152 : * in the index at all.
1153 : *
1154 : * m_nCurIndexEntry will be used to keep track of the search pointer
1155 : * when FindNext() will be used.
1156 : *----------------------------------------------------------------*/
1157 525 : m_nCurIndexEntry = 0;
1158 :
1159 525 : if (m_nSubTreeDepth == 1)
1160 : {
1161 : /*-------------------------------------------------------------
1162 : * Leaf node level... we look for an exact match
1163 : *------------------------------------------------------------*/
1164 4102 : while (m_nCurIndexEntry < m_numEntriesInNode)
1165 : {
1166 3741 : int nCmpStatus = IndexKeyCmp(pKeyValue, m_nCurIndexEntry);
1167 3741 : if (nCmpStatus > 0)
1168 : {
1169 : /* Not there yet... (pKey > IndexEntry) */
1170 3577 : m_nCurIndexEntry++;
1171 : }
1172 164 : else if (nCmpStatus == 0)
1173 : {
1174 : /* Found it! Return the record number */
1175 33 : return ReadIndexEntry(m_nCurIndexEntry, nullptr);
1176 : }
1177 : else
1178 : {
1179 : /* Item does not exist... return 0 */
1180 131 : return 0;
1181 : }
1182 : }
1183 : }
1184 : else
1185 : {
1186 : /*-------------------------------------------------------------
1187 : * Index Node: Find the child node that is the best candidate to
1188 : * contain the value
1189 : *
1190 : * In the index tree at the node level, for each node entry inside
1191 : * the parent node, the key value (in the parent) corresponds to
1192 : * the value of the first key that you will find when you access
1193 : * the corresponding child node.
1194 : *
1195 : * This means that to find the child that contains the searched
1196 : * key, we look for the first index key >= pKeyValue and the child
1197 : * node that we are looking for is the one that precedes it.
1198 : *
1199 : * If the first key in the list is >= pKeyValue then this means
1200 : * that the pKeyValue does not exist in our children and we just
1201 : * return 0. We do not bother searching the previous node at the
1202 : * same level since this is the responsibility of our parent.
1203 : *
1204 : * The same way if the last indexkey in this node is < pKeyValue
1205 : * we won't bother searching the next node since this should also
1206 : * be taken care of by our parent.
1207 : *------------------------------------------------------------*/
1208 0 : while (m_nCurIndexEntry < m_numEntriesInNode)
1209 : {
1210 0 : int nCmpStatus = IndexKeyCmp(pKeyValue, m_nCurIndexEntry);
1211 :
1212 0 : if (nCmpStatus > 0 && m_nCurIndexEntry + 1 < m_numEntriesInNode)
1213 : {
1214 : /* Not there yet... (pKey > IndexEntry) */
1215 0 : m_nCurIndexEntry++;
1216 : }
1217 : else
1218 : {
1219 : /*-----------------------------------------------------
1220 : * We either found an indexkey >= pKeyValue or reached
1221 : * the last entry in this node... still have to decide
1222 : * what we're going to do...
1223 : *----------------------------------------------------*/
1224 0 : if (nCmpStatus < 0 && m_nCurIndexEntry == 0)
1225 : {
1226 : /*-------------------------------------------------
1227 : * First indexkey in block is > pKeyValue...
1228 : * the key definitely does not exist in our children.
1229 : * However, we still want to drill down the rest of the
1230 : * tree because this function is also used when looking
1231 : * for a node to insert a new value.
1232 : *-------------------------------------------------*/
1233 : // Nothing special to do... just continue processing.
1234 : }
1235 :
1236 : /*-----------------------------------------------------
1237 : * If we found an node for which pKeyValue < indexkey
1238 : * (or pKeyValue <= indexkey for non-unique indexes) then
1239 : * we access the preceding child node.
1240 : *
1241 : * Note that for indexkey == pKeyValue in non-unique indexes
1242 : * we also check in the preceding node because when keys
1243 : * are not unique then there are chances that the requested
1244 : * key could also be found at the end of the preceding node.
1245 : * In this case, if we don't find the key in the preceding
1246 : * node then we'll do a second search in the current node.
1247 : *----------------------------------------------------*/
1248 0 : int numChildrenToVisit = 1;
1249 0 : if (m_nCurIndexEntry > 0 &&
1250 0 : (nCmpStatus < 0 || (nCmpStatus == 0 && !m_bUnique)))
1251 : {
1252 0 : m_nCurIndexEntry--;
1253 0 : if (nCmpStatus == 0)
1254 0 : numChildrenToVisit = 2;
1255 : }
1256 :
1257 : /*-----------------------------------------------------
1258 : * OK, now it is time to load/access the candidate child nodes.
1259 : *----------------------------------------------------*/
1260 0 : int nRetValue = 0;
1261 0 : for (int iChild = 0;
1262 0 : nRetValue == 0 && iChild < numChildrenToVisit; iChild++)
1263 : {
1264 : // If we're doing a second pass then jump to next entry
1265 0 : if (iChild > 0)
1266 0 : m_nCurIndexEntry++;
1267 :
1268 : int nChildNodePtr =
1269 0 : ReadIndexEntry(m_nCurIndexEntry, nullptr);
1270 0 : if (nChildNodePtr <= 0)
1271 : {
1272 : /* Invalid child node??? */
1273 0 : nRetValue = 0;
1274 0 : continue;
1275 : }
1276 0 : else if (oSetVisitedNodePtr.find(nChildNodePtr) !=
1277 0 : oSetVisitedNodePtr.end())
1278 : {
1279 0 : CPLError(CE_Failure, CPLE_AppDefined,
1280 : "Invalid child node pointer structure");
1281 0 : return -1;
1282 : }
1283 0 : else if ((nChildNodePtr % 512) != 0)
1284 : {
1285 0 : CPLError(CE_Failure, CPLE_AppDefined,
1286 : "Invalid child node pointer");
1287 0 : return -1;
1288 : }
1289 0 : else if (m_poCurChildNode == nullptr)
1290 : {
1291 : /* Child node has never been initialized...do it now!*/
1292 :
1293 0 : m_poCurChildNode = new TABINDNode(m_eAccessMode);
1294 0 : if (m_poCurChildNode->InitNode(
1295 : m_fp, nChildNodePtr, m_nKeyLength,
1296 0 : m_nSubTreeDepth - 1, m_bUnique,
1297 0 : m_poBlockManagerRef, this) != 0 ||
1298 0 : m_poCurChildNode->SetFieldType(m_eFieldType) != 0)
1299 : {
1300 : // An error happened... and was already reported
1301 0 : return -1;
1302 : }
1303 : }
1304 :
1305 0 : if (m_poCurChildNode->GotoNodePtr(nChildNodePtr) != 0)
1306 : {
1307 : // An error happened and has already been reported
1308 0 : return -1;
1309 : }
1310 :
1311 0 : oSetVisitedNodePtr.insert(nChildNodePtr);
1312 0 : nRetValue = m_poCurChildNode->FindFirst(pKeyValue,
1313 : oSetVisitedNodePtr);
1314 : } /*for iChild*/
1315 :
1316 0 : return nRetValue;
1317 : } // else
1318 : } // while numEntries
1319 :
1320 : // No node was found that contains the key value.
1321 : // We should never get here... only leaf nodes should return 0
1322 0 : CPLAssert(false);
1323 : return 0;
1324 : }
1325 :
1326 361 : return 0; // Not found
1327 : }
1328 :
1329 : /**********************************************************************
1330 : * TABINDNode::FindNext()
1331 : *
1332 : * Continue the search previously started by FindFirst() in this node
1333 : * and its children for a key value.
1334 : *
1335 : * Return value:
1336 : * - the key's corresponding record number in the .DAT file (greater than 0)
1337 : * - 0 if the key was not found
1338 : * - or -1 if an error happened
1339 : **********************************************************************/
1340 36 : GInt32 TABINDNode::FindNext(GByte *pKeyValue)
1341 : {
1342 36 : if (m_poDataBlock == nullptr)
1343 : {
1344 0 : CPLError(CE_Failure, CPLE_AssertionFailed,
1345 : "TABINDNode::Search(): Node has not been initialized yet!");
1346 0 : return -1;
1347 : }
1348 :
1349 : /*-----------------------------------------------------------------
1350 : * m_nCurIndexEntry is the index of the last item that has been
1351 : * returned by FindFirst()/FindNext().
1352 : *----------------------------------------------------------------*/
1353 :
1354 36 : if (m_nSubTreeDepth == 1)
1355 : {
1356 : /*-------------------------------------------------------------
1357 : * Leaf node level... check if the next entry is an exact match
1358 : *------------------------------------------------------------*/
1359 36 : m_nCurIndexEntry++;
1360 36 : if (m_nCurIndexEntry >= m_numEntriesInNode && m_nNextNodePtr > 0)
1361 : {
1362 : // We're at the end of a node ... continue with next node
1363 0 : GotoNodePtr(m_nNextNodePtr);
1364 0 : m_nCurIndexEntry = 0;
1365 : }
1366 :
1367 58 : if (m_nCurIndexEntry < m_numEntriesInNode &&
1368 22 : IndexKeyCmp(pKeyValue, m_nCurIndexEntry) == 0)
1369 : {
1370 : /* Found it! Return the record number */
1371 10 : return ReadIndexEntry(m_nCurIndexEntry, nullptr);
1372 : }
1373 : else
1374 : {
1375 : /* No more items with that key... return 0 */
1376 26 : return 0;
1377 : }
1378 : }
1379 : else
1380 : {
1381 : /*-------------------------------------------------------------
1382 : * Index Node: just pass the search to this child node.
1383 : *------------------------------------------------------------*/
1384 0 : while (m_nCurIndexEntry < m_numEntriesInNode)
1385 : {
1386 0 : if (m_poCurChildNode != nullptr)
1387 0 : return m_poCurChildNode->FindNext(pKeyValue);
1388 : }
1389 : }
1390 :
1391 : // No more nodes were found that contain the key value.
1392 0 : return 0;
1393 : }
1394 :
1395 : /**********************************************************************
1396 : * TABINDNode::CommitToFile()
1397 : *
1398 : * For write access, write current block and its children to file.
1399 : *
1400 : * note: TABRawBinBlock::CommitToFile() does nothing unless the block has
1401 : * been modified. (it has an internal bModified flag)
1402 : *
1403 : * Returns 0 on success, -1 on error.
1404 : **********************************************************************/
1405 42 : int TABINDNode::CommitToFile()
1406 : {
1407 42 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
1408 42 : m_poDataBlock == nullptr)
1409 0 : return -1;
1410 :
1411 42 : if (m_poCurChildNode)
1412 : {
1413 0 : if (m_poCurChildNode->CommitToFile() != 0)
1414 0 : return -1;
1415 :
1416 0 : m_nSubTreeDepth = m_poCurChildNode->GetSubTreeDepth() + 1;
1417 : }
1418 :
1419 42 : return m_poDataBlock->CommitToFile();
1420 : }
1421 :
1422 : /**********************************************************************
1423 : * TABINDNode::AddEntry()
1424 : *
1425 : * Add an .DAT record entry for pKeyValue in this index
1426 : *
1427 : * nRecordNo is the .DAT record number, record numbers start at 1.
1428 : *
1429 : * In order to insert a new value, the root node first does a FindFirst()
1430 : * that will load the whole tree branch up to the insertion point.
1431 : * Then AddEntry() is recursively called up to the leaf node level for
1432 : * the insertion of the actual value.
1433 : * If the leaf node is full then it will be split and if necessary the
1434 : * split will propagate up in the tree through the pointer that each node
1435 : * has on its parent.
1436 : *
1437 : * If bAddInThisNodeOnly=TRUE, then the entry is added only locally and
1438 : * we do not try to update the child node. This is used when the parent
1439 : * of a node that is being split has to be updated.
1440 : *
1441 : * bInsertAfterCurChild forces the insertion to happen immediately after
1442 : * the m_nCurIndexEntry. This works only when bAddInThisNodeOnly=TRUE.
1443 : * The default is to search the node for a an insertion point.
1444 : *
1445 : * Returns 0 on success, -1 on error
1446 : **********************************************************************/
1447 494 : int TABINDNode::AddEntry(GByte *pKeyValue, GInt32 nRecordNo,
1448 : GBool bAddInThisNodeOnly /*=FALSE*/,
1449 : GBool bInsertAfterCurChild /*=FALSE*/,
1450 : GBool bMakeNewEntryCurChild /*=FALSE*/)
1451 : {
1452 494 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
1453 494 : m_poDataBlock == nullptr)
1454 0 : return -1;
1455 :
1456 : /*-----------------------------------------------------------------
1457 : * If I'm the root node, then do a FindFirst() to init all the nodes
1458 : * and to make all of them point to the insertion point.
1459 : *----------------------------------------------------------------*/
1460 494 : if (m_poParentNodeRef == nullptr && !bAddInThisNodeOnly)
1461 : {
1462 494 : if (FindFirst(pKeyValue) < 0)
1463 0 : return -1; // Error happened and has already been reported.
1464 : }
1465 :
1466 494 : if (m_poCurChildNode && !bAddInThisNodeOnly)
1467 : {
1468 0 : CPLAssert(m_nSubTreeDepth > 1);
1469 : /*-------------------------------------------------------------
1470 : * Propagate the call down to our children
1471 : * Note: this recursive call could result in new levels of nodes
1472 : * being added under our feet by SplitRootnode() so it is very
1473 : * important to return right after this call or we might not be
1474 : * able to recognize this node at the end of the call!
1475 : *------------------------------------------------------------*/
1476 0 : return m_poCurChildNode->AddEntry(pKeyValue, nRecordNo);
1477 : }
1478 : else
1479 : {
1480 : /*-------------------------------------------------------------
1481 : * OK, we're a leaf node... this is where the real work happens!!!
1482 : *------------------------------------------------------------*/
1483 494 : CPLAssert(m_nSubTreeDepth == 1 || bAddInThisNodeOnly);
1484 :
1485 : /*-------------------------------------------------------------
1486 : * First thing to do is make sure that there is room for a new
1487 : * entry in this node, and to split it if necessary.
1488 : *------------------------------------------------------------*/
1489 494 : if (GetNumEntries() == GetMaxNumEntries())
1490 : {
1491 0 : if (m_poParentNodeRef == nullptr)
1492 : {
1493 : /*-----------------------------------------------------
1494 : * Splitting the root node adds one level to the tree, so
1495 : * after splitting we just redirect the call to our child.
1496 : *----------------------------------------------------*/
1497 0 : if (SplitRootNode() != 0)
1498 0 : return -1; // Error happened and has already been reported
1499 :
1500 0 : CPLAssert(m_poCurChildNode);
1501 0 : CPLAssert(m_nSubTreeDepth > 1);
1502 0 : return m_poCurChildNode->AddEntry(
1503 : pKeyValue, nRecordNo, bAddInThisNodeOnly,
1504 0 : bInsertAfterCurChild, bMakeNewEntryCurChild);
1505 : }
1506 : else
1507 : {
1508 : /*-----------------------------------------------------
1509 : * Splitting a regular node will leave it 50% full.
1510 : *----------------------------------------------------*/
1511 0 : if (SplitNode() != 0)
1512 0 : return -1;
1513 : }
1514 : }
1515 :
1516 : /*-------------------------------------------------------------
1517 : * Insert new key/value at the right position in node.
1518 : *------------------------------------------------------------*/
1519 494 : if (InsertEntry(pKeyValue, nRecordNo, bInsertAfterCurChild,
1520 494 : bMakeNewEntryCurChild) != 0)
1521 0 : return -1;
1522 : }
1523 :
1524 494 : return 0;
1525 : }
1526 :
1527 : /**********************************************************************
1528 : * TABINDNode::InsertEntry()
1529 : *
1530 : * (private method)
1531 : *
1532 : * Insert a key/value pair in the current node buffer.
1533 : *
1534 : * Returns 0 on success, -1 on error
1535 : **********************************************************************/
1536 494 : int TABINDNode::InsertEntry(GByte *pKeyValue, GInt32 nRecordNo,
1537 : GBool bInsertAfterCurChild /*=FALSE*/,
1538 : GBool bMakeNewEntryCurChild /*=FALSE*/)
1539 : {
1540 494 : int iInsertAt = 0;
1541 :
1542 494 : if (GetNumEntries() >= GetMaxNumEntries())
1543 : {
1544 0 : CPLError(CE_Failure, CPLE_AssertionFailed,
1545 : "Node is full! Cannot insert key!");
1546 0 : return -1;
1547 : }
1548 :
1549 : /*-----------------------------------------------------------------
1550 : * Find the spot where the key belongs
1551 : *----------------------------------------------------------------*/
1552 494 : if (bInsertAfterCurChild)
1553 : {
1554 0 : iInsertAt = m_nCurIndexEntry + 1;
1555 : }
1556 : else
1557 : {
1558 4024 : while (iInsertAt < m_numEntriesInNode)
1559 : {
1560 3666 : int nCmpStatus = IndexKeyCmp(pKeyValue, iInsertAt);
1561 3666 : if (nCmpStatus <= 0)
1562 : {
1563 136 : break;
1564 : }
1565 3530 : iInsertAt++;
1566 : }
1567 : }
1568 :
1569 494 : m_poDataBlock->GotoByteInBlock(12 + iInsertAt * (m_nKeyLength + 4));
1570 :
1571 : /*-----------------------------------------------------------------
1572 : * Shift all entries that follow in the array
1573 : *----------------------------------------------------------------*/
1574 494 : if (iInsertAt < m_numEntriesInNode)
1575 : {
1576 : // Since we use memmove() directly, we need to inform
1577 : // m_poDataBlock that the upper limit of the buffer will move
1578 136 : m_poDataBlock->GotoByteInBlock(12 + (m_numEntriesInNode + 1) *
1579 136 : (m_nKeyLength + 4));
1580 136 : m_poDataBlock->GotoByteInBlock(12 + iInsertAt * (m_nKeyLength + 4));
1581 :
1582 136 : memmove(m_poDataBlock->GetCurDataPtr() + (m_nKeyLength + 4),
1583 136 : m_poDataBlock->GetCurDataPtr(),
1584 136 : static_cast<size_t>(m_numEntriesInNode - iInsertAt) *
1585 136 : (m_nKeyLength + 4));
1586 : }
1587 :
1588 : /*-----------------------------------------------------------------
1589 : * Write new entry
1590 : *----------------------------------------------------------------*/
1591 494 : m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue);
1592 494 : m_poDataBlock->WriteInt32(nRecordNo);
1593 :
1594 494 : m_numEntriesInNode++;
1595 494 : m_poDataBlock->GotoByteInBlock(0);
1596 494 : m_poDataBlock->WriteInt32(m_numEntriesInNode);
1597 :
1598 494 : if (bMakeNewEntryCurChild)
1599 0 : m_nCurIndexEntry = iInsertAt;
1600 494 : else if (m_nCurIndexEntry >= iInsertAt)
1601 494 : m_nCurIndexEntry++;
1602 :
1603 : /*-----------------------------------------------------------------
1604 : * If we replaced the first entry in the node, then this node's key
1605 : * changes and we have to update the reference in the parent node.
1606 : *----------------------------------------------------------------*/
1607 494 : if (iInsertAt == 0 && m_poParentNodeRef)
1608 : {
1609 0 : if (m_poParentNodeRef->UpdateCurChildEntry(GetNodeKey(),
1610 0 : GetNodeBlockPtr()) != 0)
1611 0 : return -1;
1612 : }
1613 :
1614 494 : return 0;
1615 : }
1616 :
1617 : /**********************************************************************
1618 : * TABINDNode::UpdateCurChildEntry()
1619 : *
1620 : * Update the key for the current child node. This method is called by
1621 : * the child when its first entry (defining its node key) is changed.
1622 : *
1623 : * Returns 0 on success, -1 on error
1624 : **********************************************************************/
1625 0 : int TABINDNode::UpdateCurChildEntry(GByte *pKeyValue, GInt32 nRecordNo)
1626 : {
1627 :
1628 : /*-----------------------------------------------------------------
1629 : * Update current child entry with the info for the first node.
1630 : *
1631 : * For some reason, the key for first entry of the first node of each
1632 : * level has to be set to 0 except for the leaf level.
1633 : *----------------------------------------------------------------*/
1634 0 : m_poDataBlock->GotoByteInBlock(12 + m_nCurIndexEntry * (m_nKeyLength + 4));
1635 :
1636 : int ret;
1637 0 : if (m_nCurIndexEntry == 0 && m_nSubTreeDepth > 1 && m_nPrevNodePtr == 0)
1638 : {
1639 0 : ret = m_poDataBlock->WriteZeros(m_nKeyLength);
1640 : }
1641 : else
1642 : {
1643 0 : ret = m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue);
1644 : }
1645 0 : if (ret == 0)
1646 0 : ret = m_poDataBlock->WriteInt32(nRecordNo);
1647 :
1648 0 : return ret;
1649 : }
1650 :
1651 : /**********************************************************************
1652 : * TABINDNode::UpdateSplitChild()
1653 : *
1654 : * Update the key and/or record ptr information corresponding to the
1655 : * current child node.
1656 : *
1657 : * Returns 0 on success, -1 on error
1658 : **********************************************************************/
1659 0 : int TABINDNode::UpdateSplitChild(GByte *pKeyValue1, GInt32 nRecordNo1,
1660 : GByte *pKeyValue2, GInt32 nRecordNo2,
1661 : int nNewCurChildNo /* 1 or 2 */)
1662 : {
1663 :
1664 : /*-----------------------------------------------------------------
1665 : * Update current child entry with the info for the first node.
1666 : *
1667 : * For some reason, the key for first entry of the first node of each
1668 : * level has to be set to 0 except for the leaf level.
1669 : *----------------------------------------------------------------*/
1670 0 : m_poDataBlock->GotoByteInBlock(12 + m_nCurIndexEntry * (m_nKeyLength + 4));
1671 :
1672 0 : if (m_nCurIndexEntry == 0 && m_nSubTreeDepth > 1 && m_nPrevNodePtr == 0)
1673 : {
1674 0 : m_poDataBlock->WriteZeros(m_nKeyLength);
1675 : }
1676 : else
1677 : {
1678 0 : m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue1);
1679 : }
1680 0 : m_poDataBlock->WriteInt32(nRecordNo1);
1681 :
1682 : /*-----------------------------------------------------------------
1683 : * Add an entry for the second node after the current one and ask
1684 : * AddEntry() to update m_nCurIndexEntry if the new node should
1685 : * become the new current child.
1686 : *----------------------------------------------------------------*/
1687 0 : if (AddEntry(pKeyValue2, nRecordNo2, TRUE, /* bInThisNodeOnly */
1688 : TRUE, /* bInsertAfterCurChild */
1689 0 : (nNewCurChildNo == 2)) != 0)
1690 : {
1691 0 : return -1;
1692 : }
1693 :
1694 0 : return 0;
1695 : }
1696 :
1697 : /**********************************************************************
1698 : * TABINDNode::SplitNode()
1699 : *
1700 : * (private method)
1701 : *
1702 : * Split a node, update the references in the parent node, etc.
1703 : * Note that Root Nodes cannot be split using this method... SplitRootNode()
1704 : * should be used instead.
1705 : *
1706 : * The node is split in a way that the current child stays inside this
1707 : * node object, and a new node is created for the other half of the
1708 : * entries. This way, the object references in this node's parent and in its
1709 : * current child all remain valid. The new node is not kept in memory,
1710 : * it is written to disk right away.
1711 : *
1712 : * Returns 0 on success, -1 on error
1713 : **********************************************************************/
1714 0 : int TABINDNode::SplitNode()
1715 : {
1716 0 : CPLAssert(m_numEntriesInNode >= 2);
1717 0 : CPLAssert(m_poParentNodeRef); // This func. does not work for root nodes
1718 :
1719 : /*-----------------------------------------------------------------
1720 : * Prepare new node
1721 : *----------------------------------------------------------------*/
1722 0 : int numInNode1 = (m_numEntriesInNode + 1) / 2;
1723 0 : int numInNode2 = m_numEntriesInNode - numInNode1;
1724 :
1725 0 : TABINDNode *poNewNode = new TABINDNode(m_eAccessMode);
1726 :
1727 0 : if (m_nCurIndexEntry < numInNode1)
1728 : {
1729 : /*-------------------------------------------------------------
1730 : * We will move the second half of the array to a new node.
1731 : *------------------------------------------------------------*/
1732 0 : if (poNewNode->InitNode(m_fp, 0, m_nKeyLength, m_nSubTreeDepth,
1733 : m_bUnique, m_poBlockManagerRef,
1734 : m_poParentNodeRef, GetNodeBlockPtr(),
1735 0 : m_nNextNodePtr) != 0 ||
1736 0 : poNewNode->SetFieldType(m_eFieldType) != 0)
1737 : {
1738 0 : delete poNewNode;
1739 0 : return -1;
1740 : }
1741 :
1742 : // We have to update m_nPrevNodePtr in the node that used to follow
1743 : // the current node and will now follow the new node.
1744 0 : if (m_nNextNodePtr)
1745 : {
1746 0 : TABINDNode *poTmpNode = new TABINDNode(m_eAccessMode);
1747 0 : if (poTmpNode->InitNode(
1748 : m_fp, m_nNextNodePtr, m_nKeyLength, m_nSubTreeDepth,
1749 0 : m_bUnique, m_poBlockManagerRef, m_poParentNodeRef) != 0 ||
1750 0 : poTmpNode->SetPrevNodePtr(poNewNode->GetNodeBlockPtr()) != 0 ||
1751 0 : poTmpNode->CommitToFile() != 0)
1752 : {
1753 0 : delete poTmpNode;
1754 0 : delete poNewNode;
1755 0 : return -1;
1756 : }
1757 0 : delete poTmpNode;
1758 : }
1759 :
1760 0 : m_nNextNodePtr = poNewNode->GetNodeBlockPtr();
1761 :
1762 : // Move half the entries to the new block
1763 0 : m_poDataBlock->GotoByteInBlock(12 + numInNode1 * (m_nKeyLength + 4));
1764 :
1765 0 : if (poNewNode->SetNodeBufferDirectly(
1766 0 : numInNode2, m_poDataBlock->GetCurDataPtr()) != 0)
1767 : {
1768 0 : delete poNewNode;
1769 0 : return -1;
1770 : }
1771 :
1772 : #ifdef DEBUG
1773 : // Just in case, reset space previously used by moved entries
1774 0 : memset(m_poDataBlock->GetCurDataPtr(), 0,
1775 0 : static_cast<size_t>(numInNode2) * (m_nKeyLength + 4));
1776 : #endif
1777 : // And update current node members
1778 0 : m_numEntriesInNode = numInNode1;
1779 :
1780 : // Update parent node with new children info
1781 0 : if (m_poParentNodeRef)
1782 : {
1783 0 : if (m_poParentNodeRef->UpdateSplitChild(
1784 : GetNodeKey(), GetNodeBlockPtr(), poNewNode->GetNodeKey(),
1785 0 : poNewNode->GetNodeBlockPtr(), 1) != 0)
1786 : {
1787 0 : delete poNewNode;
1788 0 : return -1;
1789 : }
1790 : }
1791 : }
1792 : else
1793 : {
1794 : /*-------------------------------------------------------------
1795 : * We will move the first half of the array to a new node.
1796 : *------------------------------------------------------------*/
1797 0 : if (poNewNode->InitNode(m_fp, 0, m_nKeyLength, m_nSubTreeDepth,
1798 : m_bUnique, m_poBlockManagerRef,
1799 : m_poParentNodeRef, m_nPrevNodePtr,
1800 0 : GetNodeBlockPtr()) != 0 ||
1801 0 : poNewNode->SetFieldType(m_eFieldType) != 0)
1802 : {
1803 0 : delete poNewNode;
1804 0 : return -1;
1805 : }
1806 :
1807 : // We have to update m_nNextNodePtr in the node that used to precede
1808 : // the current node and will now precede the new node.
1809 0 : if (m_nPrevNodePtr)
1810 : {
1811 0 : TABINDNode *poTmpNode = new TABINDNode(m_eAccessMode);
1812 0 : if (poTmpNode->InitNode(
1813 : m_fp, m_nPrevNodePtr, m_nKeyLength, m_nSubTreeDepth,
1814 0 : m_bUnique, m_poBlockManagerRef, m_poParentNodeRef) != 0 ||
1815 0 : poTmpNode->SetNextNodePtr(poNewNode->GetNodeBlockPtr()) != 0 ||
1816 0 : poTmpNode->CommitToFile() != 0)
1817 : {
1818 0 : delete poTmpNode;
1819 0 : delete poNewNode;
1820 0 : return -1;
1821 : }
1822 0 : delete poTmpNode;
1823 : }
1824 :
1825 0 : m_nPrevNodePtr = poNewNode->GetNodeBlockPtr();
1826 :
1827 : // Move half the entries to the new block
1828 0 : m_poDataBlock->GotoByteInBlock(12 + 0);
1829 :
1830 0 : if (poNewNode->SetNodeBufferDirectly(
1831 0 : numInNode1, m_poDataBlock->GetCurDataPtr()) != 0)
1832 : {
1833 0 : delete poNewNode;
1834 0 : return -1;
1835 : }
1836 :
1837 : // Shift the second half of the entries to beginning of buffer
1838 0 : memmove(m_poDataBlock->GetCurDataPtr(),
1839 0 : m_poDataBlock->GetCurDataPtr() +
1840 0 : numInNode1 * (m_nKeyLength + 4),
1841 0 : static_cast<size_t>(numInNode2) * (m_nKeyLength + 4));
1842 :
1843 : #ifdef DEBUG
1844 : // Just in case, reset space previously used by moved entries
1845 0 : memset(m_poDataBlock->GetCurDataPtr() +
1846 0 : static_cast<size_t>(numInNode2) * (m_nKeyLength + 4),
1847 0 : 0, static_cast<size_t>(numInNode1) * (m_nKeyLength + 4));
1848 : #endif
1849 :
1850 : // And update current node members
1851 0 : m_numEntriesInNode = numInNode2;
1852 0 : m_nCurIndexEntry -= numInNode1;
1853 :
1854 : // Update parent node with new children info
1855 0 : if (m_poParentNodeRef)
1856 : {
1857 0 : if (m_poParentNodeRef->UpdateSplitChild(
1858 : poNewNode->GetNodeKey(), poNewNode->GetNodeBlockPtr(),
1859 0 : GetNodeKey(), GetNodeBlockPtr(), 2) != 0)
1860 : {
1861 0 : delete poNewNode;
1862 0 : return -1;
1863 : }
1864 : }
1865 : }
1866 :
1867 : /*-----------------------------------------------------------------
1868 : * Update current node header
1869 : *----------------------------------------------------------------*/
1870 0 : m_poDataBlock->GotoByteInBlock(0);
1871 0 : m_poDataBlock->WriteInt32(m_numEntriesInNode);
1872 0 : m_poDataBlock->WriteInt32(m_nPrevNodePtr);
1873 0 : m_poDataBlock->WriteInt32(m_nNextNodePtr);
1874 :
1875 : /*-----------------------------------------------------------------
1876 : * Flush and destroy temporary node
1877 : *----------------------------------------------------------------*/
1878 0 : if (poNewNode->CommitToFile() != 0)
1879 : {
1880 0 : delete poNewNode;
1881 0 : return -1;
1882 : }
1883 :
1884 0 : delete poNewNode;
1885 :
1886 0 : return 0;
1887 : }
1888 :
1889 : /**********************************************************************
1890 : * TABINDNode::SplitRootNode()
1891 : *
1892 : * (private method)
1893 : *
1894 : * Split a Root Node.
1895 : * First, a level of nodes must be added to the tree, then the contents
1896 : * of what used to be the root node is moved 1 level down and then that
1897 : * node is split like a regular node.
1898 : *
1899 : * Returns 0 on success, -1 on error
1900 : **********************************************************************/
1901 0 : int TABINDNode::SplitRootNode()
1902 : {
1903 : /*-----------------------------------------------------------------
1904 : * Since a root note cannot be split, we add a level of nodes
1905 : * under it and we'll do the split at that level.
1906 : *----------------------------------------------------------------*/
1907 0 : TABINDNode *poNewNode = new TABINDNode(m_eAccessMode);
1908 :
1909 0 : if (poNewNode->InitNode(m_fp, 0, m_nKeyLength, m_nSubTreeDepth, m_bUnique,
1910 0 : m_poBlockManagerRef, this, 0, 0) != 0 ||
1911 0 : poNewNode->SetFieldType(m_eFieldType) != 0)
1912 : {
1913 0 : delete poNewNode;
1914 0 : return -1;
1915 : }
1916 :
1917 : // Move all entries to the new child
1918 0 : m_poDataBlock->GotoByteInBlock(12 + 0);
1919 0 : if (poNewNode->SetNodeBufferDirectly(
1920 0 : m_numEntriesInNode, m_poDataBlock->GetCurDataPtr(),
1921 0 : m_nCurIndexEntry, m_poCurChildNode) != 0)
1922 : {
1923 0 : delete poNewNode;
1924 0 : return -1;
1925 : }
1926 :
1927 : #ifdef DEBUG
1928 : // Just in case, reset space previously used by moved entries
1929 0 : memset(m_poDataBlock->GetCurDataPtr(), 0,
1930 0 : static_cast<size_t>(m_numEntriesInNode) * (m_nKeyLength + 4));
1931 : #endif
1932 :
1933 : /*-----------------------------------------------------------------
1934 : * Rewrite current node. (the new root node)
1935 : *----------------------------------------------------------------*/
1936 0 : m_numEntriesInNode = 0;
1937 0 : m_nSubTreeDepth++;
1938 :
1939 0 : m_poDataBlock->GotoByteInBlock(0);
1940 0 : m_poDataBlock->WriteInt32(m_numEntriesInNode);
1941 :
1942 0 : InsertEntry(poNewNode->GetNodeKey(), poNewNode->GetNodeBlockPtr());
1943 :
1944 : /*-----------------------------------------------------------------
1945 : * Keep a reference to the new child
1946 : *----------------------------------------------------------------*/
1947 0 : m_poCurChildNode = poNewNode;
1948 0 : m_nCurIndexEntry = 0;
1949 :
1950 : /*-----------------------------------------------------------------
1951 : * And finally force the child to split itself
1952 : *----------------------------------------------------------------*/
1953 0 : return m_poCurChildNode->SplitNode();
1954 : }
1955 :
1956 : /**********************************************************************
1957 : * TABINDNode::SetNodeBufferDirectly()
1958 : *
1959 : * (private method)
1960 : *
1961 : * Set the key/value part of the nodes buffer and the pointers to the
1962 : * current child directly. This is used when copying info to a new node
1963 : * in SplitNode() and SplitRootNode()
1964 : *
1965 : * Returns 0 on success, -1 on error
1966 : **********************************************************************/
1967 0 : int TABINDNode::SetNodeBufferDirectly(int numEntries, GByte *pBuf,
1968 : int nCurIndexEntry /*=0*/,
1969 : TABINDNode *poCurChild /*=NULL*/)
1970 : {
1971 0 : m_poDataBlock->GotoByteInBlock(0);
1972 0 : m_poDataBlock->WriteInt32(numEntries);
1973 :
1974 0 : m_numEntriesInNode = numEntries;
1975 :
1976 0 : m_poDataBlock->GotoByteInBlock(12);
1977 0 : if (m_poDataBlock->WriteBytes(numEntries * (m_nKeyLength + 4), pBuf) != 0)
1978 : {
1979 0 : return -1; // An error msg should have been reported already
1980 : }
1981 :
1982 0 : m_nCurIndexEntry = nCurIndexEntry;
1983 0 : m_poCurChildNode = poCurChild;
1984 0 : if (m_poCurChildNode)
1985 0 : m_poCurChildNode->m_poParentNodeRef = this;
1986 :
1987 0 : return 0;
1988 : }
1989 :
1990 : /**********************************************************************
1991 : * TABINDNode::GetNodeKey()
1992 : *
1993 : * Returns a reference to the key for the first entry in the node, which
1994 : * is also the key for this node at the level above it in the tree.
1995 : *
1996 : * Returns NULL if node is empty.
1997 : **********************************************************************/
1998 0 : GByte *TABINDNode::GetNodeKey()
1999 : {
2000 0 : if (m_poDataBlock == nullptr || m_numEntriesInNode == 0)
2001 0 : return nullptr;
2002 :
2003 0 : m_poDataBlock->GotoByteInBlock(12);
2004 :
2005 0 : return m_poDataBlock->GetCurDataPtr();
2006 : }
2007 :
2008 : /**********************************************************************
2009 : * TABINDNode::SetPrevNodePtr()
2010 : *
2011 : * Update the m_nPrevNodePtr member.
2012 : *
2013 : * Returns 0 on success, -1 on error.
2014 : **********************************************************************/
2015 0 : int TABINDNode::SetPrevNodePtr(GInt32 nPrevNodePtr)
2016 : {
2017 0 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
2018 0 : m_poDataBlock == nullptr)
2019 0 : return -1;
2020 :
2021 0 : if (m_nPrevNodePtr == nPrevNodePtr)
2022 0 : return 0; // Nothing to do.
2023 :
2024 0 : m_poDataBlock->GotoByteInBlock(4);
2025 0 : return m_poDataBlock->WriteInt32(nPrevNodePtr);
2026 : }
2027 :
2028 : /**********************************************************************
2029 : * TABINDNode::SetNextNodePtr()
2030 : *
2031 : * Update the m_nNextNodePtr member.
2032 : *
2033 : * Returns 0 on success, -1 on error.
2034 : **********************************************************************/
2035 0 : int TABINDNode::SetNextNodePtr(GInt32 nNextNodePtr)
2036 : {
2037 0 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
2038 0 : m_poDataBlock == nullptr)
2039 0 : return -1;
2040 :
2041 0 : if (m_nNextNodePtr == nNextNodePtr)
2042 0 : return 0; // Nothing to do.
2043 :
2044 0 : m_poDataBlock->GotoByteInBlock(8);
2045 0 : return m_poDataBlock->WriteInt32(nNextNodePtr);
2046 : }
2047 :
2048 : /**********************************************************************
2049 : * TABINDNode::Dump()
2050 : *
2051 : * Dump block contents... available only in DEBUG mode.
2052 : **********************************************************************/
2053 : #ifdef DEBUG
2054 :
2055 0 : void TABINDNode::Dump(FILE *fpOut /*=NULL*/)
2056 : {
2057 0 : if (fpOut == nullptr)
2058 0 : fpOut = stdout;
2059 :
2060 0 : fprintf(fpOut, "----- TABINDNode::Dump() -----\n");
2061 :
2062 0 : if (m_fp == nullptr)
2063 : {
2064 0 : fprintf(fpOut, "Node is not initialized.\n");
2065 : }
2066 : else
2067 : {
2068 0 : fprintf(fpOut, " m_numEntriesInNode = %d\n", m_numEntriesInNode);
2069 0 : fprintf(fpOut, " m_nCurDataBlockPtr = %d\n", m_nCurDataBlockPtr);
2070 0 : fprintf(fpOut, " m_nPrevNodePtr = %d\n", m_nPrevNodePtr);
2071 0 : fprintf(fpOut, " m_nNextNodePtr = %d\n", m_nNextNodePtr);
2072 0 : fprintf(fpOut, " m_nSubTreeDepth = %d\n", m_nSubTreeDepth);
2073 0 : fprintf(fpOut, " m_nKeyLength = %d\n", m_nKeyLength);
2074 0 : fprintf(fpOut, " m_eFieldtype = %s\n",
2075 0 : TABFIELDTYPE_2_STRING(m_eFieldType));
2076 0 : if (m_nSubTreeDepth > 0)
2077 : {
2078 : GByte aKeyValBuf[255];
2079 : GInt32 nRecordPtr, nValue;
2080 0 : TABINDNode oChildNode;
2081 :
2082 0 : if (m_nKeyLength > 254)
2083 : {
2084 0 : CPLError(CE_Failure, CPLE_NotSupported,
2085 : "Dump() cannot handle keys longer than 254 chars.");
2086 0 : return;
2087 : }
2088 :
2089 0 : fprintf(fpOut, "\n");
2090 0 : for (int i = 0; i < m_numEntriesInNode; i++)
2091 : {
2092 0 : if (m_nSubTreeDepth > 1)
2093 : {
2094 0 : fprintf(fpOut, " >>>> Child %d of %d <<<<<\n", i,
2095 : m_numEntriesInNode);
2096 : }
2097 : else
2098 : {
2099 0 : fprintf(fpOut, " >>>> Record (leaf) %d of %d <<<<<\n", i,
2100 : m_numEntriesInNode);
2101 : }
2102 :
2103 0 : if (m_eFieldType == TABFChar)
2104 : {
2105 0 : nRecordPtr = ReadIndexEntry(i, aKeyValBuf);
2106 0 : fprintf(fpOut, " nRecordPtr = %d\n", nRecordPtr);
2107 0 : fprintf(fpOut, " Char Val= \"%s\"\n",
2108 : reinterpret_cast<char *>(aKeyValBuf));
2109 : }
2110 0 : else if (m_nKeyLength != 4)
2111 : {
2112 0 : nRecordPtr = ReadIndexEntry(i, aKeyValBuf);
2113 0 : GInt32 nInt32 = 0;
2114 0 : memcpy(&nInt32, aKeyValBuf, 4);
2115 0 : GInt16 nInt16 = 0;
2116 0 : memcpy(&nInt16, aKeyValBuf + 2, 2);
2117 0 : GUInt32 nUInt32 = 0;
2118 0 : memcpy(&nUInt32, aKeyValBuf, 4);
2119 0 : fprintf(fpOut, " nRecordPtr = %d\n", nRecordPtr);
2120 0 : fprintf(fpOut, " Int Value = %d\n", nInt32);
2121 0 : fprintf(fpOut, " Int16 Val= %d\n", nInt16);
2122 0 : fprintf(fpOut, " Hex Val= 0x%8.8x\n", nUInt32);
2123 : }
2124 : else
2125 : {
2126 : nRecordPtr =
2127 0 : ReadIndexEntry(i, reinterpret_cast<GByte *>(&nValue));
2128 0 : fprintf(fpOut, " nRecordPtr = %d\n", nRecordPtr);
2129 0 : fprintf(fpOut, " Int Value = %d\n", nValue);
2130 0 : fprintf(fpOut, " Hex Value = 0x%8.8x\n", nValue);
2131 : }
2132 :
2133 0 : if (m_nSubTreeDepth > 1)
2134 : {
2135 0 : CPL_IGNORE_RET_VAL(
2136 0 : 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 : }
2142 : }
2143 : }
2144 :
2145 0 : fflush(fpOut);
2146 : }
2147 :
2148 : #endif // DEBUG
|
