]>
Commit | Line | Data |
---|---|---|
5ffa42cb TG |
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 | long long unsigned *bitmaps; | |
28 | size_t n_bitmaps; | |
29 | size_t bitmaps_allocated; | |
5ffa42cb TG |
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(long long unsigned) * 8)) | |
41 | #define BITMAP_NUM_TO_REM(n) ((n) % (sizeof(long long unsigned) * 8)) | |
42 | #define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(long long unsigned) * 8 + (rem)) | |
43 | ||
44 | Bitmap *bitmap_new(void) { | |
45 | return new0(Bitmap, 1); | |
46 | } | |
47 | ||
48 | void bitmap_free(Bitmap *b) { | |
49 | if (!b) | |
50 | return; | |
51 | ||
52 | free(b->bitmaps); | |
53 | free(b); | |
54 | } | |
55 | ||
56 | int bitmap_ensure_allocated(Bitmap **b) { | |
57 | Bitmap *a; | |
58 | ||
59 | if (*b) | |
60 | return 0; | |
61 | ||
62 | a = bitmap_new(); | |
63 | if (!a) | |
64 | return -ENOMEM; | |
65 | ||
66 | *b = a; | |
67 | ||
68 | return 0; | |
69 | } | |
70 | ||
71 | int bitmap_set(Bitmap *b, unsigned n) { | |
cdf6f5ae | 72 | long long unsigned bitmask; |
5ffa42cb TG |
73 | unsigned offset; |
74 | ||
75 | assert(b); | |
76 | ||
77 | /* we refuse to allocate huge bitmaps */ | |
78 | if (n > BITMAPS_MAX_ENTRY) | |
79 | return -ERANGE; | |
80 | ||
81 | offset = BITMAP_NUM_TO_OFFSET(n); | |
82 | ||
83 | if (offset >= b->n_bitmaps) { | |
84 | if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1)) | |
85 | return -ENOMEM; | |
86 | ||
87 | b->n_bitmaps = offset + 1; | |
88 | } | |
89 | ||
cdf6f5ae | 90 | bitmask = 1ULL << BITMAP_NUM_TO_REM(n); |
5ffa42cb TG |
91 | |
92 | b->bitmaps[offset] |= bitmask; | |
93 | ||
94 | return 0; | |
95 | } | |
96 | ||
97 | void bitmap_unset(Bitmap *b, unsigned n) { | |
cdf6f5ae | 98 | long long unsigned bitmask; |
5ffa42cb TG |
99 | unsigned offset; |
100 | ||
101 | assert(b); | |
102 | ||
103 | offset = BITMAP_NUM_TO_OFFSET(n); | |
104 | ||
105 | if (offset >= b->n_bitmaps) | |
106 | return; | |
107 | ||
cdf6f5ae | 108 | bitmask = 1ULL << BITMAP_NUM_TO_REM(n); |
5ffa42cb TG |
109 | |
110 | b->bitmaps[offset] &= ~bitmask; | |
111 | } | |
112 | ||
113 | bool bitmap_isset(Bitmap *b, unsigned n) { | |
cdf6f5ae | 114 | long long unsigned bitmask; |
5ffa42cb TG |
115 | unsigned offset; |
116 | ||
117 | if (!b || !b->bitmaps) | |
118 | return false; | |
119 | ||
120 | offset = BITMAP_NUM_TO_OFFSET(n); | |
121 | ||
122 | if (offset >= b->n_bitmaps) | |
123 | return false; | |
124 | ||
cdf6f5ae | 125 | bitmask = 1ULL << BITMAP_NUM_TO_REM(n); |
5ffa42cb TG |
126 | |
127 | return !!(b->bitmaps[offset] & bitmask); | |
128 | } | |
129 | ||
130 | bool bitmap_isclear(Bitmap *b) { | |
131 | unsigned i; | |
132 | ||
133 | assert(b); | |
134 | ||
135 | for (i = 0; i < b->n_bitmaps; i++) | |
136 | if (b->bitmaps[i]) | |
137 | return false; | |
138 | ||
139 | return true; | |
140 | } | |
141 | ||
142 | void bitmap_clear(Bitmap *b) { | |
143 | unsigned i; | |
144 | ||
145 | assert(b); | |
146 | ||
147 | for (i = 0; i < b->n_bitmaps; i++) | |
148 | b->bitmaps[i] = 0; | |
149 | } | |
150 | ||
cb57dd41 | 151 | bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) { |
cdf6f5ae | 152 | long long unsigned bitmask; |
5ffa42cb TG |
153 | unsigned offset, rem; |
154 | ||
22cedfe1 | 155 | if (!b || i->idx == BITMAP_END) |
5ffa42cb TG |
156 | return false; |
157 | ||
cb57dd41 TG |
158 | offset = BITMAP_NUM_TO_OFFSET(i->idx); |
159 | rem = BITMAP_NUM_TO_REM(i->idx); | |
a933570d | 160 | bitmask = 1ULL << rem; |
5ffa42cb TG |
161 | |
162 | for (; offset < b->n_bitmaps; offset ++) { | |
163 | if (b->bitmaps[offset]) { | |
164 | for (; bitmask; bitmask <<= 1, rem ++) { | |
165 | if (b->bitmaps[offset] & bitmask) { | |
166 | *n = BITMAP_OFFSET_TO_NUM(offset, rem); | |
cb57dd41 | 167 | i->idx = *n + 1; |
5ffa42cb TG |
168 | |
169 | return true; | |
170 | } | |
171 | } | |
172 | } | |
173 | ||
174 | rem = 0; | |
175 | bitmask = 1; | |
176 | } | |
177 | ||
cb57dd41 | 178 | i->idx = BITMAP_END; |
5ffa42cb TG |
179 | |
180 | return false; | |
181 | } | |
182 | ||
183 | bool bitmap_equal(Bitmap *a, Bitmap *b) { | |
184 | unsigned i; | |
185 | ||
186 | if (!a ^ !b) | |
187 | return false; | |
188 | ||
189 | if (!a) | |
190 | return true; | |
191 | ||
192 | if (a->n_bitmaps != b->n_bitmaps) | |
193 | return false; | |
194 | ||
195 | for (i = 0; i < a->n_bitmaps; i++) | |
196 | if (a->bitmaps[i] != b->bitmaps[i]) | |
197 | return false; | |
198 | ||
199 | return true; | |
200 | } |