pblisam.c

B树算法实现

/*
 pblisam.c - isam 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: pblisam.c,v $
    Revision 1.2  2003/02/19 22:19:39  peter
    fixed a bug related to finding non existing
    duplicated keys

    bug was reported by Csaba P醠os

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


*/

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

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

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

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

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

/*
 * PBL ISAM FILE DESCRIPTOR
 */
typedef struct PBLISAMFILE_s
{
    char          * magic;        /* magic string pointing to file descriptor */

    pblKeyFile_t  * mainfile;     /* file desriptor of main isam file         */
    int             update;       /* flag: file open for update               */

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

    int             nkeys;        /* number of key files of file              */
    pblKeyFile_t ** keyfiles;     /* file descriptors of key files            */

    int           * keydup;       /* flag array does the key allow duplicates */
    void         ** keycompare;   /* compare functions for keyfile            */

} PBLISAMFILE_t;

/******************************************************************************/
/* globals                                                                    */
/******************************************************************************/
static int (*pblkeycompare)( void * left, size_t llen,
                             void * right, size_t rlen );

/******************************************************************************/
/* functions                                                                  */
/******************************************************************************/

/*
 * conversion between keys of the main file and reference keys
 *
 * main file keys are 8 byte unsigned string numbers
 * between "00000000"          and "ffffffff"
 * or 17 byte unsigned string numbers
 * between "g0000000100000000" and "gffffffffffffffff"
 * this implements a 64 bit key.
 *
 * reference keys are compressed binary representations
 * of the same values.
 *
 * function pblRKey2MainKey converts from the binary reference key
 * to the unsigned string main key representing the same 64 bit value
 * 
 * function pblMainKey2RKey converts from the unsigned string
 * representation to the compressed representation
 *
 * reference keys are used as data for index records of index
 * keyfiles for non duplicate keys
 * and as key postfixes for index records of index 
 * keyfiles for keys allowing duplicates
 *
 * they provide the reference from the index records back
 * to the main file records containing the data
 */
static int pblRKey2MainKey(
unsigned char * rkey,
int             rkeylen,
unsigned char * okey
)
{
    unsigned long   keyhigh = 0;
    unsigned long   keylow = 0;
    int             hkeylen = 0;
    int             lkeylen = 0;
    int             len;

    /*
     * at least two bytes are needed, one for the length and one for
     * the value of lowkey
     */
    if( rkeylen < 2 )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    /*
     * read the length of the compressed data from the end of the rkey
     */
    lkeylen = 0xff & rkey[ rkeylen - 1 ];

    /*
     * the upper halfbyte of the length stores the length of the highkey
     */
    hkeylen = lkeylen >> 4;

    /*
     * the lower halfbyte of the length stores the length of the lowkey
     */
    lkeylen &= 0x0f;

    /*
     * the length of a the low key variable string must be between 1 and 5
     */
    if( lkeylen < 1 || lkeylen > 5 )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    /*
     * additional to the length byte, lkeylen bytes are needed
     */
    if( rkeylen < 1 + lkeylen )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    /*
     * read the value of the low key from the end of the key
     */
    len = pbl_VarBufToLong( rkey + rkeylen - ( lkeylen + 1 ), &keylow );
    if( len != lkeylen )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    /*
     * if there is no high key, just return the low key as a string
     */
    if( hkeylen < 1 )
    {
        if( okey )
        {
            snprintf( okey, PBLKEYLENGTH, "%08lx", keylow );
        }

        /*
         * return the number of bytes of the rkey parsed
         */
        return( lkeylen + 1 );
    }

    /*
     * the length of a the high key variable string cannot be greater than 5
     */
    if( hkeylen > 5 )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 ); 
    }

    /*
     * additional to the length byte, lkeylen + hkeylen bytes are needed
     */
    if( rkeylen < 1 + lkeylen + hkeylen )
    {   
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    /*
     * read the value of the high key from the end of the key
     */
    len = pbl_VarBufToLong( rkey + rkeylen - (hkeylen + lkeylen + 1), &keyhigh);
    if( len != lkeylen )
    {   
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    /*
     * keyhigh must have a positive value, otherwise it would not have been
     * stored at all
     */
    if( !keyhigh )
    {   
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    /*
     * return highkey and lowkey as one string
     */
    if( okey )
    {
        snprintf( okey, PBLKEYLENGTH, "g%08lx%08lx", keyhigh, keylow );
    }

    /*
     * return the number of bytes of the rkey parsed
     */
    return( hkeylen + lkeylen + 1 );
}

static int pblLongs2RKey(
unsigned long   keylow,
unsigned long   keyhigh,
unsigned char * rkey
)
{
    int             hkeylen = 0;
    int             lkeylen = 0;
    int             len;

    if( keyhigh )
    {
        /*
         * only store the higher four byte value if it is not 0
         */
        hkeylen = pbl_LongToVarBuf( rkey, keyhigh );
    }

    /*
     * store the low 4 bytes
     */
    lkeylen = pbl_LongToVarBuf( rkey + hkeylen, keylow );

    /*
     * store the length of both 4 bytes values in one byte at the end
     * the upper halfbyte of the length stores the length of the highkey
     * the lower halfbyte of the length stores the length of the lowkey
     */
    len = ( hkeylen << 4 ) | lkeylen;
    rkey[ hkeylen + lkeylen ] = 0xff & len;

    /*
     * return the bytes used for the rkey
     */
    return( hkeylen + lkeylen + 1 );
}


static int pblMainKey2RKey(
unsigned char * okey,
int             okeylen,
unsigned char * rkey
)
{
    unsigned long   keylow;
    unsigned long   keyhigh;
    int             len;

    if( okeylen > PBLKEYLENGTH - 1 )
    {
        pbl_errno = PBL_ERROR_PARAM_KEYLEN;
        return( -1 );
    }

    /*
     * copy the input key, because the parsing destroys it
     */
    memcpy( rkey, okey, okeylen );
    if( *rkey == 'g' )
    {
        rkey[ 17 ] = 0;
        keylow = strtoul( rkey + 9, 0, 16 );
        rkey[ 9 ] = 0;
        keyhigh = strtoul( rkey + 1, 0, 16 );
    }
    else
    {
        rkey[ 8 ] = 0;
        keylow = strtoul( rkey, 0, 16 );
        keyhigh = 0;
    }

    /*
     * store both long values as variable length byte buffers
     */
    len = pblLongs2RKey( keylow, keyhigh, rkey );

    return( len );
}

/*
 * return the length a duplicate index key without the
 * reference postfix
 */
static int pblIsamDupKeyLen( char * fkey, int fkeylen )
{
    int  len;

    /*
     * parse the reference from the end of the key
     * this calculates the length of the reference needed below
     */
    len = pblRKey2MainKey( fkey, fkeylen, NULL );
    if( len < 0 )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    return( fkeylen - len );
}

/*
 * compare two duplicate keys
 */
static int pblIsamDupKeyCompare(
void * left,    /** first buffer for compare               */
size_t llen,    /** length of that buffer                  */
void * right,   /** second buffer for compare              */
size_t rlen     /** length of that buffer                  */
)
{
    int  rc;

    char lkey[ PBLKEYLENGTH ];
    char rkey[ PBLKEYLENGTH ];

    size_t  leftlen;   
    size_t  rightlen;

    /*
     * a buffer with a length 0 is logically smaller than any other buffer
     */
    if( !llen )
    {
        if( !rlen )
        {
            return( 0 );
        }
        return( -1 );
    }
    if( !rlen )
    {
        return( 1 );
    }

    leftlen  = pblRKey2MainKey( left, llen, lkey );
    rightlen = pblRKey2MainKey( right, rlen, rkey );

    if( leftlen < 1 || rightlen < 1 )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    if( leftlen >= llen || rightlen >= rlen )
    {
        pbl_errno = PBL_ERROR_BAD_FILE;
        return( -1 );
    }

    if( pblkeycompare )
    {
        /*
         * use the default key compare function
         */
        rc = (*pblkeycompare)( left, llen - leftlen,
                               right, rlen - rightlen );
    }
    else
    {
        /*
         * use the default key compare function
         */
        rc = pbl_memcmp( left, llen - leftlen,
                         right, rlen - rightlen );
    }

    if( !rc )
    {
        rc = strcmp( lkey, rkey );
    }

    return( rc );
}

/*
------------------------------------------------------------------------------
  FUNCTION:     pblIsamStartTransOnFile

  DESCRIPTION:  start a transaction on a single ISAM file

  RESTRICTIONS: transactions can be nested

  RETURNS:      int rc == 0: the transaction was started successfully
                int rc >  0: the transaction was started
                             but another transaction has resulted in
                             a rollback request on the file already
------------------------------------------------------------------------------
*/
static int pblIsamStartTransOnFile( PBLISAMFILE_t * isam )
{
    int n;

    /*
     * if there is no transaction active for the file
     */
    if( isam->transactions < 1 )
    {
        isam->transactions = 1;
        isam->rollback = 0;
    }
    else
    {
        isam->transactions++;
    }

    /*
     * start a transaction on the main file
     */
    if( pblKfStartTransaction( isam->mainfile ) > 0 )
    {
        isam->rollback = 1;
    }

    /*
     * start transactions for all keyfiles
     */
    for( n = 0; n < isam->nkeys; n++ )
    {
        if( pblKfStartTransaction( isam->keyfiles[ n ] ) > 0 )
        {
            isam->rollback = 1;
        }
    }

    return( isam->rollback );
}


/**
 * start a transaction on a set of ISAM files
 *
 * transactions can be nested
 *
 * @return int rc == 0: the transaction was started successfully
 * @return int rc >  0: the transaction was started
 *                      but another transaction has resulted in
 *                      a rollback request on the file already
 */

int pblIsamStartTransaction(
int nfiles,                  /** number of files in ISAM file list      */
pblIsamFile_t ** isamfiles   /** ISAM file list to start transaction on */
)
{
    PBLISAMFILE_t ** files = ( PBLISAMFILE_t ** ) isamfiles;
    int n;
    int rollback = 0;

    for( n = 0; n < nfiles; n++ )
    {
        if( pblIsamStartTransOnFile( files[ n ] ) > 0 )
        {
            rollback = 1;
        }
    }

    return( rollback );
}



/*
------------------------------------------------------------------------------
  FUNCTION:     pblIsamCommitFile