pblkf.c

B树算法实现

/*
 pblkf.c - key file library implementation

 Copyright (C) 2002      Peter Graf

   This file is part of PBL - The Program Base Library.
   PBL is free software.

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2.1 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

   For more information on the Program Base Library or Peter Graf,
   please see: http://mission.base.com/.

    $Log: pblkf.c,v $
    Revision 1.4  2003/02/19 22:26:49  peter
    made sure #defined values can be set by compiler switches

    Revision 1.3  2002/11/01 13:56:24  peter
    Truncation of the memory block list is now called
    at every file close.

    Revision 1.2  2002/11/01 13:27:30  peter
    The block reference hash table is deleted when the
    last block is deleted from the table, i.e. when the
    last file is closed

    Revision 1.1  2002/09/12 20:47:07  peter
    Initial revision


*/

/*
 * make sure "strings <exe> | grep Id | sort -u" shows the source file versions
 */
static char * rcsid = "$Id: pblkf.c,v 1.4 2003/02/19 22:26:49 peter Exp $";
static int    rcsid_fkt() { return( rcsid ? 0 : rcsid_fkt() ); }

#ifndef _WIN32

#include <unistd.h>

#endif

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

#include <sys/types.h>
#include <sys/stat.h>

#include <fcntl.h>
#include <memory.h>
#include <string.h>


#include "pbl.h"                 /* program base library                      */

/******************************************************************************/
/* #defines                                                                   */
/******************************************************************************/

#ifndef PBL_KF_TEST_DEFINES

#ifndef PBLDATASIZE             /* value might be set by compiler switch      */
#define PBLDATASIZE      4096   /* size of entire block data                  */
#endif

#ifndef PBLBLOCKSPERFILE        /* value might be set by compiler switch      */
#define PBLBLOCKSPERFILE   64   /* default number of cache blocks per file    */
#endif

#ifndef PBLNEXPANDED            /* value might be set by compiler switch      */
#define PBLNEXPANDED       32   /* default number of expanded blocks          */
#endif

#ifndef PBLFILEBLOCKS           /* value might be set by compiler switch      */
#define PBLFILEBLOCKS  0xffff   /* number of blocks per big file  on disk     */
#endif

#ifndef PBL_NFILES              /* value might be set by compiler switch      */
#define PBL_NFILES        256   /* maximum number of open key files           */
#endif

#else /* PBL_TEST_DEFINES */

#define PBLDATASIZE        64   /* size of entire block data                  */
#define PBLBLOCKSPERFILE   10   /* default number of blocks in our cache      */
#define PBLNEXPANDED        5   /* default number of expanded blocks          */
#define PBLFILEBLOCKS       3   /* number of blocks per file                  */

#undef  PBLKEYLENGTH
#define PBLKEYLENGTH        8   /* maximum length of a key                  */

#undef  PBLDATALENGTH
#define PBLDATALENGTH      16   /* maximum length of data that is stored      */
                                /* with an item on the level 0 block          */
                                /* data that is longer is stored on data      */
                                /* blocks                                     */
#ifndef PBL_NFILES
#define PBL_NFILES        256   /* maximum number of open key files           */
#endif

#endif /* PBL_TEST_DEFINES */

#define PBLHEADERSIZE      13   /* offset of first free byte on a new block   */

#define PBLMAGIC          "1.00 Peter's B Tree"
                                /* during creation this string is written     */
                                /* to the files                               */

/******************************************************************************/
/* #macros                                                                    */
/******************************************************************************/

/*
 * macro to determine free space on an index block
 */
#define PBLINDEXBLOCKNFREE( B ) ((PBLDATASIZE - B->free) - (2 * B->nentries))

/*
 * macro to determine free space on a data block
 */
#define PBLDATABLOCKNFREE( B ) ( PBLDATASIZE - B->free )

/*
 * macros for getting pointers or buffer offsets from the index
 */
#define PBLINDEXTOPTR( B, I ) ( B->data\
                              + ( PBLDATASIZE - 2 * ( 1 + ( I ) )))

#define PBLINDEXTOBUFOFF( B, I ) pbl_BufToShort( PBLINDEXTOPTR( B, I ))

/******************************************************************************/
/* typedefs                                                                   */
/******************************************************************************/

/*
 * PBL key file descriptor
 */
typedef struct PBLKFILE_s
{
    char * magic;                /* magic string                              */
    int    bf;                   /* file handle from bigfile handling         */
    int    update;               /* flag: file open for update                */

    long   blockno;              /* of block current record is on             */
    int    index;                /* of current record on this block           */

    long   saveblockno;          /* block number of saved position            */
    int    saveindex;            /* item index of saved position              */

    void * filesettag;           /* file set tag attached to file             */

    int    transactions;         /* number of transactions active for file    */
    int    rollback;             /* next commit should lead to a rollback     */

    void * writeableListHead;    /* head and tail of writeable blocks         */
    void * writeableListTail;

                                 /* a user defined key compare function       */
    int (*keycompare)( void * left, size_t llen, void * right, size_t rlen );

} PBLKFILE_t;

/*
 * items are the things we store in the data array of the index blocks
 */
typedef struct PBLITEM_s
{
    unsigned int    level;       /* level where item is inserted              */

    int             keycommon;   /* number of initial bytes this item has in  */
                                 /* common with its predecessor on tbe block  */

    int             keylen;      /* length of the key                         */
    unsigned char * key;         /* pointer to the key                        */

    long            datalen;     /* length of the data                        */
    unsigned char * data;        /* the data of the item                      */

    long            datablock;   /* number of block the data is on            */
    long            dataoffset;  /* offset of data on block                   */

    struct PBLITEM_s * next;     /* we save items in a list                   */
    struct PBLITEM_s * prev;     /* during an insert                          */

} PBLITEM_t;

/*
 * memory blocks that have expanded keys are stored in an extra list
 */
typedef struct PBLBLOCKLINK_s
{
    struct PBLBLOCKLINK_s * next;
    struct PBLBLOCKLINK_s * prev;

} PBLBLOCKLINK_t;

/*
 * a file block in memory has this format
 */
typedef struct PBLBLOCK_s
{
    PBLBLOCKLINK_t   blocklink;         /* for linking blocks in a list       */

    unsigned int   level;               /* of block                           */

    long           blockno;             /* block number in file               */
    int            bf;                  /* big file handle block belongs to   */
    void         * filesettag;          /* file set tag attached              */

    unsigned char  data[ PBLDATASIZE ]; /* the real data                      */

    long           nblock;              /* next block of same level           */
    long           pblock;              /* previous block of same level       */
    unsigned int   nentries;            /* number of entries                  */
    int            free;                /* offset of first free byte          */

    long           parentblock;         /* number of parent block             */
    int            parentindex;         /* index on parentblock               */

    int            writeable;           /* block can be written to            */
    int            dirty;               /* has the block been written to ?    */

    unsigned char *expandedkeys;        /* pointer to expanded keys of        */
                                        /* the block                          */

    struct PBLBLOCK_s * next;           /* we keep the blocks we have         */
    struct PBLBLOCK_s * prev;           /* in memory in a LRU chain           */

} PBLBLOCK_t;

/*
 * all file handles of all open filesystem files of
 * all bigfiles are stored in a list
 */
typedef struct PBLBIGFILEHANDLE_s
{
    int    bf;                     /* bigfile handle of file                  */
    int    n;                      /* bigfile index of file                   */

    int    fh;                     /* filesystem handle                       */
    int    mode;                   /* open mode                               */

    struct PBLBIGFILEHANDLE_s * next;
    struct PBLBIGFILEHANDLE_s * prev;

} PBLBIGFILEHANDLE_t;

/*
 * a bigfile in memory
 */
typedef struct PBLBIGFILE_s
{
    char * name;                    /* name of first filesystem file          */

    int    mode;                    /* open mode                              */
    long   blocksperfile;           /* blocks per filesystem file             */
    long   blocksize;               /* size of one block                      */
    long   nextblockno;             /* block number of next free block        */

} PBLBIGFILE_t;

/*
 * references to blocks are stored in a hashtable
 */
typedef struct PBLBLOCKREF_s
{
    long           blockno;             /* block number in file               */
    long           bf;                  /* big file handle block belongs to   */

    PBLBLOCK_t   * block;               /* address of block                   */

} PBLBLOCKREF_t;

typedef struct PBLBLOCKHASHKEY_s
{
    long           blockno;             /* block number in file               */
    long           bf;                  /* big file handle block belongs to   */

} PBLBLOCKHASHKEY_t;

/******************************************************************************/
/* globals                                                                    */
/******************************************************************************/

long pblnreads  = 0;
long pblnwrites = 0;

static char * magic = PBLMAGIC;

/*
 * pool of open bigfiles
 */
static PBLBIGFILE_t pbf_pool[ PBL_NFILES ];

/*
 * headers for lists
 */
static PBLBIGFILEHANDLE_t     * pbf_ft_head;
static PBLBIGFILEHANDLE_t     * pbf_ft_tail;
static PBLBLOCKLINK_t         * linkListHead;
static PBLBLOCKLINK_t         * linkListTail;
static PBLBLOCK_t             * blockListHead;
static PBLBLOCK_t             * blockListTail;
static PBLITEM_t              * itemListHead;
static PBLITEM_t              * itemListTail;

/*
 * counters
 */
static int            pblnblocks;
static int            pblnlinks;
static int            pblblocksperfile = PBLBLOCKSPERFILE;
static int            pblexpandedperfile = PBLNEXPANDED;
static long           pblnfiles;

/*
 * block reference hash table
 */
static pblHashTable_t * pblblockhash;

/******************************************************************************/
/* declarations                                                               */
/******************************************************************************/
static void pblBlockKeysRelease( PBLBLOCK_t * block );
static int pblBlockKeysExpand( PBLBLOCK_t * block );

/******************************************************************************/
/* functions                                                                  */
/******************************************************************************/
/*
 * verify consistency of parameters
 */
static int pblParamsCheck(
unsigned char * key,
unsigned int    keylen,
unsigned char * data,
long            datalen
)
{
    if(( keylen < 1 ) || ( keylen > 255 ))
    {
        pbl_errno = PBL_ERROR_PARAM_KEYLEN;
        return( -1 );
    }

    if( datalen < 0 )
    {
        pbl_errno = PBL_ERROR_PARAM_DATALEN;
        return( -1 );
    }

    if( !key )
    {
        pbl_errno = PBL_ERROR_PARAM_KEY;
        return( -1 );
    }

    if( datalen && ( !data ))
    {
        pbl_errno = PBL_ERROR_PARAM_DATA;
        return( -1 );
    }

    return( 0 );
}

/*
 * functions on the block reference hash table
 */
/*
------------------------------------------------------------------------------
  FUNCTION:     pblBlockHashInsert

  DESCRIPTION:  inserts a new block reference into the hash table

  RETURNS:      int rc == 0: a new reference was inserted
                int rc == 1: the reference was already there, it was udpated
                int rc <  0: some error occured, see pbl_errno
                 PBL_ERROR_OUT_OF_MEMORY:        malloc failed, out of memory
------------------------------------------------------------------------------
*/
static int pblBlockHashInsert( long blockno, long bf, PBLBLOCK_t * block )
{
    PBLBLOCKHASHKEY_t   key;
    PBLBLOCKREF_t     * ref;
    int                 rc;

    memset( &key, 0, sizeof( key ));
    key.blockno = blockno;
    key.bf      = bf;

    if( !pblblockhash )
    {
        pblblockhash = pblHtCreate();
        if( !pblblockhash )
        {
            return( -1 );
        }
    }

    /*
     * see whether we have the reference already
     */
    ref = pblHtLookup( pblblockhash, &key, sizeof( key ));
    if( ref )
    {
        /*
         * the reference is already there, update the block pointer
         */
        ref->block = block;
        return( 1 );
    }

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

    /*
     * allocate memory for new reference
     */
    ref = pbl_malloc0( "pblBlockHashInsert BLOCKREF", sizeof( PBLBLOCKREF_t ));
    if( !ref )
    {
        return( -1 );
    }

    /*
     * insert to the hash table
     */
    rc = pblHtInsert( pblblockhash, &key, sizeof( key ), ref );
    if( !rc )
    {
        ref->block   = block;
        ref->blockno = blockno;
        ref->bf      = bf;
    }
    else
    {
        PBL_FREE( ref );
        return( -1 );
    }

    return( 0 );
}

/*
------------------------------------------------------------------------------
  FUNCTION:     pblBlockHashRemove

  DESCRIPTION:  Remove a block reference from the hash table

  RETURNS:      int rc == 0: call went ok;
                otherwise:   block not found in hash table
------------------------------------------------------------------------------
*/
static int pblBlockHashRemove( long blockno, long bf )
{
    PBLBLOCKHASHKEY_t   key;
    PBLBLOCKREF_t     * ref;
    int                 rc;

    memset( &key, 0, sizeof( key ));
    key.blockno = blockno;
    key.bf      = bf;

    /*
     * if there is no hash table yet, the reference is not found
     */
    if( !pblblockhash )
    {
        return( 1 );
    }

    /*
     * see whether we have the reference
     */
    ref = pblHtLookup( pblblockhash, &key, sizeof( key ));
    if( !ref )
    {
        if( pbl_errno == PBL_ERROR_NOT_FOUND )
        {
            pbl_errno = 0;
        }

        return( 1 );
    }

    /*
     * remove the reference from the hash table
     */
    rc = pblHtRemove( pblblockhash, &key, sizeof( key ));
    if( rc )
    {
        return( 1 );
    }

    PBL_FREE( ref );

    /*
     * attempt to remove the hashtable