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