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