1 | /* General bitsets. |
2 | |
3 | Copyright (C) 2002-2006, 2009-2015, 2018-2019 Free Software Foundation, Inc. |
4 | |
5 | Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). |
6 | |
7 | This program is free software: you can redistribute it and/or modify |
8 | it under the terms of the GNU General Public License as published by |
9 | the Free Software Foundation, either version 3 of the License, or |
10 | (at your option) any later version. |
11 | |
12 | This program is distributed in the hope that it will be useful, |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
15 | GNU General Public License for more details. |
16 | |
17 | You should have received a copy of the GNU General Public License |
18 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
19 | |
20 | #include <config.h> |
21 | |
22 | #include "bitset.h" |
23 | |
24 | #include <stdlib.h> |
25 | #include <string.h> |
26 | |
27 | #include "obstack.h" |
28 | |
29 | #include "bitset/array.h" |
30 | #include "bitset/list.h" |
31 | #include "bitset/stats.h" |
32 | #include "bitset/table.h" |
33 | #include "bitset/vector.h" |
34 | |
35 | const char * const bitset_type_names[] = BITSET_TYPE_NAMES; |
36 | |
37 | |
38 | /* Return number of bytes required to create a N_BIT bitset |
39 | of TYPE. The bitset may grow to require more bytes than this. */ |
40 | size_t |
41 | bitset_bytes (enum bitset_type type, bitset_bindex n_bits) |
42 | { |
43 | if (bitset_stats_enabled) |
44 | return bitset_stats_bytes (); |
45 | |
46 | switch (type) |
47 | { |
48 | default: |
49 | abort (); |
50 | |
51 | case BITSET_ARRAY: |
52 | return abitset_bytes (n_bits); |
53 | |
54 | case BITSET_LIST: |
55 | return lbitset_bytes (n_bits); |
56 | |
57 | case BITSET_TABLE: |
58 | return tbitset_bytes (n_bits); |
59 | |
60 | case BITSET_VECTOR: |
61 | return vbitset_bytes (n_bits); |
62 | } |
63 | } |
64 | |
65 | |
66 | /* Initialise bitset BSET of TYPE for N_BITS. */ |
67 | bitset |
68 | bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) |
69 | { |
70 | if (bitset_stats_enabled) |
71 | return bitset_stats_init (bset, n_bits, type); |
72 | |
73 | switch (type) |
74 | { |
75 | default: |
76 | abort (); |
77 | |
78 | case BITSET_ARRAY: |
79 | return abitset_init (bset, n_bits); |
80 | |
81 | case BITSET_LIST: |
82 | return lbitset_init (bset, n_bits); |
83 | |
84 | case BITSET_TABLE: |
85 | return tbitset_init (bset, n_bits); |
86 | |
87 | case BITSET_VECTOR: |
88 | return vbitset_init (bset, n_bits); |
89 | } |
90 | } |
91 | |
92 | |
93 | /* Select a bitset type for a set of N_BITS and with attribute hints |
94 | specified by ATTR. For variable size bitsets, N_BITS is only a |
95 | hint and may be zero. */ |
96 | enum bitset_type |
97 | bitset_type_choose (bitset_bindex n_bits ATTRIBUTE_UNUSED, unsigned attr) |
98 | { |
99 | /* Check attributes. */ |
100 | if (attr & BITSET_FIXED && attr & BITSET_VARIABLE) |
101 | abort (); |
102 | if (attr & BITSET_SPARSE && attr & BITSET_DENSE) |
103 | abort (); |
104 | |
105 | /* Choose the type of bitset. Note that sometimes we will be asked |
106 | for a zero length fixed size bitset. */ |
107 | |
108 | |
109 | /* If no attributes selected, choose a good compromise. */ |
110 | if (!attr) |
111 | return BITSET_VECTOR; |
112 | |
113 | if (attr & BITSET_SPARSE) |
114 | return BITSET_LIST; |
115 | |
116 | if (attr & BITSET_FIXED) |
117 | return BITSET_ARRAY; |
118 | |
119 | if (attr & BITSET_GREEDY) |
120 | return BITSET_TABLE; |
121 | |
122 | return BITSET_VECTOR; |
123 | } |
124 | |
125 | |
126 | /* Create a bitset of N_BITS of type TYPE. */ |
127 | bitset |
128 | bitset_alloc (bitset_bindex n_bits, enum bitset_type type) |
129 | { |
130 | size_t bytes = bitset_bytes (type, n_bits); |
131 | |
132 | bitset bset = xzalloc (bytes); |
133 | |
134 | /* The cache is disabled until some elements are allocated. If we |
135 | have variable length arrays, then we may need to allocate a dummy |
136 | element. */ |
137 | |
138 | return bitset_init (bset, n_bits, type); |
139 | } |
140 | |
141 | |
142 | /* Create a bitset of N_BITS of type TYPE. */ |
143 | bitset |
144 | bitset_obstack_alloc (struct obstack *bobstack, |
145 | bitset_bindex n_bits, enum bitset_type type) |
146 | { |
147 | size_t bytes = bitset_bytes (type, n_bits); |
148 | |
149 | bitset bset = obstack_alloc (bobstack, bytes); |
150 | memset (bset, 0, bytes); |
151 | |
152 | return bitset_init (bset, n_bits, type); |
153 | } |
154 | |
155 | |
156 | /* Create a bitset of N_BITS and with attribute hints specified by |
157 | ATTR. */ |
158 | bitset |
159 | bitset_create (bitset_bindex n_bits, unsigned attr) |
160 | { |
161 | enum bitset_type type = bitset_type_choose (n_bits, attr); |
162 | |
163 | return bitset_alloc (n_bits, type); |
164 | } |
165 | |
166 | |
167 | /* Free bitset BSET. */ |
168 | void |
169 | bitset_free (bitset bset) |
170 | { |
171 | BITSET_FREE_ (bset); |
172 | free (bset); |
173 | } |
174 | |
175 | |
176 | /* Free bitset BSET allocated on obstack. */ |
177 | void |
178 | bitset_obstack_free (bitset bset) |
179 | { |
180 | BITSET_FREE_ (bset); |
181 | } |
182 | |
183 | |
184 | /* Return bitset type. */ |
185 | enum bitset_type |
186 | bitset_type_get (bitset bset) |
187 | { |
188 | enum bitset_type type = BITSET_TYPE_ (bset); |
189 | if (type != BITSET_STATS) |
190 | return type; |
191 | |
192 | return bitset_stats_type_get (bset); |
193 | } |
194 | |
195 | |
196 | /* Return name of bitset type. */ |
197 | const char * |
198 | bitset_type_name_get (bitset bset) |
199 | { |
200 | enum bitset_type type = bitset_type_get (bset); |
201 | |
202 | return bitset_type_names[type]; |
203 | } |
204 | |
205 | |
206 | /* Find next bit set in SRC starting from and including BITNO. |
207 | Return BITSET_BINDEX_MAX if SRC empty. */ |
208 | bitset_bindex |
209 | bitset_next (bitset src, bitset_bindex bitno) |
210 | { |
211 | bitset_bindex next = bitno; |
212 | bitset_bindex val; |
213 | if (!bitset_list (src, &val, 1, &next)) |
214 | return BITSET_BINDEX_MAX; |
215 | return val; |
216 | } |
217 | |
218 | |
219 | /* Return true if both bitsets are of the same type and size. */ |
220 | extern bool |
221 | bitset_compatible_p (bitset bset1, bitset bset2) |
222 | { |
223 | return BITSET_COMPATIBLE_ (bset1, bset2); |
224 | } |
225 | |
226 | |
227 | /* Find previous bit set in SRC starting from and including BITNO. |
228 | Return BITSET_BINDEX_MAX if SRC empty. */ |
229 | bitset_bindex |
230 | bitset_prev (bitset src, bitset_bindex bitno) |
231 | { |
232 | bitset_bindex next = bitno; |
233 | bitset_bindex val; |
234 | if (!bitset_list_reverse (src, &val, 1, &next)) |
235 | return BITSET_BINDEX_MAX; |
236 | return val; |
237 | } |
238 | |
239 | |
240 | /* Find first set bit. */ |
241 | bitset_bindex |
242 | bitset_first (bitset src) |
243 | { |
244 | return bitset_next (src, 0); |
245 | } |
246 | |
247 | |
248 | /* Find last set bit. */ |
249 | bitset_bindex |
250 | bitset_last (bitset src) |
251 | { |
252 | return bitset_prev (src, 0); |
253 | } |
254 | |
255 | |
256 | /* Is BITNO in SRC the only set bit? */ |
257 | bool |
258 | bitset_only_set_p (bitset src, bitset_bindex bitno) |
259 | { |
260 | bitset_bindex val[2]; |
261 | bitset_bindex next = 0; |
262 | |
263 | if (bitset_list (src, val, 2, &next) != 1) |
264 | return false; |
265 | return val[0] == bitno; |
266 | } |
267 | |
268 | |
269 | /* Print contents of bitset BSET to FILE. */ |
270 | static void |
271 | bitset_print (FILE *file, bitset bset, bool verbose) |
272 | { |
273 | if (verbose) |
274 | fprintf (file, "n_bits = %lu, set = {" , |
275 | (unsigned long) bitset_size (bset)); |
276 | |
277 | unsigned pos = 30; |
278 | bitset_bindex i; |
279 | bitset_iterator iter; |
280 | BITSET_FOR_EACH (iter, bset, i, 0) |
281 | { |
282 | if (pos > 70) |
283 | { |
284 | fprintf (file, "\n" ); |
285 | pos = 0; |
286 | } |
287 | |
288 | fprintf (file, "%lu " , (unsigned long) i); |
289 | pos += 1 + (i >= 10) + (i >= 100); |
290 | } |
291 | |
292 | if (verbose) |
293 | fprintf (file, "}\n" ); |
294 | } |
295 | |
296 | |
297 | /* Dump bitset BSET to FILE. */ |
298 | void |
299 | bitset_dump (FILE *file, bitset bset) |
300 | { |
301 | bitset_print (file, bset, false); |
302 | } |
303 | |
304 | |
305 | /* Release memory associated with bitsets. */ |
306 | void |
307 | bitset_release_memory (void) |
308 | { |
309 | lbitset_release_memory (); |
310 | tbitset_release_memory (); |
311 | } |
312 | |
313 | |
314 | /* Toggle bit BITNO in bitset BSET and the new value of the bit. */ |
315 | bool |
316 | bitset_toggle_ (bitset bset, bitset_bindex bitno) |
317 | { |
318 | /* This routine is for completeness. It could be optimized if |
319 | required. */ |
320 | if (bitset_test (bset, bitno)) |
321 | { |
322 | bitset_reset (bset, bitno); |
323 | return false; |
324 | } |
325 | else |
326 | { |
327 | bitset_set (bset, bitno); |
328 | return true; |
329 | } |
330 | } |
331 | |
332 | |
333 | /* Return number of bits in bitset SRC. */ |
334 | bitset_bindex |
335 | bitset_size_ (bitset src) |
336 | { |
337 | return BITSET_NBITS_ (src); |
338 | } |
339 | |
340 | |
341 | /* Return number of bits set in bitset SRC. */ |
342 | bitset_bindex |
343 | bitset_count_ (bitset src) |
344 | { |
345 | bitset_bindex list[BITSET_LIST_SIZE]; |
346 | bitset_bindex count = 0; |
347 | |
348 | /* This could be greatly sped up by adding a count method for each |
349 | bitset implementation that uses a direct technique (based on |
350 | masks) for counting the number of bits set in a word. */ |
351 | |
352 | { |
353 | bitset_bindex next = 0; |
354 | bitset_bindex num; |
355 | while ((num = bitset_list (src, list, BITSET_LIST_SIZE, &next))) |
356 | count += num; |
357 | } |
358 | |
359 | return count; |
360 | } |
361 | |
362 | |
363 | /* DST = SRC. Return true if DST != SRC. |
364 | This is a fallback for the case where SRC and DST are different |
365 | bitset types. */ |
366 | bool |
367 | bitset_copy_ (bitset dst, bitset src) |
368 | { |
369 | bitset_bindex i; |
370 | bitset_iterator iter; |
371 | |
372 | /* Convert bitset types. We assume that the DST bitset |
373 | is large enough to hold the SRC bitset. */ |
374 | bitset_zero (dst); |
375 | BITSET_FOR_EACH (iter, src, i, 0) |
376 | bitset_set (dst, i); |
377 | |
378 | return true; |
379 | } |
380 | |
381 | |
382 | /* This is a fallback for implementations that do not support |
383 | four operand operations. */ |
384 | static inline bool |
385 | bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3, |
386 | enum bitset_ops op) |
387 | { |
388 | bool changed = false; |
389 | |
390 | /* Create temporary bitset. */ |
391 | bool stats_enabled_save = bitset_stats_enabled; |
392 | bitset_stats_enabled = false; |
393 | bitset tmp = bitset_alloc (0, bitset_type_get (dst)); |
394 | bitset_stats_enabled = stats_enabled_save; |
395 | |
396 | switch (op) |
397 | { |
398 | default: |
399 | abort (); |
400 | |
401 | case BITSET_OP_OR_AND: |
402 | bitset_or (tmp, src1, src2); |
403 | changed = bitset_and_cmp (dst, src3, tmp); |
404 | break; |
405 | |
406 | case BITSET_OP_AND_OR: |
407 | bitset_and (tmp, src1, src2); |
408 | changed = bitset_or_cmp (dst, src3, tmp); |
409 | break; |
410 | |
411 | case BITSET_OP_ANDN_OR: |
412 | bitset_andn (tmp, src1, src2); |
413 | changed = bitset_or_cmp (dst, src3, tmp); |
414 | break; |
415 | } |
416 | |
417 | bitset_free (tmp); |
418 | return changed; |
419 | } |
420 | |
421 | |
422 | /* DST = (SRC1 & SRC2) | SRC3. */ |
423 | void |
424 | bitset_and_or_ (bitset dst, bitset src1, bitset src2, bitset src3) |
425 | { |
426 | bitset_and_or_cmp_ (dst, src1, src2, src3); |
427 | } |
428 | |
429 | |
430 | /* DST = (SRC1 & SRC2) | SRC3. Return non-zero if |
431 | DST != (SRC1 & SRC2) | SRC3. */ |
432 | bool |
433 | bitset_and_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3) |
434 | { |
435 | return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR); |
436 | } |
437 | |
438 | |
439 | /* DST = (SRC1 & ~SRC2) | SRC3. */ |
440 | void |
441 | bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3) |
442 | { |
443 | bitset_andn_or_cmp_ (dst, src1, src2, src3); |
444 | } |
445 | |
446 | |
447 | /* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if |
448 | DST != (SRC1 & ~SRC2) | SRC3. */ |
449 | bool |
450 | bitset_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3) |
451 | { |
452 | return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR); |
453 | } |
454 | |
455 | |
456 | /* DST = (SRC1 | SRC2) & SRC3. */ |
457 | void |
458 | bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3) |
459 | { |
460 | bitset_or_and_cmp_ (dst, src1, src2, src3); |
461 | } |
462 | |
463 | |
464 | /* DST = (SRC1 | SRC2) & SRC3. Return non-zero if |
465 | DST != (SRC1 | SRC2) & SRC3. */ |
466 | bool |
467 | bitset_or_and_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3) |
468 | { |
469 | return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND); |
470 | } |
471 | |
472 | |
473 | /* Function to be called from debugger to print bitset. */ |
474 | void |
475 | debug_bitset (bitset bset) |
476 | { |
477 | if (bset) |
478 | bitset_print (stderr, bset, true); |
479 | } |
480 | |