tabindnode.cpp

linux下一款GIS程序源码

            }
            else if (nCmpStatus == 0)
            {
                /* Found it!  Return the record number */
                return ReadIndexEntry(m_nCurIndexEntry, NULL);
            }
            else
            {
                /* Item does not exist... return 0 */
                return 0;
            }
        }
    }
    else
    {
        /*-------------------------------------------------------------
         * Index Node: Find the child node that is the best candidate to
         * contain the value
         *
         * In the index tree at the node level, for each node entry inside
         * the parent node, the key value (in the parent) corresponds to 
         * the value of the first key that you will find when you access
         * the corresponding child node.
         *
         * This means that to find the child that contains the searched
         * key, we look for the first index key >= pKeyValue and the child
         * node that we are looking for is the one that precedes it.
         *
         * If the first key in the list is >= pKeyValue then this means
         * that the pKeyValue does not exist in our children and we just
         * return 0.  We do not bother searching the previous node at the
         * same level since this is the responsibility of our parent.
         *
         * The same way if the last indexkey in this node is < pKeyValue
         * we won't bother searching the next node since this should also
         * be taken care of by our parent.
         *------------------------------------------------------------*/
        while(m_nCurIndexEntry < m_numEntriesInNode)
        {
            int nCmpStatus = IndexKeyCmp(pKeyValue, m_nCurIndexEntry);

            if (nCmpStatus > 0 && m_nCurIndexEntry+1 < m_numEntriesInNode)
            {
                /* Not there yet... (pKey > IndexEntry) */
                m_nCurIndexEntry++;
            }
            else
            {
                /*-----------------------------------------------------
                 * We either found an indexkey >= pKeyValue or reached 
                 * the last entry in this node... still have to decide 
                 * what we're going to do... 
                 *----------------------------------------------------*/
                if (nCmpStatus < 0 && m_nCurIndexEntry == 0)
                {
                    /*-------------------------------------------------
                     * First indexkey in block is > pKeyValue...
                     * the key definitely does not exist in our children.
                     * However, we still want to drill down the rest of the
                     * tree because this function is also used when looking
                     * for a node to insert a new value.
                     *-------------------------------------------------*/
                    // Nothing special to do... just continue processing.
                }

                /*-----------------------------------------------------
                 * If we found an node for which pKeyValue < indexkey 
                 * (or pKeyValue <= indexkey for non-unique indexes) then 
                 * we access the preceding child node.
                 *
                 * Note that for indexkey == pKeyValue in non-unique indexes
                 * we also check in the preceding node because when keys
                 * are not unique then there are chances that the requested
                 * key could also be found at the end of the preceding node.
                 * In this case, if we don't find the key in the preceding
                 * node then we'll do a second search in the current node.
                 *----------------------------------------------------*/
                int numChildrenToVisit=1;
                if (m_nCurIndexEntry > 0 &&
                    (nCmpStatus < 0 || (nCmpStatus==0 && !m_bUnique)) )
                {
                    m_nCurIndexEntry--;
                    if (nCmpStatus == 0)
                        numChildrenToVisit = 2;
                }

                /*-----------------------------------------------------
                 * OK, now it's time to load/access the candidate child nodes.
                 *----------------------------------------------------*/
                int nRetValue = 0;
                for(int iChild=0; nRetValue==0 && 
                                  iChild<numChildrenToVisit; iChild++)
                {
                    // If we're doing a second pass then jump to next entry
                    if (iChild > 0)
                        m_nCurIndexEntry++;

                    int nChildNodePtr = ReadIndexEntry(m_nCurIndexEntry, NULL);
                    if (nChildNodePtr == 0)
                    {
                        /* Invalid child node??? */
                        nRetValue = 0;
                        continue;
                    }
                    else if (m_poCurChildNode == NULL)
                    {
                        /* Child node has never been initialized...do it now!*/

                        m_poCurChildNode = new TABINDNode(m_eAccessMode);
                        if ( m_poCurChildNode->InitNode(m_fp, nChildNodePtr, 
                                                        m_nKeyLength, 
                                                        m_nSubTreeDepth-1,
                                                        m_bUnique,
                                                        m_poBlockManagerRef, 
                                                        this) != 0 ||
                             m_poCurChildNode->SetFieldType(m_eFieldType)!=0)
                        {
                            // An error happened... and was already reported
                            return -1;
                        }
                    }

                    if (m_poCurChildNode->GotoNodePtr(nChildNodePtr) != 0)
                    {
                        // An error happened and has already been reported
                        return -1;
                    }

                    nRetValue = m_poCurChildNode->FindFirst(pKeyValue);
                }/*for iChild*/

                return nRetValue;

            }/*else*/

        }/*while numEntries*/

        // No node was found that contains the key value.
        // We should never get here... only leaf nodes should return 0
        assert(FALSE);
        return 0;
    }

    return 0;  // Not found
}




/**********************************************************************
 *                   TABINDNode::FindNext()
 *
 * Continue the search previously started by FindFirst() in this node 
 * and its children for a key value.
 *
 * Return value:
 *  - the key's corresponding record number in the .DAT file (greater than 0)
 *  - 0 if the key was not found
 *  - or -1 if an error happened
 **********************************************************************/
UGKInt32 TABINDNode::FindNext(UGKByte *pKeyValue)
{
    if (m_poDataBlock == NULL)
    {
        UGKError(ET_Failure, UGKErr_AssertionFailed,
                  "TABINDNode::Search(): Node has not been initialized yet!");
        return -1;
    }

    /*-----------------------------------------------------------------
     * m_nCurIndexEntry is the index of the last item that has been 
     * returned by FindFirst()/FindNext().
     *----------------------------------------------------------------*/

    if (m_nSubTreeDepth == 1)
    {
        /*-------------------------------------------------------------
         * Leaf node level... check if the next entry is an exact match
         *------------------------------------------------------------*/
        m_nCurIndexEntry++;
        if (m_nCurIndexEntry >= m_numEntriesInNode && m_nNextNodePtr > 0)
        {
            // We're at the end of a node ... continue with next node
            GotoNodePtr(m_nNextNodePtr);
            m_nCurIndexEntry = 0;
        }

        if (m_nCurIndexEntry < m_numEntriesInNode &&
            IndexKeyCmp(pKeyValue, m_nCurIndexEntry) == 0)
        {
           /* Found it!  Return the record number */
            return ReadIndexEntry(m_nCurIndexEntry, NULL);
        }
        else
        {
            /* No more items with that key... return 0 */
            return 0;
        }
    }
    else
    {
        /*-------------------------------------------------------------
         * Index Node: just pass the search to this child node.
         *------------------------------------------------------------*/
        while(m_nCurIndexEntry < m_numEntriesInNode)
        {
            if (m_poCurChildNode != NULL)
                return m_poCurChildNode->FindNext(pKeyValue);
        }
    }

    // No more nodes were found that contain the key value.
    return 0;
}



/**********************************************************************
 *                   TABINDNode::CommitToFile()
 *
 * For write access, write current block and its children to file.
 *
 * note: TABRawBinBlock::CommitToFile() does nothing unless the block has
 *       been modified.  (it has an internal bModified flag)
 *
 * Returns 0 on success, -1 on error.
 **********************************************************************/
int TABINDNode::CommitToFile()
{
    if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) || 
        m_poDataBlock == NULL)
        return -1;

    if (m_poCurChildNode)
    {
        if (m_poCurChildNode->CommitToFile() != 0)
            return -1;

        m_nSubTreeDepth = m_poCurChildNode->GetSubTreeDepth() + 1;
    }

    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(UGKByte *pKeyValue, UGKInt32 nRecordNo,
                         UGKBool bAddInThisNodeOnly /*=FALSE*/,
                         UGKBool bInsertAfterCurChild /*=FALSE*/,
                         UGKBool 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)
    {
        assert(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!!!
         *------------------------------------------------------------*/
        assert(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