Mercurial > gnulib
annotate lib/bitset.c @ 40057:b06060465f09
maint: Run 'make update-copyright'
| author | Paul Eggert <eggert@cs.ucla.edu> |
|---|---|
| date | Tue, 01 Jan 2019 00:25:11 +0100 |
| parents | 14ac09965b35 |
| children |
| rev | line source |
|---|---|
| 39973 | 1 /* General bitsets. |
| 2 | |
|
40057
b06060465f09
maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents:
39981
diff
changeset
|
3 Copyright (C) 2002-2006, 2009-2015, 2018-2019 Free Software Foundation, Inc. |
| 39973 | 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" | |
|
39981
14ac09965b35
bitset: rename ebitset/expandable.* as tbitset/table.*
Akim Demaille <akim.demaille@gmail.com>
parents:
39978
diff
changeset
|
32 #include "bitset/table.h" |
| 39973 | 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: | |
|
39981
14ac09965b35
bitset: rename ebitset/expandable.* as tbitset/table.*
Akim Demaille <akim.demaille@gmail.com>
parents:
39978
diff
changeset
|
58 return tbitset_bytes (n_bits); |
| 39973 | 59 |
|
39978
9d336a02bad8
bitset: rename BITSET_VARRAY as BITSET_VECTOR
Akim Demaille <akim.demaille@gmail.com>
parents:
39973
diff
changeset
|
60 case BITSET_VECTOR: |
| 39973 | 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: | |
|
39981
14ac09965b35
bitset: rename ebitset/expandable.* as tbitset/table.*
Akim Demaille <akim.demaille@gmail.com>
parents:
39978
diff
changeset
|
85 return tbitset_init (bset, n_bits); |
| 39973 | 86 |
|
39978
9d336a02bad8
bitset: rename BITSET_VARRAY as BITSET_VECTOR
Akim Demaille <akim.demaille@gmail.com>
parents:
39973
diff
changeset
|
87 case BITSET_VECTOR: |
| 39973 | 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) | |
|
39978
9d336a02bad8
bitset: rename BITSET_VARRAY as BITSET_VECTOR
Akim Demaille <akim.demaille@gmail.com>
parents:
39973
diff
changeset
|
111 return BITSET_VECTOR; |
| 39973 | 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 | |
|
39978
9d336a02bad8
bitset: rename BITSET_VARRAY as BITSET_VECTOR
Akim Demaille <akim.demaille@gmail.com>
parents:
39973
diff
changeset
|
122 return BITSET_VECTOR; |
| 39973 | 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 = xcalloc (1, 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 (); | |
|
39981
14ac09965b35
bitset: rename ebitset/expandable.* as tbitset/table.*
Akim Demaille <akim.demaille@gmail.com>
parents:
39978
diff
changeset
|
310 tbitset_release_memory (); |
| 39973 | 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 } |