EVOLUTION-MANAGER
Edit File: mitab_mapindexblock.cpp
/********************************************************************** * * Name: mitab_mapindexblock.cpp * Project: MapInfo TAB Read/Write library * Language: C++ * Purpose: Implementation of the TABMAPIndexBlock class used to handle * reading/writing of the .MAP files' index blocks * Author: Daniel Morissette, dmorissette@dmsolutions.ca * ********************************************************************** * Copyright (c) 1999, 2000, Daniel Morissette * Copyright (c) 2014, Even Rouault <even.rouault at spatialys.com> * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the "Software"), * to deal in the Software without restriction, including without limitation * the rights to use, copy, modify, merge, publish, distribute, sublicense, * and/or sell copies of the Software, and to permit persons to whom the * Software is furnished to do so, subject to the following conditions: * * The above copyright notice and this permission notice shall be included * in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER * DEALINGS IN THE SOFTWARE. **********************************************************************/ #include "cpl_port.h" #include "mitab.h" #include <cmath> #include <cstdlib> #include <cstring> #include <algorithm> #include "cpl_conv.h" #include "cpl_error.h" #include "cpl_vsi.h" #include "mitab_priv.h" CPL_CVSID("$Id: mitab_mapindexblock.cpp 37351 2017-02-12 05:22:20Z goatbar $"); /*===================================================================== * class TABMAPIndexBlock *====================================================================*/ /********************************************************************** * TABMAPIndexBlock::TABMAPIndexBlock() * * Constructor. **********************************************************************/ TABMAPIndexBlock::TABMAPIndexBlock( TABAccess eAccessMode /*= TABRead*/ ) : TABRawBinBlock(eAccessMode, TRUE), m_numEntries(0), m_nMinX(1000000000), m_nMinY(1000000000), m_nMaxX(-1000000000), m_nMaxY(-1000000000), m_poBlockManagerRef(NULL), m_poCurChild(NULL), m_nCurChildIndex(-1), m_poParentRef(NULL) { memset(m_asEntries, 0, sizeof(m_asEntries)); } /********************************************************************** * TABMAPIndexBlock::~TABMAPIndexBlock() * * Destructor. **********************************************************************/ TABMAPIndexBlock::~TABMAPIndexBlock() { UnsetCurChild(); } /********************************************************************** * TABMAPIndexBlock::UnsetCurChild() **********************************************************************/ void TABMAPIndexBlock::UnsetCurChild() { if (m_poCurChild) { if (m_eAccess == TABWrite || m_eAccess == TABReadWrite) m_poCurChild->CommitToFile(); delete m_poCurChild; m_poCurChild = NULL; } m_nCurChildIndex = -1; } /********************************************************************** * TABMAPIndexBlock::InitBlockFromData() * * Perform some initialization on the block after its binary data has * been set or changed (or loaded from a file). * * Returns 0 if successful or -1 if an error happened, in which case * CPLError() will have been called. **********************************************************************/ int TABMAPIndexBlock::InitBlockFromData(GByte *pabyBuf, int nBlockSize, int nSizeUsed, GBool bMakeCopy /* = TRUE */, VSILFILE *fpSrc /* = NULL */, int nOffset /* = 0 */) { /*----------------------------------------------------------------- * First of all, we must call the base class' InitBlockFromData() *----------------------------------------------------------------*/ const int nStatus = TABRawBinBlock::InitBlockFromData(pabyBuf, nBlockSize, nSizeUsed, bMakeCopy, fpSrc, nOffset); if (nStatus != 0) return nStatus; /*----------------------------------------------------------------- * Validate block type *----------------------------------------------------------------*/ if (m_nBlockType != TABMAP_INDEX_BLOCK) { CPLError(CE_Failure, CPLE_FileIO, "InitBlockFromData(): Invalid Block Type: got %d expected %d", m_nBlockType, TABMAP_INDEX_BLOCK); CPLFree(m_pabyBuf); m_pabyBuf = NULL; return -1; } /*----------------------------------------------------------------- * Init member variables *----------------------------------------------------------------*/ GotoByteInBlock(0x002); m_numEntries = ReadInt16(); if (m_numEntries > 0) ReadAllEntries(); return 0; } /********************************************************************** * TABMAPIndexBlock::CommitToFile() * * Commit the current state of the binary block to the file to which * it has been previously attached. * * This method makes sure all values are properly set in the map object * block header and then calls TABRawBinBlock::CommitToFile() to do * the actual writing to disk. * * Returns 0 if successful or -1 if an error happened, in which case * CPLError() will have been called. **********************************************************************/ int TABMAPIndexBlock::CommitToFile() { int nStatus = 0; if ( m_pabyBuf == NULL ) { CPLError(CE_Failure, CPLE_AssertionFailed, "CommitToFile(): Block has not been initialized yet!"); return -1; } /*----------------------------------------------------------------- * Commit child first *----------------------------------------------------------------*/ if (m_poCurChild) { if (m_poCurChild->CommitToFile() != 0) return -1; } /*----------------------------------------------------------------- * Nothing to do here if block has not been modified *----------------------------------------------------------------*/ if (!m_bModified) return 0; /*----------------------------------------------------------------- * Make sure 4 bytes block header is up to date. *----------------------------------------------------------------*/ GotoByteInBlock(0x000); WriteInt16(TABMAP_INDEX_BLOCK); // Block type code WriteInt16((GInt16)m_numEntries); nStatus = CPLGetLastErrorNo(); /*----------------------------------------------------------------- * Loop through all entries, writing each of them, and calling * CommitToFile() (recursively) on any child index entries we may * encounter. *----------------------------------------------------------------*/ for(int i=0; nStatus == 0 && i<m_numEntries; i++) { if (nStatus == 0) nStatus = WriteNextEntry(&(m_asEntries[i])); } /*----------------------------------------------------------------- * OK, call the base class to write the block to disk. *----------------------------------------------------------------*/ if (nStatus == 0) { #ifdef DEBUG_VERBOSE CPLDebug("MITAB", "Committing INDEX block to offset %d", m_nFileOffset); #endif nStatus = TABRawBinBlock::CommitToFile(); } return nStatus; } /********************************************************************** * TABMAPIndexBlock::InitNewBlock() * * Initialize a newly created block so that it knows to which file it * is attached, its block size, etc . and then perform any specific * initialization for this block type, including writing a default * block header, etc. and leave the block ready to receive data. * * This is an alternative to calling ReadFromFile() or InitBlockFromData() * that puts the block in a stable state without loading any initial * data in it. * * Returns 0 if successful or -1 if an error happened, in which case * CPLError() will have been called. **********************************************************************/ int TABMAPIndexBlock::InitNewBlock(VSILFILE *fpSrc, int nBlockSize, int nFileOffset /* = 0*/) { /*----------------------------------------------------------------- * Start with the default initialization *----------------------------------------------------------------*/ if ( TABRawBinBlock::InitNewBlock(fpSrc, nBlockSize, nFileOffset) != 0) return -1; /*----------------------------------------------------------------- * And then set default values for the block header. *----------------------------------------------------------------*/ m_numEntries = 0; m_nMinX = 1000000000; m_nMinY = 1000000000; m_nMaxX = -1000000000; m_nMaxY = -1000000000; if (m_eAccess != TABRead && nFileOffset != 0) { GotoByteInBlock(0x000); WriteInt16(TABMAP_INDEX_BLOCK); // Block type code WriteInt16(0); // num. index entries } if (CPLGetLastErrorNo() != 0) return -1; return 0; } /********************************************************************** * TABMAPIndexBlock::ReadNextEntry() * * Read the next index entry from the block and fill the sEntry * structure. * * Returns 0 if successful or -1 if we reached the end of the block. **********************************************************************/ int TABMAPIndexBlock::ReadNextEntry(TABMAPIndexEntry *psEntry) { if (m_nCurPos < 4) GotoByteInBlock( 0x004 ); if (m_nCurPos > 4+(20*m_numEntries) ) { // End of BLock return -1; } psEntry->XMin = ReadInt32(); psEntry->YMin = ReadInt32(); psEntry->XMax = ReadInt32(); psEntry->YMax = ReadInt32(); psEntry->nBlockPtr = ReadInt32(); if (CPLGetLastErrorNo() != 0) return -1; return 0; } /********************************************************************** * TABMAPIndexBlock::ReadAllEntries() * * Init the block by reading all entries from the data block. * * Returns 0 if successful or -1 on error. **********************************************************************/ int TABMAPIndexBlock::ReadAllEntries() { CPLAssert(m_numEntries <= GetMaxEntries()); if (m_numEntries == 0) return 0; if (GotoByteInBlock( 0x004 ) != 0) return -1; for(int i=0; i<m_numEntries; i++) { if ( ReadNextEntry(&(m_asEntries[i])) != 0) return -1; } return 0; } /********************************************************************** * TABMAPIndexBlock::WriteNextEntry() * * Write the sEntry index entry at current position in the block. * * Returns 0 if successful or -1 if we reached the end of the block. **********************************************************************/ int TABMAPIndexBlock::WriteNextEntry(TABMAPIndexEntry *psEntry) { if (m_nCurPos < 4) GotoByteInBlock( 0x004 ); WriteInt32(psEntry->XMin); WriteInt32(psEntry->YMin); WriteInt32(psEntry->XMax); WriteInt32(psEntry->YMax); WriteInt32(psEntry->nBlockPtr); if (CPLGetLastErrorNo() != 0) return -1; return 0; } /********************************************************************** * TABMAPIndexBlock::GetNumFreeEntries() * * Return the number of available entries in this block. * * __TODO__ This function could eventually be improved to search * children leaves as well. **********************************************************************/ int TABMAPIndexBlock::GetNumFreeEntries() { return (m_nBlockSize-4)/20 - m_numEntries; } /********************************************************************** * TABMAPIndexBlock::GetEntry() * * Fetch a reference to the requested entry. * * @param iIndex index of entry, must be from 0 to GetNumEntries()-1. * * @return a reference to the internal copy of the entry, or NULL if out * of range. **********************************************************************/ TABMAPIndexEntry *TABMAPIndexBlock::GetEntry( int iIndex ) { if( iIndex < 0 || iIndex >= m_numEntries ) return NULL; return m_asEntries + iIndex; } /********************************************************************** * TABMAPIndexBlock::GetCurMaxDepth() * * Return maximum depth in the currently loaded part of the index tree **********************************************************************/ int TABMAPIndexBlock::GetCurMaxDepth() { if (m_poCurChild) return m_poCurChild->GetCurMaxDepth() + 1; return 1; /* No current child... this node counts for one. */ } /********************************************************************** * TABMAPIndexBlock::GetMBR() * * Return the MBR for the current block. **********************************************************************/ void TABMAPIndexBlock::GetMBR(GInt32 &nXMin, GInt32 &nYMin, GInt32 &nXMax, GInt32 &nYMax) { nXMin = m_nMinX; nYMin = m_nMinY; nXMax = m_nMaxX; nYMax = m_nMaxY; } /********************************************************************** * TABMAPIndexBlock::SetMBR() * **********************************************************************/ void TABMAPIndexBlock::SetMBR(GInt32 nXMin, GInt32 nYMin, GInt32 nXMax, GInt32 nYMax) { m_nMinX = nXMin; m_nMinY = nYMin; m_nMaxX = nXMax; m_nMaxY = nYMax; } /********************************************************************** * TABMAPIndexBlock::InsertEntry() * * Add a new entry to this index block. It is assumed that there is at * least one free slot available, so if the block has to be split then it * should have been done prior to calling this function. * * Returns 0 on success, -1 on error. **********************************************************************/ int TABMAPIndexBlock::InsertEntry(GInt32 nXMin, GInt32 nYMin, GInt32 nXMax, GInt32 nYMax, GInt32 nBlockPtr) { if (m_eAccess != TABWrite && m_eAccess != TABReadWrite) { CPLError(CE_Failure, CPLE_AssertionFailed, "Failed adding index entry: File not opened for write access."); return -1; } if (GetNumFreeEntries() < 1) { CPLError(CE_Failure, CPLE_AssertionFailed, "Current Block Index is full, cannot add new entry."); return -1; } /*----------------------------------------------------------------- * Update count of entries and store new entry. *----------------------------------------------------------------*/ m_numEntries++; CPLAssert(m_numEntries <= GetMaxEntries()); m_asEntries[m_numEntries-1].XMin = nXMin; m_asEntries[m_numEntries-1].YMin = nYMin; m_asEntries[m_numEntries-1].XMax = nXMax; m_asEntries[m_numEntries-1].YMax = nYMax; m_asEntries[m_numEntries-1].nBlockPtr = nBlockPtr; m_bModified = TRUE; return 0; } /********************************************************************** * TABMAPIndexBlock::ChooseSubEntryForInsert() * * Select the entry in this index block in which the new entry should * be inserted. The criteria used is to select the node whose MBR needs * the least enlargement to include the new entry. We resolve ties by * choosing the entry with the rectangle of smallest area. * (This is the ChooseSubtree part of Guttman's "ChooseLeaf" algorithm.) * * Returns the index of the best candidate or -1 of node is empty. **********************************************************************/ int TABMAPIndexBlock::ChooseSubEntryForInsert(GInt32 nXMin, GInt32 nYMin, GInt32 nXMax, GInt32 nYMax) { GInt32 nBestCandidate = -1; double dOptimalAreaDiff = 0.0; const double dNewEntryArea = MITAB_AREA(nXMin, nYMin, nXMax, nYMax); for( GInt32 i = 0; i<m_numEntries; i++ ) { double dAreaDiff = 0.0; const double dAreaBefore = MITAB_AREA(m_asEntries[i].XMin, m_asEntries[i].YMin, m_asEntries[i].XMax, m_asEntries[i].YMax); /* Does this entry fully contain the new entry's MBR ? */ const GBool bIsContained = nXMin >= m_asEntries[i].XMin && nYMin >= m_asEntries[i].YMin && nXMax <= m_asEntries[i].XMax && nYMax <= m_asEntries[i].YMax; if( bIsContained ) { /* If new entry is fully contained in this entry then * the area difference will be the difference between the area * of the entry to insert and the area of m_asEntries[i] * * The diff value is negative in this case. */ dAreaDiff = dNewEntryArea - dAreaBefore; } else { /* Need to calculate the expanded MBR to calculate the area * difference. */ GInt32 nXMin2 = std::min(m_asEntries[i].XMin, nXMin); GInt32 nYMin2 = std::min(m_asEntries[i].YMin, nYMin); GInt32 nXMax2 = std::max(m_asEntries[i].XMax, nXMax); GInt32 nYMax2 = std::max(m_asEntries[i].YMax, nYMax); dAreaDiff = MITAB_AREA(nXMin2,nYMin2,nXMax2,nYMax2) - dAreaBefore; } /* Is this a better candidate? * Note, possible Optimization: In case of tie, we could to pick the * candidate with the smallest area */ if (/* No best candidate yet */ (nBestCandidate == -1) /* or current candidate is contained and best candidate is not contained */ || (dAreaDiff < 0 && dOptimalAreaDiff >= 0) /* or if both are either contained or not contained then use the one * with the smallest area diff, which means maximum coverage in the case * of contained rects, or minimum area increase when not contained */ || (((dOptimalAreaDiff < 0 && dAreaDiff < 0) || (dOptimalAreaDiff > 0 && dAreaDiff > 0)) && std::abs(dAreaDiff) < std::abs(dOptimalAreaDiff)) ) { nBestCandidate = i; dOptimalAreaDiff = dAreaDiff; } } return nBestCandidate; } /********************************************************************** * TABMAPIndexBlock::ChooseLeafForInsert() * * Recursively search the tree until we find the best leaf to * contain the specified object MBR. * * Returns the nBlockPtr of the selected leaf node entry (should be a * ref to a TABMAPObjectBlock) or -1 on error. * * After this call, m_poCurChild will be pointing at the selected child * node, for use by later calls to UpdateLeafEntry() **********************************************************************/ GInt32 TABMAPIndexBlock::ChooseLeafForInsert(GInt32 nXMin, GInt32 nYMin, GInt32 nXMax, GInt32 nYMax) { GBool bFound = FALSE; if (m_numEntries < 0) return -1; /*----------------------------------------------------------------- * Look for the best candidate to contain the new entry *----------------------------------------------------------------*/ // Make sure blocks currently in memory are written to disk. // TODO: Could we avoid deleting m_poCurChild if it's already // the best candidate for insert? if (m_poCurChild) { m_poCurChild->CommitToFile(); delete m_poCurChild; m_poCurChild = NULL; m_nCurChildIndex = -1; } int nBestCandidate = ChooseSubEntryForInsert(nXMin,nYMin,nXMax,nYMax); CPLAssert(nBestCandidate != -1); if (nBestCandidate == -1) return -1; /* This should never happen! */ // Try to load corresponding child... if it fails then we are // likely in a leaf node, so we'll add the new entry in the current // node. TABRawBinBlock *poBlock = NULL; // Prevent error message if referred block not committed yet. CPLPushErrorHandler(CPLQuietErrorHandler); poBlock = TABCreateMAPBlockFromFile(m_fp, m_asEntries[nBestCandidate].nBlockPtr, m_nBlockSize, TRUE, TABReadWrite); if (poBlock != NULL && poBlock->GetBlockClass() == TABMAP_INDEX_BLOCK) { m_poCurChild = (TABMAPIndexBlock*)poBlock; poBlock = NULL; m_nCurChildIndex = nBestCandidate; m_poCurChild->SetParentRef(this); m_poCurChild->SetMAPBlockManagerRef(m_poBlockManagerRef); bFound = TRUE; } if (poBlock) delete poBlock; CPLPopErrorHandler(); CPLErrorReset(); if (bFound) { /*------------------------------------------------------------- * Found a child leaf... pass the call to it. *------------------------------------------------------------*/ return m_poCurChild->ChooseLeafForInsert(nXMin, nYMin, nXMax, nYMax); } /*------------------------------------------------------------- * Found no child index node... we must be at the leaf level * (leaf points at map object data blocks) so we return a ref * to the TABMAPObjBlock for insertion *------------------------------------------------------------*/ return m_asEntries[nBestCandidate].nBlockPtr; } /********************************************************************** * TABMAPIndexBlock::GetCurLeafEntryMBR() * * Get the MBR for specified nBlockPtr in the leaf at the end of the * chain of m_poCurChild refs. * * This method requires that the chain of m_poCurChild refs already point * to a leaf that contains the specified nBlockPtr, it is usually called * right after ChooseLeafForInsert(). * * Returns 0 on success, -1 on error. **********************************************************************/ int TABMAPIndexBlock::GetCurLeafEntryMBR(GInt32 nBlockPtr, GInt32 &nXMin, GInt32 &nYMin, GInt32 &nXMax, GInt32 &nYMax) { if (m_poCurChild) { /* Pass the call down to current child */ return m_poCurChild->GetCurLeafEntryMBR(nBlockPtr, nXMin, nYMin, nXMax, nYMax); } /* We're at the leaf level, look for the entry */ for(int i=0; i<m_numEntries; i++) { if (m_asEntries[i].nBlockPtr == nBlockPtr) { /* Found it. Return its MBR */ nXMin = m_asEntries[i].XMin; nYMin = m_asEntries[i].YMin; nXMax = m_asEntries[i].XMax; nYMax = m_asEntries[i].YMax; return 0; } } /* Not found! This should not happen if method is used properly. */ CPLError(CE_Failure, CPLE_AssertionFailed, "Entry to update not found in GetCurLeafEntryMBR()!"); return -1; } /********************************************************************** * TABMAPIndexBlock::UpdateLeafEntry() * * Update the MBR for specified nBlockPtr in the leaf at the end of the * chain of m_poCurChild refs and update MBR of parents if required. * * This method requires that the chain of m_poCurChild refs already point * to a leaf that contains the specified nBlockPtr, it is usually called * right after ChooseLeafForInsert(). * * Returns 0 on success, -1 on error. **********************************************************************/ int TABMAPIndexBlock::UpdateLeafEntry(GInt32 nBlockPtr, GInt32 nXMin, GInt32 nYMin, GInt32 nXMax, GInt32 nYMax ) { if (m_poCurChild) { /* Pass the call down to current child */ return m_poCurChild->UpdateLeafEntry(nBlockPtr, nXMin, nYMin, nXMax, nYMax); } /* We're at the leaf level, look for the entry to update */ for(int i=0; i<m_numEntries; i++) { if (m_asEntries[i].nBlockPtr == nBlockPtr) { /* Found it. */ TABMAPIndexEntry *psEntry = &m_asEntries[i]; if (psEntry->XMin != nXMin || psEntry->YMin != nYMin || psEntry->XMax != nXMax || psEntry->YMax != nYMax ) { /* MBR changed. Update MBR of entry */ psEntry->XMin = nXMin; psEntry->YMin = nYMin; psEntry->XMax = nXMax; psEntry->YMax = nYMax; m_bModified = TRUE; /* Update MBR of this node and all parents */ RecomputeMBR(); } return 0; } } /* Not found! This should not happen if method is used properly. */ CPLError(CE_Failure, CPLE_AssertionFailed, "Entry to update not found in UpdateLeafEntry()!"); return -1; } /********************************************************************** * TABMAPIndexBlock::AddEntry() * * Recursively search the tree until we encounter the best leaf to * contain the specified object MBR and add the new entry to it. * * In the even that the selected leaf node would be full, then it will be * split and this split can propagate up to its parent, etc. * * If bAddInThisNodeOnly=TRUE, then the entry is added only locally and * we do not try to update the child node. This is used when the parent * of a node that is being split has to be updated. * * Returns 0 on success, -1 on error. **********************************************************************/ int TABMAPIndexBlock::AddEntry(GInt32 nXMin, GInt32 nYMin, GInt32 nXMax, GInt32 nYMax, GInt32 nBlockPtr, GBool bAddInThisNodeOnly /*=FALSE*/) { GBool bFound = FALSE; if (m_eAccess != TABWrite && m_eAccess != TABReadWrite) { CPLError(CE_Failure, CPLE_AssertionFailed, "Failed adding index entry: File not opened for write access."); return -1; } /*----------------------------------------------------------------- * Look for the best candidate to contain the new entry *----------------------------------------------------------------*/ /*----------------------------------------------------------------- * If bAddInThisNodeOnly=TRUE then we add the entry only locally * and do not need to look for the proper leaf to insert it. *----------------------------------------------------------------*/ if (bAddInThisNodeOnly) bFound = TRUE; if (!bFound && m_numEntries > 0) { // Make sure blocks currently in memory are written to disk. if (m_poCurChild) { m_poCurChild->CommitToFile(); delete m_poCurChild; m_poCurChild = NULL; m_nCurChildIndex = -1; } int nBestCandidate = ChooseSubEntryForInsert(nXMin,nYMin,nXMax,nYMax); CPLAssert(nBestCandidate != -1); if (nBestCandidate != -1) { // Try to load corresponding child... if it fails then we are // likely in a leaf node, so we'll add the new entry in the current // node. TABRawBinBlock *poBlock = NULL; // Prevent error message if referred block not committed yet. CPLPushErrorHandler(CPLQuietErrorHandler); poBlock = TABCreateMAPBlockFromFile(m_fp, m_asEntries[nBestCandidate].nBlockPtr, m_nBlockSize, TRUE, TABReadWrite); if (poBlock != NULL && poBlock->GetBlockClass() == TABMAP_INDEX_BLOCK) { m_poCurChild = (TABMAPIndexBlock*)poBlock; poBlock = NULL; m_nCurChildIndex = nBestCandidate; m_poCurChild->SetParentRef(this); m_poCurChild->SetMAPBlockManagerRef(m_poBlockManagerRef); bFound = TRUE; } if (poBlock) delete poBlock; CPLPopErrorHandler(); CPLErrorReset(); } } if (bFound && !bAddInThisNodeOnly) { /*------------------------------------------------------------- * Found a child leaf... pass the call to it. *------------------------------------------------------------*/ if (m_poCurChild->AddEntry(nXMin, nYMin, nXMax, nYMax, nBlockPtr) != 0) return -1; } else { /*------------------------------------------------------------- * Found no child to store new object... we're likely at the leaf * level so we'll store new object in current node *------------------------------------------------------------*/ /*------------------------------------------------------------- * First thing to do is make sure that there is room for a new * entry in this node, and to split it if necessary. *------------------------------------------------------------*/ if (GetNumFreeEntries() < 1) { if (m_poParentRef == NULL) { /*----------------------------------------------------- * Splitting the root node adds one level to the tree, so * after splitting we just redirect the call to the new * child that's just been created. *----------------------------------------------------*/ if (SplitRootNode(nXMin, nYMin, nXMax, nYMax) != 0) return -1; // Error happened and has already been reported CPLAssert(m_poCurChild); return m_poCurChild->AddEntry(nXMin, nYMin, nXMax, nYMax, nBlockPtr, TRUE); } else { /*----------------------------------------------------- * Splitting a regular node *----------------------------------------------------*/ if (SplitNode(nXMin, nYMin, nXMax, nYMax) != 0) return -1; } } if (InsertEntry(nXMin, nYMin, nXMax, nYMax, nBlockPtr) != 0) return -1; } /*----------------------------------------------------------------- * Update current node MBR and the reference to it in our parent. *----------------------------------------------------------------*/ RecomputeMBR(); return 0; } /********************************************************************** * TABMAPIndexBlock::ComputeAreaDiff() * * (static method, also used by the TABMAPObjBlock class) * * Compute the area difference between two MBRs. Used in the SplitNode * algorithm to decide to which of the two nodes an entry should be added. * * The returned AreaDiff value is positive if NodeMBR has to be enlarged * and negative if new Entry is fully contained in the NodeMBR. **********************************************************************/ double TABMAPIndexBlock::ComputeAreaDiff( GInt32 nNodeXMin, GInt32 nNodeYMin, GInt32 nNodeXMax, GInt32 nNodeYMax, GInt32 nEntryXMin, GInt32 nEntryYMin, GInt32 nEntryXMax, GInt32 nEntryYMax ) { double dAreaDiff = 0.0; const double dNodeAreaBefore = MITAB_AREA(nNodeXMin, nNodeYMin, nNodeXMax, nNodeYMax); // Does the node fully contain the new entry's MBR? const GBool bIsContained = nEntryXMin >= nNodeXMin && nEntryYMin >= nNodeYMin && nEntryXMax <= nNodeXMax && nEntryYMax <= nNodeYMax; if( bIsContained ) { /* If new entry is fully contained in this entry then * the area difference will be the difference between the area * of the entry to insert and the area of the node */ dAreaDiff = MITAB_AREA(nEntryXMin, nEntryYMin, nEntryXMax, nEntryYMax) - dNodeAreaBefore; } else { /* Need to calculate the expanded MBR to calculate the area * difference. */ nNodeXMin = std::min(nNodeXMin, nEntryXMin); nNodeYMin = std::min(nNodeYMin, nEntryYMin); nNodeXMax = std::max(nNodeXMax, nEntryXMax); nNodeYMax = std::max(nNodeYMax, nEntryYMax); dAreaDiff = MITAB_AREA(nNodeXMin,nNodeYMin, nNodeXMax,nNodeYMax) - dNodeAreaBefore; } return dAreaDiff; } /********************************************************************** * TABMAPIndexBlock::PickSeedsForSplit() * * (static method, also used by the TABMAPObjBlock class) * * Pick two seeds to use to start splitting this node. * * Guttman's LinearPickSeed: * - Along each dimension find the entry whose rectangle has the * highest low side, and the one with the lowest high side * - Calculate the separation for each pair * - Normalize the separation by dividing by the extents of the * corresponding dimension * - Choose the pair with the greatest normalized separation along * any dimension **********************************************************************/ int TABMAPIndexBlock::PickSeedsForSplit( TABMAPIndexEntry *pasEntries, int numEntries, int nSrcCurChildIndex, GInt32 nNewEntryXMin, GInt32 nNewEntryYMin, GInt32 nNewEntryXMax, GInt32 nNewEntryYMax, int &nSeed1, int &nSeed2 ) { GInt32 nSrcMinX = 0; GInt32 nSrcMinY = 0; GInt32 nSrcMaxX = 0; GInt32 nSrcMaxY = 0; int nLowestMaxX = -1; int nHighestMinX = -1; int nLowestMaxY = -1; int nHighestMinY = -1; GInt32 nLowestMaxXId=-1; GInt32 nHighestMinXId=-1; GInt32 nLowestMaxYId=-1; GInt32 nHighestMinYId = -1; nSeed1 = -1; nSeed2 = -1; // Along each dimension find the entry whose rectangle has the // highest low side, and the one with the lowest high side for(int iEntry=0; iEntry<numEntries; iEntry++) { if (nLowestMaxXId == -1 || pasEntries[iEntry].XMax < nLowestMaxX) { nLowestMaxX = pasEntries[iEntry].XMax; nLowestMaxXId = iEntry; } if (nHighestMinXId == -1 || pasEntries[iEntry].XMin > nHighestMinX) { nHighestMinX = pasEntries[iEntry].XMin; nHighestMinXId = iEntry; } if (nLowestMaxYId == -1 || pasEntries[iEntry].YMax < nLowestMaxY) { nLowestMaxY = pasEntries[iEntry].YMax; nLowestMaxYId = iEntry; } if (nHighestMinYId == -1 || pasEntries[iEntry].YMin > nHighestMinY) { nHighestMinY = pasEntries[iEntry].YMin; nHighestMinYId = iEntry; } // Also keep track of MBR of all entries if (iEntry == 0) { nSrcMinX = pasEntries[iEntry].XMin; nSrcMinY = pasEntries[iEntry].YMin; nSrcMaxX = pasEntries[iEntry].XMax; nSrcMaxY = pasEntries[iEntry].YMax; } else { nSrcMinX = std::min(nSrcMinX, pasEntries[iEntry].XMin); nSrcMinY = std::min(nSrcMinY, pasEntries[iEntry].YMin); nSrcMaxX = std::max(nSrcMaxX, pasEntries[iEntry].XMax); nSrcMaxY = std::max(nSrcMaxY, pasEntries[iEntry].YMax); } } const int nSrcWidth = std::abs(nSrcMaxX - nSrcMinX); const int nSrcHeight = std::abs(nSrcMaxY - nSrcMinY); // Calculate the separation for each pair (note that it may be negative // in case of overlap) // Normalize the separation by dividing by the extents of the // corresponding dimension const double dX = nSrcWidth == 0 ? 0 : (double)(nHighestMinX - nLowestMaxX) / nSrcWidth; const double dY = nSrcHeight == 0 ? 0 : (double)(nHighestMinY - nLowestMaxY) / nSrcHeight; // Choose the pair with the greatest normalized separation along // any dimension if (dX > dY) { nSeed1 = nHighestMinXId; nSeed2 = nLowestMaxXId; } else { nSeed1 = nHighestMinYId; nSeed2 = nLowestMaxYId; } // If nSeed1==nSeed2 then just pick any two (giving pref to current child) if (nSeed1 == nSeed2) { if (nSeed1 != nSrcCurChildIndex && nSrcCurChildIndex != -1) nSeed1 = nSrcCurChildIndex; else if (nSeed1 != 0) nSeed1 = 0; else nSeed1 = 1; } // Decide which of the two seeds best matches the new entry. That seed and // the new entry will stay in current node (new entry will be added by the // caller later). The other seed will go in the 2nd node const double dAreaDiff1 = ComputeAreaDiff(pasEntries[nSeed1].XMin, pasEntries[nSeed1].YMin, pasEntries[nSeed1].XMax, pasEntries[nSeed1].YMax, nNewEntryXMin, nNewEntryYMin, nNewEntryXMax, nNewEntryYMax); const double dAreaDiff2 = ComputeAreaDiff(pasEntries[nSeed2].XMin, pasEntries[nSeed2].YMin, pasEntries[nSeed2].XMax, pasEntries[nSeed2].YMax, nNewEntryXMin, nNewEntryYMin, nNewEntryXMax, nNewEntryYMax); /* Note that we want to keep this node's current child in here. * Since splitting happens only during an addentry() operation and * then both the current child and the New Entry should fit in the same * area. */ if (nSeed1 != nSrcCurChildIndex && (dAreaDiff1 > dAreaDiff2 || nSeed2 == nSrcCurChildIndex)) { // Seed2 stays in this node, Seed1 moves to new node // ... swap Seed1 and Seed2 indices int nTmp = nSeed1; nSeed1 = nSeed2; nSeed2 = nTmp; } return 0; } /********************************************************************** * TABMAPIndexBlock::SplitNode() * * Split current Node, update the references in the parent node, etc. * Note that Root Nodes cannot be split using this method... SplitRootNode() * should be used instead. * * nNewEntry* are the coord. of the new entry that * will be added after the split. The split is done so that the current * node will be the one in which the new object should be stored. * * Returns 0 on success, -1 on error. **********************************************************************/ int TABMAPIndexBlock::SplitNode(GInt32 nNewEntryXMin, GInt32 nNewEntryYMin, GInt32 nNewEntryXMax, GInt32 nNewEntryYMax) { CPLAssert(m_poBlockManagerRef); /*----------------------------------------------------------------- * Create a 2nd node *----------------------------------------------------------------*/ TABMAPIndexBlock *poNewNode = new TABMAPIndexBlock(m_eAccess); if (poNewNode->InitNewBlock(m_fp, m_nBlockSize, m_poBlockManagerRef->AllocNewBlock("INDEX")) != 0) { return -1; } poNewNode->SetMAPBlockManagerRef(m_poBlockManagerRef); /*----------------------------------------------------------------- * Make a temporary copy of the entries in current node *----------------------------------------------------------------*/ int nSrcEntries = m_numEntries; TABMAPIndexEntry *pasSrcEntries = (TABMAPIndexEntry*)CPLMalloc(m_numEntries*sizeof(TABMAPIndexEntry)); memcpy(pasSrcEntries, &m_asEntries, m_numEntries*sizeof(TABMAPIndexEntry)); int nSrcCurChildIndex = m_nCurChildIndex; /*----------------------------------------------------------------- * Pick Seeds for each node *----------------------------------------------------------------*/ int nSeed1, nSeed2; PickSeedsForSplit(pasSrcEntries, nSrcEntries, nSrcCurChildIndex, nNewEntryXMin, nNewEntryYMin, nNewEntryXMax, nNewEntryYMax, nSeed1, nSeed2); /*----------------------------------------------------------------- * Reset number of entries in this node and start moving new entries *----------------------------------------------------------------*/ m_numEntries = 0; // Insert nSeed1 in this node InsertEntry(pasSrcEntries[nSeed1].XMin, pasSrcEntries[nSeed1].YMin, pasSrcEntries[nSeed1].XMax, pasSrcEntries[nSeed1].YMax, pasSrcEntries[nSeed1].nBlockPtr); // Move nSeed2 to 2nd node poNewNode->InsertEntry(pasSrcEntries[nSeed2].XMin, pasSrcEntries[nSeed2].YMin, pasSrcEntries[nSeed2].XMax, pasSrcEntries[nSeed2].YMax, pasSrcEntries[nSeed2].nBlockPtr); // Update cur child index if necessary if (nSeed1 == nSrcCurChildIndex) m_nCurChildIndex = m_numEntries-1; /*----------------------------------------------------------------- * Go through the rest of the entries and assign them to one * of the 2 nodes. * * Criteria is minimal area difference. * Resolve ties by adding the entry to the node with smaller total * area, then to the one with fewer entries, then to either. *----------------------------------------------------------------*/ for(int iEntry=0; iEntry<nSrcEntries; iEntry++) { if (iEntry == nSeed1 || iEntry == nSeed2) continue; // If one of the two nodes is almost full then all remaining // entries should go to the other node // The entry corresponding to the current child also automatically // stays in this node. if (iEntry == nSrcCurChildIndex) { InsertEntry(pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin, pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax, pasSrcEntries[iEntry].nBlockPtr); // Update current child index m_nCurChildIndex = m_numEntries-1; continue; } else if (m_numEntries >= GetMaxEntries()-1) { poNewNode->InsertEntry(pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin, pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax, pasSrcEntries[iEntry].nBlockPtr); continue; } else if (poNewNode->GetNumEntries() >= GetMaxEntries()-1) { InsertEntry(pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin, pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax, pasSrcEntries[iEntry].nBlockPtr); continue; } // Decide which of the two nodes to put this entry in RecomputeMBR(); const double dAreaDiff1 = ComputeAreaDiff(m_nMinX, m_nMinY, m_nMaxX, m_nMaxY, pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin, pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax); GInt32 nXMin2 = 0; GInt32 nYMin2 = 0; GInt32 nXMax2 = 0; GInt32 nYMax2 = 0; poNewNode->RecomputeMBR(); poNewNode->GetMBR(nXMin2, nYMin2, nXMax2, nYMax2); const double dAreaDiff2 = ComputeAreaDiff(nXMin2, nYMin2, nXMax2, nYMax2, pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin, pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax); if( dAreaDiff1 < dAreaDiff2 ) { // This entry stays in this node. InsertEntry(pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin, pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax, pasSrcEntries[iEntry].nBlockPtr); } else { // This entry goes to new node poNewNode->InsertEntry(pasSrcEntries[iEntry].XMin, pasSrcEntries[iEntry].YMin, pasSrcEntries[iEntry].XMax, pasSrcEntries[iEntry].YMax, pasSrcEntries[iEntry].nBlockPtr); } } /*----------------------------------------------------------------- * Recompute MBR and update current node info in parent *----------------------------------------------------------------*/ RecomputeMBR(); poNewNode->RecomputeMBR(); /*----------------------------------------------------------------- * Add second node info to parent and then flush it to disk. * This may trigger splitting of parent *----------------------------------------------------------------*/ CPLAssert(m_poParentRef); int nMinX, nMinY, nMaxX, nMaxY; poNewNode->GetMBR(nMinX, nMinY, nMaxX, nMaxY); m_poParentRef->AddEntry(nMinX, nMinY, nMaxX, nMaxY, poNewNode->GetNodeBlockPtr(), TRUE); poNewNode->CommitToFile(); delete poNewNode; CPLFree(pasSrcEntries); return 0; } /********************************************************************** * TABMAPIndexBlock::SplitRootNode() * * (private method) * * Split a Root Node. * First, a level of nodes must be added to the tree, then the contents * of what used to be the root node is moved 1 level down and then that * node is split like a regular node. * * Returns 0 on success, -1 on error **********************************************************************/ int TABMAPIndexBlock::SplitRootNode(GInt32 nNewEntryXMin, GInt32 nNewEntryYMin, GInt32 nNewEntryXMax, GInt32 nNewEntryYMax) { CPLAssert(m_poBlockManagerRef); CPLAssert(m_poParentRef == NULL); /*----------------------------------------------------------------- * Since a root note cannot be split, we add a level of nodes * under it and we'll do the split at that level. *----------------------------------------------------------------*/ TABMAPIndexBlock *poNewNode = new TABMAPIndexBlock(m_eAccess); if (poNewNode->InitNewBlock(m_fp, m_nBlockSize, m_poBlockManagerRef->AllocNewBlock("INDEX")) != 0) { return -1; } poNewNode->SetMAPBlockManagerRef(m_poBlockManagerRef); // Move all entries to the new child int nSrcEntries = m_numEntries; m_numEntries = 0; for(int iEntry=0; iEntry<nSrcEntries; iEntry++) { poNewNode->InsertEntry(m_asEntries[iEntry].XMin, m_asEntries[iEntry].YMin, m_asEntries[iEntry].XMax, m_asEntries[iEntry].YMax, m_asEntries[iEntry].nBlockPtr); } /*----------------------------------------------------------------- * Transfer current child object to new node. *----------------------------------------------------------------*/ if (m_poCurChild) { poNewNode->SetCurChildRef(m_poCurChild, m_nCurChildIndex); m_poCurChild->SetParentRef(poNewNode); m_poCurChild = NULL; m_nCurChildIndex = -1; } /*----------------------------------------------------------------- * Place info about new child in current node. *----------------------------------------------------------------*/ poNewNode->RecomputeMBR(); int nMinX, nMinY, nMaxX, nMaxY; poNewNode->GetMBR(nMinX, nMinY, nMaxX, nMaxY); InsertEntry(nMinX, nMinY, nMaxX, nMaxY, poNewNode->GetNodeBlockPtr()); /*----------------------------------------------------------------- * Keep a reference to the new child *----------------------------------------------------------------*/ poNewNode->SetParentRef(this); m_poCurChild = poNewNode; m_nCurChildIndex = m_numEntries -1; /*----------------------------------------------------------------- * And finally force the child to split itself *----------------------------------------------------------------*/ return m_poCurChild->SplitNode(nNewEntryXMin, nNewEntryYMin, nNewEntryXMax, nNewEntryYMax); } /********************************************************************** * TABMAPIndexBlock::RecomputeMBR() * * Recompute current block MBR, and update info in parent. **********************************************************************/ void TABMAPIndexBlock::RecomputeMBR() { GInt32 nMinX, nMinY, nMaxX, nMaxY; nMinX = 1000000000; nMinY = 1000000000; nMaxX = -1000000000; nMaxY = -1000000000; for(int i=0; i<m_numEntries; i++) { if (m_asEntries[i].XMin < nMinX) nMinX = m_asEntries[i].XMin; if (m_asEntries[i].XMax > nMaxX) nMaxX = m_asEntries[i].XMax; if (m_asEntries[i].YMin < nMinY) nMinY = m_asEntries[i].YMin; if (m_asEntries[i].YMax > nMaxY) nMaxY = m_asEntries[i].YMax; } if (m_nMinX != nMinX || m_nMinY != nMinY || m_nMaxX != nMaxX || m_nMaxY != nMaxY ) { m_nMinX = nMinX; m_nMinY = nMinY; m_nMaxX = nMaxX; m_nMaxY = nMaxY; m_bModified = TRUE; if (m_poParentRef) m_poParentRef->UpdateCurChildMBR(m_nMinX, m_nMinY, m_nMaxX, m_nMaxY, GetNodeBlockPtr()); } } /********************************************************************** * TABMAPIndexBlock::UpdateCurChildMBR() * * Update current child MBR info, and propagate info in parent. * * nBlockPtr is passed only to validate the consistency of the tree. **********************************************************************/ void TABMAPIndexBlock::UpdateCurChildMBR(GInt32 nXMin, GInt32 nYMin, GInt32 nXMax, GInt32 nYMax, CPL_UNUSED GInt32 nBlockPtr) { CPLAssert(m_poCurChild); CPLAssert(m_asEntries[m_nCurChildIndex].nBlockPtr == nBlockPtr); if (m_asEntries[m_nCurChildIndex].XMin == nXMin && m_asEntries[m_nCurChildIndex].YMin == nYMin && m_asEntries[m_nCurChildIndex].XMax == nXMax && m_asEntries[m_nCurChildIndex].YMax == nYMax) { return; /* Nothing changed... nothing to do */ } m_bModified = TRUE; m_asEntries[m_nCurChildIndex].XMin = nXMin; m_asEntries[m_nCurChildIndex].YMin = nYMin; m_asEntries[m_nCurChildIndex].XMax = nXMax; m_asEntries[m_nCurChildIndex].YMax = nYMax; m_nMinX = 1000000000; m_nMinY = 1000000000; m_nMaxX = -1000000000; m_nMaxY = -1000000000; for(int i=0; i<m_numEntries; i++) { if (m_asEntries[i].XMin < m_nMinX) m_nMinX = m_asEntries[i].XMin; if (m_asEntries[i].XMax > m_nMaxX) m_nMaxX = m_asEntries[i].XMax; if (m_asEntries[i].YMin < m_nMinY) m_nMinY = m_asEntries[i].YMin; if (m_asEntries[i].YMax > m_nMaxY) m_nMaxY = m_asEntries[i].YMax; } if (m_poParentRef) m_poParentRef->UpdateCurChildMBR(m_nMinX, m_nMinY, m_nMaxX, m_nMaxY, GetNodeBlockPtr()); } /********************************************************************** * TABMAPIndexBlock::SetMAPBlockManagerRef() * * Pass a reference to the block manager object for the file this * block belongs to. The block manager will be used by this object * when it needs to automatically allocate a new block. **********************************************************************/ void TABMAPIndexBlock::SetMAPBlockManagerRef(TABBinBlockManager *poBlockMgr) { m_poBlockManagerRef = poBlockMgr; }; /********************************************************************** * TABMAPIndexBlock::SetParentRef() * * Used to pass a reference to this node's parent. **********************************************************************/ void TABMAPIndexBlock::SetParentRef(TABMAPIndexBlock *poParent) { m_poParentRef = poParent; } /********************************************************************** * TABMAPIndexBlock::SetCurChildRef() * * Used to transfer a child object from one node to another **********************************************************************/ void TABMAPIndexBlock::SetCurChildRef(TABMAPIndexBlock *poChild, int nChildIndex) { m_poCurChild = poChild; m_nCurChildIndex = nChildIndex; } /********************************************************************** * TABMAPIndexBlock::Dump() * * Dump block contents... available only in DEBUG mode. **********************************************************************/ #ifdef DEBUG void TABMAPIndexBlock::Dump(FILE *fpOut /*=NULL*/) { if (fpOut == NULL) fpOut = stdout; fprintf(fpOut, "----- TABMAPIndexBlock::Dump() -----\n"); if (m_pabyBuf == NULL) { fprintf(fpOut, "Block has not been initialized yet."); } else { fprintf(fpOut,"Index Block (type %d) at offset %d.\n", m_nBlockType, m_nFileOffset); fprintf(fpOut," m_numEntries = %d\n", m_numEntries); /*------------------------------------------------------------- * Loop through all entries, dumping each of them *------------------------------------------------------------*/ if (m_numEntries > 0) ReadAllEntries(); for(int i=0; i<m_numEntries; i++) { fprintf(fpOut, " %6d -> (%d, %d) - (%d, %d)\n", m_asEntries[i].nBlockPtr, m_asEntries[i].XMin, m_asEntries[i].YMin, m_asEntries[i].XMax, m_asEntries[i].YMax ); } } fflush(fpOut); } #endif // DEBUG