mitab_indfile.cpp

GIS系统支持库Geospatial Data Abstraction Library代码.GDAL is a translator library for raster geospatial dat

    return m_poDataBlock->CommitToFile();
}

/**********************************************************************
 *                   TABINDNode::AddEntry()
 *
 * Add an .DAT record entry for pKeyValue in this index
 *
 * nRecordNo is the .DAT record number, record numbers start at 1.
 *
 * In order to insert a new value, the root node first does a FindFirst()
 * that will load the whole tree branch up to the insertion point.
 * Then AddEntry() is recursively called up to the leaf node level for
 * the insertion of the actual value.
 * If the leaf node is full then it will be split and if necessary the 
 * split will propagate up in the tree through the pointer that each node
 * has on its parent.
 *
 * 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 splitted has to be updated.
 *
 * bInsertAfterCurChild forces the insertion to happen immediately after
 * the m_nCurIndexEntry.  This works only when bAddInThisNodeOnly=TRUE.
 * The default is to search the node for a an insertion point.
 *
 * Returns 0 on success, -1 on error
 **********************************************************************/
int TABINDNode::AddEntry(GByte *pKeyValue, GInt32 nRecordNo,
                         GBool bAddInThisNodeOnly /*=FALSE*/,
                         GBool bInsertAfterCurChild /*=FALSE*/,
                         GBool bMakeNewEntryCurChild /*=FALSE*/)
{
    if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) || 
        m_poDataBlock == NULL)
        return -1;

    /*-----------------------------------------------------------------
     * If I'm the root node, then do a FindFirst() to init all the nodes
     * and to make all of them point ot the insertion point.
     *----------------------------------------------------------------*/
    if (m_poParentNodeRef == NULL && !bAddInThisNodeOnly)
    {
        if (FindFirst(pKeyValue) < 0)
            return -1;  // Error happened and has already been reported.
    }

    if (m_poCurChildNode && !bAddInThisNodeOnly)
    {
        CPLAssert(m_nSubTreeDepth > 1);
        /*-------------------------------------------------------------
         * Propagate the call down to our children
         * Note: this recursive call could result in new levels of nodes
         * being added under our feet by SplitRootnode() so it is very 
         * important to return right after this call or we might not be 
         * able to recognize this node at the end of the call!
         *------------------------------------------------------------*/
        return m_poCurChildNode->AddEntry(pKeyValue, nRecordNo);
    }
    else
    {
        /*-------------------------------------------------------------
         * OK, we're a leaf node... this is where the real work happens!!!
         *------------------------------------------------------------*/
        CPLAssert(m_nSubTreeDepth == 1 || bAddInThisNodeOnly);

        /*-------------------------------------------------------------
         * 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 (GetNumEntries() == GetMaxNumEntries())
        {
            if (m_poParentNodeRef == NULL)
            {
                /*-----------------------------------------------------
                 * Splitting the root node adds one level to the tree, so
                 * after splitting we just redirect the call to our child.
                 *----------------------------------------------------*/
                if (SplitRootNode() != 0)
                    return -1;  // Error happened and has already been reported

                CPLAssert(m_poCurChildNode);
                CPLAssert(m_nSubTreeDepth > 1);
                return m_poCurChildNode->AddEntry(pKeyValue, nRecordNo,
                                                  bAddInThisNodeOnly,
                                                  bInsertAfterCurChild,
                                                  bMakeNewEntryCurChild);
            }
            else
            {
                /*-----------------------------------------------------
                 * Splitting a regular node will leave it 50% full.
                 *----------------------------------------------------*/
                if (SplitNode() != 0)
                    return -1; 
            }
        }

        /*-------------------------------------------------------------
         * Insert new key/value at the right position in node.
         *------------------------------------------------------------*/
        if (InsertEntry(pKeyValue, nRecordNo, 
                        bInsertAfterCurChild, bMakeNewEntryCurChild) != 0)
            return -1;
    }

    return 0;
}

/**********************************************************************
 *                   TABINDNode::InsertEntry()
 *
 * (private method)
 *
 * Insert a key/value pair in the current node buffer.
 *
 * Returns 0 on success, -1 on error
 **********************************************************************/
int TABINDNode::InsertEntry(GByte *pKeyValue, GInt32 nRecordNo,
                            GBool bInsertAfterCurChild /*=FALSE*/,
                            GBool bMakeNewEntryCurChild /*=FALSE*/)
{
    int iInsertAt=0;

    if (GetNumEntries() >= GetMaxNumEntries())
    {   
        CPLError(CE_Failure, CPLE_AssertionFailed,
                 "Node is full!  Cannot insert key!");
        return -1;
    }

    /*-----------------------------------------------------------------
     * Find the spot where the key belongs
     *----------------------------------------------------------------*/
    if (bInsertAfterCurChild)
    {
        iInsertAt = m_nCurIndexEntry+1;
    }
    else
    {
        while(iInsertAt < m_numEntriesInNode)
        {
            int nCmpStatus = IndexKeyCmp(pKeyValue, iInsertAt);
            if (nCmpStatus <= 0)
            {
                break;
            }
            iInsertAt++;
        }
    }

    m_poDataBlock->GotoByteInBlock(12 + iInsertAt*(m_nKeyLength+4));

    /*-----------------------------------------------------------------
     * Shift all entries that follow in the array
     *----------------------------------------------------------------*/
    if (iInsertAt < m_numEntriesInNode)
    {
        // Since we use memmove() directly, we need to inform 
        // m_poDataBlock that the upper limit of the buffer will move
        m_poDataBlock->GotoByteInBlock(12 + (m_numEntriesInNode+1)*
                                                        (m_nKeyLength+4));
        m_poDataBlock->GotoByteInBlock(12 + iInsertAt*(m_nKeyLength+4));

        memmove(m_poDataBlock->GetCurDataPtr()+(m_nKeyLength+4),
                m_poDataBlock->GetCurDataPtr(),
                (m_numEntriesInNode-iInsertAt)*(m_nKeyLength+4));

    }

    /*-----------------------------------------------------------------
     * Write new entry
     *----------------------------------------------------------------*/
    m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue);
    m_poDataBlock->WriteInt32(nRecordNo);

    m_numEntriesInNode++;
    m_poDataBlock->GotoByteInBlock(0);
    m_poDataBlock->WriteInt32(m_numEntriesInNode);

    if (bMakeNewEntryCurChild)
        m_nCurIndexEntry = iInsertAt;
    else if (m_nCurIndexEntry >= iInsertAt)
        m_nCurIndexEntry++;

    /*-----------------------------------------------------------------
     * If we replaced the first entry in the node, then this node's key
     * changes and we have to update the reference in the parent node.
     *----------------------------------------------------------------*/
    if (iInsertAt == 0 && m_poParentNodeRef)
    {
        if (m_poParentNodeRef->UpdateCurChildEntry(GetNodeKey(),
                                                   GetNodeBlockPtr()) != 0)
            return -1;
    }

    return 0;
}


/**********************************************************************
 *                   TABINDNode::UpdateCurChildEntry()
 *
 * Update the key for the current child node.  This method is called by
 * the child when its first entry (defining its node key) is changed.
 *
 * Returns 0 on success, -1 on error
 **********************************************************************/
int TABINDNode::UpdateCurChildEntry(GByte *pKeyValue, GInt32 nRecordNo)
{

    /*-----------------------------------------------------------------
     * Update current child entry with the info for the first node.
     *
     * For some reason, the key for first entry of the first node of each
     * level has to be set to 0 except for the leaf level.
     *----------------------------------------------------------------*/
    m_poDataBlock->GotoByteInBlock(12 + m_nCurIndexEntry*(m_nKeyLength+4));

    if (m_nCurIndexEntry == 0 && m_nSubTreeDepth > 1 && m_nPrevNodePtr == 0)
    {
        m_poDataBlock->WriteZeros(m_nKeyLength);
    }
    else
    {
        m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue);
    }
    m_poDataBlock->WriteInt32(nRecordNo);

    return 0;
}



/**********************************************************************
 *                   TABINDNode::UpdateSplitChild()
 *
 * Update the key and/or record ptr information corresponding to the 
 * current child node.
 *
 * Returns 0 on success, -1 on error
 **********************************************************************/
int TABINDNode::UpdateSplitChild(GByte *pKeyValue1, GInt32 nRecordNo1,
                                 GByte *pKeyValue2, GInt32 nRecordNo2,
                                 int nNewCurChildNo /* 1 or 2 */)
{

    /*-----------------------------------------------------------------
     * Update current child entry with the info for the first node.
     *
     * For some reason, the key for first entry of the first node of each
     * level has to be set to 0 except for the leaf level.
     *----------------------------------------------------------------*/
    m_poDataBlock->GotoByteInBlock(12 + m_nCurIndexEntry*(m_nKeyLength+4));

    if (m_nCurIndexEntry == 0 && m_nSubTreeDepth > 1 && m_nPrevNodePtr == 0)
    {
        m_poDataBlock->WriteZeros(m_nKeyLength);
    }
    else
    {
        m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue1);
    }
    m_poDataBlock->WriteInt32(nRecordNo1);

    /*-----------------------------------------------------------------
     * Add an entry for the second node after the current one and ask 
     * AddEntry() to update m_nCurIndexEntry if the new node should 
     * become the new current child.
     *----------------------------------------------------------------*/
    if (AddEntry(pKeyValue2, nRecordNo2, 
                 TRUE, /* bInThisNodeOnly */
                 TRUE, /* bInsertAfterCurChild */
                 (nNewCurChildNo==2)) != 0)
    {
            return -1;
    }

    return 0;
}


/**********************************************************************
 *                   TABINDNode::SplitNode()
 *
 * (private method)
 *
 * Split a node, update the references in the parent node, etc.
 * Note that Root Nodes cannot be split using this method... SplitRootNode()
 * should be used instead.
 *
 * The node is split in a way that the current child stays inside this
 * node object, and a new node is created for the other half of the
 * entries.  This way, the object references in this node's parent and in its 
 * current child all remain valid.  The new node is not kept in memory, 
 * it is written to disk right away.
 *
 * Returns 0 on success, -1 on error
 **********************************************************************/
int TABINDNode::SplitNode()
{
    TABINDNode *poNewNode=NULL;
    int numInNode1, numInNode2;

    CPLAssert(m_numEntriesInNode >= 2);
    CPLAssert(m_poParentNodeRef);  // This func. does not work for root nodes

    /*-----------------------------------------------------------------
     * Prepare new node
     *----------------------------------------------------------------*/
    numInNode1 = (m_numEntriesInNode+1)/2;
    numInNode2 = m_numEntriesInNode - numInNode1;

    poNewNode = new TABINDNode(m_eAccessMode);

    if (m_nCurIndexEntry < numInNode1)
    {
        /*-------------------------------------------------------------
         * We will move the second half of the array to a new node.
         *------------------------------------------------------------*/
        if (poNewNode->InitNode(m_fp, 0, m_nKeyLength, 
                                m_nSubTreeDepth, m_bUnique, 
                                m_poBlockManagerRef, m_poParentNodeRef, 
                                GetNodeBlockPtr(), m_nNextNodePtr)!= 0 ||
            poNewNode->SetFieldType(m_eFieldType) != 0 )
        {
            return -1;
        }

        // We have to update m_nPrevNodePtr in the node that used to follow
        // the current node and will now follow the new node.
        if (m_nNextNodePtr)
        {
            TABINDNode *poTmpNode = new TABINDNode(m_eAccessMode);
            if (poTmpNode->InitNode(m_fp, m_nNextNodePtr, 
                                    m_nKeyLength, m_nSubTreeDepth,
                                    m_bUnique, m_poBlockManagerRef, 
                                    m_poParentNodeRef) != 0 ||
                poTmpNode->SetPrevNodePtr(poNewNode->GetNodeBlockPtr()) != 0 ||
                poTmpNode->CommitToFile() != 0)
            {
                return -1;
            }
            delete poTmpNode;
        }

        m_nNex