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