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