lib/bitmap.h

   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 #ifndef _BIRD_BITMAP_H_
  11 #define _BIRD_BITMAP_H_
  12
  13 struct bmap
  14 {
  15   u32 size;
  16   u32 *data;
  17 };
  18
  19 void bmap_init(struct bmap *b, pool *p, uint size);
  20 void bmap_grow(struct bmap *b, uint need);
  21 void bmap_free(struct bmap *b);
  22
  23 static inline uint bmap_max(struct bmap *b)
  24 { return 8 * b->size; }
  25
  26 static inline int bmap_test(struct bmap *b, uint n)
  27 { return (n < bmap_max(b)) && BIT32_TEST(b->data, n); }
  28
  29 static inline void bmap_set(struct bmap *b, uint n)
  30 {
  31   if (n >= bmap_max(b)) bmap_grow(b, n/8 + 1);
  32   BIT32_SET(b->data, n);
  33 }
  34
  35 static inline void bmap_clear(struct bmap *b, uint n)
  36 {
  37   if (n >= bmap_max(b)) return;
  38   BIT32_CLR(b->data, n);
  39 }
  40
  41
  42 struct hmap
  43 {
  44   u32 size[4];
  45   u32 *data[4];
  46   u32 root[8];
  47 };
  48
  49 static inline uint hmap_max(struct hmap *b)
  50 { return 8 * b->size[0]; }
  51
  52 static inline int hmap_test(struct hmap *b, uint n)
  53 { return (n < hmap_max(b)) && BIT32_TEST(b->data[0], n); }
  54
  55 void hmap_init(struct hmap *b, pool *p, uint size);
  56 void hmap_free(struct hmap *b);
  57 void hmap_set(struct hmap *b, uint n);
  58 void hmap_clear(struct hmap *b, uint n);
  59 u32 hmap_first_zero(struct hmap *b);
  60 void hmap_check(struct hmap *b);
  61
  62 #endif