* Search one of the indexes for a key value.  
 *
 * Note that index numbers are positive values starting at 1.
 *
 * 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 TABINDFile::FindFirst(int nIndexNumber, GByte *pKeyValue)
{
    if (ValidateIndexNo(nIndexNumber) != 0)
        return -1;

    return m_papoIndexRootNodes[nIndexNumber-1]->FindFirst(pKeyValue);
}

/**********************************************************************
 *                   TABINDFile::FindNext()
 *
 * Continue the Search for pKeyValue previously initiated by FindFirst().  
 * NOTE: FindFirst() MUST have been previously called for this call to
 *       work...
 *
 * Note that index numbers are positive values starting at 1.
 *
 * 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 TABINDFile::FindNext(int nIndexNumber, GByte *pKeyValue)
{
    if (ValidateIndexNo(nIndexNumber) != 0)
        return -1;

    return m_papoIndexRootNodes[nIndexNumber-1]->FindNext(pKeyValue);
}


/**********************************************************************
 *                   TABINDFile::CreateIndex()
 *
 * Create a new index with the specified field type and size.
 * Field size applies only to char field type... the other types have a
 * predefined key length.
 *
 * Key length is limited to 128 chars. char fields longer than 128 chars
 * will have their key truncated to 128 bytes.
 *
 * Note that a .IND file can contain only a maximum of 29 indexes.
 *
 * Returns the new field index on success (greater than 0), or -1 on error.
 **********************************************************************/
int TABINDFile::CreateIndex(TABFieldType eType, int nFieldSize)
{
    int i, nNewIndexNo = -1;

    if (m_fp == NULL || 
        (m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite))
        return -1;

    // __TODO__
    // We'll need more work in TABDATFile::WriteDateTimeField() before
    // we can support indexes on fields of type DateTime (see bug #1844)
    if (eType == TABFDateTime)
    {
        CPLError(CE_Failure, CPLE_AssertionFailed,
                 "Index on fields of type DateTime not supported yet.");
        return -1;
    }

    /*-----------------------------------------------------------------
     * Look for an empty slot in the current array, if there is none
     * then extend the array.
     *----------------------------------------------------------------*/
    for(i=0; m_papoIndexRootNodes && i<m_numIndexes; i++)
    {
        if (m_papoIndexRootNodes[i] == NULL)
        {
            nNewIndexNo = i;
            break;
        }
    }

    if (nNewIndexNo == -1 && m_numIndexes >= 29)
    {
        CPLError(CE_Failure, CPLE_AppDefined,
                 "Cannot add new index to %s.  A dataset can contain only a "
                 "maximum of 29 indexes.", m_pszFname);
        return -1;
    }

    if (nNewIndexNo == -1)
    {
        /*-------------------------------------------------------------
         * Add a slot for new index at the end of the nodes array.
         *------------------------------------------------------------*/
        m_numIndexes++;
        m_papoIndexRootNodes = (TABINDNode**)CPLRealloc( m_papoIndexRootNodes,
                                                         m_numIndexes*
                                                         sizeof(TABINDNode*));

        m_papbyKeyBuffers = (GByte **)CPLRealloc(m_papbyKeyBuffers,
                                                 m_numIndexes*sizeof(GByte*));

        nNewIndexNo = m_numIndexes-1;
    }

    /*-----------------------------------------------------------------
     * Alloc and init new node
     * The call to InitNode() automatically allocates storage space for
     * the node in the file.
     * New nodes are created with a subtree_depth=1 since they start as
     * leaf nodes, i.e. their entries point directly to .DAT records
     *----------------------------------------------------------------*/
    int nKeyLength = ((eType == TABFInteger)  ? 4:
                      (eType == TABFSmallInt) ? 2:
                      (eType == TABFFloat)    ? 8:
                      (eType == TABFDecimal)  ? 8:
                      (eType == TABFDate)     ? 4:
                      (eType == TABFTime)     ? 4:
                      (eType == TABFDateTime) ? 8:
                      (eType == TABFLogical)  ? 4: MIN(128,nFieldSize));

    m_papoIndexRootNodes[nNewIndexNo] = new TABINDNode(m_eAccessMode);
    if (m_papoIndexRootNodes[nNewIndexNo]->InitNode(m_fp, 0, nKeyLength, 
                                                    1,  // subtree depth=1
                                                    FALSE, // not unique
                                                    &m_oBlockManager, 
                                                    NULL, 0, 0)!= 0)
    {
        // CPLError has already been called
        return -1;
    }

    // Alloc a temporary key buffer for this index.
    // This buffer will be used by the BuildKey() method
    m_papbyKeyBuffers[nNewIndexNo] = (GByte *)CPLCalloc(nKeyLength+1,
                                                        sizeof(GByte));

    // Return 1-based index number
    return nNewIndexNo+1;
}


/**********************************************************************
 *                   TABINDFile::AddEntry()
 *
 * Add an .DAT record entry for pKeyValue in the specified index.
 *
 * Note that index numbers are positive values starting at 1.
 * nRecordNo is the .DAT record number, record numbers start at 1.
 *
 * Returns 0 on success, -1 on error
 **********************************************************************/
int TABINDFile::AddEntry(int nIndexNumber, GByte *pKeyValue, GInt32 nRecordNo)
{
    if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) || 
        ValidateIndexNo(nIndexNumber) != 0)
        return -1;

    return m_papoIndexRootNodes[nIndexNumber-1]->AddEntry(pKeyValue,nRecordNo);
}


/**********************************************************************
 *                   TABINDFile::Dump()
 *
 * Dump block contents... available only in DEBUG mode.
 **********************************************************************/
#ifdef DEBUG

void TABINDFile::Dump(FILE *fpOut /*=NULL*/)
{
    if (fpOut == NULL)
        fpOut = stdout;

    fprintf(fpOut, "----- TABINDFile::Dump() -----\n");

    if (m_fp == NULL)
    {
        fprintf(fpOut, "File is not opened.\n");
    }
    else
    {
        fprintf(fpOut, "File is opened: %s\n", m_pszFname);
        fprintf(fpOut, "   m_numIndexes   = %d\n", m_numIndexes);
        for(int i=0; i<m_numIndexes && m_papoIndexRootNodes; i++)
        {
            if (m_papoIndexRootNodes[i])
            {
                fprintf(fpOut, "  ----- Index # %d -----\n", i+1);
                m_papoIndexRootNodes[i]->Dump(fpOut);
            }
        }

    }

    fflush(fpOut);
}

#endif // DEBUG





/*=====================================================================
 *                      class TABINDNode
 *====================================================================*/

/**********************************************************************
 *                   TABINDNode::TABINDNode()
 *
 * Constructor.
 **********************************************************************/
TABINDNode::TABINDNode(TABAccess eAccessMode /*=TABRead*/)
{
    m_fp = NULL;
    m_poCurChildNode = NULL;
    m_nSubTreeDepth = 0;
    m_nKeyLength = 0;
    m_eFieldType = TABFUnknown;
    m_poDataBlock = NULL;
    m_numEntriesInNode = 0;
    m_nCurIndexEntry = 0;
    m_nPrevNodePtr = 0;
    m_nNextNodePtr = 0;
    m_poBlockManagerRef = NULL;
    m_poParentNodeRef = NULL;
    m_bUnique = FALSE;

    m_eAccessMode = eAccessMode;
}

/**********************************************************************
 *                   TABINDNode::~TABINDNode()
 *
 * Destructor.
 **********************************************************************/
TABINDNode::~TABINDNode()
{
    if (m_poCurChildNode)
        delete m_poCurChildNode;

    if (m_poDataBlock)
        delete m_poDataBlock;
}

/**********************************************************************
 *                   TABINDNode::InitNode()
 *
 * Init a node... this function can be used either to initialize a new
 * node, or to make it point to a new data block in the file.
 *
 * By default, this call will read the data from the file at the
 * specified location if necessary, and leave the object ready to be searched.
 *
 * In write access, if the block does not exist (i.e. nBlockPtr=0) then a
 * new one is created and initialized.
 *
 * poParentNode is used in write access in order to update the parent node
 * when this node becomes full and has to be split.
 *
 * Returns 0 on success, -1 on error.
 **********************************************************************/
int TABINDNode::InitNode(FILE *fp, int nBlockPtr, 
                         int nKeyLength, int nSubTreeDepth, 
                         GBool bUnique,
                         TABBinBlockManager *poBlockMgr /*=NULL*/,
                         TABINDNode *poParentNode /*=NULL*/,
                         int nPrevNodePtr /*=0*/, int nNextNodePtr /*=0*/)
{
    /*-----------------------------------------------------------------
     * If the block already points to the right block, then don't do 
     * anything here.
     *----------------------------------------------------------------*/
    if (m_fp == fp && nBlockPtr> 0 && m_nCurDataBlockPtr == nBlockPtr)
        return 0;

    // Keep track of some info
    m_fp = fp;
    m_nKeyLength = nKeyLength;
    m_nSubTreeDepth = nSubTreeDepth;
    m_nCurDataBlockPtr = nBlockPtr;
    m_bUnique = bUnique;

    // Do not overwrite the following values if we receive NULL (the defaults)
    if (poBlockMgr)
        m_poBlockManagerRef = poBlockMgr;
    if (poParentNode)
        m_poParentNodeRef = poParentNode;

    // Set some defaults
    m_numEntriesInNode = 0;
    m_nPrevNodePtr = nPrevNodePtr;
    m_nNextNodePtr = nNextNodePtr;

    m_nCurIndexEntry = 0;

    /*-----------------------------------------------------------------
     * Init RawBinBlock
     * The node's buffer has to be created with read/write access since
     * the index is a very dynamic structure!
     *----------------------------------------------------------------*/
    if (m_poDataBlock == NULL)
        m_poDataBlock = new TABRawBinBlock(TABReadWrite, TRUE);

    if ((m_eAccessMode == TABWrite || m_eAccessMode == TABReadWrite) && 
        nBlockPtr == 0 && m_poBlockManagerRef)
    {
        /*-------------------------------------------------------------
         * Write access: Create and init a new block
         *------------------------------------------------------------*/
        m_nCurDataBlockPtr = m_poBlockManagerRef->AllocNewBlock();
        m_poDataBlock->InitNewBlock(m_fp, 512, m_nCurDataBlockPtr);

        m_poDataBlock->WriteInt32( m_numEntriesInNode );
        m_poDataBlock->WriteInt32( m_nPrevNodePtr );
        m_poDataBlock->WriteInt32( m_nNextNodePtr );
    }
    else
    {
        CPLAssert(m_nCurDataBlockPtr > 0);
        /*-------------------------------------------------------------
         * Read the data block from the file, applies to read access, or
         * to write access (to modify an existing block)
         *------------------------------------------------------------*/
        if (m_poDataBlock->ReadFromFile(m_fp, m_nCurDataBlockPtr, 512) != 0)
        {
            // CPLError() has already been called.
            return -1;
        }

        m_poDataBlock->GotoByteInBlock(0);
        m_numEntriesInNode = m_poDataBlock->ReadInt32();
        m_nPrevNodePtr = m_poDataBlock->ReadInt32();
        m_nNextNodePtr = m_poDataBlock->ReadInt32();
    }