pblisam.c

B树算法实现

                pbl_errno = PBL_ERROR_BAD_FILE;
                retval = -1;
                continue;
            }

            /*
             * the key in the index record has the reference key
             * as a postfix appended to it
             *
             * create a unique key for the delete
             */
            if( keylen + rkeylen > PBLKEYLENGTH )
            {
                pbl_errno = PBL_ERROR_BAD_FILE;
                retval = -1;
                continue;
            }

            /*
             * concatenate the key and the reference
             */
            memcpy( ikey, key, keylen );
            memcpy( ikey + keylen, rkey, rkeylen );

            /*
             * make sure any user defined key compare function gets used
             */
            pblkeycompare = isam->keycompare[ n ];

            /*
             * delete the key from the file
             */
            if( pblKfFind( isam->keyfiles[ n ],
                           PBLEQ, ikey, keylen + rkeylen, 0, 0 ) < 0 )
            {
                pbl_errno = PBL_ERROR_BAD_FILE;
                retval = -1;
                continue;
            }

            if( pblKfDelete( isam->keyfiles[ n ] ))
            {
                pbl_errno = PBL_ERROR_BAD_FILE;
                retval = -1;
                continue;
            }
        }
        else
        {
            /*
             * directly use the key as stored in the allkeys record
             * of the main file
             *
             * delete the key from the index file
             */
            if( pblKfFind( isam->keyfiles[ n ],
                           PBLEQ, key, keylen, 0, 0 ) < 0 )
            {
                pbl_errno = PBL_ERROR_BAD_FILE;
                retval = -1;
                continue;
            }

            if( pblKfDelete( isam->keyfiles[ n ] ))
            {
                pbl_errno = PBL_ERROR_BAD_FILE;
                retval = -1;
                continue;
            }
        }

        /*
         * move the key along the keys
         */
        key += keylen;
    }

    /*
     * delete all records from the main file
     * this deletes the "allkeys" record having a keylength of 8/17 bytes
     */
    while( pblKfFind( isam->mainfile, PBLEQ, okey, okeylen, 0, 0 ) >= 0 )
    {
        if( pblKfDelete( isam->mainfile ))
        {
            pbl_errno = PBL_ERROR_BAD_FILE;
            retval = -1;
        }
    }

    /*
     * this deletes the data records having a keylength of 9/18 bytes
     */
    while( pblKfFind( isam->mainfile, PBLEQ, okey, okeylen + 1, 0, 0 ) >= 0 )
    {
        if( pblKfDelete( isam->mainfile ))
        {
            pbl_errno = PBL_ERROR_BAD_FILE;
            retval = -1;
        }
    }

    /*
     * position the current record of the main file to the
     * allkeys record of another entry of the main file
     */
    pblIsamSetCurrentRecord( isam );

    if( retval < 0 )
    {
        pblIsamCommit( 1, &isamfile, 1 );
        return( -1 );
    }

    if( pblIsamCommit( 1, &isamfile, 0 ))
    {
        return( -1 );
    }
    return( retval );
}

/*
 * get the main key from a given index key
 *
 * for non duplicate index keys this assumes
 * that the index keyfile is positioned
 * on the record who's key is given as skey
 *
 * for index keys allowing duplicates this assumes
 * that the skey given is the "long" version,
 * with the reference key postfix attached.
 *
 * the current record of the main file is
 * positioned on the allkeys record having the key
 */
static int pblIsamGetMainKey(
PBLISAMFILE_t  * isam,
int              index,
unsigned char  * skey,
int              skeylen,
unsigned char  * okey
)
{
    long            rc;
    char            key[ PBLKEYLENGTH ];
    int             keylen;
    long            datalen;

    /*
     * make sure the index is in bounds
     */
    if( index >= isam->nkeys )
    {
        pbl_errno = PBL_ERROR_PARAM_INDEX;
        return( -1 );
    }

    /*
     * if the key has duplicates
     */
    if( isam->keydup[ index ] )
    {
        /*
         * the main key is a postfix of the referece key
         * read the key from there and convert it to an unsigned string
         */
        keylen = pblRKey2MainKey( skey, skeylen, okey );
        if( keylen < 0 )
        {
            return( -1 );
        }
    }
    else
    {
        /*
         * read the reference, this assumes that the record is positioned!
         */
        rc = pblKfRead( isam->keyfiles[ index ], key, sizeof( key ) );
        if( rc < 0 )
        {
            return( -1 );
        }
        keylen = rc;

        /*
         * get the key used in the main file
         */
        if( pblRKey2MainKey( key, keylen, okey ) < 0 )
        {
            return( -1 );
        }
    }

    /*
     * get the length of the key
     */
    keylen = strlen( okey );

    /*
     * position the current record of the main file to the allkeys record
     */
    datalen = pblKfFind( isam->mainfile, PBLFI, okey, keylen, 0, 0 );
    if( datalen < 0 )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    return( keylen );
}


/*
 * find for index keys with possible duplicates
 * 
 * writes the index key found with the reference postfix attached
 * to the supplied buffer rkey
 *
 * returns the length of that key excluding the reference postfix
 *
 * sets the length of that key including the reference postfix to rkeylen
 */
static int pblIsamFindDupKey(
PBLISAMFILE_t  * isam,
int              which,
int              index,
unsigned char  * skey,
int              skeylen,
unsigned char  * rkey,
int            * rkeylen
)
{
    long            datalen;
    char            fkey[ PBLKEYLENGTH ];
    int             fkeylen = 0;
    char            ikey[ PBLKEYLENGTH ];
    int             ikeylen = 0;
    int             keylen;
    int             lwhich = PBLLT;

    /*
     * the search key needs to leave space for the reference
     */
    if( skeylen > PBLKEYLENGTH - 2 )
    {
        pbl_errno = PBL_ERROR_PARAM_KEYLEN;
        return( -1 );
    }

    switch( which )
    {
      case PBLLT:
        /*
         * create a reference key smaller than all real ones
         */
        fkeylen = pblLongs2RKey( 0, 0, fkey );

        /*
         * search for key lower than the one created
         */
        lwhich = PBLLT;
        break;

      case PBLLE:
        /*
         * the lower equal case is treated as FIRST or LOWER THAN
         */
        fkeylen = pblIsamFindDupKey( isam, PBLFI, index,
                                     skey, skeylen, rkey, rkeylen );
        if( fkeylen > 0 )
        {
            return( fkeylen );
        }

        fkeylen = pblIsamFindDupKey( isam, PBLLT, index,                                                             skey, skeylen, rkey, rkeylen );
        return( fkeylen );
        break;

      case PBLFI:
      case PBLEQ:
        /*
         * create a reference key smaller than all real ones
         */
        fkeylen = pblLongs2RKey( 0, 0, fkey );

        /*
         * search for key greater than the one created
         */
        lwhich = PBLGT;
        break;

      case PBLLA:
        /* 
         * create a reference key bigger than all real ones
         */
        fkeylen = pblLongs2RKey( 0xffffffff, 0xffffffff, fkey );

        /*
         * search for a key lower than the one created
         */
        lwhich = PBLLT;
        break;

      case PBLGE:
        /*
         * the lower equal case is treated as LAST or GREATER THAN
         */
        fkeylen = pblIsamFindDupKey( isam, PBLLA, index,
                                     skey, skeylen, rkey, rkeylen );
        if( fkeylen > 0 )
        {
            return( fkeylen );
        }

        fkeylen = pblIsamFindDupKey( isam, PBLGT, index,                                                             skey, skeylen, rkey, rkeylen );
        return( fkeylen );
        break;

      default: /* PBLGT */
        /*
         * create a reference key bigger than all real ones
         */
        fkeylen = pblLongs2RKey( 0xffffffff, 0xffffffff, fkey );

        /*
         * search for a key greater than the one created
         */
        lwhich = PBLGT;
        break;
    }

    /*
     * create the key for the search
     */
    if( fkeylen + skeylen >= PBLKEYLENGTH )
    {
        pbl_errno = PBL_ERROR_PARAM_KEYLEN;
        return( -1 );
    }

    /*
     * concatenate the key and the reference key
     * the reference key is used as postfix of the index key
     */
    if( skeylen )
    {
        memcpy( ikey, skey, skeylen );
    }
    memcpy( ikey + skeylen, fkey, fkeylen );
    ikeylen = skeylen + fkeylen;

    /*
     * find the record in the key file
     */
    datalen = pblKfFind( isam->keyfiles[ index ], lwhich,
                         ikey, ikeylen, fkey, &fkeylen );
    if( datalen < 0 )
    {
        return( -1 );
    }

    /*
     * calculate the length of the key without the reference
     */
    keylen = pblIsamDupKeyLen( fkey, fkeylen );
    if( keylen < 0 )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    /*
     * in the FIRST, EQUAL and the LAST case the key has to match
     */
    if( which == PBLFI || which == PBLEQ || which == PBLLA )
    {
        /*
         * see whether the key matches the searchkey
         */
        if( skeylen != keylen || memcmp( skey, fkey, skeylen ))
        {
            pbl_errno = PBL_ERROR_NOT_FOUND;
            return( -1 );
        }
    }

    /*
     * save the key including the reference as return value
     */
    memcpy( rkey, fkey, fkeylen );
    *rkeylen = fkeylen;

    return( keylen );
}
    

/**
 * find a record in an ISAM file, set the current record
 *
 * parameter which specifies which record to find relative
 * to the search key specified by skey and skeylen.
 * the following values for which are possible
 *
 * <BR><B> PBLEQ </B> - find a record whose key is equal to skey
 * <BR><B> PBLFI </B> - find the first record that is equal
 * <BR><B> PBLLA </B> - find the last record that is equal
 * <BR><B> PBLGE </B> - find the last record that is equal or the smallest
 *                      record that is greater
 * <BR><B> PBLGT </B> - find the smallest record that is greater
 * <BR><B> PBLLE </B> - find the first record that is equal or the biggest
 *                      record that is smaller
 * <BR><B> PBLLT </B> - find the biggest record that is smaller
 *
 * parameter index specifies which of the keys to use
 *
 * <P>
 * <B>RESTRICTIONS</B>:
 * <BR> - the out parameter okey must point to a memory area that is
 *        big enough to hold any possible key, i.e 255 bytes
 *
 * @return int rc >= 0:
 * <UL>
 * <LI>                  call went ok,
 *                       the value returned is the length
 *                       of the key of the record found,
 * <LI>                  the key of the record is copied to okey,
 * <LI>                  the current record of the file is set to the
 *                       record found
 * </UL>
 *
 * @return int rc <  0:
 * <UL>
 * <LI>                  some error occured, see pbl_errno
 *                       especially PBL_ERROR_NOT_FOUND, if there is no
 *                       matching record
 * </UL>
 */

int pblIsamFind(
pblIsamFile_t  * isamfile,  /** ISAM file to search in                    */
int              which,     /** mode to use for search                    */
int              index,     /** index of key to use for search            */
unsigned char  * skey,      /** key to use for search                     */
int              skeylen,   /** length of search key                      */
unsigned char  * okey       /** buffer for result key                     */
)
{
    PBLISAMFILE_t * isam = ( PBLISAMFILE_t * ) isamfile;
    long            datalen;
    char            key[ PBLKEYLENGTH ];
    int             keylen;
    int             okeylen;

    /*
     * make sure the index is in bounds
     */
    if( index >= isam->nkeys )
    {
        pbl_errno = PBL_ERROR_PARAM_INDEX;
        return( -1 );
    }

    /*
     * if the key has duplicates
     */
    if( isam->keydup[ index ] )
    {
        /*
         * make sure any user defined key compare function gets used
         */
        pblkeycompare = isam->keycompare[ index ];

        /*
         * search the duplicate key
         */
        keylen = pblIsamFindDupKey( isam, which, index,
                                    skey, skeylen, okey, &okeylen );
        if( keylen < 0 )
        {
            return( keylen );
        }
    }
    else
    {
        /*
         * find the record in the key file
         */
        datalen = pblKfFind( isam->keyfiles[ index ], which,
                             skey, skeylen, okey, &okeylen );
        if( datalen < 0 )
        {
            return( datalen );
        }

        if( datalen < 2 || datalen > PBLKEYLENGTH )
        {
            pbl_errno = PBL_ERROR_BAD_FILE;
            return( -1 );
        }

        /*
         * set the return value
         */
        keylen = okeylen;
    }

    /*
     * position current record of the main file on that key
     */
    if( pblIsamGetMainKey( isam, index, okey, okeylen, key ) < 1 )
    {
        return( -1 );
    }