pblkf.c

B树算法实现

 * read a block from a bigfile
 */
static int pbf_blockread( int bf, long blockno, unsigned char * buffer )
{
    int        rc;

    rc = pbf_blockio( bf, 0, blockno, buffer );

    return( rc );
}

/*
 * write a block to a bigfile
 */
static int pbf_blockwrite( int bf, long blockno, unsigned char * buffer )
{
    int        rc;

    rc = pbf_blockio( bf, 1, blockno, buffer );

    return( rc );
}

/*
 * append a block to a bigfile
 */
static long pbf_blockappend( int bf, unsigned char * buffer )
{
    int           fh;
    long          offset;
    int           i;
    int           j;
    long          rc = -1;
    unsigned char c;

    if( bf < 0 || bf >= PBL_NFILES || !pbf_pool[ bf ].name )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    if( pbf_pool[ bf ].nextblockno == 0x3fff )
    {
        rc = -1;
    }

    /*
     * if we don't know the next free block of the file yet
     */
    if( pbf_pool[ bf ].nextblockno < 0 )
    {
        /*
         * find the next free block of a bigfile
         */
        for( i = 0; 1; i++ )
        {
            /*
             * create and open next filesytem file used for the bigfile
             */
            fh = pbf_fh_open( pbf_pool[ bf ].name, pbf_pool[ bf ].mode, bf, i );
            if( -1 == fh )
            {
                pbl_errno = PBL_ERROR_WRITE;
                return( -1 );
            }

            /*
             * reopen the filesystem file read only
             */
            fh = pbf_fh_open( pbf_pool[ bf ].name, O_BINARY | O_RDONLY, bf, i );
            if( -1 == fh )
            {
                pbl_errno = PBL_ERROR_WRITE;
                return( -1 );
            }

            /*
             * seek to the end of the file
             */
            offset = pbf_pool[ bf ].blocksperfile * pbf_pool[ bf ].blocksize -1;

            for( j = 0; j < 3; j++ )
            {
                rc = lseek( fh, offset, SEEK_SET );
                if( offset != rc )
                {
                    if( errno == EINTR )
                    {
                        continue;
                    }
                    rc = -1;
                    break;
                }

                /*
                 * check whether the block exist, by reading its last byte
                 */
                rc = read( fh, &c, 1 );
                if( rc < 1 )
                {
                    if( errno == EINTR )
                    {
                        continue;
                    }
                }
                break;
            }
                
            if( rc == 1 )
            {
                /*
                 * we can read the last byte of the block, it is not free
                 */
                continue;
            }

            /*
             * we found the last filesystem file used for the bigfile
             * seek to the end of the file
             */
            for( j = 0; j < 3; j++ )
            {
                rc = lseek( fh, 0, SEEK_END );
                if( rc < 0 )
                {
                    if( errno == EINTR )
                    {
                        continue;
                    }

                    pbl_errno = PBL_ERROR_WRITE;
                    return( -1 );
                }
                break;
            }

            if( rc % pbf_pool[ bf ].blocksize )
            {
                pbl_errno = PBL_ERROR_BAD_FILE;
                return( -1 );
            }

            pbf_pool[ bf ].nextblockno = rc / pbf_pool[ bf ].blocksize;
            break;
        }
    }

    /*
     * append the block to the bigfile
     */
    rc = pbf_blockio( bf, 1, pbf_pool[ bf ].nextblockno, buffer );
    if( rc )
    {
        return( rc );
    }

    return( pbf_pool[ bf ].nextblockno++ );
}

/*
 * ITEM functions
 *
 * Layout of an item in the data of a block with a level greater than 0
 *
 * LENGTH    NAME        SEMANTICS
 *
 * 1        KEYLEN        length of the key of the item
 * 1        KEYCOMMON     number of bytes the key has in common with
 *                        the key of the predecessor of the item on the block
 * VARLONG  DATABLOCK     block number of block this item points to
 * KEYLEN   KEY           the key itself, only the last KEYLEN - KEYCOMMON
 *                        bytes are stored
 *
 * Layout of an item in the data of a block with a level 0 and
 * with the datalen of the item smaller than or equal to PBLDATALENGTH
 *
 * LENGTH    NAME        SEMANTICS
 *
 * 1         KEYLEN       length of the key of the item
 * 1         KEYCOMMON    number of bytes the key has in common with
 *                        the key of the predecessor of the item on the block
 * VARLONG   DATALEN      length of the data stored on the block
 * KEYLEN    KEY          the key itself, only the last KEYLEN - KEYCOMMON
 *                        bytes are stored
 * DATALEN   DATA         the data is stored on the block
 *
 * Layout of an item in the data of a block with a level 0 and
 * with the datalen of the item greater than PBLDATALENGTH
 *
 * LENGTH    NAME        SEMANTICS
 *
 * 1         KEYLEN       length of the key of the item
 * 1         KEYCOMMON    number of bytes the key has in common with
 *                        the key of the predecessor of the item on the block
 * VARLONG   DATALEN      length of the data stored on the datablock
 * KEYLEN    KEY          the key itself, only the last KEYLEN - KEYCOMMON
 *                        bytes are stored
 * VARLONG   DATABLOCK    block number of block data is stored on
 * VARLONG   DATAOFFSET   offset of the data on that block
 *
 * The long values stored for an item, DATALEN, DATABLOCK and DATAOFFSET
 * are stored as variable length buffers, i.e. the number of bytes
 * used in the file for the values depends on their numerical value.
 * See the VarBuf* functions for details.
 *
 * The smallest item of an inner block always has KEYLEN 0, which makes
 * it's key logically smaller than any other possible key of an item.
 *
 * The items stored on a block start at address ( block->data + PBLHEADERSIZE ).
 * The items are always stored immediately one after the other starting at
 * at this address, we leave no space in between.
 *
 * As the keys of the items and therefore the items themselves can have
 * different lengths, we store the relative offsets of the items in the
 * data of a block also in the data of the block. Those relative offsets
 * are stored as two byte unsigned shorts at the end of the data of the block.
 * The relative offsets are called slots in the code below.
 *
 * The slots in the slot array are kept in order.
 *
 * For every block the short block->free gives the relative offset of the first
 * free byte of the block, immediately after the end of the last item stored.
 *
 * Before we append an item we check if there is enough space for the item
 * and its slot between the end of the last item stored and the beginning
 * of the slot array of the items stored. If not, PBL_ERROR_NOFIT is given
 * to the pblinsert procedure which then has to split the block.
 *
 * During deletion we pack the ordered array of the slots
 * and the items themselves by shifting them on the block.
 *
 * The number of bytes the key of an item has in common with the key
 * of the predecessor of the item is stored with each item.
 * This is done in order to minimize the space needed for keys.
 *
 * EG: If a key is "New York" and its predecessor is "New Haven",
 *     only the string "York" is stored for the second key together
 *     with one byte indicating that the key has the first 4 bytes
 *     with its predecessor, the key "New Haven".
 * 
 * Whenever the full keys are needed for the items of a block,
 * the keys of the items of the block have to be "expanded" first.
 */

/*
 * The following three static procedures are the only ones that 'know' the
 * layout of an item stored on a block
 */
static void pblItemToBuf( PBLBLOCK_t * block, int bufoff, PBLITEM_t * item )
{
    unsigned char * ptr = &( block->data[ bufoff ] );

    *ptr++ = ( unsigned char ) item->keylen;
    *ptr++ = ( unsigned char ) item->keycommon;

    if( block->level > 0 )
    {
        ptr += pbl_LongToVarBuf( ptr, item->datablock );
    }
    else
    {
        ptr += pbl_LongToVarBuf( ptr, item->datalen );
    }

    if( item->keylen - item->keycommon > 0 )
    {
        /*
         * make sure we don't copy in place
         */
        if( ptr != item->key + item->keycommon )
        {
            pbl_memlcpy( ptr, PBLKEYLENGTH,
                         item->key + item->keycommon,
                         item->keylen - item->keycommon );
        }
        ptr += item->keylen - item->keycommon;
    }

    /*
     * the block needs to be written to the filesystem
     */
    block->dirty = 1;

    if( block->level > 0 )
    {
        return;
    }

    if( item->datalen <= PBLDATALENGTH )
    {
        if( item->datalen > 0 )
        {
            if( ptr != item->data )
            {
                memcpy( ptr, item->data, item->datalen );
            }
        }
    }
    else
    {
        ptr += pbl_LongToVarBuf( ptr, item->datablock );
        pbl_LongToVarBuf( ptr, item->dataoffset );
    }
}

static int pblBufToItem( PBLBLOCK_t * block, int bufoff, PBLITEM_t * item )
{
    unsigned char * ptr;
    unsigned char * endptr;

    item->level = block->level;

    /*
     * make sure the offset is in bounds
     */
    if( bufoff >= sizeof( block->data ))
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }
    endptr = &( block->data[ sizeof( block->data ) ] );
    ptr = &( block->data[ bufoff ] );

    /*
     * parse the item
     */
    item->keylen = *ptr++;
    item->keycommon = *ptr++;

    if( block->level > 0 )
    {
        ptr += pbl_VarBufToLong( ptr, &( item->datablock ));
        item->datalen = 0;
    }
    else
    {
        ptr += pbl_VarBufToLong( ptr, &( item->datalen ));
        item->datablock = 0;
    }

    if( ptr >= endptr )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    if( item->keylen - item->keycommon > 0 )
    {
        item->key = ptr;
        ptr += item->keylen - item->keycommon;
        if( ptr >= endptr )
        {
            pbl_errno = PBL_ERROR_BAD_FILE;
            return( -1 );
        }
    }
    else
    {
        item->key = 0;
    }

    if( block->level > 0 )
    {
        item->dataoffset = 0;
        item->data = 0;

        return( 0 );
    }

    if( item->datalen <= PBLDATALENGTH )
    {
        item->dataoffset = 0;
        if( item->datalen > 0 )
        {
            item->data = ptr;
            ptr += item->datalen;
            if( ptr >= endptr )
            {
                pbl_errno = PBL_ERROR_BAD_FILE;
                return( -1 );
            }
        }
        else
        {
            item->data = 0;
        }
    }
    else
    {
        ptr += pbl_VarBufToLong( ptr, &( item->datablock ));
        pbl_VarBufToLong( ptr, &( item->dataoffset ));
        item->data = 0;
    }

    if( ptr >= endptr )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }
    return( 0 );
}

static int pblItemSize( PBLBLOCK_t * block, PBLITEM_t * item )
{
    int rc = 2;

    if( block->level > 0 )
    {
        rc += pbl_LongSize( item->datablock );
    }
    else
    {
        rc += pbl_LongSize( item->datalen );
    }

    if( item->keylen - item->keycommon > 0 )
    {
        rc += item->keylen - item->keycommon;
    }

    if( block->level > 0 )
    {
        return( rc );
    }

    if( item->datalen <= PBLDATALENGTH )
    {
        if( item->datalen > 0 )
        {
            rc += item->datalen;
        }
    }
    else
    {
        rc += pbl_LongSize( item->datablock );
        rc += pbl_LongSize( item->dataoffset );
    }

    return( rc );
}

/*
 * compare two items
 */
static int pblItemCompare( PBLKFILE_t *kf, PBLITEM_t *left, PBLITEM_t *right )
{
    int rc;

    if( kf->keycompare )
    {
        /*
         * there is a specific compare function for the key file
         */
        rc = (*kf->keycompare)( left->key, left->keylen,
                                right->key, right->keylen );
    }
    else
    {
        /*
         * use the default key compare function
         */
        rc = pbl_memcmp( left->key, left->keylen,
                         right->key, right->keylen );
    }

    return( rc );
}

static int pblItemGet( PBLBLOCK_t * block, unsigned int index, PBLITEM_t *item )
{
    /*
     * if there is no item with required index
     */
    if( index >= (unsigned int)block->nentries )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    /*
     * copy the item with the required index
     */
    if( pblBufToItem( block, PBLINDEXTOBUFOFF( block, index ), item ))
    {
        return( -1 );
    }

    /*
     * if we have the expanded keys for the block we
     * actually use those keys
     */
    if( item->keycommon > 0 && block->expandedkeys )
    {
        item->key = block->expandedkeys + index * PBLKEYLENGTH;
    }

    return( 0 );
}

/*
 * append an item to a block
 */
static int pblItemAppend(
PBLBLOCK_t      * block,
unsigned char   * predkey,
unsigned int      predkeylen,
PBLITEM_t       * item
)
{
    unsigned char * ptr;
    unsigned int    itemsize;

    if( !block->writeable )
    {
        pbl_errno = PBL_ERROR_PROGRAM;
        return( -1 );