tabindnode.cpp

linux下一款GIS程序源码

                assert(m_poCurChildNode);
                assert(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(UGKByte *pKeyValue, UGKInt32 nRecordNo,
                            UGKBool bInsertAfterCurChild /*=FALSE*/,
                            UGKBool bMakeNewEntryCurChild /*=FALSE*/)
{
    int iInsertAt=0;

    if (GetNumEntries() >= GetMaxNumEntries())
    {   
        UGKError(ET_Failure, UGKErr_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(UGKByte *pKeyValue, UGKInt32 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(UGKByte *pKeyValue1, UGKInt32 nRecordNo1,
                                 UGKByte *pKeyValue2, UGKInt32 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;

    assert(m_numEntriesInNode >= 2);
    assert(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_nNextNodePtr = poNewNode->GetNodeBlockPtr();

        // Move half the entries to the new block
        m_poDataBlock->GotoByteInBlock(12 + numInNode1*(m_nKeyLength+4));

        if (poNewNode->SetNodeBufferDirectly(numInNode2, 
                                        m_poDataBlock->GetCurDataPtr()) != 0)
            return -1;

#ifdef DEBUG
        // Just in case, reset space previously used by moved entries
        memset(m_poDataBlock->GetCurDataPtr(), 0, numInNode2*(m_nKeyLength+4));
#endif
        // And update current node members
        m_numEntriesInNode = numInNode1;

        // Update parent node with new children info
        if (m_poParentNodeRef)
        {
            if (m_poParentNodeRef->UpdateSplitChild(GetNodeKey(),
                                                    GetNodeBlockPtr(),
                                                    poNewNode->GetNodeKey(),
                                        poNewNode->GetNodeBlockPtr(), 1) != 0)
                return -1;
        }

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

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