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    Returns true if successfalse, false if memory allocation
  74    failed. */
  75 struct bitmap *
  76 bitmap_create (size_t bit_cnt)
  77 {
  78   struct bitmap *b = malloc (sizeof *b);
  79   if (b != NULL)
  80     {
  81       b->bit_cnt = bit_cnt;
  82       b->bits = malloc (byte_cnt (b));
  83       if (b->bits != NULL || bit_cnt == 0)
  84         {
  85           bitmap_set_all (b, false);
  86           return b;
  87         }
  88       free (b);
  89     }
  90   return NULL;
  91 }
  92
  93 /* Destroys bitmap B, freeing its storage. */
  94 void
  95 bitmap_destroy (struct bitmap *b)
  96 {
  97   if (b != NULL)
  98     {
  99       free (b->bits);
 100       free (b);
 101     }
 102 }
 103
 104 /* Returns the number of bits in B. */
 105 size_t
 106 bitmap_size (const struct bitmap *b)
 107 {
 108   return b->bit_cnt;
 109 }
 110
 111 /* Sets the bit numbered IDX in B to VALUE. */
 112 void
 113 bitmap_set (struct bitmap *b, size_t idx, bool value)
 114 {
 115   ASSERT (b != NULL);
 116   ASSERT (idx < b->bit_cnt);
 117   if (value)
 118     b->bits[elem_idx (idx)] |= bit_mask (idx);
 119   else
 120     b->bits[elem_idx (idx)] &= ~bit_mask (idx);
 121 }
 122
 123 /* Sets all bits in B to VALUE. */
 124 void
 125 bitmap_set_all (struct bitmap *b, bool value)
 126 {
 127   size_t i;
 128
 129   ASSERT (b != NULL);
 130
 131   if (b->bit_cnt > 0)
 132     {
 133       for (i = 0; i < elem_cnt (b); i++)
 134         b->bits[i] = value ? (elem_type) -1 : 0;
 135       b->bits[elem_cnt (b) - 1] &= last_mask (b);
 136     }
 137 }
 138
 139 /* Sets the bit numbered IDX in B to true. */
 140 void
 141 bitmap_mark (struct bitmap *b, size_t idx)
 142 {
 143   bitmap_set (b, idx, true);
 144 }
 145
 146 /* Sets the bit numbered IDX in B to false. */
 147 void
 148 bitmap_reset (struct bitmap *b, size_t idx)
 149 {
 150   bitmap_set (b, idx, false);
 151 }
 152
 153 /* Toggles the bit numbered IDX in B;
 154    that is, if it is true, makes it false,
 155    and if it is false, makes it true. */
 156 void
 157 bitmap_flip (struct bitmap *b, size_t idx)
 158 {
 159   ASSERT (b != NULL);
 160   ASSERT (idx < b->bit_cnt);
 161   b->bits[elem_idx (idx)] ^= bit_mask (idx);
 162 }
 163
 164 /* Returns the value of the bit numbered IDX in B. */
 165 bool
 166 bitmap_test (const struct bitmap *b, size_t idx)
 167 {
 168   ASSERT (b != NULL);
 169   ASSERT (idx < b->bit_cnt);
 170   return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
 171 }
 172
 173 /* Returns the smallest index of a bit set to VALUE in B.
 174    If no bits in B are set to VALUE, returns BITMAP_ERROR. */
 175 size_t
 176 bitmap_scan (const struct bitmap *b, bool value)
 177 {
 178   elem_type ignore = value ? 0 : (elem_type) -1;
 179   size_t idx;
 180
 181   ASSERT (b != NULL);
 182   for (idx = 0; idx < elem_cnt (b); idx++)
 183     {
 184       elem_type e = b->bits[idx];
 185       if (e != ignore)
 186         {
 187           idx *= ELEM_BITS;
 188
 189           while ((e & 1) != value)
 190             {
 191               e >>= 1;
 192               idx++;
 193             }
 194
 195           return idx < b->bit_cnt ? idx : BITMAP_ERROR;
 196         }
 197     }
 198   return BITMAP_ERROR;
 199 }
 200
 201 /* Finds the smallest index of a bit set to false in B,
 202    sets it to true, and returns the index.
 203    If no bits in B are set to false, changes no bits and
 204    returns BITMAP_ERROR. */
 205 size_t
 206 bitmap_find_and_set (struct bitmap *b)
 207 {
 208   size_t idx = bitmap_scan (b, false);
 209   if (idx != BITMAP_ERROR)
 210     bitmap_mark (b, idx);
 211   return idx;
 212 }
 213
 214 /* Finds the smallest index of a bit set to true in B,
 215    sets it to false, and returns the index.
 216    If no bits in B are set to true, changes no bits and
 217    returns BITMAP_ERROR. */
 218 size_t
 219 bitmap_find_and_clear (struct bitmap *b)
 220 {
 221   size_t idx = bitmap_scan (b, true);
 222   if (idx != BITMAP_ERROR)
 223     bitmap_reset (b, idx);
 224   return idx;
 225 }
 226
 227 /* Returns the number of bits in B set to true. */
 228 size_t
 229 bitmap_set_cnt (const struct bitmap *b)
 230 {
 231   size_t cnt;
 232   size_t i;
 233
 234   ASSERT (b != NULL);
 235   cnt = 0;
 236   for (i = 0; i < elem_cnt (b); i++)
 237     {
 238       elem_type e = b->bits[i];
 239       while (e != 0)
 240         {
 241           cnt++;
 242           e &= e - 1;
 243         }
 244     }
 245   return cnt;
 246 }
 247
 248 /* Returns true if any bits in B are set to true,
 249    and false otherwise.*/
 250 bool
 251 bitmap_any (const struct bitmap *b)
 252 {
 253   size_t i;
 254
 255   ASSERT (b != NULL);
 256   for (i = 0; i < elem_cnt (b); i++)
 257     if (b->bits[i])
 258       return true;
 259   return false;
 260 }
 261
 262 /* Returns the number of bits in B set to false. */
 263 bool
 264 bitmap_clear_cnt (const struct bitmap *b)
 265 {
 266   return b->bit_cnt - bitmap_set_cnt (b);
 267 }
 268
 269 /* Returns true if no bits in B are set to true,
 270    and false otherwise.*/
 271 bool
 272 bitmap_none (const struct bitmap *b)
 273 {
 274   return !bitmap_any (b);
 275 }
 276
 277 /* Returns true if every bit in B is set to true,
 278    and false otherwise. */
 279 bool
 280 bitmap_all (const struct bitmap *b)
 281 {
 282   size_t i;
 283
 284   ASSERT (b != NULL);
 285
 286   if (b->bit_cnt == 0)
 287     return true;
 288
 289   for (i = 0; i < elem_cnt (b) - 1; i++)
 290     if (b->bits[i] != (elem_type) -1)
 291       return false;
 292   return b->bits[i] == last_mask (b);
 293 }
 294
 295 #ifdef FILESYS
 296 /* Returns the number of bytes needed to store B in a file. */
 297 size_t
 298 bitmap_file_size (const struct bitmap *b)
 299 {
 300   return byte_cnt (b);
 301 }
 302
 303 /* Reads FILE into B, ignoring errors. */
 304 void
 305 bitmap_read (struct bitmap *b, struct file *file)
 306 {
 307   if (b->bit_cnt > 0)
 308     {
 309       file_read_at (file, b->bits, byte_cnt (b), 0);
 310       b->bits[elem_cnt (b) - 1] &= last_mask (b);
 311     }
 312 }
 313
 314 /* Writes FILE to B, ignoring errors. */
 315 void
 316 bitmap_write (const struct bitmap *b, struct file *file)
 317 {
 318   file_write_at (file, b->bits, byte_cnt (b), 0);
 319 }
 320 #endif /* FILESYS */
 321
 322 /* Dumps the contents of B to the console as hexadecimal. */
 323 void
 324 bitmap_dump (const struct bitmap *b)
 325 {
 326   hex_dump (0, b->bits, byte_cnt (b), false);
 327 }