pintos-os.org Git - pintos-anon/blob - src/lib/bitmap.c

   1 #define NDEBUG
   2 #include "bitmap.h"
   3 #include <limits.h>
   4 #include "debug.h"
   5 #include "lib.h"
   6 #include "malloc.h"
   7 #ifdef FILESYS
   8 #include "file.h"
   9 #endif
  10 \f
  11 /* Number of bits in an element. */
  12 #define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
  13
  14 /* Returns the index of the element that contains the bit
  15    numbered BIT_IDX. */
  16 static inline size_t
  17 elem_idx (size_t bit_idx)
  18 {
  19   return bit_idx / ELEM_BITS;
  20 }
  21
  22 /* Returns an elem_type where only the bit corresponding to
  23    BIT_IDX is turned on. */
  24 static inline elem_type
  25 bit_mask (size_t bit_idx)
  26 {
  27   return (elem_type) 1 << (bit_idx % ELEM_BITS);
  28 }
  29
  30 /* Returns the number of elements required for B's bits. */
  31 static inline size_t
  32 elem_cnt (const struct bitmap *b)
  33 {
  34   return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
  35 }
  36
  37 /* Returns the number of bytes required by B's elements. */
  38 static inline size_t
  39 byte_cnt (const struct bitmap *b)
  40 {
  41   return sizeof (elem_type) * elem_cnt (b);
  42 }
  43
  44 /* Returns a bit mask in which the bits actually used in the last
  45    element of B's bits are set to 1 and the rest are set to 0. */
  46 static inline elem_type
  47 last_mask (const struct bitmap *b)
  48 {
  49   int last_bits = b->bit_cnt % ELEM_BITS;
  50   return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
  51 }
  52 \f
  53 /* Initializes B to be a bitmap of BIT_CNT bits.
  54    Returns true if successfalse, false if memory allocation
  55    failed. */
  56 bool
  57 bitmap_init (struct bitmap *b, size_t bit_cnt)
  58 {
  59   b->bit_cnt = bit_cnt;
  60   b->bits = malloc (byte_cnt (b));
  61   if (b->bits == NULL && bit_cnt > 0)
  62     return false;
  63
  64   bitmap_set_all (b, false);
  65   return true;
  66 }
  67
  68 /* Destroys bitmap B, freeing its storage. */
  69 void
  70 bitmap_destroy (struct bitmap *b)
  71 {
  72   ASSERT (b);
  73
  74   free (b->bits);
  75 }
  76
  77 /* Returns the number of bits in B. */
  78 size_t
  79 bitmap_size (const struct bitmap *b)
  80 {
  81   return b->bit_cnt;
  82 }
  83
  84 /* Sets the bit numbered IDX in B to VALUE. */
  85 void
  86 bitmap_set (struct bitmap *b, size_t idx, bool value)
  87 {
  88   ASSERT (b != NULL);
  89   ASSERT (idx < b->bit_cnt);
  90   if (value)
  91     b->bits[elem_idx (idx)] |= bit_mask (idx);
  92   else
  93     b->bits[elem_idx (idx)] &= ~bit_mask (idx);
  94 }
  95
  96 /* Sets all bits in B to VALUE. */
  97 void
  98 bitmap_set_all (struct bitmap *b, bool value)
  99 {
 100   size_t i;
 101
 102   ASSERT (b != NULL);
 103
 104   if (b->bit_cnt > 0)
 105     {
 106       for (i = 0; i < elem_cnt (b); i++)
 107         b->bits[i] = value ? (elem_type) -1 : 0;
 108       b->bits[elem_cnt (b) - 1] &= last_mask (b);
 109     }
 110 }
 111
 112 /* Sets the bit numbered IDX in B to true. */
 113 void
 114 bitmap_mark (struct bitmap *b, size_t idx)
 115 {
 116   bitmap_set (b, idx, true);
 117 }
 118
 119 /* Sets the bit numbered IDX in B to false. */
 120 void
 121 bitmap_reset (struct bitmap *b, size_t idx)
 122 {
 123   bitmap_set (b, idx, false);
 124 }
 125
 126 /* Toggles the bit numbered IDX in B;
 127    that is, if it is true, makes it false,
 128    and if it is false, makes it true. */
 129 void
 130 bitmap_flip (struct bitmap *b, size_t idx)
 131 {
 132   ASSERT (b != NULL);
 133   ASSERT (idx < b->bit_cnt);
 134   b->bits[elem_idx (idx)] ^= bit_mask (idx);
 135 }
 136
 137 /* Returns the value of the bit numbered IDX in B. */
 138 bool
 139 bitmap_test (const struct bitmap *b, size_t idx)
 140 {
 141   ASSERT (b != NULL);
 142   ASSERT (idx < b->bit_cnt);
 143   return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
 144 }
 145
 146 /* Returns the smallest index of a bit set to VALUE in B.
 147    If no bits in B are set to VALUE, returns BITMAP_ERROR. */
 148 size_t
 149 bitmap_scan (const struct bitmap *b, bool value)
 150 {
 151   elem_type ignore = value ? 0 : (elem_type) -1;
 152   size_t idx;
 153
 154   ASSERT (b != NULL);
 155   for (idx = 0; idx < elem_cnt (b); idx++)
 156     {
 157       elem_type e = b->bits[idx];
 158       if (e != ignore)
 159         {
 160           idx *= ELEM_BITS;
 161
 162           while ((e & 1) != value)
 163             {
 164               e >>= 1;
 165               idx++;
 166             }
 167
 168           return idx < b->bit_cnt ? idx : BITMAP_ERROR;
 169         }
 170     }
 171   return BITMAP_ERROR;
 172 }
 173
 174 /* Finds the smallest index of a bit set to false in B,
 175    sets it to true, and returns the index.
 176    If no bits in B are set to false, changes no bits and
 177    returns BITMAP_ERROR. */
 178 size_t
 179 bitmap_find_and_set (struct bitmap *b)
 180 {
 181   size_t idx = bitmap_scan (b, false);
 182   if (idx != BITMAP_ERROR)
 183     bitmap_mark (b, idx);
 184   return idx;
 185 }
 186
 187 /* Finds the smallest index of a bit set to true in B,
 188    sets it to false, and returns the index.
 189    If no bits in B are set to true, changes no bits and
 190    returns BITMAP_ERROR. */
 191 size_t
 192 bitmap_find_and_clear (struct bitmap *b)
 193 {
 194   size_t idx = bitmap_scan (b, true);
 195   if (idx != BITMAP_ERROR)
 196     bitmap_reset (b, idx);
 197   return idx;
 198 }
 199
 200 /* Returns the number of bits in B set to true. */
 201 size_t
 202 bitmap_set_cnt (const struct bitmap *b)
 203 {
 204   size_t cnt;
 205   size_t i;
 206
 207   ASSERT (b != NULL);
 208   cnt = 0;
 209   for (i = 0; i < elem_cnt (b); i++)
 210     {
 211       elem_type e = b->bits[i];
 212       while (e != 0)
 213         {
 214           cnt++;
 215           e &= e - 1;
 216         }
 217     }
 218   return cnt;
 219 }
 220
 221 /* Returns true if any bits in B are set to true,
 222    and false otherwise.*/
 223 bool
 224 bitmap_any (const struct bitmap *b)
 225 {
 226   size_t i;
 227
 228   ASSERT (b != NULL);
 229   for (i = 0; i < elem_cnt (b); i++)
 230     if (b->bits[i])
 231       return true;
 232   return false;
 233 }
 234
 235 /* Returns the number of bits in B set to false. */
 236 bool
 237 bitmap_clear_cnt (const struct bitmap *b)
 238 {
 239   return b->bit_cnt - bitmap_set_cnt (b);
 240 }
 241
 242 /* Returns true if no bits in B are set to true,
 243    and false otherwise.*/
 244 bool
 245 bitmap_none (const struct bitmap *b)
 246 {
 247   return !bitmap_any (b);
 248 }
 249
 250 /* Returns true if every bit in B is set to true,
 251    and false otherwise. */
 252 bool
 253 bitmap_all (const struct bitmap *b)
 254 {
 255   size_t i;
 256
 257   ASSERT (b != NULL);
 258
 259   if (b->bit_cnt == 0)
 260     return true;
 261
 262   for (i = 0; i < elem_cnt (b) - 1; i++)
 263     if (b->bits[i] != (elem_type) -1)
 264       return false;
 265   return b->bits[i] == last_mask (b);
 266 }
 267
 268 #ifdef FILESYS
 269 /* Returns the number of bytes needed to store B in a file. */
 270 size_t
 271 bitmap_file_size (const struct bitmap *b)
 272 {
 273   return byte_cnt (b);
 274 }
 275
 276 /* Reads FILE into B, ignoring errors. */
 277 void
 278 bitmap_read (struct bitmap *b, struct file *file)
 279 {
 280   if (b->bit_cnt > 0)
 281     {
 282       file_read_at (file, b->bits, byte_cnt (b), 0);
 283       b->bits[elem_cnt (b) - 1] &= last_mask (b);
 284     }
 285 }
 286
 287 /* Writes FILE to B, ignoring errors. */
 288 void
 289 bitmap_write (const struct bitmap *b, struct file *file)
 290 {
 291   file_write_at (file, b->bits, byte_cnt (b), 0);
 292 }
 293 #endif /* FILESYS */
 294
 295 /* Dumps the contents of B to the console as hexadecimal. */
 296 void
 297 bitmap_dump (const struct bitmap *b)
 298 {
 299   hex_dump (b->bits, byte_cnt (b), false);
 300 }