1
2 /* Bit array support
3
4 Copyright (C) 2016 Molnar Karoly
5
6 This file is part of gputils.
7
8 gputils is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
11 any later version.
12
13 gputils is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with gputils; see the file COPYING. If not, write to
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
22
23 #include "libgputils.h"
24
25 #define BITARRAY_GROUP_SIZE (sizeof(uint64_t) * 8)
26
27 /*------------------------------------------------------------------------------------------------*/
28
29 void
gp_bitarray_create(gp_bit_array_t * Bits,size_t Bit_size)30 gp_bitarray_create(gp_bit_array_t *Bits, size_t Bit_size)
31 {
32 assert(Bits != NULL);
33
34 if (Bit_size == 0) {
35 Bits->bit_length = 0;
36 Bits->group_length = 0;
37 Bits->byte_length = 0;
38 Bits->array = NULL;
39 }
40
41 Bits->bit_length = Bit_size;
42 Bits->group_length = (Bit_size + BITARRAY_GROUP_SIZE - 1) / BITARRAY_GROUP_SIZE;
43 Bits->byte_length = Bits->group_length * (sizeof(uint64_t) / sizeof(uint8_t));
44 Bits->array = GP_Calloc(sizeof(uint64_t), Bits->group_length);
45 }
46
47 /*------------------------------------------------------------------------------------------------*/
48
49 void
gp_bitarray_delete(gp_bit_array_t * Bits)50 gp_bitarray_delete(gp_bit_array_t *Bits)
51 {
52 assert(Bits != NULL);
53
54 if (Bits->array != NULL) {
55 free(Bits->array);
56 Bits->array = NULL;
57 }
58
59 Bits->bit_length = 0;
60 Bits->byte_length = 0;
61 Bits->group_length = 0;
62 }
63
64 /*------------------------------------------------------------------------------------------------*/
65
66 gp_boolean
gp_bitarray_write(gp_bit_array_t * Bits,size_t Bit_index,gp_boolean Value)67 gp_bitarray_write(gp_bit_array_t *Bits, size_t Bit_index, gp_boolean Value)
68 {
69 size_t group_index;
70 size_t bit_index;
71 uint64_t cluster;
72
73 assert(Bits != NULL);
74
75 if ((Bits->array == NULL) || (Bit_index >= Bits->bit_length)) {
76 return false;
77 }
78
79 group_index = Bit_index / BITARRAY_GROUP_SIZE;
80 bit_index = Bit_index % BITARRAY_GROUP_SIZE;
81 cluster = Bits->array[group_index];
82
83 if (Value) {
84 cluster |= 1 << bit_index;
85 }
86 else {
87 cluster &= ~(1 << bit_index);
88 }
89
90 Bits->array[group_index] = cluster;
91 return true;
92 }
93
94 /*------------------------------------------------------------------------------------------------*/
95
96 gp_boolean
gp_bitarray_write_range(gp_bit_array_t * Bits,size_t Bit_index_start,size_t Bit_index_end,gp_boolean Value)97 gp_bitarray_write_range(gp_bit_array_t *Bits, size_t Bit_index_start, size_t Bit_index_end,
98 gp_boolean Value)
99 {
100 size_t group_index_start;
101 size_t bit_index_start;
102 size_t group_index_end;
103 size_t bit_index_end;
104 size_t i;
105 uint64_t mask_start;
106 uint64_t mask_end;
107 uint64_t cluster;
108
109 assert(Bits != NULL);
110
111 if ((Bits->array == NULL) || (Bit_index_end >= Bits->bit_length)) {
112 return false;
113 }
114
115 if (Bit_index_start > Bit_index_end) {
116 i = Bit_index_end;
117 Bit_index_end = Bit_index_start;
118 Bit_index_start = i;
119 }
120
121 group_index_start = Bit_index_start / BITARRAY_GROUP_SIZE;
122 bit_index_start = Bit_index_start % BITARRAY_GROUP_SIZE;
123 group_index_end = Bit_index_end / BITARRAY_GROUP_SIZE;
124 bit_index_end = Bit_index_end % BITARRAY_GROUP_SIZE;
125
126 mask_start = (uint64_t)(-1);
127 mask_end = (uint64_t)(-1);
128 mask_start <<= bit_index_start;
129 mask_end >>= BITARRAY_GROUP_SIZE - bit_index_end - 1;
130
131 i = group_index_end - group_index_start;
132 cluster = Bits->array[group_index_start];
133
134 if (i == 0) {
135 mask_start &= mask_end;
136
137 if (Value) {
138 cluster |= mask_start;
139 }
140 else {
141 cluster &= ~(mask_start);
142 }
143
144 Bits->array[group_index_start] = cluster;
145 return true;
146 }
147
148 if (Value) {
149 cluster |= mask_start;
150 }
151 else {
152 cluster &= ~(mask_start);
153 }
154
155 Bits->array[group_index_start] = cluster;
156
157 if (i > 1) {
158 cluster = (Value) ? (uint64_t)(-1) : 0;
159 for (i = group_index_start + 1; i < group_index_end; ++i) {
160 Bits->array[i] = cluster;
161 }
162 }
163
164 cluster = Bits->array[group_index_end];
165
166 if (Value) {
167 cluster |= mask_end;
168 }
169 else {
170 cluster &= ~(mask_end);
171 }
172
173 Bits->array[group_index_end] = cluster;
174 return true;
175 }
176
177 /*------------------------------------------------------------------------------------------------*/
178
179 gp_boolean
gp_bitarray_clear(gp_bit_array_t * Bits)180 gp_bitarray_clear(gp_bit_array_t *Bits)
181 {
182 assert(Bits != NULL);
183
184 if (Bits->array == NULL) {
185 return false;
186 }
187
188 memset(Bits->array, 0, Bits->byte_length);
189 return true;
190 }
191
192 /*------------------------------------------------------------------------------------------------*/
193
194 gp_boolean
gp_bitarray_read(const gp_bit_array_t * Bits,size_t Bit_index)195 gp_bitarray_read(const gp_bit_array_t *Bits, size_t Bit_index)
196 {
197 size_t group_index;
198 size_t bit_index;
199 uint64_t cluster;
200
201 assert(Bits != NULL);
202
203 if ((Bits->array == NULL) || (Bit_index >= Bits->bit_length)) {
204 return false;
205 }
206
207 group_index = Bit_index / BITARRAY_GROUP_SIZE;
208 bit_index = Bit_index % BITARRAY_GROUP_SIZE;
209 cluster = Bits->array[group_index];
210
211 return ((cluster & (1 << bit_index)) ? true : false);
212 }
213
214 /*------------------------------------------------------------------------------------------------*/
215
216 static gp_boolean
_find_lowest_bit(const uint64_t * Array,size_t Group_index,size_t * Find)217 _find_lowest_bit(const uint64_t *Array, size_t Group_index, size_t *Find)
218 {
219 gp_boolean first;
220 size_t num;
221 uint64_t cluster;
222
223 first = true;
224 num = 0;
225 while (true) {
226 cluster = Array[Group_index];
227 if (cluster == 0) {
228 if (first) {
229 return false;
230 }
231
232 ++Group_index;
233 *Find = num - 1 + (Group_index * BITARRAY_GROUP_SIZE);
234 return true;
235 }
236
237 num = gp_find_lowest_bit(cluster);
238 if (num > 1) {
239 *Find = num - 1 + (Group_index * BITARRAY_GROUP_SIZE);
240 return true;
241 }
242
243 if (Group_index == 0) {
244 break;
245 }
246
247 --Group_index;
248 first = false;
249 }
250
251 return false;
252 }
253
254 /*------------------------------------------------------------------------------------------------*/
255
256 static gp_boolean
_find_highest_bit(const uint64_t * Array,size_t Group_index,size_t Group_end,size_t * Find)257 _find_highest_bit(const uint64_t *Array, size_t Group_index, size_t Group_end, size_t *Find)
258 {
259 gp_boolean first;
260 size_t num;
261 uint64_t cluster;
262
263 first = true;
264 num = 0;
265 while (true) {
266 cluster = Array[Group_index];
267 if (cluster == 0) {
268 if (first) {
269 return false;
270 }
271
272 --Group_index;
273 *Find = num - 1 + (Group_index * BITARRAY_GROUP_SIZE);
274 return true;
275 }
276
277 num = gp_find_highest_bit(cluster);
278 if (num < 64) {
279 *Find = num - 1 + (Group_index * BITARRAY_GROUP_SIZE);
280 return true;
281 }
282
283 if (Group_index >= Group_end) {
284 break;
285 }
286
287 ++Group_index;
288 first = false;
289 }
290
291 return false;
292 }
293
294 /*------------------------------------------------------------------------------------------------*/
295
296 gp_boolean
gp_bitarray_get_range_borders(const gp_bit_array_t * Bits,size_t Bit_index,size_t * Start,size_t * End)297 gp_bitarray_get_range_borders(const gp_bit_array_t *Bits, size_t Bit_index, size_t *Start, size_t *End)
298 {
299 size_t group_index;
300 gp_boolean ret;
301
302 assert(Bits != NULL);
303 assert(Start != NULL);
304 assert(End != NULL);
305
306 if ((Bits->array == NULL) || (Bit_index >= Bits->bit_length)) {
307 return false;
308 }
309
310 group_index = Bit_index / BITARRAY_GROUP_SIZE;
311 ret = _find_lowest_bit(Bits->array, group_index, Start);
312 ret |= _find_highest_bit(Bits->array, group_index, Bits->group_length, End);
313 return ret;
314 }
315