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

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