]>
git.proxmox.com Git - mirror_frr.git/blob - lib/bitfield.h
2 * Copyright (C) 2016 Cumulus Networks, Inc.
4 * This file is part of Quagga.
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
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.
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
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.
29 * #include "bitfield.h"
31 * bitfield_t bitfield;
33 * bf_init(bitfield, 32);
35 * bf_assign_index(bitfield, id1);
36 * bf_assign_index(bitfield, id2);
38 * bf_release_index(bitfield, id1);
48 typedef unsigned int word_t
;
49 #define WORD_MAX 0xFFFFFFFF
50 #define WORD_SIZE (sizeof(word_t) * 8)
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'
58 #define bitfield_t struct { word_t *data; size_t n, m; }
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.
66 #define bf_init(v, N) \
69 (v).m = ((N) / WORD_SIZE + 1); \
70 (v).data = calloc(1, ((v).m * sizeof(word_t))); \
74 * allocate and assign an id from bitfield v.
76 #define bf_assign_index(v, id) \
83 * return an id to bitfield v
85 #define bf_release_index(v, id) \
86 (v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
88 #define bf_index(b) ((b) / WORD_SIZE)
89 #define bf_offset(b) ((b) % WORD_SIZE)
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.
95 #define bf_set_bit(v, b) \
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) { \
102 (v).data = realloc((v).data, (v).m * sizeof(word_t)); \
106 /* Find a clear bit in v and assign it to b. */
107 #define bf_find_bit(v, b) \
110 unsigned int w, sh; \
111 for (w = 0; w <= (v).n; w++) { \
112 if ((word = (v).data[w]) != WORD_MAX) break; \
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); \