]>
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 | * | |
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 | |
19 | * 02111-1307, USA. | |
20 | */ | |
c3c0ac83 DS |
21 | /** |
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. | |
27 | * | |
28 | * An example: | |
29 | * #include "bitfield.h" | |
30 | * | |
31 | * bitfield_t bitfield; | |
32 | * | |
33 | * bf_init(bitfield, 32); | |
34 | * ... | |
35 | * bf_assign_index(bitfield, id1); | |
36 | * bf_assign_index(bitfield, id2); | |
37 | * ... | |
38 | * bf_release_index(bitfield, id1); | |
39 | */ | |
40 | ||
41 | #ifndef _BITFIELD_H | |
42 | #define _BITFIELD_H | |
43 | ||
44 | #include <stdio.h> | |
45 | #include <string.h> | |
46 | #include <stdlib.h> | |
47 | ||
48 | typedef unsigned int word_t; | |
49 | #define WORD_MAX 0xFFFFFFFF | |
50 | #define WORD_SIZE (sizeof(word_t) * 8) | |
51 | ||
52 | /** | |
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' | |
57 | */ | |
58 | #define bitfield_t struct { word_t *data; size_t n, m; } | |
59 | ||
60 | /** | |
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. | |
65 | */ | |
66 | #define bf_init(v, N) \ | |
67 | do { \ | |
68 | (v).n = 0; \ | |
69 | (v).m = ((N) / WORD_SIZE + 1); \ | |
70 | (v).data = calloc(1, ((v).m * sizeof(word_t))); \ | |
71 | } while (0) | |
72 | ||
73 | /** | |
74 | * allocate and assign an id from bitfield v. | |
75 | */ | |
76 | #define bf_assign_index(v, id) \ | |
77 | do { \ | |
78 | bf_find_bit(v, id); \ | |
79 | bf_set_bit(v, id); \ | |
80 | } while (0) | |
81 | ||
82 | /** | |
83 | * return an id to bitfield v | |
84 | */ | |
85 | #define bf_release_index(v, id) \ | |
86 | (v).data[bf_index(id)] &= ~(1 << (bf_offset(id))) | |
87 | ||
88 | #define bf_index(b) ((b) / WORD_SIZE) | |
89 | #define bf_offset(b) ((b) % WORD_SIZE) | |
90 | ||
91 | /** | |
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. | |
94 | */ | |
95 | #define bf_set_bit(v, b) \ | |
96 | do { \ | |
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) { \ | |
101 | (v).m = (v).m + 1; \ | |
102 | (v).data = realloc((v).data, (v).m * sizeof(word_t)); \ | |
103 | } \ | |
104 | } while (0) | |
105 | ||
106 | /* Find a clear bit in v and assign it to b. */ | |
107 | #define bf_find_bit(v, b) \ | |
108 | do { \ | |
45ef4300 | 109 | word_t word = 0; \ |
c3c0ac83 DS |
110 | unsigned int w, sh; \ |
111 | for (w = 0; w <= (v).n; w++) { \ | |
112 | if ((word = (v).data[w]) != WORD_MAX) break; \ | |
113 | } \ | |
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); \ | |
120 | } while (0) | |
121 | ||
122 | #endif |