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 #define bitfield_t struct { word_t *data; size_t n, m; }
  62
  63 /**
  64  * Initialize the bits.
  65  * @v: an instance of bitfield_t struct.
  66  * @N: number of bits to start with, which equates to how many
  67  *     IDs can be allocated.
  68  */
  69 #define bf_init(v, N)                                                          \
  70         do {                                                                   \
  71                 (v).n = 0;                                                     \
  72                 (v).m = ((N) / WORD_SIZE + 1);                                 \
  73                 (v).data = calloc(1, ((v).m * sizeof(word_t)));                \
  74         } while (0)
  75
  76 /**
  77  * allocate and assign an id from bitfield v.
  78  */
  79 #define bf_assign_index(v, id)                                                 \
  80         do {                                                                   \
  81                 bf_find_bit(v, id);                                            \
  82                 bf_set_bit(v, id);                                             \
  83         } while (0)
  84
  85 /*
  86  * allocate and assign 0th bit in the bitfiled.
  87  */
  88 #define bf_assign_zero_index(v)                                                \
  89         do {                                                                   \
  90                 int id = 0;                                                    \
  91                 bf_assign_index(v, id);                                        \
  92         } while (0)
  93
  94 /*
  95  * return an id to bitfield v
  96  */
  97 #define bf_release_index(v, id)                                                \
  98         (v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
  99
 100 /*
 101  * return 0th index back to bitfield
 102  */
 103 #define bf_release_zero_index(v) bf_release_index(v, 0)
 104
 105 #define bf_index(b) ((b) / WORD_SIZE)
 106 #define bf_offset(b) ((b) % WORD_SIZE)
 107
 108 /**
 109  * Set a bit in the array. If it fills up that word and we are
 110  * out of words, extend it by one more word.
 111  */
 112 #define bf_set_bit(v, b)                                                       \
 113         do {                                                                   \
 114                 size_t w = bf_index(b);                                        \
 115                 (v).data[w] |= 1 << (bf_offset(b));                            \
 116                 (v).n += ((v).data[w] == WORD_MAX);                            \
 117                 if ((v).n == (v).m) {                                          \
 118                         (v).m = (v).m + 1;                                     \
 119                         (v).data = realloc((v).data, (v).m * sizeof(word_t));  \
 120                 }                                                              \
 121         } while (0)
 122
 123 /* Find a clear bit in v and assign it to b. */
 124 #define bf_find_bit(v, b)                                                      \
 125         do {                                                                   \
 126                 word_t word = 0;                                               \
 127                 unsigned int w, sh;                                            \
 128                 for (w = 0; w <= (v).n; w++) {                                 \
 129                         if ((word = (v).data[w]) != WORD_MAX)                  \
 130                                 break;                                         \
 131                 }                                                              \
 132                 (b) = ((word & 0xFFFF) == 0xFFFF) << 4;                        \
 133                 word >>= (b);                                                  \
 134                 sh = ((word & 0xFF) == 0xFF) << 3;                             \
 135                 word >>= sh;                                                   \
 136                 (b) |= sh;                                                     \
 137                 sh = ((word & 0xF) == 0xF) << 2;                               \
 138                 word >>= sh;                                                   \
 139                 (b) |= sh;                                                     \
 140                 sh = ((word & 0x3) == 0x3) << 1;                               \
 141                 word >>= sh;                                                   \
 142                 (b) |= sh;                                                     \
 143                 sh = ((word & 0x1) == 0x1) << 0;                               \
 144                 word >>= sh;                                                   \
 145                 (b) |= sh;                                                     \
 146                 (b) += (w * WORD_SIZE);                                        \
 147         } while (0)
 148
 149 /*
 150  * Free the allocated memory for data
 151  * @v: an instance of bitfield_t struct.
 152  */
 153 #define bf_free(v)                                                             \
 154         do {                                                                   \
 155                 if ((v).data) {                                                \
 156                         free((v).data);                                        \
 157                 }                                                              \
 158         } while (0)
 159
 160 #ifdef __cplusplus
 161 }
 162 #endif
 163
 164 #endif