]>
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 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
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.
28 * #include "bitfield.h"
30 * bitfield_t bitfield;
32 * bf_init(bitfield, 32);
34 * bf_assign_index(bitfield, id1);
35 * bf_assign_index(bitfield, id2);
37 * bf_release_index(bitfield, id1);
51 typedef unsigned int word_t
;
52 #define WORD_MAX 0xFFFFFFFF
53 #define WORD_SIZE (sizeof(word_t) * 8)
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'
61 typedef struct {word_t
*data
; size_t n
, m
; } bitfield_t
;
63 DECLARE_MTYPE(BITFIELD
);
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.
71 #define bf_init(v, N) \
74 (v).m = ((N) / WORD_SIZE + 1); \
75 (v).data = XCALLOC(MTYPE_BITFIELD, ((v).m * sizeof(word_t))); \
79 * allocate and assign an id from bitfield v.
81 #define bf_assign_index(v, id) \
88 * allocate and assign 0th bit in the bitfiled.
90 #define bf_assign_zero_index(v) \
93 bf_assign_index(v, id); \
97 * return an id to bitfield v
99 #define bf_release_index(v, id) \
100 (v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
102 /* check if an id is in use */
103 #define bf_test_index(v, id) \
104 ((v).data[bf_index(id)] & (1 << (bf_offset(id))))
106 /* check if the bit field has been setup */
107 #define bf_is_inited(v) ((v).data)
109 /* compare two bitmaps of the same length */
110 #define bf_cmp(v1, v2) (memcmp((v1).data, (v2).data, ((v1).m * sizeof(word_t))))
113 * return 0th index back to bitfield
115 #define bf_release_zero_index(v) bf_release_index(v, 0)
117 #define bf_index(b) ((b) / WORD_SIZE)
118 #define bf_offset(b) ((b) % WORD_SIZE)
121 * Set a bit in the array. If it fills up that word and we are
122 * out of words, extend it by one more word.
124 #define bf_set_bit(v, b) \
126 size_t w = bf_index(b); \
127 (v).data[w] |= 1 << (bf_offset(b)); \
128 (v).n += ((v).data[w] == WORD_MAX); \
129 if ((v).n == (v).m) { \
131 (v).data = realloc((v).data, (v).m * sizeof(word_t)); \
135 /* Find a clear bit in v and assign it to b. */
136 #define bf_find_bit(v, b) \
139 unsigned int w, sh; \
140 for (w = 0; w <= (v).n; w++) { \
141 if ((word = (v).data[w]) != WORD_MAX) \
144 (b) = ((word & 0xFFFF) == 0xFFFF) << 4; \
146 sh = ((word & 0xFF) == 0xFF) << 3; \
149 sh = ((word & 0xF) == 0xF) << 2; \
152 sh = ((word & 0x3) == 0x3) << 1; \
155 sh = ((word & 0x1) == 0x1) << 0; \
158 (b) += (w * WORD_SIZE); \
161 static inline unsigned int bf_find_next_set_bit(bitfield_t v
,
165 unsigned long i
, offset
;
167 start_bit
= start_index
& (WORD_SIZE
- 1);
169 for (i
= bf_index(start_index
); i
< v
.m
; ++i
) {
170 if (v
.data
[i
] == 0) {
171 /* if the whole word is empty move to the next */
175 /* scan one word for set bits */
176 for (offset
= start_bit
; offset
< WORD_SIZE
; ++offset
) {
177 if ((v
.data
[i
] >> offset
) & 1)
178 return ((i
* WORD_SIZE
) + offset
);
180 /* move to the next word */
186 /* iterate through all the set bits */
187 #define bf_for_each_set_bit(v, b, max) \
188 for ((b) = bf_find_next_set_bit((v), 0); \
190 (b) = bf_find_next_set_bit((v), (b) + 1))
193 * Free the allocated memory for data
194 * @v: an instance of bitfield_t struct.
198 XFREE(MTYPE_BITFIELD, (v).data); \