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   for (i = 0; i < elem_cnt (b); i++)
 105     b->bits[i] = value ? (elem_type) -1 : 0;
 106   b->bits[elem_cnt (b) - 1] &= last_mask (b);
 107 }
 108
 109 /* Sets the bit numbered IDX in B to true. */
 110 void
 111 bitmap_mark (struct bitmap *b, size_t idx)
 112 {
 113   bitmap_set (b, idx, true);
 114 }
 115
 116 /* Sets the bit numbered IDX in B to false. */
 117 void
 118 bitmap_reset (struct bitmap *b, size_t idx)
 119 {
 120   bitmap_set (b, idx, false);
 121 }
 122
 123 /* Toggles the bit numbered IDX in B;
 124    that is, if it is true, makes it false,
 125    and if it is false, makes it true. */
 126 void
 127 bitmap_flip (struct bitmap *b, size_t idx)
 128 {
 129   ASSERT (b != NULL);
 130   ASSERT (idx < b->bit_cnt);
 131   b->bits[elem_idx (idx)] ^= bit_mask (idx);
 132 }
 133
 134 /* Returns the value of the bit numbered IDX in B. */
 135 bool
 136 bitmap_test (const struct bitmap *b, size_t idx)
 137 {
 138   ASSERT (b != NULL);
 139   ASSERT (idx < b->bit_cnt);
 140   return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
 141 }
 142
 143 /* Returns the smallest index of a bit set to VALUE in B.
 144    If no bits in B are set to VALUE, returns BITMAP_ERROR. */
 145 size_t
 146 bitmap_scan (const struct bitmap *b, bool value)
 147 {
 148   elem_type ignore = value ? 0 : (elem_type) -1;
 149   size_t idx;
 150
 151   ASSERT (b != NULL);
 152   for (idx = 0; idx < elem_cnt (b); idx++)
 153     {
 154       elem_type e = b->bits[idx];
 155       if (e != ignore)
 156         {
 157           idx *= ELEM_BITS;
 158
 159           while ((e & 1) != value)
 160             {
 161               e >>= 1;
 162               idx++;
 163             }
 164
 165           return idx < b->bit_cnt ? idx : BITMAP_ERROR;
 166         }
 167     }
 168   return BITMAP_ERROR;
 169 }
 170
 171 /* Finds the smallest index of a bit set to false in B,
 172    sets it to true, and returns the index.
 173    If no bits in B are set to false, changes no bits and
 174    returns BITMAP_ERROR. */
 175 size_t
 176 bitmap_find_and_set (struct bitmap *b)
 177 {
 178   size_t idx = bitmap_scan (b, false);
 179   if (idx != BITMAP_ERROR)
 180     bitmap_mark (b, idx);
 181   return idx;
 182 }
 183
 184 /* Finds the smallest index of a bit set to true in B,
 185    sets it to false, and returns the index.
 186    If no bits in B are set to true, changes no bits and
 187    returns BITMAP_ERROR. */
 188 size_t
 189 bitmap_find_and_clear (struct bitmap *b)
 190 {
 191   size_t idx = bitmap_scan (b, true);
 192   if (idx != BITMAP_ERROR)
 193     bitmap_reset (b, idx);
 194   return idx;
 195 }
 196
 197 /* Returns the number of bits in B set to true. */
 198 size_t
 199 bitmap_set_cnt (const struct bitmap *b)
 200 {
 201   size_t cnt;
 202   size_t i;
 203
 204   ASSERT (b != NULL);
 205   cnt = 0;
 206   for (i = 0; i < elem_cnt (b); i++)
 207     {
 208       elem_type e = b->bits[i];
 209       while (e != 0)
 210         {
 211           cnt++;
 212           e &= e - 1;
 213         }
 214     }
 215   return cnt;
 216 }
 217
 218 /* Returns true if any bits in B are set to true,
 219    and false otherwise.*/
 220 bool
 221 bitmap_any (const struct bitmap *b)
 222 {
 223   size_t i;
 224
 225   ASSERT (b != NULL);
 226   for (i = 0; i < elem_cnt (b); i++)
 227     if (b->bits[i])
 228       return true;
 229   return false;
 230 }
 231
 232 /* Returns the number of bits in B set to false. */
 233 bool
 234 bitmap_clear_cnt (const struct bitmap *b)
 235 {
 236   return b->bit_cnt - bitmap_set_cnt (b);
 237 }
 238
 239 /* Returns true if no bits in B are set to true,
 240    and false otherwise.*/
 241 bool
 242 bitmap_none (const struct bitmap *b)
 243 {
 244   return !bitmap_any (b);
 245 }
 246
 247 /* Returns true if every bit in B is set to true,
 248    and false otherwise. */
 249 bool
 250 bitmap_all (const struct bitmap *b)
 251 {
 252   size_t i;
 253
 254   ASSERT (b != NULL);
 255
 256   if (b->bit_cnt == 0)
 257     return true;
 258
 259   for (i = 0; i < elem_cnt (b) - 1; i++)
 260     if (b->bits[i] != (elem_type) -1)
 261       return false;
 262   return b->bits[i] == last_mask (b);
 263 }
 264
 265 #ifdef FILESYS
 266 /* Returns the number of bytes needed to store B in a file. */
 267 size_t
 268 bitmap_file_size (const struct bitmap *b)
 269 {
 270   return byte_cnt (b);
 271 }
 272
 273 /* Reads FILE into B, ignoring errors. */
 274 void
 275 bitmap_read (struct bitmap *b, struct file *file)
 276 {
 277   file_read_at (file, b->bits, byte_cnt (b), 0);
 278   b->bits[elem_cnt (b) - 1] &= last_mask (b);
 279 }
 280
 281 /* Writes FILE to B, ignoring errors. */
 282 void
 283 bitmap_write (const struct bitmap *b, struct file *file)
 284 {
 285   file_write_at (file, b->bits, byte_cnt (b), 0);
 286 }
 287 #endif /* FILESYS */
 288
 289 /* Dumps the contents of B to the console as hexadecimal. */
 290 void
 291 bitmap_dump (const struct bitmap *b)
 292 {
 293   hex_dump (b->bits, byte_cnt (b), false);
 294 }