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