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

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