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