lib/bitfield.h

   1 /* Bitfields
   2  * Copyright (C) 2016 Cumulus Networks, Inc.
   3  *
   4  * This file is part of Quagga.
   5  *
   6  * Quagga is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation; either version 2, or (at your option) any
   9  * later version.
  10  *
  11  * Quagga is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with Quagga; see the file COPYING.  If not, write to the Free
  18  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  19  * 02111-1307, USA.
  20  */
  21 /**
  22  * A simple bit array implementation to allocate and free IDs. An example
  23  * of its usage is in allocating link state IDs for OSPFv3 as OSPFv3 has
  24  * removed all address semantics from LS ID. Another usage can be in
  25  * allocating IDs for BGP neighbors (and dynamic update groups) for
  26  * efficient storage of adj-rib-out.
  27  *
  28  * An example:
  29  * #include "bitfield.h"
  30  *
  31  * bitfield_t bitfield;
  32  *
  33  * bf_init(bitfield, 32);
  34  * ...
  35  * bf_assign_index(bitfield, id1);
  36  * bf_assign_index(bitfield, id2);
  37  * ...
  38  * bf_release_index(bitfield, id1);
  39  */
  40
  41 #ifndef _BITFIELD_H
  42 #define _BITFIELD_H
  43
  44 #include <stdio.h>
  45 #include <string.h>
  46 #include <stdlib.h>
  47
  48 typedef unsigned int word_t;
  49 #define WORD_MAX 0xFFFFFFFF
  50 #define WORD_SIZE (sizeof(word_t) * 8)
  51
  52 /**
  53  * The bitfield structure.
  54  * @data: the bits to manage.
  55  * @n: The current word number that is being used.
  56  * @m: total number of words in 'data'
  57  */
  58 #define bitfield_t struct { word_t *data; size_t n, m; }
  59
  60 /**
  61  * Initialize the bits.
  62  * @v: an instance of bitfield_t struct.
  63  * @N: number of bits to start with, which equates to how many
  64  *     IDs can be allocated.
  65  */
  66 #define bf_init(v, N)                               \
  67   do {                                              \
  68     (v).n = 0;                                      \
  69     (v).m = ((N) / WORD_SIZE + 1);                  \
  70     (v).data = calloc(1, ((v).m * sizeof(word_t))); \
  71   } while (0)
  72
  73 /**
  74  * allocate and assign an id from bitfield v.
  75  */
  76 #define bf_assign_index(v, id)                          \
  77   do {                                                  \
  78     bf_find_bit(v, id);                                 \
  79     bf_set_bit(v, id);                                  \
  80   } while (0)
  81
  82 /**
  83  * return an id to bitfield v
  84  */
  85 #define bf_release_index(v, id)                 \
  86   (v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
  87
  88 #define bf_index(b) ((b) / WORD_SIZE)
  89 #define bf_offset(b) ((b) % WORD_SIZE)
  90
  91 /**
  92  * Set a bit in the array. If it fills up that word and we are
  93  * out of words, extend it by one more word.
  94  */
  95 #define bf_set_bit(v, b)                                        \
  96   do {                                                          \
  97     size_t w = bf_index(b);                                     \
  98     (v).data[w] |= 1 << (bf_offset(b));                         \
  99     (v).n += ((v).data[w] == WORD_MAX);                         \
 100     if ((v).n == (v).m) {                                       \
 101       (v).m = (v).m + 1;                                        \
 102       (v).data = realloc((v).data, (v).m * sizeof(word_t));     \
 103     }                                                           \
 104   } while (0)
 105
 106 /* Find a clear bit in v and assign it to b. */
 107 #define bf_find_bit(v, b)                                       \
 108   do {                                                          \
 109     word_t word;                                                \
 110     unsigned int w, sh;                                         \
 111     for (w = 0; w <= (v).n; w++) {                              \
 112       if ((word = (v).data[w]) != WORD_MAX) break;              \
 113     }                                                           \
 114     (b) = ((word & 0xFFFF) == 0xFFFF) << 4; word >>= (b);       \
 115     sh = ((word & 0xFF) == 0xFF) << 3; word >>= sh; (b) |= sh;  \
 116     sh = ((word & 0xF) == 0xF) << 2; word >>= sh; (b) |= sh;    \
 117     sh = ((word & 0x3) == 0x3) << 1; word >>= sh; (b) |= sh;    \
 118     sh = ((word & 0x1) == 0x1) << 0; word >>= sh; (b) |= sh;    \
 119     (b) += (w * WORD_SIZE);                                     \
 120   } while (0)
 121
 122 #endif