home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PROGRAMS / UTILS / HARDDISK / BADCLU.ZIP / AE.ZIP / BITSET.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-26  |  3.1 KB  |  163 lines
  1. /**********************************************************************
  2.  *  
  3.  *  bitset.c
  4.  *  
  5.  *  copyright (c) 1988 j. alan eldridge
  6.  * 
  7.  *  this code will run correctly on machines where an int
  8.  *  is either a short or a long (i.e., 2 or 4 bytes)
  9.  * 
  10.  *********************************************************************/
  11.  
  12.  
  13. #include <stdlib.h>
  14. #include <limits.h>
  15.  
  16. #include <bitset.h>
  17.  
  18.  
  19. #define INT_BITS    (CHAR_BIT * sizeof(int))
  20.  
  21. #define BITMAP_SIZE(lo,hi) (((hi)-(lo))/INT_BITS + 1)
  22.  
  23. int
  24. bitset_new(bsp, lo, hi)
  25. BITSET  *bsp;
  26. int     lo;
  27. int     hi;
  28. {
  29.     bsp->bitmap = calloc(BITMAP_SIZE(lo,hi), sizeof(int));
  30.     
  31.     if (bsp->bitmap) {
  32.         bsp->lo = lo;
  33.         bsp->hi = hi;
  34.         bsp->n_memb = 0;
  35.         return 0;
  36.     } else
  37.         return -1;
  38. }
  39.  
  40. int
  41. bitset_clr(bsp)
  42. BITSET  *bsp;
  43. {
  44.     if (bsp->bitmap) {
  45.         bsp->n_memb = 0;
  46.         memset(bsp->bitmap, 0, BITMAP_SIZE(bsp->lo,bsp->hi) * sizeof(int));
  47.         return 0;
  48.     } else
  49.         return -1;
  50. }
  51.  
  52. int
  53. bitset_set(bsp)
  54. BITSET  *bsp;
  55. {
  56.     if (bsp->bitmap) {
  57.         bsp->n_memb = bsp->hi - bsp->lo + 1;
  58.         memset(bsp->bitmap, 0xff, BITMAP_SIZE(bsp->lo,bsp->hi) * sizeof(int));
  59.         return 0;
  60.     } else
  61.         return -1;
  62. }
  63.  
  64. int
  65. bitset_free(bsp)
  66. BITSET  *bsp;
  67. {
  68.     if (bsp->bitmap) {
  69.         free(bsp->bitmap);
  70.         bsp->bitmap = NULL;
  71.         bsp->lo = 
  72.         bsp->hi = 
  73.         bsp->n_memb = 0;
  74.     }
  75.     return 0;
  76. }
  77.  
  78. int
  79. bitset_cnt(bsp)
  80. BITSET   *bsp;
  81. {
  82.    return bsp->n_memb;
  83. }   
  84.  
  85. static long bitmasks[] = {
  86.    0x00000001, 0x00000002, 0x00000004, 0x00000008,
  87.    0x00000010, 0x00000020, 0x00000040, 0x00000080,
  88.    0x00000100, 0x00000200, 0x00000400, 0x00000800,
  89.    0x00001000, 0x00002000, 0x00004000, 0x00008000,
  90.    0x00010000, 0x00020000, 0x00040000, 0x00080000,
  91.    0x00100000, 0x00200000, 0x00400000, 0x00800000,
  92.    0x01000000, 0x02000000, 0x04000000, 0x08000000,
  93.    0x10000000, 0x20000000, 0x40000000, 0x80000000
  94. };
  95.  
  96. static int
  97. locate_bit(bsp, val, mask_p)
  98. BITSET  *bsp;
  99. int     val;
  100. int     *mask_p;
  101. {
  102.     int abs_val, byte;
  103.     
  104.     abs_val = val - bsp->lo;
  105.     
  106.     *mask_p = bitmasks[abs_val % INT_BITS];
  107.     return abs_val / INT_BITS;
  108. }
  109.     
  110. int
  111. bitset_in(bsp, val)
  112. BITSET   *bsp;
  113. int      val;
  114. {
  115.     int mask, byte;
  116.         
  117.     if (val < bsp->lo || val > bsp->hi)
  118.         return -1;
  119.       
  120.     byte = locate_bit(bsp, val, &mask);
  121.     
  122.     return (bsp->bitmap[byte] & mask) != 0;
  123. }
  124.  
  125. int
  126. bitset_add(bsp, val)
  127. BITSET   *bsp;
  128. int      val;
  129. {
  130.     int mask, byte, found;
  131.     
  132.     found = bitset_in(bsp, val);
  133.     
  134.     if (found >= 0) {
  135.         if (!found) {
  136.             byte = locate_bit(bsp, val, &mask);
  137.             bsp->bitmap[byte] |= mask;
  138.             bsp->n_memb++;
  139.         }
  140.         return 0;
  141.     } else
  142.         return -1;
  143. }
  144.  
  145. int
  146. bitset_rmv(bsp, val)
  147. BITSET   *bsp;
  148. int      val;
  149. {
  150.     int mask, byte, found;
  151.     
  152.     found = bitset_in(bsp, val);
  153.     
  154.     if (found == 1) {
  155.         byte = locate_bit(bsp, val, &mask);
  156.         bsp->bitmap[byte] &= ~mask;
  157.         bsp->n_memb--;
  158.     }
  159.     
  160.     return found;
  161. }
  162.  
  163.