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
  11 #define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
  12 #define ELEM_IDX(BIT_IDX) ((BIT_IDX) / ELEM_BITS)
  13 #define BIT_MASK(BIT_IDX) ((elem_type) 1 << ((BIT_IDX) % ELEM_BITS))
  14
  15 static inline size_t
  16 elem_cnt (const struct bitmap *b)
  17 {
  18   return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
  19 }
  20
  21 static inline size_t
  22 byte_cnt (const struct bitmap *b)
  23 {
  24   return sizeof (elem_type) * elem_cnt (b);
  25 }
  26
  27 bool
  28 bitmap_init (struct bitmap *b, size_t bit_cnt)
  29 {
  30   b->bit_cnt = bit_cnt;
  31   b->bits = malloc (byte_cnt (b));
  32   if (b->bits == NULL && bit_cnt > 0)
  33     return false;
  34
  35   bitmap_set_all (b, false);
  36   return true;
  37 }
  38
  39 size_t
  40 bitmap_storage_size (const struct bitmap *b)
  41 {
  42   return byte_cnt (b);
  43 }
  44
  45 void
  46 bitmap_destroy (struct bitmap *b)
  47 {
  48   ASSERT (b);
  49
  50   free (b->bits);
  51 }
  52
  53 size_t
  54 bitmap_size (const struct bitmap *b)
  55 {
  56   return b->bit_cnt;
  57 }
  58
  59 void
  60 bitmap_set (struct bitmap *b, size_t idx, bool value)
  61 {
  62   ASSERT (b != NULL);
  63   ASSERT (idx < b->bit_cnt);
  64   if (value)
  65     b->bits[ELEM_IDX (idx)] |= BIT_MASK (idx);
  66   else
  67     b->bits[ELEM_IDX (idx)] &= ~BIT_MASK (idx);
  68 }
  69
  70 void
  71 bitmap_set_all (struct bitmap *b, bool value)
  72 {
  73   size_t i;
  74   size_t leftover_bits;
  75
  76   ASSERT (b != NULL);
  77
  78   for (i = 0; i < elem_cnt (b); i++)
  79     b->bits[i] = value ? (elem_type) -1 : 0;
  80
  81   leftover_bits = b->bit_cnt % ELEM_BITS;
  82   if (leftover_bits != 0)
  83     b->bits[i - 1] = ((elem_type) 1 << leftover_bits) - 1;
  84 }
  85
  86 void
  87 bitmap_mark (struct bitmap *b, size_t idx)
  88 {
  89   bitmap_set (b, idx, true);
  90 }
  91
  92 void
  93 bitmap_reset (struct bitmap *b, size_t idx)
  94 {
  95   bitmap_set (b, idx, false);
  96 }
  97
  98 void
  99 bitmap_flip (struct bitmap *b, size_t idx)
 100 {
 101   ASSERT (b != NULL);
 102   ASSERT (idx < b->bit_cnt);
 103   b->bits[ELEM_IDX (idx)] ^= BIT_MASK (idx);
 104 }
 105
 106 bool
 107 bitmap_test (const struct bitmap *b, size_t idx)
 108 {
 109   ASSERT (b != NULL);
 110   ASSERT (idx < b->bit_cnt);
 111   return (b->bits[ELEM_IDX (idx)] & BIT_MASK (idx)) != 0;
 112 }
 113
 114 size_t
 115 bitmap_scan (const struct bitmap *b, bool value)
 116 {
 117   elem_type ignore;
 118   size_t idx;
 119
 120   ASSERT (b != NULL);
 121   ignore = value ? 0 : (elem_type) -1;
 122   for (idx = 0; idx < elem_cnt (b); idx++)
 123     {
 124       elem_type e = b->bits[idx];
 125       if (e != (elem_type) -1)
 126         {
 127           idx *= ELEM_BITS;
 128
 129           while ((e & 1) == 1)
 130             {
 131               e >>= 1;
 132               idx++;
 133             }
 134
 135           return idx;
 136         }
 137     }
 138   return BITMAP_ERROR;
 139 }
 140
 141 size_t
 142 bitmap_find_and_set (struct bitmap *b)
 143 {
 144   size_t idx = bitmap_scan (b, false);
 145   if (idx != BITMAP_ERROR)
 146     bitmap_mark (b, idx);
 147   return idx;
 148 }
 149
 150 size_t
 151 bitmap_find_and_clear (struct bitmap *b)
 152 {
 153   size_t idx = bitmap_scan (b, true);
 154   if (idx != BITMAP_ERROR)
 155     bitmap_reset (b, idx);
 156   return idx;
 157 }
 158
 159 size_t
 160 bitmap_set_cnt (const struct bitmap *b)
 161 {
 162   size_t cnt;
 163   size_t i;
 164
 165   ASSERT (b != NULL);
 166   cnt = 0;
 167   for (i = 0; i < elem_cnt (b); i++)
 168     {
 169       elem_type e = b->bits[i];
 170       while (e != 0)
 171         {
 172           cnt++;
 173           e &= e - 1;
 174         }
 175     }
 176   return cnt;
 177 }
 178
 179 bool
 180 bitmap_any (const struct bitmap *b)
 181 {
 182   size_t i;
 183
 184   ASSERT (b != NULL);
 185   for (i = 0; i < elem_cnt (b); i++)
 186     if (b->bits[i])
 187       return true;
 188   return false;
 189 }
 190
 191 bool
 192 bitmap_clear_cnt (const struct bitmap *b)
 193 {
 194   return b->bit_cnt - bitmap_set_cnt (b);
 195 }
 196
 197 bool
 198 bitmap_none (const struct bitmap *b)
 199 {
 200   return !bitmap_any (b);
 201 }
 202
 203 bool
 204 bitmap_all (const struct bitmap *b)
 205 {
 206   size_t leftover_bits;
 207   size_t i;
 208
 209   ASSERT (b != NULL);
 210
 211   if (b->bit_cnt == 0)
 212     return true;
 213
 214   for (i = 0; i < elem_cnt (b) - 1; i++)
 215     if (b->bits[i] != (elem_type) -1)
 216       return true;
 217
 218   leftover_bits = b->bit_cnt % ELEM_BITS;
 219   if (leftover_bits == 0)
 220     return b->bits[i] == (elem_type) -1;
 221   else
 222     return b->bits[i] == ((elem_type) 1 << leftover_bits) - 1;
 223 }
 224
 225 #ifdef FILESYS
 226 void
 227 bitmap_read (struct bitmap *b, struct file *file)
 228 {
 229   file_read_at (file, b->bits, byte_cnt (b), 0);
 230 }
 231
 232 void
 233 bitmap_write (const struct bitmap *b, struct file *file)
 234 {
 235   file_write_at (file, b->bits, byte_cnt (b), 0);
 236 }
 237 #endif /* FILESYS */