Line data Source code
1 : /**********************************************************************
2 : *
3 : * Name: mitab_mapindexblock.cpp
4 : * Project: MapInfo TAB Read/Write library
5 : * Language: C++
6 : * Purpose: Implementation of the TABMAPIndexBlock class used to handle
7 : * reading/writing of the .MAP files' index blocks
8 : * Author: Daniel Morissette, dmorissette@dmsolutions.ca
9 : *
10 : **********************************************************************
11 : * Copyright (c) 1999, 2000, 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 <cmath>
21 : #include <cstdlib>
22 : #include <cstring>
23 :
24 : #include <algorithm>
25 :
26 : #include "cpl_conv.h"
27 : #include "cpl_error.h"
28 : #include "cpl_vsi.h"
29 : #include "mitab_priv.h"
30 :
31 : /*=====================================================================
32 : * class TABMAPIndexBlock
33 : *====================================================================*/
34 :
35 : /**********************************************************************
36 : * TABMAPIndexBlock::TABMAPIndexBlock()
37 : *
38 : * Constructor.
39 : **********************************************************************/
40 34493 : TABMAPIndexBlock::TABMAPIndexBlock(TABAccess eAccessMode /*= TABRead*/)
41 : : TABRawBinBlock(eAccessMode, TRUE), m_numEntries(0), m_nMinX(1000000000),
42 : m_nMinY(1000000000), m_nMaxX(-1000000000), m_nMaxY(-1000000000),
43 34493 : m_poBlockManagerRef(nullptr), m_nCurChildIndex(-1), m_poParentRef(nullptr)
44 : {
45 34493 : memset(m_asEntries, 0, sizeof(m_asEntries));
46 34493 : }
47 :
48 : /**********************************************************************
49 : * TABMAPIndexBlock::~TABMAPIndexBlock()
50 : *
51 : * Destructor.
52 : **********************************************************************/
53 68986 : TABMAPIndexBlock::~TABMAPIndexBlock()
54 : {
55 34493 : UnsetCurChild();
56 68986 : }
57 :
58 : /**********************************************************************
59 : * TABMAPIndexBlock::UnsetCurChild()
60 : **********************************************************************/
61 :
62 88676 : void TABMAPIndexBlock::UnsetCurChild()
63 : {
64 88676 : if (m_poCurChild)
65 : {
66 616 : if (m_eAccess == TABWrite || m_eAccess == TABReadWrite)
67 616 : m_poCurChild->CommitToFile();
68 616 : m_poCurChild.reset();
69 : }
70 88676 : m_nCurChildIndex = -1;
71 88676 : }
72 :
73 : /**********************************************************************
74 : * TABMAPIndexBlock::InitBlockFromData()
75 : *
76 : * Perform some initialization on the block after its binary data has
77 : * been set or changed (or loaded from a file).
78 : *
79 : * Returns 0 if successful or -1 if an error happened, in which case
80 : * CPLError() will have been called.
81 : **********************************************************************/
82 34375 : int TABMAPIndexBlock::InitBlockFromData(GByte *pabyBuf, int nBlockSize,
83 : int nSizeUsed,
84 : GBool bMakeCopy /* = TRUE */,
85 : VSILFILE *fpSrc /* = NULL */,
86 : int nOffset /* = 0 */)
87 : {
88 : /*-----------------------------------------------------------------
89 : * First of all, we must call the base class' InitBlockFromData()
90 : *----------------------------------------------------------------*/
91 34375 : const int nStatus = TABRawBinBlock::InitBlockFromData(
92 : pabyBuf, nBlockSize, nSizeUsed, bMakeCopy, fpSrc, nOffset);
93 34375 : if (nStatus != 0)
94 0 : return nStatus;
95 :
96 : /*-----------------------------------------------------------------
97 : * Validate block type
98 : *----------------------------------------------------------------*/
99 34375 : if (m_nBlockType != TABMAP_INDEX_BLOCK)
100 : {
101 0 : CPLError(CE_Failure, CPLE_FileIO,
102 : "InitBlockFromData(): Invalid Block Type: got %d expected %d",
103 : m_nBlockType, TABMAP_INDEX_BLOCK);
104 0 : CPLFree(m_pabyBuf);
105 0 : m_pabyBuf = nullptr;
106 0 : return -1;
107 : }
108 :
109 : /*-----------------------------------------------------------------
110 : * Init member variables
111 : *----------------------------------------------------------------*/
112 34375 : GotoByteInBlock(0x002);
113 34375 : m_numEntries = ReadInt16();
114 :
115 34375 : if (m_numEntries > 0)
116 34375 : ReadAllEntries();
117 :
118 34375 : return 0;
119 : }
120 :
121 : /**********************************************************************
122 : * TABMAPIndexBlock::CommitToFile()
123 : *
124 : * Commit the current state of the binary block to the file to which
125 : * it has been previously attached.
126 : *
127 : * This method makes sure all values are properly set in the map object
128 : * block header and then calls TABRawBinBlock::CommitToFile() to do
129 : * the actual writing to disk.
130 : *
131 : * Returns 0 if successful or -1 if an error happened, in which case
132 : * CPLError() will have been called.
133 : **********************************************************************/
134 12392 : int TABMAPIndexBlock::CommitToFile()
135 : {
136 12392 : if (m_pabyBuf == nullptr)
137 : {
138 0 : CPLError(CE_Failure, CPLE_AssertionFailed,
139 : "CommitToFile(): Block has not been initialized yet!");
140 0 : return -1;
141 : }
142 :
143 : /*-----------------------------------------------------------------
144 : * Commit child first
145 : *----------------------------------------------------------------*/
146 12392 : if (m_poCurChild)
147 : {
148 619 : if (m_poCurChild->CommitToFile() != 0)
149 0 : return -1;
150 : }
151 :
152 : /*-----------------------------------------------------------------
153 : * Nothing to do here if block has not been modified
154 : *----------------------------------------------------------------*/
155 12392 : if (!m_bModified)
156 10385 : return 0;
157 :
158 : /*-----------------------------------------------------------------
159 : * Make sure 4 bytes block header is up to date.
160 : *----------------------------------------------------------------*/
161 2007 : GotoByteInBlock(0x000);
162 :
163 2007 : WriteInt16(TABMAP_INDEX_BLOCK); // Block type code
164 2007 : WriteInt16(static_cast<GInt16>(m_numEntries));
165 :
166 2007 : int nStatus = CPLGetLastErrorType() == CE_Failure ? -1 : 0;
167 :
168 : /*-----------------------------------------------------------------
169 : * Loop through all entries, writing each of them, and calling
170 : * CommitToFile() (recursively) on any child index entries we may
171 : * encounter.
172 : *----------------------------------------------------------------*/
173 24802 : for (int i = 0; nStatus == 0 && i < m_numEntries; i++)
174 : {
175 22795 : nStatus = WriteNextEntry(&(m_asEntries[i]));
176 : }
177 :
178 : /*-----------------------------------------------------------------
179 : * OK, call the base class to write the block to disk.
180 : *----------------------------------------------------------------*/
181 2007 : if (nStatus == 0)
182 : {
183 : #ifdef DEBUG_VERBOSE
184 : CPLDebug("MITAB", "Committing INDEX block to offset %d", m_nFileOffset);
185 : #endif
186 2007 : nStatus = TABRawBinBlock::CommitToFile();
187 : }
188 :
189 2007 : return nStatus;
190 : }
191 :
192 : /**********************************************************************
193 : * TABMAPIndexBlock::InitNewBlock()
194 : *
195 : * Initialize a newly created block so that it knows to which file it
196 : * is attached, its block size, etc . and then perform any specific
197 : * initialization for this block type, including writing a default
198 : * block header, etc. and leave the block ready to receive data.
199 : *
200 : * This is an alternative to calling ReadFromFile() or InitBlockFromData()
201 : * that puts the block in a stable state without loading any initial
202 : * data in it.
203 : *
204 : * Returns 0 if successful or -1 if an error happened, in which case
205 : * CPLError() will have been called.
206 : **********************************************************************/
207 118 : int TABMAPIndexBlock::InitNewBlock(VSILFILE *fpSrc, int nBlockSize,
208 : int nFileOffset /* = 0*/)
209 : {
210 : /*-----------------------------------------------------------------
211 : * Start with the default initialization
212 : *----------------------------------------------------------------*/
213 118 : if (TABRawBinBlock::InitNewBlock(fpSrc, nBlockSize, nFileOffset) != 0)
214 0 : return -1;
215 :
216 : /*-----------------------------------------------------------------
217 : * And then set default values for the block header.
218 : *----------------------------------------------------------------*/
219 118 : m_numEntries = 0;
220 :
221 118 : m_nMinX = 1000000000;
222 118 : m_nMinY = 1000000000;
223 118 : m_nMaxX = -1000000000;
224 118 : m_nMaxY = -1000000000;
225 :
226 118 : if (m_eAccess != TABRead && nFileOffset != 0)
227 : {
228 118 : GotoByteInBlock(0x000);
229 :
230 118 : WriteInt16(TABMAP_INDEX_BLOCK); // Block type code
231 118 : WriteInt16(0); // num. index entries
232 : }
233 :
234 118 : if (CPLGetLastErrorType() == CE_Failure)
235 0 : return -1;
236 :
237 118 : return 0;
238 : }
239 :
240 : /**********************************************************************
241 : * TABMAPIndexBlock::ReadNextEntry()
242 : *
243 : * Read the next index entry from the block and fill the sEntry
244 : * structure.
245 : *
246 : * Returns 0 if successful or -1 if we reached the end of the block.
247 : **********************************************************************/
248 558293 : int TABMAPIndexBlock::ReadNextEntry(TABMAPIndexEntry *psEntry)
249 : {
250 558293 : if (m_nCurPos < 4)
251 0 : GotoByteInBlock(0x004);
252 :
253 558293 : if (m_nCurPos > 4 + (20 * m_numEntries))
254 : {
255 : // End of BLock
256 0 : return -1;
257 : }
258 :
259 558293 : psEntry->XMin = ReadInt32();
260 558293 : psEntry->YMin = ReadInt32();
261 558293 : psEntry->XMax = ReadInt32();
262 558293 : psEntry->YMax = ReadInt32();
263 558293 : psEntry->nBlockPtr = ReadInt32();
264 :
265 558293 : if (CPLGetLastErrorType() == CE_Failure)
266 0 : return -1;
267 :
268 558293 : return 0;
269 : }
270 :
271 : /**********************************************************************
272 : * TABMAPIndexBlock::ReadAllEntries()
273 : *
274 : * Init the block by reading all entries from the data block.
275 : *
276 : * Returns 0 if successful or -1 on error.
277 : **********************************************************************/
278 34375 : int TABMAPIndexBlock::ReadAllEntries()
279 : {
280 34375 : CPLAssert(m_numEntries <= GetMaxEntries());
281 34375 : if (m_numEntries == 0)
282 0 : return 0;
283 :
284 34375 : if (GotoByteInBlock(0x004) != 0)
285 0 : return -1;
286 :
287 592668 : for (int i = 0; i < m_numEntries; i++)
288 : {
289 558293 : if (ReadNextEntry(&(m_asEntries[i])) != 0)
290 0 : return -1;
291 : }
292 :
293 34375 : return 0;
294 : }
295 :
296 : /**********************************************************************
297 : * TABMAPIndexBlock::WriteNextEntry()
298 : *
299 : * Write the sEntry index entry at current position in the block.
300 : *
301 : * Returns 0 if successful or -1 if we reached the end of the block.
302 : **********************************************************************/
303 22795 : int TABMAPIndexBlock::WriteNextEntry(TABMAPIndexEntry *psEntry)
304 : {
305 22795 : if (m_nCurPos < 4)
306 0 : GotoByteInBlock(0x004);
307 :
308 22795 : WriteInt32(psEntry->XMin);
309 22795 : WriteInt32(psEntry->YMin);
310 22795 : WriteInt32(psEntry->XMax);
311 22795 : WriteInt32(psEntry->YMax);
312 22795 : WriteInt32(psEntry->nBlockPtr);
313 :
314 22795 : if (CPLGetLastErrorType() == CE_Failure)
315 0 : return -1;
316 :
317 22795 : return 0;
318 : }
319 :
320 : /**********************************************************************
321 : * TABMAPIndexBlock::GetNumFreeEntries()
322 : *
323 : * Return the number of available entries in this block.
324 : *
325 : * __TODO__ This function could eventually be improved to search
326 : * children leaves as well.
327 : **********************************************************************/
328 1609 : int TABMAPIndexBlock::GetNumFreeEntries()
329 : {
330 1609 : return (m_nBlockSize - 4) / 20 - m_numEntries;
331 : }
332 :
333 : /**********************************************************************
334 : * TABMAPIndexBlock::GetEntry()
335 : *
336 : * Fetch a reference to the requested entry.
337 : *
338 : * @param iIndex index of entry, must be from 0 to GetNumEntries()-1.
339 : *
340 : * @return a reference to the internal copy of the entry, or NULL if out
341 : * of range.
342 : **********************************************************************/
343 414607 : TABMAPIndexEntry *TABMAPIndexBlock::GetEntry(int iIndex)
344 : {
345 414607 : if (iIndex < 0 || iIndex >= m_numEntries)
346 0 : return nullptr;
347 :
348 414607 : return m_asEntries + iIndex;
349 : }
350 :
351 : /**********************************************************************
352 : * TABMAPIndexBlock::GetCurMaxDepth()
353 : *
354 : * Return maximum depth in the currently loaded part of the index tree
355 : **********************************************************************/
356 2200 : int TABMAPIndexBlock::GetCurMaxDepth()
357 : {
358 2200 : if (m_poCurChild)
359 571 : return m_poCurChild->GetCurMaxDepth() + 1;
360 :
361 1629 : return 1; /* No current child... this node counts for one. */
362 : }
363 :
364 : /**********************************************************************
365 : * TABMAPIndexBlock::GetMBR()
366 : *
367 : * Return the MBR for the current block.
368 : **********************************************************************/
369 16237 : void TABMAPIndexBlock::GetMBR(GInt32 &nXMin, GInt32 &nYMin, GInt32 &nXMax,
370 : GInt32 &nYMax)
371 : {
372 16237 : nXMin = m_nMinX;
373 16237 : nYMin = m_nMinY;
374 16237 : nXMax = m_nMaxX;
375 16237 : nYMax = m_nMaxY;
376 16237 : }
377 :
378 : /**********************************************************************
379 : * TABMAPIndexBlock::SetMBR()
380 : *
381 : **********************************************************************/
382 1044 : void TABMAPIndexBlock::SetMBR(GInt32 nXMin, GInt32 nYMin, GInt32 nXMax,
383 : GInt32 nYMax)
384 : {
385 1044 : m_nMinX = nXMin;
386 1044 : m_nMinY = nYMin;
387 1044 : m_nMaxX = nXMax;
388 1044 : m_nMaxY = nYMax;
389 1044 : }
390 :
391 : /**********************************************************************
392 : * TABMAPIndexBlock::InsertEntry()
393 : *
394 : * Add a new entry to this index block. It is assumed that there is at
395 : * least one free slot available, so if the block has to be split then it
396 : * should have been done prior to calling this function.
397 : *
398 : * Returns 0 on success, -1 on error.
399 : **********************************************************************/
400 1117 : int TABMAPIndexBlock::InsertEntry(GInt32 nXMin, GInt32 nYMin, GInt32 nXMax,
401 : GInt32 nYMax, GInt32 nBlockPtr)
402 : {
403 1117 : if (m_eAccess != TABWrite && m_eAccess != TABReadWrite)
404 : {
405 0 : CPLError(
406 : CE_Failure, CPLE_AssertionFailed,
407 : "Failed adding index entry: File not opened for write access.");
408 0 : return -1;
409 : }
410 :
411 1117 : if (GetNumFreeEntries() < 1)
412 : {
413 0 : CPLError(CE_Failure, CPLE_AssertionFailed,
414 : "Current Block Index is full, cannot add new entry.");
415 0 : return -1;
416 : }
417 :
418 : /*-----------------------------------------------------------------
419 : * Update count of entries and store new entry.
420 : *----------------------------------------------------------------*/
421 1117 : m_numEntries++;
422 1117 : CPLAssert(m_numEntries <= GetMaxEntries());
423 :
424 1117 : m_asEntries[m_numEntries - 1].XMin = nXMin;
425 1117 : m_asEntries[m_numEntries - 1].YMin = nYMin;
426 1117 : m_asEntries[m_numEntries - 1].XMax = nXMax;
427 1117 : m_asEntries[m_numEntries - 1].YMax = nYMax;
428 1117 : m_asEntries[m_numEntries - 1].nBlockPtr = nBlockPtr;
429 :
430 1117 : m_bModified = TRUE;
431 :
432 1117 : return 0;
433 : }
434 :
435 : /**********************************************************************
436 : * TABMAPIndexBlock::ChooseSubEntryForInsert()
437 : *
438 : * Select the entry in this index block in which the new entry should
439 : * be inserted. The criteria used is to select the node whose MBR needs
440 : * the least enlargement to include the new entry. We resolve ties by
441 : * choosing the entry with the rectangle of smallest area.
442 : * (This is the ChooseSubtree part of Guttman's "ChooseLeaf" algorithm.)
443 : *
444 : * Returns the index of the best candidate or -1 of node is empty.
445 : **********************************************************************/
446 22519 : int TABMAPIndexBlock::ChooseSubEntryForInsert(GInt32 nXMin, GInt32 nYMin,
447 : GInt32 nXMax, GInt32 nYMax)
448 : {
449 22519 : GInt32 nBestCandidate = -1;
450 :
451 22519 : double dOptimalAreaDiff = 0.0;
452 :
453 22519 : const double dNewEntryArea = MITAB_AREA(nXMin, nYMin, nXMax, nYMax);
454 :
455 385639 : for (GInt32 i = 0; i < m_numEntries; i++)
456 : {
457 363120 : double dAreaDiff = 0.0;
458 363120 : const double dAreaBefore =
459 363120 : MITAB_AREA(m_asEntries[i].XMin, m_asEntries[i].YMin,
460 : m_asEntries[i].XMax, m_asEntries[i].YMax);
461 :
462 : /* Does this entry fully contain the new entry's MBR ?
463 : */
464 363120 : const GBool bIsContained =
465 246297 : nXMin >= m_asEntries[i].XMin && nYMin >= m_asEntries[i].YMin &&
466 609417 : nXMax <= m_asEntries[i].XMax && nYMax <= m_asEntries[i].YMax;
467 :
468 363120 : if (bIsContained)
469 : {
470 : /* If new entry is fully contained in this entry then
471 : * the area difference will be the difference between the area
472 : * of the entry to insert and the area of m_asEntries[i]
473 : *
474 : * The diff value is negative in this case.
475 : */
476 31191 : dAreaDiff = dNewEntryArea - dAreaBefore;
477 : }
478 : else
479 : {
480 : /* Need to calculate the expanded MBR to calculate the area
481 : * difference.
482 : */
483 331929 : GInt32 nXMin2 = std::min(m_asEntries[i].XMin, nXMin);
484 331929 : GInt32 nYMin2 = std::min(m_asEntries[i].YMin, nYMin);
485 331929 : GInt32 nXMax2 = std::max(m_asEntries[i].XMax, nXMax);
486 331929 : GInt32 nYMax2 = std::max(m_asEntries[i].YMax, nYMax);
487 :
488 331929 : dAreaDiff =
489 331929 : MITAB_AREA(nXMin2, nYMin2, nXMax2, nYMax2) - dAreaBefore;
490 : }
491 :
492 : /* Is this a better candidate?
493 : * Note, possible Optimization: In case of tie, we could to pick the
494 : * candidate with the smallest area
495 : */
496 :
497 363120 : if (/* No best candidate yet */
498 : (nBestCandidate == -1)
499 : /* or current candidate is contained and best candidate is not
500 : contained */
501 340601 : || (dAreaDiff < 0 && dOptimalAreaDiff >= 0)
502 : /* or if both are either contained or not contained then use the one
503 : * with the smallest area diff, which means maximum coverage in the
504 : * case of contained rects, or minimum area increase when not
505 : * contained
506 : */
507 856182 : || (((dOptimalAreaDiff < 0 && dAreaDiff < 0) ||
508 302583 : (dOptimalAreaDiff > 0 && dAreaDiff > 0)) &&
509 152436 : std::abs(dAreaDiff) < std::abs(dOptimalAreaDiff)))
510 : {
511 80089 : nBestCandidate = i;
512 80089 : dOptimalAreaDiff = dAreaDiff;
513 : }
514 : }
515 :
516 22519 : return nBestCandidate;
517 : }
518 :
519 : /**********************************************************************
520 : * TABMAPIndexBlock::ChooseLeafForInsert()
521 : *
522 : * Recursively search the tree until we find the best leaf to
523 : * contain the specified object MBR.
524 : *
525 : * Returns the nBlockPtr of the selected leaf node entry (should be a
526 : * ref to a TABMAPObjectBlock) or -1 on error.
527 : *
528 : * After this call, m_poCurChild will be pointing at the selected child
529 : * node, for use by later calls to UpdateLeafEntry()
530 : **********************************************************************/
531 21905 : GInt32 TABMAPIndexBlock::ChooseLeafForInsert(GInt32 nXMin, GInt32 nYMin,
532 : GInt32 nXMax, GInt32 nYMax)
533 : {
534 21905 : GBool bFound = FALSE;
535 :
536 21905 : if (m_numEntries < 0)
537 0 : return -1;
538 :
539 : /*-----------------------------------------------------------------
540 : * Look for the best candidate to contain the new entry
541 : *----------------------------------------------------------------*/
542 :
543 : // Make sure blocks currently in memory are written to disk.
544 : // TODO: Could we avoid deleting m_poCurChild if it is already
545 : // the best candidate for insert?
546 21905 : if (m_poCurChild)
547 : {
548 9762 : m_poCurChild->CommitToFile();
549 9762 : m_poCurChild.reset();
550 9762 : m_nCurChildIndex = -1;
551 : }
552 :
553 21905 : int nBestCandidate = ChooseSubEntryForInsert(nXMin, nYMin, nXMax, nYMax);
554 :
555 21905 : CPLAssert(nBestCandidate != -1);
556 21905 : if (nBestCandidate == -1)
557 0 : return -1; /* This should never happen! */
558 :
559 : // Try to load corresponding child... if it fails then we are
560 : // likely in a leaf node, so we'll add the new entry in the current
561 : // node.
562 :
563 : // Prevent error message if referred block not committed yet.
564 21905 : CPLPushErrorHandler(CPLQuietErrorHandler);
565 :
566 : auto poBlock = std::unique_ptr<TABRawBinBlock>(
567 : TABCreateMAPBlockFromFile(m_fp, m_asEntries[nBestCandidate].nBlockPtr,
568 43810 : m_nBlockSize, TRUE, TABReadWrite));
569 21905 : if (poBlock != nullptr && poBlock->GetBlockClass() == TABMAP_INDEX_BLOCK)
570 : {
571 10343 : m_poCurChild.reset(
572 : cpl::down_cast<TABMAPIndexBlock *>(poBlock.release()));
573 10343 : m_nCurChildIndex = nBestCandidate;
574 10343 : m_poCurChild->SetParentRef(this);
575 10343 : m_poCurChild->SetMAPBlockManagerRef(m_poBlockManagerRef);
576 10343 : bFound = TRUE;
577 : }
578 :
579 21905 : CPLPopErrorHandler();
580 21905 : CPLErrorReset();
581 :
582 21905 : if (bFound)
583 : {
584 : /*-------------------------------------------------------------
585 : * Found a child leaf... pass the call to it.
586 : *------------------------------------------------------------*/
587 10343 : return m_poCurChild->ChooseLeafForInsert(nXMin, nYMin, nXMax, nYMax);
588 : }
589 :
590 : /*-------------------------------------------------------------
591 : * Found no child index node... we must be at the leaf level
592 : * (leaf points at map object data blocks) so we return a ref
593 : * to the TABMAPObjBlock for insertion
594 : *------------------------------------------------------------*/
595 11562 : return m_asEntries[nBestCandidate].nBlockPtr;
596 : }
597 :
598 : /**********************************************************************
599 : * TABMAPIndexBlock::GetCurLeafEntryMBR()
600 : *
601 : * Get the MBR for specified nBlockPtr in the leaf at the end of the
602 : * chain of m_poCurChild refs.
603 : *
604 : * This method requires that the chain of m_poCurChild refs already point
605 : * to a leaf that contains the specified nBlockPtr, it is usually called
606 : * right after ChooseLeafForInsert().
607 : *
608 : * Returns 0 on success, -1 on error.
609 : **********************************************************************/
610 20891 : int TABMAPIndexBlock::GetCurLeafEntryMBR(GInt32 nBlockPtr, GInt32 &nXMin,
611 : GInt32 &nYMin, GInt32 &nXMax,
612 : GInt32 &nYMax)
613 : {
614 20891 : if (m_poCurChild)
615 : {
616 : /* Pass the call down to current child */
617 10150 : return m_poCurChild->GetCurLeafEntryMBR(nBlockPtr, nXMin, nYMin, nXMax,
618 10150 : nYMax);
619 : }
620 :
621 : /* We're at the leaf level, look for the entry */
622 89883 : for (int i = 0; i < m_numEntries; i++)
623 : {
624 89883 : if (m_asEntries[i].nBlockPtr == nBlockPtr)
625 : {
626 : /* Found it. Return its MBR */
627 10741 : nXMin = m_asEntries[i].XMin;
628 10741 : nYMin = m_asEntries[i].YMin;
629 10741 : nXMax = m_asEntries[i].XMax;
630 10741 : nYMax = m_asEntries[i].YMax;
631 :
632 10741 : return 0;
633 : }
634 : }
635 :
636 : /* Not found! This should not happen if method is used properly. */
637 0 : CPLError(CE_Failure, CPLE_AssertionFailed,
638 : "Entry to update not found in GetCurLeafEntryMBR()!");
639 0 : return -1;
640 : }
641 :
642 : /**********************************************************************
643 : * TABMAPIndexBlock::UpdateLeafEntry()
644 : *
645 : * Update the MBR for specified nBlockPtr in the leaf at the end of the
646 : * chain of m_poCurChild refs and update MBR of parents if required.
647 : *
648 : * This method requires that the chain of m_poCurChild refs already point
649 : * to a leaf that contains the specified nBlockPtr, it is usually called
650 : * right after ChooseLeafForInsert().
651 : *
652 : * Returns 0 on success, -1 on error.
653 : **********************************************************************/
654 21911 : int TABMAPIndexBlock::UpdateLeafEntry(GInt32 nBlockPtr, GInt32 nXMin,
655 : GInt32 nYMin, GInt32 nXMax, GInt32 nYMax)
656 : {
657 21911 : if (m_poCurChild)
658 : {
659 : /* Pass the call down to current child */
660 10343 : return m_poCurChild->UpdateLeafEntry(nBlockPtr, nXMin, nYMin, nXMax,
661 10343 : nYMax);
662 : }
663 :
664 : /* We're at the leaf level, look for the entry to update */
665 91085 : for (int i = 0; i < m_numEntries; i++)
666 : {
667 91085 : if (m_asEntries[i].nBlockPtr == nBlockPtr)
668 : {
669 : /* Found it. */
670 11568 : TABMAPIndexEntry *psEntry = &m_asEntries[i];
671 :
672 11568 : if (psEntry->XMin != nXMin || psEntry->YMin != nYMin ||
673 11366 : psEntry->XMax != nXMax || psEntry->YMax != nYMax)
674 : {
675 : /* MBR changed. Update MBR of entry */
676 1394 : psEntry->XMin = nXMin;
677 1394 : psEntry->YMin = nYMin;
678 1394 : psEntry->XMax = nXMax;
679 1394 : psEntry->YMax = nYMax;
680 :
681 1394 : m_bModified = TRUE;
682 :
683 : /* Update MBR of this node and all parents */
684 1394 : RecomputeMBR();
685 : }
686 :
687 11568 : return 0;
688 : }
689 : }
690 :
691 : /* Not found! This should not happen if method is used properly. */
692 0 : CPLError(CE_Failure, CPLE_AssertionFailed,
693 : "Entry to update not found in UpdateLeafEntry()!");
694 0 : return -1;
695 : }
696 :
697 : /**********************************************************************
698 : * TABMAPIndexBlock::AddEntry()
699 : *
700 : * Recursively search the tree until we encounter the best leaf to
701 : * contain the specified object MBR and add the new entry to it.
702 : *
703 : * In the even that the selected leaf node would be full, then it will be
704 : * split and this split can propagate up to its parent, etc.
705 : *
706 : * If bAddInThisNodeOnly=TRUE, then the entry is added only locally and
707 : * we do not try to update the child node. This is used when the parent
708 : * of a node that is being split has to be updated.
709 : *
710 : * Returns 0 on success, -1 on error.
711 : **********************************************************************/
712 732 : int TABMAPIndexBlock::AddEntry(GInt32 nXMin, GInt32 nYMin, GInt32 nXMax,
713 : GInt32 nYMax, GInt32 nBlockPtr,
714 : GBool bAddInThisNodeOnly /*=FALSE*/)
715 : {
716 732 : GBool bFound = FALSE;
717 :
718 732 : if (m_eAccess != TABWrite && m_eAccess != TABReadWrite)
719 : {
720 0 : CPLError(
721 : CE_Failure, CPLE_AssertionFailed,
722 : "Failed adding index entry: File not opened for write access.");
723 0 : return -1;
724 : }
725 :
726 : /*-----------------------------------------------------------------
727 : * Look for the best candidate to contain the new entry
728 : *----------------------------------------------------------------*/
729 :
730 : /*-----------------------------------------------------------------
731 : * If bAddInThisNodeOnly=TRUE then we add the entry only locally
732 : * and do not need to look for the proper leaf to insert it.
733 : *----------------------------------------------------------------*/
734 732 : if (bAddInThisNodeOnly)
735 25 : bFound = TRUE;
736 :
737 732 : if (!bFound && m_numEntries > 0)
738 : {
739 : // Make sure blocks currently in memory are written to disk.
740 614 : if (m_poCurChild)
741 : {
742 211 : m_poCurChild->CommitToFile();
743 211 : m_poCurChild.reset();
744 211 : m_nCurChildIndex = -1;
745 : }
746 :
747 : int nBestCandidate =
748 614 : ChooseSubEntryForInsert(nXMin, nYMin, nXMax, nYMax);
749 :
750 614 : CPLAssert(nBestCandidate != -1);
751 :
752 614 : if (nBestCandidate != -1)
753 : {
754 : // Try to load corresponding child... if it fails then we are
755 : // likely in a leaf node, so we'll add the new entry in the current
756 : // node.
757 :
758 : // Prevent error message if referred block not committed yet.
759 614 : CPLPushErrorHandler(CPLQuietErrorHandler);
760 :
761 : auto poBlock =
762 : std::unique_ptr<TABRawBinBlock>(TABCreateMAPBlockFromFile(
763 : m_fp, m_asEntries[nBestCandidate].nBlockPtr, m_nBlockSize,
764 1228 : TRUE, TABReadWrite));
765 1228 : if (poBlock != nullptr &&
766 614 : poBlock->GetBlockClass() == TABMAP_INDEX_BLOCK)
767 : {
768 240 : m_poCurChild.reset(
769 : cpl::down_cast<TABMAPIndexBlock *>(poBlock.release()));
770 240 : m_nCurChildIndex = nBestCandidate;
771 240 : m_poCurChild->SetParentRef(this);
772 240 : m_poCurChild->SetMAPBlockManagerRef(m_poBlockManagerRef);
773 240 : bFound = TRUE;
774 : }
775 :
776 614 : CPLPopErrorHandler();
777 614 : CPLErrorReset();
778 : }
779 : }
780 :
781 732 : if (bFound && !bAddInThisNodeOnly)
782 : {
783 : /*-------------------------------------------------------------
784 : * Found a child leaf... pass the call to it.
785 : *------------------------------------------------------------*/
786 240 : if (m_poCurChild->AddEntry(nXMin, nYMin, nXMax, nYMax, nBlockPtr) != 0)
787 0 : return -1;
788 : }
789 : else
790 : {
791 : /*-------------------------------------------------------------
792 : * Found no child to store new object... we're likely at the leaf
793 : * level so we'll store new object in current node
794 : *------------------------------------------------------------*/
795 :
796 : /*-------------------------------------------------------------
797 : * First thing to do is make sure that there is room for a new
798 : * entry in this node, and to split it if necessary.
799 : *------------------------------------------------------------*/
800 492 : if (GetNumFreeEntries() < 1)
801 : {
802 19 : if (m_poParentRef == nullptr)
803 : {
804 : /*-----------------------------------------------------
805 : * Splitting the root node adds one level to the tree, so
806 : * after splitting we just redirect the call to the new
807 : * child that's just been created.
808 : *----------------------------------------------------*/
809 6 : if (SplitRootNode(nXMin, nYMin, nXMax, nYMax) != 0)
810 0 : return -1; // Error happened and has already been reported
811 :
812 6 : CPLAssert(m_poCurChild);
813 6 : return m_poCurChild->AddEntry(nXMin, nYMin, nXMax, nYMax,
814 6 : nBlockPtr, TRUE);
815 : }
816 : else
817 : {
818 : /*-----------------------------------------------------
819 : * Splitting a regular node
820 : *----------------------------------------------------*/
821 13 : if (SplitNode(nXMin, nYMin, nXMax, nYMax) != 0)
822 0 : return -1;
823 : }
824 : }
825 :
826 486 : if (InsertEntry(nXMin, nYMin, nXMax, nYMax, nBlockPtr) != 0)
827 0 : return -1;
828 : }
829 :
830 : /*-----------------------------------------------------------------
831 : * Update current node MBR and the reference to it in our parent.
832 : *----------------------------------------------------------------*/
833 726 : RecomputeMBR();
834 :
835 726 : return 0;
836 : }
837 :
838 : /**********************************************************************
839 : * TABMAPIndexBlock::ComputeAreaDiff()
840 : *
841 : * (static method, also used by the TABMAPObjBlock class)
842 : *
843 : * Compute the area difference between two MBRs. Used in the SplitNode
844 : * algorithm to decide to which of the two nodes an entry should be added.
845 : *
846 : * The returned AreaDiff value is positive if NodeMBR has to be enlarged
847 : * and negative if new Entry is fully contained in the NodeMBR.
848 : **********************************************************************/
849 17738 : double TABMAPIndexBlock::ComputeAreaDiff(GInt32 nNodeXMin, GInt32 nNodeYMin,
850 : GInt32 nNodeXMax, GInt32 nNodeYMax,
851 : GInt32 nEntryXMin, GInt32 nEntryYMin,
852 : GInt32 nEntryXMax, GInt32 nEntryYMax)
853 : {
854 17738 : double dAreaDiff = 0.0;
855 :
856 17738 : const double dNodeAreaBefore =
857 17738 : MITAB_AREA(nNodeXMin, nNodeYMin, nNodeXMax, nNodeYMax);
858 :
859 : // Does the node fully contain the new entry's MBR?
860 17738 : const GBool bIsContained =
861 13779 : nEntryXMin >= nNodeXMin && nEntryYMin >= nNodeYMin &&
862 31517 : nEntryXMax <= nNodeXMax && nEntryYMax <= nNodeYMax;
863 :
864 17738 : if (bIsContained)
865 : {
866 : /* If new entry is fully contained in this entry then
867 : * the area difference will be the difference between the area
868 : * of the entry to insert and the area of the node
869 : */
870 6823 : dAreaDiff = MITAB_AREA(nEntryXMin, nEntryYMin, nEntryXMax, nEntryYMax) -
871 : dNodeAreaBefore;
872 : }
873 : else
874 : {
875 : /* Need to calculate the expanded MBR to calculate the area
876 : * difference.
877 : */
878 10915 : nNodeXMin = std::min(nNodeXMin, nEntryXMin);
879 10915 : nNodeYMin = std::min(nNodeYMin, nEntryYMin);
880 10915 : nNodeXMax = std::max(nNodeXMax, nEntryXMax);
881 10915 : nNodeYMax = std::max(nNodeYMax, nEntryYMax);
882 :
883 10915 : dAreaDiff = MITAB_AREA(nNodeXMin, nNodeYMin, nNodeXMax, nNodeYMax) -
884 : dNodeAreaBefore;
885 : }
886 :
887 17738 : return dAreaDiff;
888 : }
889 :
890 : /**********************************************************************
891 : * TABMAPIndexBlock::PickSeedsForSplit()
892 : *
893 : * (static method, also used by the TABMAPObjBlock class)
894 : *
895 : * Pick two seeds to use to start splitting this node.
896 : *
897 : * Guttman's LinearPickSeed:
898 : * - Along each dimension find the entry whose rectangle has the
899 : * highest low side, and the one with the lowest high side
900 : * - Calculate the separation for each pair
901 : * - Normalize the separation by dividing by the extents of the
902 : * corresponding dimension
903 : * - Choose the pair with the greatest normalized separation along
904 : * any dimension
905 : **********************************************************************/
906 272 : int TABMAPIndexBlock::PickSeedsForSplit(
907 : TABMAPIndexEntry *pasEntries, int numEntries, int nSrcCurChildIndex,
908 : GInt32 nNewEntryXMin, GInt32 nNewEntryYMin, GInt32 nNewEntryXMax,
909 : GInt32 nNewEntryYMax, int &nSeed1, int &nSeed2)
910 : {
911 272 : GInt32 nSrcMinX = 0;
912 272 : GInt32 nSrcMinY = 0;
913 272 : GInt32 nSrcMaxX = 0;
914 272 : GInt32 nSrcMaxY = 0;
915 272 : int nLowestMaxX = -1;
916 272 : int nHighestMinX = -1;
917 272 : int nLowestMaxY = -1;
918 272 : int nHighestMinY = -1;
919 272 : GInt32 nLowestMaxXId = -1;
920 272 : GInt32 nHighestMinXId = -1;
921 272 : GInt32 nLowestMaxYId = -1;
922 272 : GInt32 nHighestMinYId = -1;
923 :
924 272 : nSeed1 = -1;
925 272 : nSeed2 = -1;
926 :
927 : // Along each dimension find the entry whose rectangle has the
928 : // highest low side, and the one with the lowest high side
929 9414 : for (int iEntry = 0; iEntry < numEntries; iEntry++)
930 : {
931 9142 : if (nLowestMaxXId == -1 || pasEntries[iEntry].XMax < nLowestMaxX)
932 : {
933 750 : nLowestMaxX = pasEntries[iEntry].XMax;
934 750 : nLowestMaxXId = iEntry;
935 : }
936 :
937 9142 : if (nHighestMinXId == -1 || pasEntries[iEntry].XMin > nHighestMinX)
938 : {
939 1700 : nHighestMinX = pasEntries[iEntry].XMin;
940 1700 : nHighestMinXId = iEntry;
941 : }
942 :
943 9142 : if (nLowestMaxYId == -1 || pasEntries[iEntry].YMax < nLowestMaxY)
944 : {
945 612 : nLowestMaxY = pasEntries[iEntry].YMax;
946 612 : nLowestMaxYId = iEntry;
947 : }
948 :
949 9142 : if (nHighestMinYId == -1 || pasEntries[iEntry].YMin > nHighestMinY)
950 : {
951 1643 : nHighestMinY = pasEntries[iEntry].YMin;
952 1643 : nHighestMinYId = iEntry;
953 : }
954 :
955 : // Also keep track of MBR of all entries
956 9142 : if (iEntry == 0)
957 : {
958 272 : nSrcMinX = pasEntries[iEntry].XMin;
959 272 : nSrcMinY = pasEntries[iEntry].YMin;
960 272 : nSrcMaxX = pasEntries[iEntry].XMax;
961 272 : nSrcMaxY = pasEntries[iEntry].YMax;
962 : }
963 : else
964 : {
965 8870 : nSrcMinX = std::min(nSrcMinX, pasEntries[iEntry].XMin);
966 8870 : nSrcMinY = std::min(nSrcMinY, pasEntries[iEntry].YMin);
967 8870 : nSrcMaxX = std::max(nSrcMaxX, pasEntries[iEntry].XMax);
968 8870 : nSrcMaxY = std::max(nSrcMaxY, pasEntries[iEntry].YMax);
969 : }
970 : }
971 :
972 : const double dfSrcWidth =
973 272 : std::abs(static_cast<double>(nSrcMaxX) - nSrcMinX);
974 : const double dfSrcHeight =
975 272 : std::abs(static_cast<double>(nSrcMaxY) - nSrcMinY);
976 :
977 : // Calculate the separation for each pair (note that it may be negative
978 : // in case of overlap)
979 : // Normalize the separation by dividing by the extents of the
980 : // corresponding dimension
981 272 : const double dX =
982 : dfSrcWidth == 0.0
983 272 : ? 0.0
984 252 : : (static_cast<double>(nHighestMinX) - nLowestMaxX) / dfSrcWidth;
985 272 : const double dY =
986 : dfSrcHeight == 0.0
987 272 : ? 0.0
988 252 : : (static_cast<double>(nHighestMinY) - nLowestMaxY) / dfSrcHeight;
989 :
990 : // Choose the pair with the greatest normalized separation along
991 : // any dimension
992 272 : if (dX > dY)
993 : {
994 7 : nSeed1 = nHighestMinXId;
995 7 : nSeed2 = nLowestMaxXId;
996 : }
997 : else
998 : {
999 265 : nSeed1 = nHighestMinYId;
1000 265 : nSeed2 = nLowestMaxYId;
1001 : }
1002 :
1003 : // If nSeed1==nSeed2 then just pick any two (giving pref to current child)
1004 272 : if (nSeed1 == nSeed2)
1005 : {
1006 20 : if (nSeed1 != nSrcCurChildIndex && nSrcCurChildIndex != -1)
1007 0 : nSeed1 = nSrcCurChildIndex;
1008 20 : else if (nSeed1 != 0)
1009 0 : nSeed1 = 0;
1010 : else
1011 20 : nSeed1 = 1;
1012 : }
1013 :
1014 : // Decide which of the two seeds best matches the new entry. That seed and
1015 : // the new entry will stay in current node (new entry will be added by the
1016 : // caller later). The other seed will go in the 2nd node
1017 544 : const double dAreaDiff1 = ComputeAreaDiff(
1018 272 : pasEntries[nSeed1].XMin, pasEntries[nSeed1].YMin,
1019 272 : pasEntries[nSeed1].XMax, pasEntries[nSeed1].YMax, nNewEntryXMin,
1020 : nNewEntryYMin, nNewEntryXMax, nNewEntryYMax);
1021 :
1022 544 : const double dAreaDiff2 = ComputeAreaDiff(
1023 272 : pasEntries[nSeed2].XMin, pasEntries[nSeed2].YMin,
1024 272 : pasEntries[nSeed2].XMax, pasEntries[nSeed2].YMax, nNewEntryXMin,
1025 : nNewEntryYMin, nNewEntryXMax, nNewEntryYMax);
1026 :
1027 : /* Note that we want to keep this node's current child in here.
1028 : * Since splitting happens only during an addentry() operation and
1029 : * then both the current child and the New Entry should fit in the same
1030 : * area.
1031 : */
1032 272 : if (nSeed1 != nSrcCurChildIndex &&
1033 155 : (dAreaDiff1 > dAreaDiff2 || nSeed2 == nSrcCurChildIndex))
1034 : {
1035 : // Seed2 stays in this node, Seed1 moves to new node
1036 : // ... swap Seed1 and Seed2 indices
1037 117 : int nTmp = nSeed1;
1038 117 : nSeed1 = nSeed2;
1039 117 : nSeed2 = nTmp;
1040 : }
1041 :
1042 272 : return 0;
1043 : }
1044 :
1045 : /**********************************************************************
1046 : * TABMAPIndexBlock::SplitNode()
1047 : *
1048 : * Split current Node, update the references in the parent node, etc.
1049 : * Note that Root Nodes cannot be split using this method... SplitRootNode()
1050 : * should be used instead.
1051 : *
1052 : * nNewEntry* are the coord. of the new entry that
1053 : * will be added after the split. The split is done so that the current
1054 : * node will be the one in which the new object should be stored.
1055 : *
1056 : * Returns 0 on success, -1 on error.
1057 : **********************************************************************/
1058 19 : int TABMAPIndexBlock::SplitNode(GInt32 nNewEntryXMin, GInt32 nNewEntryYMin,
1059 : GInt32 nNewEntryXMax, GInt32 nNewEntryYMax)
1060 : {
1061 19 : CPLAssert(m_poBlockManagerRef);
1062 :
1063 : /*-----------------------------------------------------------------
1064 : * Create a 2nd node
1065 : *----------------------------------------------------------------*/
1066 19 : TABMAPIndexBlock *poNewNode = new TABMAPIndexBlock(m_eAccess);
1067 19 : if (poNewNode->InitNewBlock(m_fp, m_nBlockSize,
1068 38 : m_poBlockManagerRef->AllocNewBlock("INDEX")) !=
1069 : 0)
1070 : {
1071 0 : return -1;
1072 : }
1073 19 : poNewNode->SetMAPBlockManagerRef(m_poBlockManagerRef);
1074 :
1075 : /*-----------------------------------------------------------------
1076 : * Make a temporary copy of the entries in current node
1077 : *----------------------------------------------------------------*/
1078 19 : int nSrcEntries = m_numEntries;
1079 : TABMAPIndexEntry *pasSrcEntries = static_cast<TABMAPIndexEntry *>(
1080 19 : CPLMalloc(m_numEntries * sizeof(TABMAPIndexEntry)));
1081 19 : memcpy(pasSrcEntries, &m_asEntries,
1082 19 : m_numEntries * sizeof(TABMAPIndexEntry));
1083 :
1084 19 : int nSrcCurChildIndex = m_nCurChildIndex;
1085 :
1086 : /*-----------------------------------------------------------------
1087 : * Pick Seeds for each node
1088 : *----------------------------------------------------------------*/
1089 : int nSeed1, nSeed2;
1090 19 : PickSeedsForSplit(pasSrcEntries, nSrcEntries, nSrcCurChildIndex,
1091 : nNewEntryXMin, nNewEntryYMin, nNewEntryXMax,
1092 : nNewEntryYMax, nSeed1, nSeed2);
1093 :
1094 : /*-----------------------------------------------------------------
1095 : * Reset number of entries in this node and start moving new entries
1096 : *----------------------------------------------------------------*/
1097 19 : m_numEntries = 0;
1098 :
1099 : // Insert nSeed1 in this node
1100 19 : InsertEntry(pasSrcEntries[nSeed1].XMin, pasSrcEntries[nSeed1].YMin,
1101 19 : pasSrcEntries[nSeed1].XMax, pasSrcEntries[nSeed1].YMax,
1102 19 : pasSrcEntries[nSeed1].nBlockPtr);
1103 :
1104 : // Move nSeed2 to 2nd node
1105 19 : poNewNode->InsertEntry(
1106 19 : pasSrcEntries[nSeed2].XMin, pasSrcEntries[nSeed2].YMin,
1107 19 : pasSrcEntries[nSeed2].XMax, pasSrcEntries[nSeed2].YMax,
1108 19 : pasSrcEntries[nSeed2].nBlockPtr);
1109 :
1110 : // Update cur child index if necessary
1111 19 : if (nSeed1 == nSrcCurChildIndex)
1112 0 : m_nCurChildIndex = m_numEntries - 1;
1113 :
1114 : /*-----------------------------------------------------------------
1115 : * Go through the rest of the entries and assign them to one
1116 : * of the 2 nodes.
1117 : *
1118 : * Criteria is minimal area difference.
1119 : * Resolve ties by adding the entry to the node with smaller total
1120 : * area, then to the one with fewer entries, then to either.
1121 : *----------------------------------------------------------------*/
1122 494 : for (int iEntry = 0; iEntry < nSrcEntries; iEntry++)
1123 : {
1124 475 : if (iEntry == nSeed1 || iEntry == nSeed2)
1125 39 : continue;
1126 :
1127 : // If one of the two nodes is almost full then all remaining
1128 : // entries should go to the other node
1129 : // The entry corresponding to the current child also automatically
1130 : // stays in this node.
1131 437 : if (iEntry == nSrcCurChildIndex)
1132 : {
1133 1 : InsertEntry(pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin,
1134 1 : pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax,
1135 1 : pasSrcEntries[iEntry].nBlockPtr);
1136 :
1137 : // Update current child index
1138 1 : m_nCurChildIndex = m_numEntries - 1;
1139 :
1140 1 : continue;
1141 : }
1142 436 : else if (m_numEntries >= GetMaxEntries() - 1)
1143 : {
1144 0 : poNewNode->InsertEntry(
1145 0 : pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin,
1146 0 : pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax,
1147 0 : pasSrcEntries[iEntry].nBlockPtr);
1148 0 : continue;
1149 : }
1150 436 : else if (poNewNode->GetNumEntries() >= GetMaxEntries() - 1)
1151 : {
1152 0 : InsertEntry(pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin,
1153 0 : pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax,
1154 0 : pasSrcEntries[iEntry].nBlockPtr);
1155 0 : continue;
1156 : }
1157 :
1158 : // Decide which of the two nodes to put this entry in
1159 436 : RecomputeMBR();
1160 872 : const double dAreaDiff1 = ComputeAreaDiff(
1161 436 : m_nMinX, m_nMinY, m_nMaxX, m_nMaxY, pasSrcEntries[iEntry].XMin,
1162 436 : pasSrcEntries[iEntry].YMin, pasSrcEntries[iEntry].XMax,
1163 436 : pasSrcEntries[iEntry].YMax);
1164 :
1165 436 : GInt32 nXMin2 = 0;
1166 436 : GInt32 nYMin2 = 0;
1167 436 : GInt32 nXMax2 = 0;
1168 436 : GInt32 nYMax2 = 0;
1169 436 : poNewNode->RecomputeMBR();
1170 436 : poNewNode->GetMBR(nXMin2, nYMin2, nXMax2, nYMax2);
1171 872 : const double dAreaDiff2 = ComputeAreaDiff(
1172 436 : nXMin2, nYMin2, nXMax2, nYMax2, pasSrcEntries[iEntry].XMin,
1173 436 : pasSrcEntries[iEntry].YMin, pasSrcEntries[iEntry].XMax,
1174 436 : pasSrcEntries[iEntry].YMax);
1175 436 : if (dAreaDiff1 < dAreaDiff2)
1176 : {
1177 : // This entry stays in this node.
1178 156 : InsertEntry(pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin,
1179 156 : pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax,
1180 156 : pasSrcEntries[iEntry].nBlockPtr);
1181 : }
1182 : else
1183 : {
1184 : // This entry goes to new node
1185 280 : poNewNode->InsertEntry(
1186 280 : pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin,
1187 280 : pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax,
1188 280 : pasSrcEntries[iEntry].nBlockPtr);
1189 : }
1190 : }
1191 :
1192 : /*-----------------------------------------------------------------
1193 : * Recompute MBR and update current node info in parent
1194 : *----------------------------------------------------------------*/
1195 19 : RecomputeMBR();
1196 19 : poNewNode->RecomputeMBR();
1197 :
1198 : /*-----------------------------------------------------------------
1199 : * Add second node info to parent and then flush it to disk.
1200 : * This may trigger splitting of parent
1201 : *----------------------------------------------------------------*/
1202 19 : CPLAssert(m_poParentRef);
1203 : int nMinX, nMinY, nMaxX, nMaxY;
1204 19 : poNewNode->GetMBR(nMinX, nMinY, nMaxX, nMaxY);
1205 19 : m_poParentRef->AddEntry(nMinX, nMinY, nMaxX, nMaxY,
1206 : poNewNode->GetNodeBlockPtr(), TRUE);
1207 19 : poNewNode->CommitToFile();
1208 19 : delete poNewNode;
1209 :
1210 19 : CPLFree(pasSrcEntries);
1211 :
1212 19 : return 0;
1213 : }
1214 :
1215 : /**********************************************************************
1216 : * TABMAPIndexBlock::SplitRootNode()
1217 : *
1218 : * (private method)
1219 : *
1220 : * Split a Root Node.
1221 : * First, a level of nodes must be added to the tree, then the contents
1222 : * of what used to be the root node is moved 1 level down and then that
1223 : * node is split like a regular node.
1224 : *
1225 : * Returns 0 on success, -1 on error
1226 : **********************************************************************/
1227 6 : int TABMAPIndexBlock::SplitRootNode(GInt32 nNewEntryXMin, GInt32 nNewEntryYMin,
1228 : GInt32 nNewEntryXMax, GInt32 nNewEntryYMax)
1229 : {
1230 6 : CPLAssert(m_poBlockManagerRef);
1231 6 : CPLAssert(m_poParentRef == nullptr);
1232 :
1233 : /*-----------------------------------------------------------------
1234 : * Since a root note cannot be split, we add a level of nodes
1235 : * under it and we'll do the split at that level.
1236 : *----------------------------------------------------------------*/
1237 12 : auto poNewNode = std::make_unique<TABMAPIndexBlock>(m_eAccess);
1238 :
1239 12 : if (poNewNode->InitNewBlock(m_fp, m_nBlockSize,
1240 12 : m_poBlockManagerRef->AllocNewBlock("INDEX")) !=
1241 : 0)
1242 : {
1243 0 : return -1;
1244 : }
1245 6 : poNewNode->SetMAPBlockManagerRef(m_poBlockManagerRef);
1246 :
1247 : // Move all entries to the new child
1248 6 : int nSrcEntries = m_numEntries;
1249 6 : m_numEntries = 0;
1250 156 : for (int iEntry = 0; iEntry < nSrcEntries; iEntry++)
1251 : {
1252 150 : poNewNode->InsertEntry(
1253 : m_asEntries[iEntry].XMin, m_asEntries[iEntry].YMin,
1254 : m_asEntries[iEntry].XMax, m_asEntries[iEntry].YMax,
1255 : m_asEntries[iEntry].nBlockPtr);
1256 : }
1257 :
1258 : /*-----------------------------------------------------------------
1259 : * Transfer current child object to new node.
1260 : *----------------------------------------------------------------*/
1261 6 : if (m_poCurChild)
1262 : {
1263 1 : poNewNode->SetCurChild(std::move(m_poCurChild), m_nCurChildIndex);
1264 1 : m_nCurChildIndex = -1;
1265 : }
1266 :
1267 : /*-----------------------------------------------------------------
1268 : * Place info about new child in current node.
1269 : *----------------------------------------------------------------*/
1270 6 : poNewNode->RecomputeMBR();
1271 : int nMinX, nMinY, nMaxX, nMaxY;
1272 6 : poNewNode->GetMBR(nMinX, nMinY, nMaxX, nMaxY);
1273 6 : InsertEntry(nMinX, nMinY, nMaxX, nMaxY, poNewNode->GetNodeBlockPtr());
1274 :
1275 : /*-----------------------------------------------------------------
1276 : * Keep a reference to the new child
1277 : *----------------------------------------------------------------*/
1278 6 : poNewNode->SetParentRef(this);
1279 6 : m_poCurChild = std::move(poNewNode);
1280 6 : m_nCurChildIndex = m_numEntries - 1;
1281 :
1282 : /*-----------------------------------------------------------------
1283 : * And finally force the child to split itself
1284 : *----------------------------------------------------------------*/
1285 6 : return m_poCurChild->SplitNode(nNewEntryXMin, nNewEntryYMin, nNewEntryXMax,
1286 6 : nNewEntryYMax);
1287 : }
1288 :
1289 : /**********************************************************************
1290 : * TABMAPIndexBlock::RecomputeMBR()
1291 : *
1292 : * Recompute current block MBR, and update info in parent.
1293 : **********************************************************************/
1294 3036 : void TABMAPIndexBlock::RecomputeMBR()
1295 : {
1296 : GInt32 nMinX, nMinY, nMaxX, nMaxY;
1297 :
1298 3036 : nMinX = 1000000000;
1299 3036 : nMinY = 1000000000;
1300 3036 : nMaxX = -1000000000;
1301 3036 : nMaxY = -1000000000;
1302 :
1303 36190 : for (int i = 0; i < m_numEntries; i++)
1304 : {
1305 33154 : if (m_asEntries[i].XMin < nMinX)
1306 8180 : nMinX = m_asEntries[i].XMin;
1307 33154 : if (m_asEntries[i].XMax > nMaxX)
1308 5259 : nMaxX = m_asEntries[i].XMax;
1309 :
1310 33154 : if (m_asEntries[i].YMin < nMinY)
1311 5686 : nMinY = m_asEntries[i].YMin;
1312 33154 : if (m_asEntries[i].YMax > nMaxY)
1313 6415 : nMaxY = m_asEntries[i].YMax;
1314 : }
1315 :
1316 3036 : if (m_nMinX != nMinX || m_nMinY != nMinY || m_nMaxX != nMaxX ||
1317 1059 : m_nMaxY != nMaxY)
1318 : {
1319 2002 : m_nMinX = nMinX;
1320 2002 : m_nMinY = nMinY;
1321 2002 : m_nMaxX = nMaxX;
1322 2002 : m_nMaxY = nMaxY;
1323 :
1324 2002 : m_bModified = TRUE;
1325 :
1326 2002 : if (m_poParentRef)
1327 890 : m_poParentRef->UpdateCurChildMBR(m_nMinX, m_nMinY, m_nMaxX, m_nMaxY,
1328 : GetNodeBlockPtr());
1329 : }
1330 3036 : }
1331 :
1332 : /**********************************************************************
1333 : * TABMAPIndexBlock::UpdateCurChildMBR()
1334 : *
1335 : * Update current child MBR info, and propagate info in parent.
1336 : *
1337 : * nBlockPtr is passed only to validate the consistency of the tree.
1338 : **********************************************************************/
1339 913 : void TABMAPIndexBlock::UpdateCurChildMBR(GInt32 nXMin, GInt32 nYMin,
1340 : GInt32 nXMax, GInt32 nYMax,
1341 : CPL_UNUSED GInt32 nBlockPtr)
1342 : {
1343 913 : CPLAssert(m_poCurChild);
1344 913 : CPLAssert(m_asEntries[m_nCurChildIndex].nBlockPtr == nBlockPtr);
1345 :
1346 913 : if (m_asEntries[m_nCurChildIndex].XMin == nXMin &&
1347 874 : m_asEntries[m_nCurChildIndex].YMin == nYMin &&
1348 843 : m_asEntries[m_nCurChildIndex].XMax == nXMax &&
1349 506 : m_asEntries[m_nCurChildIndex].YMax == nYMax)
1350 : {
1351 496 : return; /* Nothing changed... nothing to do */
1352 : }
1353 :
1354 417 : m_bModified = TRUE;
1355 :
1356 417 : m_asEntries[m_nCurChildIndex].XMin = nXMin;
1357 417 : m_asEntries[m_nCurChildIndex].YMin = nYMin;
1358 417 : m_asEntries[m_nCurChildIndex].XMax = nXMax;
1359 417 : m_asEntries[m_nCurChildIndex].YMax = nYMax;
1360 :
1361 417 : m_nMinX = 1000000000;
1362 417 : m_nMinY = 1000000000;
1363 417 : m_nMaxX = -1000000000;
1364 417 : m_nMaxY = -1000000000;
1365 :
1366 2558 : for (int i = 0; i < m_numEntries; i++)
1367 : {
1368 2141 : if (m_asEntries[i].XMin < m_nMinX)
1369 1219 : m_nMinX = m_asEntries[i].XMin;
1370 2141 : if (m_asEntries[i].XMax > m_nMaxX)
1371 451 : m_nMaxX = m_asEntries[i].XMax;
1372 :
1373 2141 : if (m_asEntries[i].YMin < m_nMinY)
1374 767 : m_nMinY = m_asEntries[i].YMin;
1375 2141 : if (m_asEntries[i].YMax > m_nMaxY)
1376 561 : m_nMaxY = m_asEntries[i].YMax;
1377 : }
1378 :
1379 417 : if (m_poParentRef)
1380 23 : m_poParentRef->UpdateCurChildMBR(m_nMinX, m_nMinY, m_nMaxX, m_nMaxY,
1381 : GetNodeBlockPtr());
1382 : }
1383 :
1384 : /**********************************************************************
1385 : * TABMAPIndexBlock::SetMAPBlockManagerRef()
1386 : *
1387 : * Pass a reference to the block manager object for the file this
1388 : * block belongs to. The block manager will be used by this object
1389 : * when it needs to automatically allocate a new block.
1390 : **********************************************************************/
1391 34493 : void TABMAPIndexBlock::SetMAPBlockManagerRef(TABBinBlockManager *poBlockMgr)
1392 : {
1393 34493 : m_poBlockManagerRef = poBlockMgr;
1394 34493 : }
1395 :
1396 : /**********************************************************************
1397 : * TABMAPIndexBlock::SetParentRef()
1398 : *
1399 : * Used to pass a reference to this node's parent.
1400 : **********************************************************************/
1401 33333 : void TABMAPIndexBlock::SetParentRef(TABMAPIndexBlock *poParent)
1402 : {
1403 33333 : m_poParentRef = poParent;
1404 33333 : }
1405 :
1406 : /**********************************************************************
1407 : * TABMAPIndexBlock::SetCurChild()
1408 : *
1409 : * Used to transfer a child object from one node to another
1410 : **********************************************************************/
1411 437351 : void TABMAPIndexBlock::SetCurChild(std::unique_ptr<TABMAPIndexBlock> &&poChild,
1412 : int nChildIndex)
1413 : {
1414 437351 : if (poChild)
1415 22744 : poChild->SetParentRef(this);
1416 437351 : m_poCurChild = std::move(poChild);
1417 437351 : m_nCurChildIndex = nChildIndex;
1418 437351 : }
1419 :
1420 : /**********************************************************************
1421 : * TABMAPIndexBlock::Dump()
1422 : *
1423 : * Dump block contents... available only in DEBUG mode.
1424 : **********************************************************************/
1425 : #ifdef DEBUG
1426 :
1427 0 : void TABMAPIndexBlock::Dump(FILE *fpOut /*=NULL*/)
1428 : {
1429 0 : if (fpOut == nullptr)
1430 0 : fpOut = stdout;
1431 :
1432 0 : fprintf(fpOut, "----- TABMAPIndexBlock::Dump() -----\n");
1433 0 : if (m_pabyBuf == nullptr)
1434 : {
1435 0 : fprintf(fpOut, "Block has not been initialized yet.");
1436 : }
1437 : else
1438 : {
1439 0 : fprintf(fpOut, "Index Block (type %d) at offset %d.\n", m_nBlockType,
1440 : m_nFileOffset);
1441 0 : fprintf(fpOut, " m_numEntries = %d\n", m_numEntries);
1442 :
1443 : /*-------------------------------------------------------------
1444 : * Loop through all entries, dumping each of them
1445 : *------------------------------------------------------------*/
1446 0 : if (m_numEntries > 0)
1447 0 : ReadAllEntries();
1448 :
1449 0 : for (int i = 0; i < m_numEntries; i++)
1450 : {
1451 0 : fprintf(fpOut, " %6d -> (%d, %d) - (%d, %d)\n",
1452 : m_asEntries[i].nBlockPtr, m_asEntries[i].XMin,
1453 : m_asEntries[i].YMin, m_asEntries[i].XMax,
1454 : m_asEntries[i].YMax);
1455 : }
1456 : }
1457 :
1458 0 : fflush(fpOut);
1459 0 : }
1460 : #endif // DEBUG
|
