Line data Source code
1 : /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
2 :
3 : /***
4 : This file is part of systemd.
5 :
6 : Copyright 2015 Tom Gundersen
7 :
8 : systemd is free software; you can redistribute it and/or modify it
9 : under the terms of the GNU Lesser General Public License as published by
10 : the Free Software Foundation; either version 2.1 of the License, or
11 : (at your option) any later version.
12 :
13 : systemd is distributed in the hope that it will be useful, but
14 : WITHOUT ANY WARRANTY; without even the implied warranty of
15 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 : Lesser General Public License for more details.
17 :
18 : You should have received a copy of the GNU Lesser General Public License
19 : along with systemd; If not, see <http://www.gnu.org/licenses/>.
20 : ***/
21 :
22 : #include "util.h"
23 :
24 : #include "bitmap.h"
25 :
26 : struct Bitmap {
27 : uint64_t *bitmaps;
28 : size_t n_bitmaps;
29 : size_t bitmaps_allocated;
30 : };
31 :
32 : /* Bitmaps are only meant to store relatively small numbers
33 : * (corresponding to, say, an enum), so it is ok to limit
34 : * the max entry. 64k should be plenty. */
35 : #define BITMAPS_MAX_ENTRY 0xffff
36 :
37 : /* This indicates that we reached the end of the bitmap */
38 : #define BITMAP_END ((unsigned) -1)
39 :
40 : #define BITMAP_NUM_TO_OFFSET(n) ((n) / (sizeof(uint64_t) * 8))
41 : #define BITMAP_NUM_TO_REM(n) ((n) % (sizeof(uint64_t) * 8))
42 : #define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 8 + (rem))
43 :
44 2 : Bitmap *bitmap_new(void) {
45 2 : return new0(Bitmap, 1);
46 : }
47 :
48 2 : void bitmap_free(Bitmap *b) {
49 2 : if (!b)
50 0 : return;
51 :
52 2 : free(b->bitmaps);
53 2 : free(b);
54 : }
55 :
56 2 : int bitmap_ensure_allocated(Bitmap **b) {
57 : Bitmap *a;
58 :
59 2 : assert(b);
60 :
61 2 : if (*b)
62 1 : return 0;
63 :
64 1 : a = bitmap_new();
65 1 : if (!a)
66 0 : return -ENOMEM;
67 :
68 1 : *b = a;
69 :
70 1 : return 0;
71 : }
72 :
73 8 : int bitmap_set(Bitmap *b, unsigned n) {
74 : uint64_t bitmask;
75 : unsigned offset;
76 :
77 8 : assert(b);
78 :
79 : /* we refuse to allocate huge bitmaps */
80 8 : if (n > BITMAPS_MAX_ENTRY)
81 1 : return -ERANGE;
82 :
83 7 : offset = BITMAP_NUM_TO_OFFSET(n);
84 :
85 7 : if (offset >= b->n_bitmaps) {
86 2 : if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1))
87 0 : return -ENOMEM;
88 :
89 2 : b->n_bitmaps = offset + 1;
90 : }
91 :
92 7 : bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
93 :
94 7 : b->bitmaps[offset] |= bitmask;
95 :
96 7 : return 0;
97 : }
98 :
99 5 : void bitmap_unset(Bitmap *b, unsigned n) {
100 : uint64_t bitmask;
101 : unsigned offset;
102 :
103 5 : if (!b)
104 0 : return;
105 :
106 5 : offset = BITMAP_NUM_TO_OFFSET(n);
107 :
108 5 : if (offset >= b->n_bitmaps)
109 0 : return;
110 :
111 5 : bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
112 :
113 5 : b->bitmaps[offset] &= ~bitmask;
114 : }
115 :
116 10 : bool bitmap_isset(Bitmap *b, unsigned n) {
117 : uint64_t bitmask;
118 : unsigned offset;
119 :
120 10 : if (!b)
121 0 : return false;
122 :
123 10 : offset = BITMAP_NUM_TO_OFFSET(n);
124 :
125 10 : if (offset >= b->n_bitmaps)
126 3 : return false;
127 :
128 7 : bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
129 :
130 7 : return !!(b->bitmaps[offset] & bitmask);
131 : }
132 :
133 8 : bool bitmap_isclear(Bitmap *b) {
134 : unsigned i;
135 :
136 8 : assert(b);
137 :
138 19 : for (i = 0; i < b->n_bitmaps; i++)
139 14 : if (b->bitmaps[i] != 0)
140 3 : return false;
141 :
142 5 : return true;
143 : }
144 :
145 1 : void bitmap_clear(Bitmap *b) {
146 1 : assert(b);
147 :
148 1 : b->n_bitmaps = 0;
149 1 : }
150 :
151 9 : bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) {
152 : uint64_t bitmask;
153 : unsigned offset, rem;
154 :
155 9 : assert(i);
156 9 : assert(n);
157 :
158 9 : if (!b || i->idx == BITMAP_END)
159 1 : return false;
160 :
161 8 : offset = BITMAP_NUM_TO_OFFSET(i->idx);
162 8 : rem = BITMAP_NUM_TO_REM(i->idx);
163 8 : bitmask = UINT64_C(1) << rem;
164 :
165 18 : for (; offset < b->n_bitmaps; offset ++) {
166 16 : if (b->bitmaps[offset]) {
167 260 : for (; bitmask; bitmask <<= 1, rem ++) {
168 256 : if (b->bitmaps[offset] & bitmask) {
169 6 : *n = BITMAP_OFFSET_TO_NUM(offset, rem);
170 6 : i->idx = *n + 1;
171 :
172 6 : return true;
173 : }
174 : }
175 : }
176 :
177 10 : rem = 0;
178 10 : bitmask = 1;
179 : }
180 :
181 2 : i->idx = BITMAP_END;
182 :
183 2 : return false;
184 : }
185 :
186 0 : bool bitmap_equal(Bitmap *a, Bitmap *b) {
187 :
188 0 : if (!a ^ !b)
189 0 : return false;
190 :
191 0 : if (!a)
192 0 : return true;
193 :
194 0 : if (a->n_bitmaps != b->n_bitmaps)
195 0 : return false;
196 :
197 0 : return memcmp(a->bitmaps, b->bitmaps, sizeof(uint64_t) * a->n_bitmaps) == 0;
198 : }
|
