home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 4 / DATAFILE_PDCD4.iso / unix / unixtools / util / c / bitset < prev    next >
Text File  |  1992-07-21  |  6KB  |  250 lines
  1. /*      > C.Bitset - Bitset data type */
  2.  
  3. #include <stddef.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include "bitset.h"
  7.  
  8. #ifdef test
  9. #include <stdio.h>
  10. #endif
  11.  
  12. /* Return values from functions */
  13.  
  14. #define OK      1
  15. #define ERR     0
  16.  
  17. #define CHAR_BIT_SHIFT  3
  18. #define CHAR_BIT_MASK   0x07
  19.  
  20. /* General component routines */
  21.  
  22. bitset bset_new (int bits)
  23. {
  24.         bitset b;
  25.         int bytes = ( bits >> CHAR_BIT_SHIFT )
  26.                   + ( ( bits & CHAR_BIT_MASK ) ? 1 : 0 );
  27.  
  28.         /* Create a zero-filled bitmap (all unset) */
  29.  
  30.         b = calloc( sizeof(struct bitset) - 1 + bytes, 1 );
  31.  
  32.         if ( b == NULL )
  33.                 return NULL;
  34.  
  35.         b->bits = bits;
  36.         b->bytes = bytes;
  37.  
  38.         return b;
  39. }
  40.  
  41. void bset_free (bitset b)
  42. {
  43.         free(b);
  44. }
  45.  
  46. void bset_clear (bitset b)
  47. {
  48.         memset(b->bitmap,0,b->bytes);
  49. }
  50.  
  51. int bset_copy (bitset b1, bitset b2)
  52. {
  53.         if ( b1->bits != b2->bits )
  54.                 return ERR;
  55.  
  56.         memcpy(b1->bitmap,b2->bitmap,b1->bytes);
  57.  
  58.         return OK;
  59. }
  60.  
  61. int bset_equal (bitset b1, bitset b2)
  62. {
  63.         if ( b1->bits != b2->bits )
  64.                 return 0;
  65.  
  66.         return ( memcmp(b1->bitmap,b2->bitmap,b1->bytes) );
  67. }
  68.  
  69. int bset_empty (bitset b)
  70. {
  71.         int i;
  72.  
  73.         for ( i = 0; i < b->bytes; ++i )
  74.                 if ( b->bitmap[i] != 0 )
  75.                         return 0;
  76.  
  77.         return 1;
  78. }
  79.  
  80. int bset_size (bitset b)
  81. {
  82.         int i;
  83.         unsigned char byte;
  84.         int count = 0;
  85.  
  86.         for ( i = 0; i < b->bytes; ++i )
  87.         {
  88.                 byte = b->bitmap[i];
  89.                 while ( byte != 0 )
  90.                 {
  91.                         if ( ( byte & 1 ) != 0 )
  92.                                 ++count;
  93.                         byte >>= 1;
  94.                 }
  95.         }
  96.  
  97.         return count;
  98. }
  99.  
  100. int bset_iterate (bitset b, int (*process)(int))
  101. {
  102.         int i;
  103.         int ret;
  104.         unsigned char byte;
  105.         int current;
  106.  
  107.         for ( i = 0; i < b->bytes; ++i )
  108.         {
  109.                 current = i << CHAR_BIT_SHIFT;
  110.                 byte = b->bitmap[i];
  111.                 while ( byte != 0 )
  112.                 {
  113.                         if ( ( byte & 1 ) != 0 )
  114.                         {
  115.                                 ret = (*process)(current);
  116.  
  117.                                 /* Non-zero => stop processing here */
  118.                                 /* Negative => Abnormal (error) termination */
  119.  
  120.                                 if ( ret != 0 )
  121.                                         return ( ret >= 0 );
  122.                         }
  123.  
  124.                         ++current;
  125.                         byte >>= 1;
  126.                 }
  127.         }
  128.  
  129.         return OK;
  130. }
  131.  
  132. /* Bitset-specific routines */
  133.  
  134. int bset_set (bitset b, int bit)
  135. {
  136.         if ( bit >= b->bits )
  137.                 return ERR;
  138.  
  139.         b->bitmap [bit >> CHAR_BIT_SHIFT ] |= 1 << (bit & CHAR_BIT_MASK);
  140.  
  141.         return OK;
  142. }
  143.  
  144. int bset_clr (bitset b, int bit)
  145. {
  146.         if ( bit >= b->bits )
  147.                 return ERR;
  148.  
  149.         b->bitmap [bit >> CHAR_BIT_SHIFT ] &= ~(1 << (bit & CHAR_BIT_MASK));
  150.  
  151.         return OK;
  152. }
  153.  
  154. int bset_invert (bitset b, int bit)
  155. {
  156.         if ( bit >= b->bits )
  157.                 return ERR;
  158.  
  159.         b->bitmap [bit >> CHAR_BIT_SHIFT ] ^= 1 << (bit & CHAR_BIT_MASK);
  160.  
  161.         return OK;
  162. }
  163.  
  164. int bset_test (bitset b, int bit)
  165. {
  166.         int res;
  167.  
  168.         if ( bit >= b->bits )
  169.                 return 0;
  170.  
  171.         res = b->bitmap [ bit >> CHAR_BIT_SHIFT ]
  172.             & ( 1 << (bit & CHAR_BIT_MASK) );
  173.  
  174.         return res;
  175. }
  176.  
  177. /*---------------------------------------------------------------------------*/
  178.  
  179. #ifdef test
  180. int print (int i)
  181. {
  182.         printf("%d ",i);
  183.         return STATUS_CONTINUE;
  184. }
  185.  
  186. void bset_dump (bitset b)
  187. {
  188.         printf("Bitset: ");
  189.         bset_iterate(b,print);
  190.         putchar('\n');
  191. }
  192. #endif
  193.  
  194. /*---------------------------------------------------------------------------*/
  195.  
  196. #ifdef test
  197.  
  198. #define BUFLEN 255
  199.  
  200. int main (void)
  201. {
  202.         char buf[BUFLEN];
  203.         int i, j, num;
  204.         bitset b[10];
  205.  
  206.         for ( i = 0; i < 10; ++i )
  207.                 b[i] = bset_new(255);
  208.  
  209.         for ( ; ; )
  210.         {
  211.                 printf(">");
  212.                 fgets(buf,BUFLEN,stdin);
  213.  
  214.                 if ( buf[0] == '\n' || buf[0] == '\0' )
  215.                         continue;
  216.                 else if ( sscanf(buf,"clear %1d",&i) == 1 )
  217.                         bset_clear(b[i]);
  218.                 else if ( sscanf(buf,"copy %1d %1d",&i,&j) == 2 )
  219.                         bset_copy(b[i],b[j]);
  220.                 else if ( sscanf(buf,"equal %1d %1d",&i,&j) == 2 )
  221.                         printf("%s\n",(bset_equal(b[i],b[j]) ? "yes" : "no"));
  222.                 else if ( sscanf(buf,"empty %1d",&i) == 1 )
  223.                         printf("%s\n",(bset_empty(b[i]) ? "yes" : "no"));
  224.                 else if ( sscanf(buf,"size %1d",&i) == 1 )
  225.                         printf("%d\n",bset_size(b[i]));
  226.                 else if ( sscanf(buf,"dump %1d",&i) == 1 )
  227.                         bset_dump(b[i]);
  228.                 else if ( sscanf(buf,"set %1d %d",&i,&num) == 2 )
  229.                         bset_set(b[i],num);
  230.                 else if ( sscanf(buf,"clr %1d %d",&i,&num) == 2 )
  231.                         bset_clr(b[i],num);
  232.                 else if ( sscanf(buf,"invert %1d %d",&i,&num) == 2 )
  233.                         bset_invert(b[i],num);
  234.                 else if ( sscanf(buf,"test %1d %d",&i,&num) == 2 )
  235.                         printf("%s\n",( bset_test(b[i],num) ? "yes" : "no" ));
  236.                 else if ( strncmp(buf,"quit",4) == 0 )
  237.                         break;
  238.                 else
  239.                         printf("Mistake\n");
  240.         }
  241.  
  242.         printf("Deleting b[0-9]\n");
  243.         for ( i = 0; i < 10; ++i )
  244.                 bset_free(b[i]);
  245.  
  246.         return 0;
  247. }
  248.  
  249. #endif
  250.