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