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