home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_11_11 / allison / bits.c < prev    next >
C/C++ Source or Header  |  1993-09-01  |  5KB  |  262 lines
  1. LISTING 7 - Bits Object Implementation
  2. /* bits.c */
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <limits.h>
  7. #include <string.h>
  8. #include <assert.h>
  9. #include "bits.h"
  10.  
  11. /* Pick the base integral type */
  12. typedef unsigned char Block;
  13.  
  14. /* Some implementation specifics */
  15. #define BLKSIZ          (CHAR_BIT * sizeof(Block))
  16. #define offset(b)       (b % BLKSIZ)
  17. #define mask1(b)        ((Block)1 << offset(b))
  18. #define mask0(b)       ~((Block)1 << offset(b))
  19.  
  20. /* Data Structure */
  21. typedef struct bits
  22. {
  23.     size_t nbits_;      /* The # of bits */
  24.     Block *bits_;       /* The base array */
  25.     size_t nblks_;      /* The # of blocks in base array */
  26.     Block clean_mask_;  /* To mask-off unused bits */
  27. } Bits;
  28.  
  29. /* Private functions */
  30. static size_t word_(Bits* bp, size_t bit)
  31. {
  32.     return bp->nblks_ - 1 - bit/BLKSIZ;
  33. }
  34.  
  35. static void set_(Bits *bp, size_t b)
  36. {
  37.     bp->bits_[word_(bp,b)] |= mask1(b);
  38. }
  39.  
  40. static void reset_(Bits *bp, size_t b)
  41. {
  42.     bp->bits_[word_(bp,b)] &= mask0(b);
  43. }
  44.  
  45. static void toggle_(Bits *bp, size_t b)
  46. {
  47.     bp->bits_[word_(bp,b)] ^= mask1(b);
  48. }
  49.  
  50. static int test_(Bits *bp,size_t b)
  51. {
  52.     return !!(bp->bits_[word_(bp,b)] & mask1(b));
  53. }
  54.  
  55. static size_t count_block_(Block n)
  56. {
  57.     size_t sum = 0;
  58.  
  59.     while (n)
  60.     {
  61.         if (n & (Block)1)
  62.             ++sum;
  63.         n >>= 1;
  64.     }
  65.     return sum;
  66. }
  67.  
  68. static void cleanup_(Bits *bp)
  69. {
  70.     if (bp->nbits_ % BLKSIZ)
  71.         bp->bits_[0] &= bp->clean_mask_;
  72. }
  73.  
  74. /* Implementation of public interface */
  75. Bits * bits_create(size_t nbits)
  76. {
  77.     Bits *bp = malloc(sizeof(Bits));
  78.     size_t nbytes;
  79.  
  80.     if (bp == NULL)
  81.         return NULL;
  82.  
  83.     /* Allocate base array */
  84.     bp->nblks_ = (nbits + BLKSIZ - 1) / BLKSIZ;
  85.     nbytes = bp->nblks_ * sizeof(Block);
  86.     bp->bits_ = malloc(nbytes);
  87.     if (bp->bits_ == NULL)
  88.     {
  89.         free(bp);
  90.         return NULL;
  91.     }
  92.  
  93.     memset(bp->bits_,'\0',nbytes);
  94.     bp->nbits_ = nbits;
  95.     bp->clean_mask_ = ~(Block)0 >> (bp->nblks_*BLKSIZ - nbits);
  96.     return bp;
  97. }
  98.  
  99. unsigned bits_to_uint(Bits *bp)
  100. {
  101.     size_t nblks = sizeof(unsigned) / sizeof(Block);
  102.     if (nblks > 1)
  103.     {
  104.         int i;
  105.         unsigned n = bp->bits_[bp->nblks_ - nblks];
  106.  
  107.         /* Collect low-order sub-blocks into an unsigned */
  108.         if (nblks > bp->nblks_)
  109.             nblks = bp->nblks_;
  110.         while (--nblks)
  111.             n = (n << BLKSIZ) | bp->bits_[bp->nblks_ - nblks];
  112.         return n;
  113.     }
  114.     else
  115.         return (unsigned) bp->bits_[bp->nblks_ - 1];
  116. }
  117.  
  118. Bits * bits_from_uint(Bits *bp, unsigned n)
  119. {
  120.     size_t nblks = sizeof(unsigned) / sizeof(Block);
  121.     assert(bp);
  122.     memset(bp->bits_, '\0', bp->nblks_ * sizeof(Block));
  123.     if (nblks > 1)
  124.     {
  125.         int i;
  126.         if (nblks > bp->nblks_)
  127.             nblks = bp->nblks_;
  128.         for (i = 1; i <= nblks; ++i)
  129.         {
  130.             bp->bits_[bp->nblks_ - i] = (Block) n;
  131.             n >>= BLKSIZ;
  132.         }
  133.     }
  134.     else
  135.         bp->bits_[bp->nblks_ - 1] = n;
  136.  
  137.     return bp;
  138. }
  139.  
  140. Bits * bits_set(Bits *bp, size_t bit)
  141. {
  142.     assert(bp && (bit < bp->nbits_));
  143.     set_(bp,bit);
  144.     return bp;
  145. }
  146.  
  147. Bits * bits_set_all(Bits *bp)
  148. {
  149.     assert(bp);
  150.     memset(bp->bits_,~0u,bp->nblks_*sizeof(Block));
  151.     cleanup_(bp);
  152.     return bp;
  153. }
  154.  
  155. Bits * bits_reset(Bits *bp, size_t bit)
  156. {
  157.     assert(bp && (bit < bp->nbits_));
  158.     reset_(bp,bit);
  159.     return bp;
  160. }
  161.  
  162. Bits * bits_reset_all(Bits *bp)
  163. {
  164.     assert(bp);
  165.     memset(bp->bits_,'\0',bp->nblks_*sizeof(Block));
  166.     return bp;
  167. }
  168.  
  169. Bits * bits_toggle(Bits *bp, size_t bit)
  170. {
  171.     assert(bp && (bit < bp->nbits_));
  172.     toggle_(bp,bit);
  173.     return bp;
  174. }
  175.  
  176. Bits * bits_toggle_all(Bits *bp)
  177. {
  178.     size_t nw;
  179.  
  180.     assert(bp);
  181.     nw = bp->nblks_;
  182.     while (nw--)
  183.         bp->bits_[nw] = ~bp->bits_[nw];
  184.     cleanup_(bp);
  185.     return bp;
  186. }
  187.  
  188. int bits_test(Bits *bp,size_t bit)
  189. {
  190.     assert(bp && (bit < bp->nbits_));
  191.     return test_(bp,bit);
  192. }
  193.  
  194. int bits_any(Bits *bp)
  195. {
  196.     int i;
  197.  
  198.     assert(bp);
  199.     for (i = 0; i < bp->nblks_; ++i)
  200.         if (bp->bits_[i])
  201.             return 1;
  202.     return 0;
  203. }
  204.  
  205. size_t bits_count(Bits *bp)
  206. {
  207.     int i;
  208.     size_t sum;
  209.  
  210.     assert(bp);
  211.     for (i = 0, sum = 0; i < bp->nblks_; ++i)
  212.         sum += count_block_(bp->bits_[i]);
  213.     return sum;
  214. }
  215.  
  216. Bits * bits_put(Bits *bp, FILE *f)
  217. {
  218.     int i;
  219.  
  220.     assert(bp);
  221.     for (i = 0; i < bp->nbits_; ++i)
  222.         fprintf(f,"%d",bits_test(bp,bp->nbits_-1-i));
  223.     return bp;
  224. }
  225.  
  226. Bits * bits_get(Bits *bp, FILE *f)
  227. {
  228.     char *buf;
  229.     char format[9];
  230.  
  231.     /* Reset all bits */
  232.     assert(bp);
  233.     bits_reset_all(bp);
  234.  
  235.     /* Allocate string buffer */
  236.     buf = malloc(bp->nbits_+1);
  237.     if (buf == NULL)
  238.         return 0;
  239.  
  240.     /* Build read format (e.g., " %16[01]") */
  241.     sprintf(format," %%%d[01]",bp->nbits_);
  242.     if (fscanf(f,format,buf) == 1)
  243.     {
  244.         int i;
  245.         size_t slen = strlen(buf);
  246.  
  247.         /* Set corresponding bits in bitset */
  248.         for (i = 0; i < slen; ++i)
  249.             if (buf[slen-1-i] == '1')
  250.                 bits_set(bp,i);
  251.     }
  252.     free(buf);
  253.     return bp;
  254. }
  255.  
  256. void bits_destroy(Bits *bp)
  257. {
  258.     assert(bp);
  259.     free(bp->bits_);
  260.     free(bp);
  261. }
  262.