pbl.c

B树算法实现

    if( !tag )
    {
        tag = "pbl_mem2dup";
    }

    ret = pbl_malloc( tag, len1 + len2 );
    if( !ret )
    {
        return( 0 );
    }

    if( len1 )
    {
        memcpy( ret, mem1, len1 );
    }

    if( len2 )
    {
        memcpy( ((char*)ret) + len1, mem2, len2 );
    }

    return( ret );
}

/**
 * memcpy with target length check
 *
 * @return   size_t rc: number of bytes copied
 */
size_t pbl_memlcpy(
void * to,          /** target buffer to copy to                             */
size_t tolen,       /** number of bytes in the target buffer                 */
void * from,        /** source to copy from                                  */
size_t n            /** length of source                                     */
)
{
    size_t l = n > tolen ? tolen : n;

    memcpy( to, from, l );
    return( l );
}

/**
 * find out how many starting bytes of two buffers are equal
 *  
 * @return   int rc: number of equal bytes
 */ 
        
int pbl_memcmplen(
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                  */
)       
{           
    unsigned int i;
    unsigned char * l = ( unsigned char * )left;
    unsigned char * r = ( unsigned char * )right;

    if( llen > rlen )
    {
        llen = rlen;
    }

    for( i = 0; i < llen; i++ )
    {
        if( *l++ != *r++ )
        {
            break;
        }
    }

    return( i );
}

/**
 * compare two memory buffers, similar to memcmp
 *
 * @return   int rc  < 0: left is smaller than right
 * @return   int rc == 0: left and right are equal
 * @return   int rc  > 0: left is bigger than right
 */

int pbl_memcmp(
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                  */
)
{
    size_t len;
    int    rc;

    /*
     * 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 );
    }

    /*
     * use the shorter of the two buffer lengths for the memcmp
     */
    if( llen <= rlen )
    {
        len = llen;
    }
    else
    {
        len = rlen;
    }

    /*
     * memcmp is used, therefore the ordering is ascii
     */
    rc = memcmp( left, right, len );
    if( rc )
    {
        return( rc );
    }

    /*
     * if the two buffers are equal in the first len bytes, but don't have
     * the same lengths, the longer one is logically bigger
     */
    return( (int) ( ((int)llen) - ((int)rlen) ));
}

/**
 * copy a two byte short to a two byte buffer
 */
void pbl_ShortToBuf(
unsigned char * buf,        /** buffer to copy to                 */
int s                       /** short value to copy               */
)
{
    *buf++ = ( unsigned char ) ( s >> 8 );
    *buf   = ( unsigned char ) ( s );
}

/**
 * read a two byte short from a two byte buffer
 *
 * @return int rc: the short value read
 */
int pbl_BufToShort(
unsigned char * buf            /** buffer to read from      */
)
{
    unsigned int s  = (( unsigned int ) ( *buf++ )) << 8;

    s |= *buf;
    return( s );
}

/**
 * copy a four byte long to a four byte buffer
 */
void pbl_LongToBuf(
unsigned char * buf,        /** buffer to copy to                 */
long l                      /** long value to copy                */
)
{

    *buf++ = (unsigned char ) ( ( l >> 24 ));
    *buf++ = (unsigned char ) ( ( l >> 16 ));
    *buf++ = (unsigned char ) ( ( l >>  8 ));
    *buf   = (unsigned char ) ( l );
}

/**
 * read a four byte long from a four byte buffer
 *
 * @return long ret: the long value read
 */
long pbl_BufToLong(
unsigned char * buf        /** the buffer to read from   */
)
{
    unsigned long l  = ((( unsigned long ) ( *buf++ ) )) << 24;

    l |= ((( unsigned long ) ( *buf++ ) ) ) << 16;
    l |= ((( unsigned long ) ( *buf++ ) ) ) <<  8;
    l |= *buf;

    return( l );
}

/**
 * copy a four byte long to a variable length buffer
 *
 * @return int rc: the number of bytes used in the buffer
 */
int pbl_LongToVarBuf( unsigned char * buffer, unsigned long value )
{
    if( value <= 0x7f )
    {
        *buffer = (unsigned char)value;
        return( 1 );
    }

    if( value <= 0x3fff )
    {
        *buffer++ = (unsigned char)( value / 0x100 ) | 0x80;
        *buffer = (unsigned char)value & 0xff;
        return( 2 );
    }

    if( value <= 0x1fffff )
    {
        *buffer++ = (unsigned char)( value / 0x10000 ) | 0x80 | 0x40;
        *buffer++ = (unsigned char)( value / 0x100 );
        *buffer = (unsigned char)value & 0xff;
        return( 3 );
    }

    if( value <= 0x0fffffff )
    {
        *buffer++ = (unsigned char)( value / 0x1000000 ) | 0x80 | 0x40 | 0x20;
        *buffer++ = (unsigned char)( value / 0x10000 );
        *buffer++ = (unsigned char)( value / 0x100 );
        *buffer = (unsigned char)value & 0xff;
        return( 4 );
    }

    *buffer++ = (unsigned char)0xf0;
    pbl_LongToBuf( buffer, value );

    return( 5 );
}


/**
 * read a four byte long from a variable length buffer
 *
 * @return int rc: the number of bytes used in the buffer
 */
int pbl_VarBufToLong(
unsigned char * buffer,    /** buffer to read from                 */
long * value               /** long to read to                     */
)
{
    int c = 0xff & *buffer++;
    int val;

    if( !( c & 0x80 ))
    {
        *value = c;
        return( 1 );
    }

    if( !( c & 0x40 ))
    {
        *value = ( c & 0x3f ) * 0x100 + ( *buffer & 0xff );
        return( 2 );
    }
    if( !( c & 0x20 ))
    {
        val = ( c & 0x1f ) * 0x10000;
        val += (( *buffer++ ) & 0xff ) * 0x100;
        *value = val + (( *buffer ) & 0xff );
        return( 3 );
    }

    if( !( c & 0x10 ))
    {
        val = ( c & 0x0f ) * 0x1000000;
        val += (( *buffer++ ) & 0xff ) * 0x10000;
        val += (( *buffer++ ) & 0xff ) * 0x100;
        *value = val + (( *buffer ) & 0xff );
        return( 4 );
    }

    *value = pbl_BufToLong( buffer );
    return( 5 );
}

/**
 * find out how many bytes a four byte long would use in a buffer
 *
 * @return int rc: number of bytes used in buffer
 */

int pbl_LongSize(
unsigned long value               /** value to check          */
)
{
    if( value <= 0x7f )
    {
        return( 1 );
    }

    if( value <= 0x3fff )
    {
        return( 2 );
    }

    if( value <= 0x1fffff )
    {
        return( 3 );
    }

    if( value <= 0x0fffffff )
    {
        return( 4 );
    }

    return( 5 );
}

/**
 * find out how many bytes a four byte long uses in a buffer
 *
 * @return int rc: number of bytes used in buffer
 */

int pbl_VarBufSize(
unsigned char * buffer   /** buffer to check                  */
)
{
    int c = 0xff & *buffer;

    if( !( c & 0x80 ))
    {
        return( 1 );
    }

    if( !( c & 0x40 ))
    {
        return( 2 );
    }

    if( !( c & 0x20 ))
    {
        return( 3 );
    }

    if( !( c & 0x10 ))
    {
        return( 4 );
    }

    return( 5 );
}