mitab_indfile.cpp

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

/**********************************************************************
 *                   TABINDNode::IndexKeyCmp()
 *
 * Compare the specified index entry with the key value, and 
 * return 0 if equal, an integer less than 0 if key is smaller than 
 * index entry, and an integer greater than 0 if key is bigger than 
 * index entry.
 *
 * nEntryNo is the 0-based index of the index entry that we are interested
 * in inside the current node.
 **********************************************************************/
int   TABINDNode::IndexKeyCmp(GByte *pKeyValue, int nEntryNo)
{
    CPLAssert(pKeyValue);
    CPLAssert(nEntryNo >= 0 && nEntryNo < m_numEntriesInNode);

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

    return memcmp(pKeyValue, m_poDataBlock->GetCurDataPtr(), m_nKeyLength);
}

/**********************************************************************
 *                   TABINDNode::SetFieldType()
 *
 * Sets the field type for the current index and recursively set all 
 * children as well.
 * This information will then be used in building the key values, etc.
 *
 * Returns 0 on success, -1 on error.
 **********************************************************************/
int TABINDNode::SetFieldType(TABFieldType eType)
{
    if (m_fp == NULL)
    {
        CPLError(CE_Failure, CPLE_AssertionFailed,
                 "TABINDNode::SetFieldType(): File has not been opened yet!");
        return -1;
    }

    /*-----------------------------------------------------------------
     * Validate field type with key length
     *----------------------------------------------------------------*/
    if ((eType == TABFInteger && m_nKeyLength != 4) ||
        (eType == TABFSmallInt && m_nKeyLength != 2) ||
        (eType == TABFFloat && m_nKeyLength != 8) ||
        (eType == TABFDecimal && m_nKeyLength != 8) ||
        (eType == TABFDate && m_nKeyLength != 4) ||
        (eType == TABFLogical && m_nKeyLength != 4) )
    {
        CPLError(CE_Failure, CPLE_IllegalArg,
                 "Index key length (%d) does not match field type (%s).",
                 m_nKeyLength, TABFIELDTYPE_2_STRING(eType) );
        return -1;
    }           
    
    m_eFieldType = eType;

    /*-----------------------------------------------------------------
     * Pass the field type info to child nodes
     *----------------------------------------------------------------*/
    if (m_poCurChildNode)
        return m_poCurChildNode->SetFieldType(eType);

    return 0;
}

/**********************************************************************
 *                   TABINDNode::FindFirst()
 *
 * Start a new search in this node and its children for a key value.
 * If the index is not unique, then FindNext() can be used to return
 * the other values that correspond to the key.
 *
 * 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
 **********************************************************************/
GInt32 TABINDNode::FindFirst(GByte *pKeyValue)
{
    if (m_poDataBlock == NULL)
    {
        CPLError(CE_Failure, CPLE_AssertionFailed,
                 "TABINDNode::Search(): Node has not been initialized yet!");
        return -1;
    }

    /*-----------------------------------------------------------------
     * Unless something has been broken, this method will be called by our
     * parent node after it has established that we are the best candidate
     * to contain the first instance of the key value.  So there is no
     * need to look in the previous or next nodes in the chain... if the
     * value is not found in the current node block then it is not present
     * in the index at all.
     *
     * m_nCurIndexEntry will be used to keep track of the search pointer
     * when FindNext() will be used.
     *----------------------------------------------------------------*/
    m_nCurIndexEntry = 0;

    if (m_nSubTreeDepth == 1)
    {
        /*-------------------------------------------------------------
         * Leaf node level... we look for an exact match
         *------------------------------------------------------------*/
        while(m_nCurIndexEntry < m_numEntriesInNode)
        {
            int nCmpStatus = IndexKeyCmp(pKeyValue, m_nCurIndexEntry);
            if (nCmpStatus > 0)
            {
                /* Not there yet... (pKey > IndexEntry) */
                m_nCurIndexEntry++;
            }
            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
        CPLAssert(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
 **********************************************************************/
GInt32 TABINDNode::FindNext(GByte *pKeyValue)
{
    if (m_poDataBlock == NULL)
    {
        CPLError(CE_Failure, CPLE_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;
    }