lib/bitmap.c

   1 /*
   2  *      BIRD Library -- Bitmaps
   3  *
   4  *      (c) 2019 Ondrej Zajicek <santiago@crfreenet.org>
   5  *      (c) 2019 CZ.NIC z.s.p.o.
   6  *
   7  *      Can be freely distributed and used under the terms of the GNU GPL.
   8  */
   9
  10 #include <stdlib.h>
  11
  12 #include "nest/bird.h"
  13 #include "lib/bitmap.h"
  14 #include "lib/bitops.h"
  15 #include "lib/resource.h"
  16
  17
  18 /*
  19  *      Basic bitmap
  20  */
  21
  22 void
  23 bmap_init(struct bmap *b, pool *p, uint size)
  24 {
  25   b->size = BIRD_ALIGN(size, 4);
  26   b->data = mb_allocz(p, b->size);
  27 }
  28
  29 void
  30 bmap_reset(struct bmap *b, uint size)
  31 {
  32   b->size = BIRD_ALIGN(size, 4);
  33   memset(b->data, 0, b->size);
  34 }
  35
  36 void
  37 bmap_grow(struct bmap *b, uint need)
  38 {
  39   uint size = b->size * 2;
  40   while (size < need)
  41     size *= 2;
  42
  43   uint old_size = b->size;
  44   b->size = size;
  45   b->data = mb_realloc(b->data, b->size);
  46
  47   ASSERT(size >= old_size);
  48   memset(b->data + (old_size / 4), 0, size - old_size);
  49 }
  50
  51 void
  52 bmap_free(struct bmap *b)
  53 {
  54   mb_free(b->data);
  55   b->size = 0;
  56   b->data = NULL;
  57 }
  58
  59
  60
  61 /*
  62  *      Hierarchical bitmap
  63  */
  64
  65 #define B256_SIZE(b)  BIRD_ALIGN(b, 32)
  66 #define B256_STEP(b) (BIRD_ALIGN(b, 8192) >> 8)
  67
  68 void
  69 hmap_init(struct hmap *b, pool *p, uint size)
  70 {
  71   b->size[0] = B256_SIZE(size);
  72   b->size[1] = B256_STEP(b->size[0]);
  73   b->size[2] = B256_STEP(b->size[1]);
  74   b->size[3] = sizeof(b->root);
  75
  76   b->data[0] = mb_allocz(p, b->size[0]);
  77   b->data[1] = mb_allocz(p, b->size[1]);
  78   b->data[2] = mb_allocz(p, b->size[2]);
  79   b->data[3] = b->root;
  80
  81   memset(b->root, 0, sizeof(b->root));
  82 }
  83
  84 static void
  85 hmap_grow(struct hmap *b, uint need)
  86 {
  87   uint size = b->size[0] * 2;
  88   while (size < need)
  89     size *= 2;
  90
  91   for (uint i = 0; i < 3; i++)
  92   {
  93     uint old_size = b->size[i];
  94     b->size[i] = size;
  95     b->data[i] = mb_realloc(b->data[i], b->size[i]);
  96
  97     ASSERT(size >= old_size);
  98     memset(b->data[i] + (old_size / 4), 0, size - old_size);
  99
 100     size = B256_STEP(size);
 101   }
 102 }
 103
 104 void
 105 hmap_free(struct hmap *b)
 106 {
 107   mb_free(b->data[0]);
 108   mb_free(b->data[1]);
 109   mb_free(b->data[2]);
 110
 111   memset(b, 0, sizeof(struct hmap));
 112 }
 113
 114 static inline int
 115 b256_and(u32 *p)
 116 {
 117   for (int i = 0; i < 8; i++)
 118     if (~p[i])
 119       return 0;
 120
 121   return 1;
 122 }
 123
 124 void
 125 hmap_set(struct hmap *b, uint n)
 126 {
 127   if (n >= hmap_max(b))
 128     hmap_grow(b, n/8 + 1);
 129
 130   for (int i = 0; i < 4; i++)
 131   {
 132     BIT32_SET(b->data[i], n);
 133     n = n >> 8;
 134
 135     /* Continue if all bits in 256-bit block are set */
 136     if (! b256_and(b->data[i] + 8*n))
 137       break;
 138   }
 139 }
 140
 141 void
 142 hmap_clear(struct hmap *b, uint n)
 143 {
 144   if (n >= hmap_max(b))
 145     return;
 146
 147   for (int i = 0; i < 4; i++)
 148   {
 149     BIT32_CLR(b->data[i], n);
 150     n = n >> 8;
 151   }
 152 }
 153
 154 static inline int
 155 b256_first_zero(u32 *p)
 156 {
 157   for (int i = 0; i < 8; i++)
 158     if (~p[i])
 159       return 32*i + u32_ctz(~p[i]);
 160
 161   return 256;
 162 }
 163
 164 u32
 165 hmap_first_zero(struct hmap *b)
 166 {
 167   u32 n = 0;
 168
 169   for (int i = 3; i >= 0; i--)
 170   {
 171     if (32*n >= b->size[i])
 172       return hmap_max(b);
 173
 174     u32 *p = b->data[i] + 8*n;
 175
 176     n = (n << 8) + b256_first_zero(p);
 177   }
 178
 179   return n;
 180 }
 181
 182 void
 183 hmap_check(struct hmap *b)
 184 {
 185   for (int i = 0; i < 2; i++)
 186   {
 187     int max = b->size[i] / 32;
 188
 189     for (int j = 0; j < max; j++)
 190     {
 191       int x = b256_and(b->data[i] + 8*j);
 192       int y = !!BIT32_TEST(b->data[i+1], j);
 193       if (x != y)
 194         bug("Inconsistent data on %d:%d (%d vs %d)", i, j, x, y);
 195     }
 196   }
 197 }