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 along
  17  * with this program; see the file COPYING; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20 /**
  21  * A simple bit array implementation to allocate and free IDs. An example
  22  * of its usage is in allocating link state IDs for OSPFv3 as OSPFv3 has
  23  * removed all address semantics from LS ID. Another usage can be in
  24  * allocating IDs for BGP neighbors (and dynamic update groups) for
  25  * efficient storage of adj-rib-out.
  26  *
  27  * An example:
  28  * #include "bitfield.h"
  29  *
  30  * bitfield_t bitfield;
  31  *
  32  * bf_init(bitfield, 32);
  33  * ...
  34  * bf_assign_index(bitfield, id1);
  35  * bf_assign_index(bitfield, id2);
  36  * ...
  37  * bf_release_index(bitfield, id1);
  38  */
  39
  40 #ifndef _BITFIELD_H
  41 #define _BITFIELD_H
  42
  43 #include <stdio.h>
  44 #include <string.h>
  45 #include <stdlib.h>
  46
  47 #ifdef __cplusplus
  48 extern "C" {
  49 #endif
  50
  51 typedef unsigned int word_t;
  52 #define WORD_MAX 0xFFFFFFFF
  53 #define WORD_SIZE (sizeof(word_t) * 8)
  54
  55 /**
  56  * The bitfield structure.
  57  * @data: the bits to manage.
  58  * @n: The current word number that is being used.
  59  * @m: total number of words in 'data'
  60  */
  61 typedef struct {word_t *data; size_t n, m; } bitfield_t;
  62
  63 DECLARE_MTYPE(BITFIELD);
  64
  65 /**
  66  * Initialize the bits.
  67  * @v: an instance of bitfield_t struct.
  68  * @N: number of bits to start with, which equates to how many
  69  *     IDs can be allocated.
  70  */
  71 #define bf_init(v, N)                                                          \
  72         do {                                                                   \
  73                 (v).n = 0;                                                     \
  74                 (v).m = ((N) / WORD_SIZE + 1);                                 \
  75                 (v).data = (word_t *)XCALLOC(MTYPE_BITFIELD,                   \
  76                                              ((v).m * sizeof(word_t)));        \
  77         } while (0)
  78
  79 /**
  80  * allocate and assign an id from bitfield v.
  81  */
  82 #define bf_assign_index(v, id)                                                 \
  83         do {                                                                   \
  84                 bf_find_bit(v, id);                                            \
  85                 bf_set_bit(v, id);                                             \
  86         } while (0)
  87
  88 /*
  89  * allocate and assign 0th bit in the bitfiled.
  90  */
  91 #define bf_assign_zero_index(v)                                                \
  92         do {                                                                   \
  93                 int id = 0;                                                    \
  94                 bf_assign_index(v, id);                                        \
  95         } while (0)
  96
  97 /*
  98  * return an id to bitfield v
  99  */
 100 #define bf_release_index(v, id)                                                \
 101         (v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
 102
 103 /* check if an id is in use */
 104 #define bf_test_index(v, id)                                                \
 105         ((v).data[bf_index(id)] & (1 << (bf_offset(id))))
 106
 107 /* check if the bit field has been setup */
 108 #define bf_is_inited(v) ((v).data)
 109
 110 /* compare two bitmaps of the same length */
 111 #define bf_cmp(v1, v2) (memcmp((v1).data, (v2).data, ((v1).m * sizeof(word_t))))
 112
 113 /*
 114  * return 0th index back to bitfield
 115  */
 116 #define bf_release_zero_index(v) bf_release_index(v, 0)
 117
 118 #define bf_index(b) ((b) / WORD_SIZE)
 119 #define bf_offset(b) ((b) % WORD_SIZE)
 120
 121 /**
 122  * Set a bit in the array. If it fills up that word and we are
 123  * out of words, extend it by one more word.
 124  */
 125 #define bf_set_bit(v, b)                                                       \
 126         do {                                                                   \
 127                 size_t w = bf_index(b);                                        \
 128                 (v).data[w] |= 1 << (bf_offset(b));                            \
 129                 (v).n += ((v).data[w] == WORD_MAX);                            \
 130                 if ((v).n == (v).m) {                                          \
 131                         (v).m = (v).m + 1;                                     \
 132                         (v).data = realloc((v).data, (v).m * sizeof(word_t));  \
 133                 }                                                              \
 134         } while (0)
 135
 136 /* Find a clear bit in v and assign it to b. */
 137 #define bf_find_bit(v, b)                                                      \
 138         do {                                                                   \
 139                 word_t word = 0;                                               \
 140                 unsigned int w, sh;                                            \
 141                 for (w = 0; w <= (v).n; w++) {                                 \
 142                         if ((word = (v).data[w]) != WORD_MAX)                  \
 143                                 break;                                         \
 144                 }                                                              \
 145                 (b) = ((word & 0xFFFF) == 0xFFFF) << 4;                        \
 146                 word >>= (b);                                                  \
 147                 sh = ((word & 0xFF) == 0xFF) << 3;                             \
 148                 word >>= sh;                                                   \
 149                 (b) |= sh;                                                     \
 150                 sh = ((word & 0xF) == 0xF) << 2;                               \
 151                 word >>= sh;                                                   \
 152                 (b) |= sh;                                                     \
 153                 sh = ((word & 0x3) == 0x3) << 1;                               \
 154                 word >>= sh;                                                   \
 155                 (b) |= sh;                                                     \
 156                 sh = ((word & 0x1) == 0x1) << 0;                               \
 157                 word >>= sh;                                                   \
 158                 (b) |= sh;                                                     \
 159                 (b) += (w * WORD_SIZE);                                        \
 160         } while (0)
 161
 162 /*
 163  * Find a clear bit in v and return it
 164  * Start looking in the word containing bit position start_index.
 165  * If necessary, wrap around after bit position max_index.
 166  */
 167 static inline unsigned int
 168 bf_find_next_clear_bit_wrap(bitfield_t *v, word_t start_index, word_t max_index)
 169 {
 170         int start_bit;
 171         unsigned long i, offset, scanbits, wordcount_max, index_max;
 172
 173         if (start_index > max_index)
 174                 start_index = 0;
 175
 176         start_bit = start_index & (WORD_SIZE - 1);
 177         wordcount_max = bf_index(max_index) + 1;
 178
 179         scanbits = WORD_SIZE;
 180         for (i = bf_index(start_index); i < v->m; ++i) {
 181                 if (v->data[i] == WORD_MAX) {
 182                         /* if the whole word is full move to the next */
 183                         start_bit = 0;
 184                         continue;
 185                 }
 186                 /* scan one word for clear bits */
 187                 if ((i == v->m - 1) && (v->m >= wordcount_max))
 188                         /* max index could be only part of word */
 189                         scanbits = (max_index % WORD_SIZE) + 1;
 190                 for (offset = start_bit; offset < scanbits; ++offset) {
 191                         if (!((v->data[i] >> offset) & 1))
 192                                 return ((i * WORD_SIZE) + offset);
 193                 }
 194                 /* move to the next word */
 195                 start_bit = 0;
 196         }
 197
 198         if (v->m < wordcount_max) {
 199                 /*
 200                  * We can expand bitfield, so no need to wrap.
 201                  * Return the index of the first bit of the next word.
 202                  * Assumption is that caller will call bf_set_bit which
 203                  * will allocate additional space.
 204                  */
 205                 v->m += 1;
 206                 v->data = (word_t *)realloc(v->data, v->m * sizeof(word_t));
 207                 v->data[v->m - 1] = 0;
 208                 return v->m * WORD_SIZE;
 209         }
 210
 211         /*
 212          * start looking for a clear bit at the start of the bitfield and
 213          * stop when we reach start_index
 214          */
 215         scanbits = WORD_SIZE;
 216         index_max = bf_index(start_index - 1);
 217         for (i = 0; i <= index_max; ++i) {
 218                 if (i == index_max)
 219                         scanbits = ((start_index - 1) % WORD_SIZE) + 1;
 220                 for (offset = start_bit; offset < scanbits; ++offset) {
 221                         if (!((v->data[i] >> offset) & 1))
 222                                 return ((i * WORD_SIZE) + offset);
 223                 }
 224                 /* move to the next word */
 225                 start_bit = 0;
 226         }
 227
 228         return WORD_MAX;
 229 }
 230
 231 static inline unsigned int bf_find_next_set_bit(bitfield_t v,
 232                 word_t start_index)
 233 {
 234         int start_bit;
 235         unsigned long i, offset;
 236
 237         start_bit = start_index & (WORD_SIZE - 1);
 238
 239         for (i = bf_index(start_index); i < v.m; ++i) {
 240                 if (v.data[i] == 0) {
 241                         /* if the whole word is empty move to the next */
 242                         start_bit = 0;
 243                         continue;
 244                 }
 245                 /* scan one word for set bits */
 246                 for (offset = start_bit; offset < WORD_SIZE; ++offset) {
 247                         if ((v.data[i] >> offset) & 1)
 248                                 return ((i * WORD_SIZE) + offset);
 249                 }
 250                 /* move to the next word */
 251                 start_bit = 0;
 252         }
 253         return WORD_MAX;
 254 }
 255
 256 /* iterate through all the set bits */
 257 #define bf_for_each_set_bit(v, b, max)                 \
 258         for ((b) = bf_find_next_set_bit((v), 0);           \
 259                         (b) < max;                                 \
 260                         (b) = bf_find_next_set_bit((v), (b) + 1))
 261
 262 /*
 263  * Free the allocated memory for data
 264  * @v: an instance of bitfield_t struct.
 265  */
 266 #define bf_free(v)                                                             \
 267         do {                                                                   \
 268                 XFREE(MTYPE_BITFIELD, (v).data);                               \
 269                 (v).data = NULL;                                               \
 270         } while (0)
 271
 272 static inline bitfield_t bf_copy(bitfield_t src)
 273 {
 274         bitfield_t dst;
 275
 276         assert(bf_is_inited(src));
 277         bf_init(dst, WORD_SIZE * (src.m - 1));
 278         for (size_t i = 0; i < src.m; i++)
 279                 dst.data[i] = src.data[i];
 280         dst.n = src.n;
 281         return dst;
 282 }
 283
 284
 285 #ifdef __cplusplus
 286 }
 287 #endif
 288
 289 #endif