sflbits.c

短小精悍的C语言标准函数库。提供450个以上的可移植的算法和工具代码。

/*  ----------------------------------------------------------------<Prolog>-
    Name:       sflbits.c
    Title:      Large bitstring manipulation functions
    Package:    Standard Function Library (SFL)

    Written:    1996/05/14  iMatix SFL project team <[e-mail]>
    Revised:    1997/09/08

    Copyright:  Copyright (c) 1996-2000 iMatix Corporation
    License:    This is free software; you can redistribute it and/or modify
                it under the terms of the SFL License Agreement as provided
                in the file LICENSE.TXT.  This software is distributed in
                the hope that it will be useful, but without any warranty.
 ------------------------------------------------------------------</Prolog>-*/

#include "prelude.h"                    /*  Universal header file            */
#include "sflcomp.h"                    /*  Compression functions            */
#include "sfllist.h"                    /*  Linked-list functions            */
#include "sflmem.h"                     /*  Memory allocation functions      */
#include "sflbits.h"                    /*  Prototypes for functions         */


/*  Local function prototypes                                                */

static int locate_bit   (const BITS *bits, long bit, int *index_in_bits,
                         int *section_in_index, dbyte *bit_in_section);
static int get_section  (BITS *bits, int index, int section, byte *buffer,
                         Bool update);
static int put_section  (BITS *bits, int index, int section, byte *buffer);
static int alloc_block  (BITS *bits);


/*  Variables used in this source by various functions                       */

static byte
    section_data [BIT_SECTSIZE + 10],
    compressed   [(BIT_SECTSIZE * 11) / 10],
    *comp_zero = NULL,                  /*  What all zeroes looks like       */
    *comp_ones = NULL;                  /*  What all ones looks like         */
static int
    comp_ones_size,                     /*  Size of all zeroes, compressed   */
    comp_zero_size;                     /*  Size of all zeroes, compressed   */


/*  ---------------------------------------------------------------------[<]-
    Function: bits_init

    Synopsis: Initialises bitstring functions.  You must call this before
    using any other bitstring functions.  Returns 0 if okay, -1 if there
    was an error.
    ---------------------------------------------------------------------[>]-*/

int
bits_init (void)
{
    ASSERT (comp_zero == NULL);

    comp_zero = mem_alloc (BIT_SECTSIZE + 1);
    if (!comp_zero)
        return (-1);                    /*  Could not allocate new block     */

    memset (compressed, BIT_SECTSIZE, 0x00);
    comp_zero_size = compress_bits (compressed, comp_zero, BIT_SECTSIZE);
    comp_zero      = mem_realloc (comp_zero, comp_zero_size);

    comp_ones = mem_alloc (BIT_SECTSIZE + 1);
    if (!comp_ones)
      {
        mem_free (comp_ones);
        return (-1);                    /*  Could not allocate new block     */
      }
    memset (compressed, BIT_SECTSIZE, 0xFF);
    comp_ones_size = compress_bits (compressed, comp_ones, BIT_SECTSIZE);
    comp_ones      = mem_realloc (comp_ones, comp_ones_size);

    return (0);
}


/*  ---------------------------------------------------------------------[<]-
    Function: bits_term

    Synopsis: Terminates bitstring functions.  You must call this when you
    are finished using the bitstring functions.  Returns 0 if okay, -1 if
    there was an error.
    ---------------------------------------------------------------------[>]-*/

int
bits_term (void)
{
    mem_free (comp_zero);
    mem_free (comp_ones);
    return (0);
}


/*  ---------------------------------------------------------------------[<]-
    Function: bits_create

    Synopsis: Creates a new bitstring and initialises all bits to zero.
    Returns a BITS handle which you should use in all further references
    to the bitstring.
    ---------------------------------------------------------------------[>]-*/

BITS *
bits_create (void)
{
    BITS
        *bits;                          /*  Newly-created bitstring          */
    BITBLOCK
        *index;                         /*  Newly-created index block        */

    bits = mem_alloc (sizeof (BITS));
    if (bits)
      {
        memset (bits, 0, sizeof (BITS));
        index = mem_alloc (sizeof (BITBLOCK));
        if (index)
          {
            /*  Set all index fields to 0: bitstring is all zeroes           */
            memset (index, 0, sizeof (BITBLOCK));
            index-> left       = 0;
            index-> right      = 0;
            index-> size       = BIT_DATASIZE;
            bits-> block [0]   = index;
            bits-> block_count = 1;
            bits-> free_list   = 0;     /*  No blocks in free list           */
          }
        else
          {
            mem_free (bits);
            bits = NULL;
          }
      }
    return (bits);
}


/*  ---------------------------------------------------------------------[<]-
    Function: bits_destroy

    Synopsis: Releases all memory used by a bitstring and deletes the
    bitstring.  Do not refer to the bitstring after calling this function.
    ---------------------------------------------------------------------[>]-*/

void
bits_destroy (
    BITS *bits)
{
    int
        block_nbr;                      /*  Bitstring block number           */

    ASSERT (bits);

    /*  Free all blocks allocated to bitmap                                  */
    for (block_nbr = 0; block_nbr < bits-> block_count; block_nbr++)
        mem_free (bits-> block [block_nbr]);

    mem_free (bits);
}


/*  ---------------------------------------------------------------------[<]-
    Function: bits_set

    Synopsis: Sets the specified bit in the bitmap.  Returns ?
    ---------------------------------------------------------------------[>]-*/

int
bits_set (
    BITS *bits,
    long bit)
{
    int
        index,                          /*  Number of index block            */
        section;                        /*  Number of section in index       */
    dbyte
        bit_nbr;                        /*  Number of bit in section         */

    ASSERT (bits);

    locate_bit  (bits, bit, &index, &section, &bit_nbr);
    get_section (bits, index, section, section_data, TRUE);
    section_data [bit_nbr / 8] |= 1 << (bit_nbr % 8);
    put_section (bits, index, section, section_data);

    return 0;
}


/*  ---------------------------------------------------------------------[<]-
    Function: bits_clear

    Synopsis: Clears the specified bit in the bitmap.  Returns ?
    ---------------------------------------------------------------------[>]-*/

int
bits_clear (
    BITS *bits,
    long bit)
{
    int
        index,                          /*  Number of index block            */
        section;                        /*  Number of section in index       */
    dbyte
        bit_nbr;                        /*  Number of bit in section         */

    ASSERT (bits);

    locate_bit  (bits, bit, &index, &section, &bit_nbr);
    get_section (bits, index, section, section_data, TRUE);
    section_data [bit_nbr / 8] &= 255 - (1 << (bit_nbr % 8));
    put_section (bits, index, section, section_data);

    return 0;
}


/*  -------------------------------------------------------------------------
 *  locate_bit -- internal
 *
 *  For a particular bit in a bitstring, finds the index block that contains
 *  the bit, and returns the index block number, the section number within
 *  the index block, and the bit position within the section.  Returns TRUE
 *  if there was no error, FALSE if the specified bit lay outside the range
 *  currently defined by the bitstring.
 */

static int
locate_bit (
    const  BITS *bits,
    long   bit,
    int   *index_in_bits,
    int   *section_in_index,
    dbyte *bit_in_section)
{
    long
        index_base,
        relative_bit;

    ASSERT (bits);
    ASSERT (bit >= 0);
    ASSERT (bit < BIT_MAXBITS);

    *index_in_bits    = 0;              /*  Index block is always 0          */
    index_base        = *index_in_bits * (long) (BIT_SECTSIZE * BIT_INDEXSIZE);
    relative_bit      = bit - index_base;
    *section_in_index = (int)   (relative_bit / ((long) BIT_SECTSIZE * 8));
    *bit_in_section   = (dbyte) (relative_bit % ((long) BIT_SECTSIZE * 8));
    return (TRUE);
}


/*  -------------------------------------------------------------------------
 *  get_section -- internal
 *
 *  Expands the specified section into the working area specified.  If the
 *  update argument is TRUE, previously allocated blocks, if any, are put
 *  onto the free list.  Use this argument if you are changing the section
 *  and will recompress it using put_section().
 */

static int
get_section (
    BITS *bits,                         /*  Bitstring to work with           */
    int   index,                        /*  Index block number               */
    int   section,                      /*  Section within index             */
    byte *buffer,                       /*  Returned buffer                  */
    Bool  update)                       /*  If TRUE, frees section blocks    */
{
    BITBLOCK
        *index_block,                   /*  Points to index block            */