pblkf.c

B树算法实现

    }

    if( !predkey && block->nentries > 0 )
    {
        pbl_errno = PBL_ERROR_PROGRAM;
        return( -1 );
    }

    /*
     * calculate how many bytes the key of the item has in common
     * with the key of the predecessor on the block
     */
    if( predkey && ( predkeylen > 0 ))
    {
        item->keycommon = pbl_memcmplen( predkey, predkeylen,
                                         item->key, item->keylen );
    }
    else
    {
        item->keycommon = 0;
    }

    /*
     * calculate the size the item needs on the block
     */
    itemsize = pblItemSize( block, item );

    /*
     * check if the item fits here, the "+ 2" is for the slot!
     */
    if( PBLINDEXBLOCKNFREE( block ) < itemsize + 2 )
    {
        pbl_errno = PBL_ERROR_NOFIT;
        return( -1 );
    }

    /*
     * put item to data part of block
     */
    pblItemToBuf( block, block->free, item );

    /*
     * put the slot to the block
     */
    ptr = PBLINDEXTOPTR( block, block->nentries );
    pbl_ShortToBuf( ptr, block->free );

    block->free     += itemsize;
    block->nentries += 1;

    if( block->expandedkeys )
    {
        pblBlockKeysRelease( block );
    }

    return( 0 );
}

/*
 * delete an item from a block
 */
static int pblItemDelete( PBLBLOCK_t * block, int index )
{
    PBLITEM_t       item;
    int             ntomove;
    unsigned int    i;
    int             offset;
    int             itemoffset;
    unsigned char * ptr;
    unsigned int    itemsize;

    /*
     * read the item to delete
     */
    if( pblItemGet( block, index, &item ))
    {
        return( -1 );
    }

    /*
     * calculate the size the item ocupies on the block
     */
    itemsize = pblItemSize( block, &item );

    /*
     * calculate the number of items that have to be moved
     */
    itemoffset = PBLINDEXTOBUFOFF( block, index );
    ptr = block->data + itemoffset;
    ntomove = block->free - ( itemoffset + itemsize );
    if( ntomove < 0 )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    if( ntomove > 0 )
    {
        /*
         * move the other items to the left
         */
        memmove( ptr, ptr + itemsize, ntomove );

        /*
         * the slots who's offsets are to the right of the deleted item
         * have to change, because the items where moved
         */
        for( i = 0; i < block->nentries; i++ )
        {
            offset = PBLINDEXTOBUFOFF( block, i );
            if( offset > itemoffset )
            {
                offset -= itemsize;
                ptr = PBLINDEXTOPTR( block, i );
                pbl_ShortToBuf( ptr, offset );
            }
        }
    }

    /*
     * blank out the bytes deleted
     */
    memset(( block->data + block->free ) - itemsize, 0, itemsize );

    /*
     * there is more free space on the block now
     */
    block->free -= itemsize;

    /*
     * delete the slot from the slots array
     */
    ptr = PBLINDEXTOPTR( block, block->nentries - 1 );
    if( index < (int)block->nentries - 1 )
    {
        ntomove = ( block->nentries - 1 ) - index;
        memmove( ptr + 2, ptr, ntomove * 2 );
    }

    /*
     * blank out the last slot
     */
    *ptr++ = 0;
    *ptr   = 0;

    /*
     * there is one less slot on the block
     */
    block->nentries -= 1;

    if( block->expandedkeys )
    {
        pblBlockKeysRelease( block );
    }

    block->dirty = 1;
    return( 0 );
}

/*
 * insert an item on a block before the item with a given index
 */
static int pblItemInsert( PBLBLOCK_t * block, PBLITEM_t * item, int index )
{
    int             ntomove;
    unsigned char * ptr;
    unsigned int    itemsize;

    /*
     * calculate the size the item needs on the block
     */
    itemsize = pblItemSize( block, item );

    /*
     * check if the item fits here, the "+ 2" is for the slot!
     */
    if( PBLINDEXBLOCKNFREE( block ) < itemsize + 2 )
    {
        pbl_errno = PBL_ERROR_NOFIT;
        return( -1 );
    }

    /*
     * put item to data part of block
     */
    pblItemToBuf( block, block->free, item );

    /*
     * move the slots of the items after index
     */
    ptr = PBLINDEXTOPTR( block, block->nentries );
    ntomove = block->nentries - index;
    if( ntomove > 0 )
    {
        memmove( ptr, ptr + 2, 2 * ntomove );
    }

    /*
     * put the slot to the slots array
     */
    ptr = PBLINDEXTOPTR( block, index );
    pbl_ShortToBuf( ptr, block->free );

    block->free     += itemsize;
    block->nentries += 1;

    if( block->expandedkeys )
    {
        pblBlockKeysRelease( block );
    }

    block->dirty = 1;
    return( 0 );
}

/*
 * remove an item from a block
 */
static int pblItemRemove( PBLBLOCK_t *block, unsigned int index )
{
    PBLITEM_t         peeritem;
    PBLITEM_t         previtem;
    unsigned char     data[ PBLDATALENGTH ];
    unsigned char     savekey[ PBLKEYLENGTH ];
    int               rc;
    int               keycommon;
    int               dodelete = 0;

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

    /*
     * if there is no item with required index
     */
    if( index >= block->nentries )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    /*
     * create the expanded keys of the block
     */
    if( pblBlockKeysExpand( block ))
    {
        return( -1 );
    }

    if( index == block->nentries - 1 )
    {
        /*
         * delete the last item on the block
         */
        rc = pblItemDelete( block, index );
        return( rc );
    }

    /*
     * read the previous item on the block
     */
    if( index > 0 )
    {
        if( pblItemGet( block, index - 1, &previtem ))
        {
            return( -1 );
        }
    }

    /*
     * read the next item on the block
     */
    if( pblItemGet( block, index + 1, &peeritem ))
    {
        return( -1 );
    }

    if(( index > 0 ) && ( previtem.keylen > 0 ))
    {
        keycommon = pbl_memcmplen( previtem.key, previtem.keylen,
                                   peeritem.key, peeritem.keylen );
    }
    else
    {
        keycommon = 0;
    }

    /*
     * if the next item has to change
     */
    if( keycommon != peeritem.keycommon )
    {
        /*
         * delete and reinsert the next item, because its keycommon changed
         */
        dodelete = 1;

        /*
         * set the new keycommon value for the next item
         */
        peeritem.keycommon = keycommon;

        /*
         * save the data of the next item
         */
        if( peeritem.datalen <= PBLDATALENGTH )
        {
            memcpy( data, peeritem.data, peeritem.datalen );
            peeritem.data = data;
        }

        /*
         * save the key of the next item
         */
        memcpy( savekey, peeritem.key, peeritem.keylen );
        peeritem.key = savekey;

        /*
         * delete the next item
         */
        rc = pblItemDelete( block, index + 1 );
        if( rc )
        {
            return( rc );
        }
    }

    /*
     * delete the index'th item
     */
    rc = pblItemDelete( block, index );
    if( rc )
    {
        return( rc );
    }

    if( dodelete )
    {
        /*
         * insert the saved item again
         */
        rc = pblItemInsert( block, &peeritem, index );
    }
    return( rc );
}

/*
 * find an item that has a key equal to the search key
 *
 * - uses a binary search to position to an item on a block
 */
static int pblItemFind(
PBLKFILE_t * kf,
PBLBLOCK_t * block,
PBLITEM_t  * item,
int          which
)
{
    int       found = -1;
    int       index = 0;
    int       left  = 0;
    int       right = block->nentries - 1;
    int       rc    = 1;
    PBLITEM_t curitem;

    while( left <= right )
    {
        index = ( left + right ) / 2;

        if( pblItemGet( block, index, &curitem ))
        {
            return( -1 );
        }

        rc = pblItemCompare( kf, &curitem, item );
        if( rc == 0 )
        {
            switch( which )
            {
              case PBLLT:
                right = index - 1;
                break;

              case PBLLE:
              case PBLFI:
                found = index;
                right = index - 1;
                break;

              case PBLEQ:
                found = index;
                return( found );

              case PBLLA:
              case PBLGE:
                found = index;
                left  = index + 1;
                break;

              case PBLGT:
                left  = index + 1;
                break;
            }
        }
        else if ( rc < 0 )
        {
            switch( which )
            {
              case PBLLT:
              case PBLLE:
                found = index;
                left  = index + 1;
                break;

              case PBLFI:
              case PBLEQ:
              case PBLLA:
              case PBLGE:
              case PBLGT:
                left  = index + 1;
                break;
            }
        }
        else
        {
            switch( which )
            {
              case PBLLT:
              case PBLLE:
              case PBLFI:
              case PBLEQ:
              case PBLLA:
                right = index - 1;
                break;

              case PBLGE:
              case PBLGT:
                found = index;
                right = index - 1;
                break;
            }
        }
    }

    if( found < 0 )
    {
        pbl_errno = PBL_ERROR_NOT_FOUND;
    }

    return( found );
}

static int pblItemAdd( PBLKFILE_t * kf, PBLBLOCK_t * block, PBLITEM_t * item )
{
    PBLITEM_t         previtem;
    PBLITEM_t         peeritem;
    int               rc;
    int               index;
    unsigned char     savekey[ PBLKEYLENGTH ];
    unsigned int      savekeylen;
    unsigned char     data[ PBLDATALENGTH ];
    unsigned int      itemsize;
    int               keycommon;

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

    if( block->nentries < 1 )
    {
        if( pblItemAppend( block, 0, 0, item ))
        {
            return( -1 );
        }
        return( 0 );
    }

    /*
     * create the expanded keys of the block
     */
    if( pblBlockKeysExpand( block ))
    {
        return( -1 );
    }

    /*
     * find the first item that is bigger than the one we insert
     */
    index = pblItemFind( kf, block, item, PBLGT );
    if( index < 0 )
    {
        if( pbl_errno != PBL_ERROR_NOT_FOUND )
        {
            return( -1 );
        }

        /*
         * append to the block
         */
        pbl_errno = 0;
        index = block->nentries;

        if( pblItemGet( block, index - 1, &peeritem ))
        {
            return( -1 );
        }

        savekeylen = peeritem.keylen;
        if( savekeylen > 0 )
        {
            pbl_memlcpy( savekey, sizeof( savekey ), peeritem.key, savekeylen );
        }