lib/bitfield.h

   1 /**
   2  * A simple bit array implementation to allocate and free IDs. An example
   3  * of its usage is in allocating link state IDs for OSPFv3 as OSPFv3 has
   4  * removed all address semantics from LS ID. Another usage can be in
   5  * allocating IDs for BGP neighbors (and dynamic update groups) for
   6  * efficient storage of adj-rib-out.
   7  *
   8  * An example:
   9  * #include "bitfield.h"
  10  *
  11  * bitfield_t bitfield;
  12  *
  13  * bf_init(bitfield, 32);
  14  * ...
  15  * bf_assign_index(bitfield, id1);
  16  * bf_assign_index(bitfield, id2);
  17  * ...
  18  * bf_release_index(bitfield, id1);
  19  */
  20
  21 #ifndef _BITFIELD_H
  22 #define _BITFIELD_H
  23
  24 #include <stdio.h>
  25 #include <string.h>
  26 #include <stdlib.h>
  27
  28 typedef unsigned int word_t;
  29 #define WORD_MAX 0xFFFFFFFF
  30 #define WORD_SIZE (sizeof(word_t) * 8)
  31
  32 /**
  33  * The bitfield structure.
  34  * @data: the bits to manage.
  35  * @n: The current word number that is being used.
  36  * @m: total number of words in 'data'
  37  */
  38 #define bitfield_t struct { word_t *data; size_t n, m; }
  39
  40 /**
  41  * Initialize the bits.
  42  * @v: an instance of bitfield_t struct.
  43  * @N: number of bits to start with, which equates to how many
  44  *     IDs can be allocated.
  45  */
  46 #define bf_init(v, N)                               \
  47   do {                                              \
  48     (v).n = 0;                                      \
  49     (v).m = ((N) / WORD_SIZE + 1);                  \
  50     (v).data = calloc(1, ((v).m * sizeof(word_t))); \
  51   } while (0)
  52
  53 /**
  54  * allocate and assign an id from bitfield v.
  55  */
  56 #define bf_assign_index(v, id)                          \
  57   do {                                                  \
  58     bf_find_bit(v, id);                                 \
  59     bf_set_bit(v, id);                                  \
  60   } while (0)
  61
  62 /**
  63  * return an id to bitfield v
  64  */
  65 #define bf_release_index(v, id)                 \
  66   (v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
  67
  68 #define bf_index(b) ((b) / WORD_SIZE)
  69 #define bf_offset(b) ((b) % WORD_SIZE)
  70
  71 /**
  72  * Set a bit in the array. If it fills up that word and we are
  73  * out of words, extend it by one more word.
  74  */
  75 #define bf_set_bit(v, b)                                        \
  76   do {                                                          \
  77     size_t w = bf_index(b);                                     \
  78     (v).data[w] |= 1 << (bf_offset(b));                         \
  79     (v).n += ((v).data[w] == WORD_MAX);                         \
  80     if ((v).n == (v).m) {                                       \
  81       (v).m = (v).m + 1;                                        \
  82       (v).data = realloc((v).data, (v).m * sizeof(word_t));     \
  83     }                                                           \
  84   } while (0)
  85
  86 /* Find a clear bit in v and assign it to b. */
  87 #define bf_find_bit(v, b)                                       \
  88   do {                                                          \
  89     word_t word = 0;                                            \
  90     unsigned int w, sh;                                         \
  91     for (w = 0; w <= (v).n; w++) {                              \
  92       if ((word = (v).data[w]) != WORD_MAX) break;              \
  93     }                                                           \
  94     (b) = ((word & 0xFFFF) == 0xFFFF) << 4; word >>= (b);       \
  95     sh = ((word & 0xFF) == 0xFF) << 3; word >>= sh; (b) |= sh;  \
  96     sh = ((word & 0xF) == 0xF) << 2; word >>= sh; (b) |= sh;    \
  97     sh = ((word & 0x3) == 0x3) << 1; word >>= sh; (b) |= sh;    \
  98     sh = ((word & 0x1) == 0x1) << 0; word >>= sh; (b) |= sh;    \
  99     (b) += (w * WORD_SIZE);                                     \
 100   } while (0)
 101
 102 #endif