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