Listing 7 Bits object implementation

/* bits.c */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <assert.h>
#include "bits.h"

/* Pick the base integral type */
typedef unsigned char Block;

/* Some implementation specifics */
#define BLKSIZ          (CHAR_BIT * sizeof(Block))
#define offset(b)       (b % BLKSIZ)
#define mask1(b)        ((Block)1 << offset(b))
#define mask0(b)       ~((Block)1 << offset(b))

/* Data Structure */
typedef struct bits
{
   size_t nbits_;      /* The # of bits */
   Block *bits_;       /* The base array */
   size_t nblks_;      /* The # of blocks in base array */
   Block clean_mask_;  /* To mask-off unused bits */
} Bits;

/* Private functions */
static size_t word_(Bits* bp, size_t bit)
{
   return bp->nblks_- 1 - bit/BLKSIZ;
}

static void set_(Bits *bp, size_t b)
{
   bp->bits_[word_(bp,b)] |= mask1(b);
}

static void reset_(Bits *bp, size_t b)
{
   bp->bits_[word_(bp,b)] &= mask0(b);
}

static void toggle_(Bits *bp, size_t b)
{
   bp->bits_[word_(bp, b)] ^= mask1(b);
}

static int test_(Bits *bp,size_t b)
{
   return !!(bp->bits_[word_(bp,b)] & mask1(b));
}

static size_t count_block_(Block n)
{
   size_t sum = 0;
   
   while (n)
   {
      if (n & (Block)1)
         ++sum;
      n >>= 1;
   }
   return sum;
}

static void cleanup_(Bits *bp)
{
   if (bp->nbits_% BLKSIZ)
      bp->bits_[0] &= bp->clean_mask_;
}

/* Implementation of public interface */
Bits * bits_create(size_t nbits)
{
   Bits *bp = malloc(sizeof(Bits));
   size_t nbytes;
   if (bp == NULL)
      return NULL;

   /* Allocate base array */
   bp->nblks_ = (nbits + BLKSIZ - 1) / BLKSIZ;
   nbytes = bp->nblks_ * sizeof(Block);
   bp->bits_ = malloc(nbytes);
   if (bp->bits_ == NULL)
   {
      free(bp);
      return NULL;
   }
   
   memset(bp->bits_,'\0',nbytes);
   bp->nbits_ = nbits;
   bp->clean_mask_ = ~(Block)0 >> (bp->nblks_*BLKSIZ - nbits);
   return bp;
}

unsigned bits_to_uint(Bits *bp)
{
   size_t nblks = sizeof(unsigned) / sizeof(Block);
   if (nblks > 1)
   {
      int i;
      unsigned n = bp->bits_[bp->nblks_ - nblks];
      
      /* Collect low-order sub-blocks into an unsigned */
      if (nblks > bp->nblks_)
         nblks = bp->nblks_;
      while (--nblks)
         n = (n << BLKSIZ) | bp->bits_[bp->nblks_ - nblks];
      return n;
   }
   else
      return (unsigned) bp->bits_[bp->nblks_ - 1];
}

Bits * bits_from_uint(Bits *bp, unsigned n)
{
   size_t nblks = sizeof(unsigned) / sizeof(Block);
   assert(bp);
   memset(bp->bits_, '\0', bp->nblks_ * sizeof(Block));
   if (nblks > 1)
   {
      int i;
      if (nblks > bp->nblks_)
         nblks = bp->nblks_;
      for (i = 1; i <- nblks; ++i)
      {
         bp->bits [bp->nblks_ - i] = (Block) n;
         n >>= BLKSIZ;
      }
   }
   else
      bp->bits_[bp->nblks_- 1] = n;
   
   return bp;
}

Bits * bits_set(Bits *bp, size_t bit)
{
   assert(bp && (bit < bp->nbits_));
   set_(bp,bit);
   return bp;
}

Bits * bits_set_all(Bits *bp)
{
   assert(bp);
   memset(bp->bits_,~Ou,bp->nblks_*sizeof(Block));
   cleanup_(bp);
   return bp;
}

Bits * bits_reset(Bits *bp, size_t bit)
{
   assert(bp && (bit < bp->nbits_));
   reset_(bp,bit);
   return bp;
}

Bits * bits_reset_all(Bits *bp)
{
   assert(bp);
   memset(bp->bits_,'\0',bp->nblks_*sizeof(Block));
   return bp;
}

Bits * bits_toggle(Bits *bp, size_t bit)
{
   assert(bp && (bit < bp->nbits_));
   toggle_(bp,bit);
   return bp;
}

Bits * bits_toggle_all(Bits *bp)
{
   size_t nw;
   
   assert(bp);
   nw = bp->nblks_;
   while (nw--)
      bp->bits_[nw] = ~bp->bits_[nw];
   cleanup_(bp);
   return bp;
}

int bits_test(Bits *bp,size_t bit)
{
   assert(bp && (bit < bp->nbits_));
   return test_(bp,bit);
}

int bits_any(Bits *bp)
{
   int i;
   
   assert(bp);
   for (i = 0; i < bp->nblks_; ++i)
      if (bp->bits_[i])
         return 1;
   return 0;
}

size_t bits_count(Bits *bp)
{
   int i;
   size_t sum;
   
   assert(bp);
   for (i = 0, sum = 0; i < bp->nblks_; ++i)
      sum += count_block_(bp->bits_[i]);
   return sum;
}

Bits * bits_put(Bits *bp, FILE *f)
{
   int i;
   
   assert(bp);
   for (i = 0; i < bp->nbits_; ++i)
      fprintf(f,"%d",bits_test(bp,bp->nbits_-1-i));
   return bp;
}

Bits * bits_get(Bits *bp, FILE *f)
{
   char *buf;
   char format[9];
   
   /* Reset all bits */
   assert(bp);
   bits_reset_all(bp);
   
   /* Allocate string buffer */
   buf = malloc(bp->nbits_+1);
   if (buf == NULL)
      return 0;
   
   /* Build read format (e.g., " %16[01]") */
   sprintf(format," %%%d[01]",bp->nbits_);
   if (fscanf(f,format,buf) == 1)
   {
      int i;
      size_t slen = strlen(buf);
      
      /* Set corresponding bits in bitset */
      for (i = 0; i < slen; ++i)
         if (buf[slen-1-i] == '1')
            bits_set(bp,i);
   }
   free(buf);
   return bp;
}

void bits_destroy(Bits *bp)
{
   assert(bp);
   free(bp->bits_);
   free(bp);
}
/* End of File */