]>
Commit | Line | Data |
---|---|---|
50e24903 DS |
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 | * | |
896014f4 DL |
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 | |
50e24903 | 19 | */ |
c3c0ac83 DS |
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 | ||
5e244469 RW |
47 | #ifdef __cplusplus |
48 | extern "C" { | |
49 | #endif | |
50 | ||
c3c0ac83 DS |
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 | */ | |
d62a17ae | 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) | |
c3c0ac83 DS |
75 | |
76 | /** | |
77 | * allocate and assign an id from bitfield v. | |
78 | */ | |
d62a17ae | 79 | #define bf_assign_index(v, id) \ |
80 | do { \ | |
81 | bf_find_bit(v, id); \ | |
82 | bf_set_bit(v, id); \ | |
83 | } while (0) | |
c3c0ac83 | 84 | |
4e9da201 | 85 | /* |
86 | * allocate and assign 0th bit in the bitfiled. | |
87 | */ | |
d62a17ae | 88 | #define bf_assign_zero_index(v) \ |
89 | do { \ | |
90 | int id = 0; \ | |
91 | bf_assign_index(v, id); \ | |
92 | } while (0) | |
4e9da201 | 93 | |
94 | /* | |
c3c0ac83 DS |
95 | * return an id to bitfield v |
96 | */ | |
d62a17ae | 97 | #define bf_release_index(v, id) \ |
98 | (v).data[bf_index(id)] &= ~(1 << (bf_offset(id))) | |
c3c0ac83 | 99 | |
4e9da201 | 100 | /* |
101 | * return 0th index back to bitfield | |
102 | */ | |
d62a17ae | 103 | #define bf_release_zero_index(v) bf_release_index(v, 0) |
4e9da201 | 104 | |
c3c0ac83 DS |
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 | */ | |
d62a17ae | 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) | |
c3c0ac83 DS |
122 | |
123 | /* Find a clear bit in v and assign it to b. */ | |
d62a17ae | 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) | |
c3c0ac83 | 148 | |
4e9da201 | 149 | /* |
150 | * Free the allocated memory for data | |
151 | * @v: an instance of bitfield_t struct. | |
152 | */ | |
d62a17ae | 153 | #define bf_free(v) \ |
154 | do { \ | |
1ac10b15 QY |
155 | free((v).data); \ |
156 | (v).data = NULL; \ | |
d62a17ae | 157 | } while (0) |
4e9da201 | 158 | |
5e244469 RW |
159 | #ifdef __cplusplus |
160 | } | |
161 | #endif | |
162 | ||
c3c0ac83 | 163 | #endif |