OLD | NEW |
(Empty) | |
| 1 /* Functions to support expandable bitsets. |
| 2 Copyright (C) 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. |
| 3 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). |
| 4 |
| 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 3 of the License, or |
| 8 (at your option) any later version. |
| 9 |
| 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. |
| 14 |
| 15 You should have received a copy of the GNU General Public License |
| 16 along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
| 17 |
| 18 #include <config.h> |
| 19 |
| 20 #include "ebitset.h" |
| 21 |
| 22 #include "obstack.h" |
| 23 #include <stdlib.h> |
| 24 #include <string.h> |
| 25 |
| 26 /* This file implements expandable bitsets. These bitsets can be of |
| 27 arbitrary length and are more efficient than arrays of bits for |
| 28 large sparse sets. |
| 29 |
| 30 Empty elements are represented by a NULL pointer in the table of |
| 31 element pointers. An alternative is to point to a special zero |
| 32 element. Similarly, we could represent an all 1's element with |
| 33 another special ones element pointer. |
| 34 |
| 35 Bitsets are commonly empty so we need to ensure that this special |
| 36 case is fast. A zero bitset is indicated when cdata is 0. This is |
| 37 conservative since cdata may be non zero and the bitset may still |
| 38 be zero. |
| 39 |
| 40 The bitset cache can be disabled either by setting cindex to |
| 41 BITSET_WINDEX_MAX or by setting csize to 0. Here |
| 42 we use the former approach since cindex needs to be updated whenever |
| 43 cdata is changed. |
| 44 */ |
| 45 |
| 46 |
| 47 /* Number of words to use for each element. */ |
| 48 #define EBITSET_ELT_WORDS 2 |
| 49 |
| 50 /* Number of bits stored in each element. */ |
| 51 #define EBITSET_ELT_BITS \ |
| 52 ((unsigned int) (EBITSET_ELT_WORDS * BITSET_WORD_BITS)) |
| 53 |
| 54 /* Ebitset element. We use an array of bits. */ |
| 55 typedef struct ebitset_elt_struct |
| 56 { |
| 57 union |
| 58 { |
| 59 bitset_word words[EBITSET_ELT_WORDS]; /* Bits that are set. */ |
| 60 struct ebitset_elt_struct *next; |
| 61 } |
| 62 u; |
| 63 } |
| 64 ebitset_elt; |
| 65 |
| 66 |
| 67 typedef ebitset_elt *ebitset_elts; |
| 68 |
| 69 |
| 70 /* Number of elements to initially allocate. */ |
| 71 |
| 72 #ifndef EBITSET_INITIAL_SIZE |
| 73 #define EBITSET_INITIAL_SIZE 2 |
| 74 #endif |
| 75 |
| 76 |
| 77 enum ebitset_find_mode |
| 78 { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST }; |
| 79 |
| 80 static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits. */ |
| 81 |
| 82 /* Obstack to allocate bitset elements from. */ |
| 83 static struct obstack ebitset_obstack; |
| 84 static bool ebitset_obstack_init = false; |
| 85 static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */ |
| 86 |
| 87 #define EBITSET_N_ELTS(N) (((N) + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS) |
| 88 #define EBITSET_ELTS(BSET) ((BSET)->e.elts) |
| 89 #define EBITSET_SIZE(BSET) EBITSET_N_ELTS (BITSET_NBITS_ (BSET)) |
| 90 #define EBITSET_ASIZE(BSET) ((BSET)->e.size) |
| 91 |
| 92 #define EBITSET_NEXT(ELT) ((ELT)->u.next) |
| 93 #define EBITSET_WORDS(ELT) ((ELT)->u.words) |
| 94 |
| 95 /* Disable bitset cache and mark BSET as being zero. */ |
| 96 #define EBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \ |
| 97 (BSET)->b.cdata = 0) |
| 98 |
| 99 #define EBITSET_CACHE_DISABLE(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX) |
| 100 |
| 101 /* Disable bitset cache and mark BSET as being possibly non-zero. */ |
| 102 #define EBITSET_NONZERO_SET(BSET) \ |
| 103 (EBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0) |
| 104 |
| 105 /* A conservative estimate of whether the bitset is zero. |
| 106 This is non-zero only if we know for sure that the bitset is zero. */ |
| 107 #define EBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0) |
| 108 |
| 109 /* Enable cache to point to element with table index EINDEX. |
| 110 The element must exist. */ |
| 111 #define EBITSET_CACHE_SET(BSET, EINDEX) \ |
| 112 ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \ |
| 113 (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX])) |
| 114 |
| 115 #undef min |
| 116 #undef max |
| 117 #define min(a, b) ((a) > (b) ? (b) : (a)) |
| 118 #define max(a, b) ((a) > (b) ? (a) : (b)) |
| 119 |
| 120 static bitset_bindex |
| 121 ebitset_resize (bitset src, bitset_bindex n_bits) |
| 122 { |
| 123 bitset_windex oldsize; |
| 124 bitset_windex newsize; |
| 125 |
| 126 if (n_bits == BITSET_NBITS_ (src)) |
| 127 return n_bits; |
| 128 |
| 129 oldsize = EBITSET_SIZE (src); |
| 130 newsize = EBITSET_N_ELTS (n_bits); |
| 131 |
| 132 if (oldsize < newsize) |
| 133 { |
| 134 bitset_windex size; |
| 135 |
| 136 /* The bitset needs to grow. If we already have enough memory |
| 137 allocated, then just zero what we need. */ |
| 138 if (newsize > EBITSET_ASIZE (src)) |
| 139 { |
| 140 /* We need to allocate more memory. When oldsize is |
| 141 non-zero this means that we are changing the size, so |
| 142 grow the bitset 25% larger than requested to reduce |
| 143 number of reallocations. */ |
| 144 |
| 145 if (oldsize == 0) |
| 146 size = newsize; |
| 147 else |
| 148 size = newsize + newsize / 4; |
| 149 |
| 150 EBITSET_ELTS (src) |
| 151 = realloc (EBITSET_ELTS (src), size * sizeof (ebitset_elt *)); |
| 152 EBITSET_ASIZE (src) = size; |
| 153 } |
| 154 |
| 155 memset (EBITSET_ELTS (src) + oldsize, 0, |
| 156 (newsize - oldsize) * sizeof (ebitset_elt *)); |
| 157 } |
| 158 else |
| 159 { |
| 160 /* The bitset needs to shrink. There's no point deallocating |
| 161 the memory unless it is shrinking by a reasonable amount. */ |
| 162 if ((oldsize - newsize) >= oldsize / 2) |
| 163 { |
| 164 EBITSET_ELTS (src) |
| 165 = realloc (EBITSET_ELTS (src), newsize * sizeof (ebitset_elt *)); |
| 166 EBITSET_ASIZE (src) = newsize; |
| 167 } |
| 168 |
| 169 /* Need to prune any excess bits. FIXME. */ |
| 170 } |
| 171 |
| 172 BITSET_NBITS_ (src) = n_bits; |
| 173 return n_bits; |
| 174 } |
| 175 |
| 176 |
| 177 /* Allocate a ebitset element. The bits are not cleared. */ |
| 178 static inline ebitset_elt * |
| 179 ebitset_elt_alloc (void) |
| 180 { |
| 181 ebitset_elt *elt; |
| 182 |
| 183 if (ebitset_free_list != 0) |
| 184 { |
| 185 elt = ebitset_free_list; |
| 186 ebitset_free_list = EBITSET_NEXT (elt); |
| 187 } |
| 188 else |
| 189 { |
| 190 if (!ebitset_obstack_init) |
| 191 { |
| 192 ebitset_obstack_init = true; |
| 193 |
| 194 /* Let particular systems override the size of a chunk. */ |
| 195 |
| 196 #ifndef OBSTACK_CHUNK_SIZE |
| 197 #define OBSTACK_CHUNK_SIZE 0 |
| 198 #endif |
| 199 |
| 200 /* Let them override the alloc and free routines too. */ |
| 201 |
| 202 #ifndef OBSTACK_CHUNK_ALLOC |
| 203 #define OBSTACK_CHUNK_ALLOC xmalloc |
| 204 #endif |
| 205 |
| 206 #ifndef OBSTACK_CHUNK_FREE |
| 207 #define OBSTACK_CHUNK_FREE free |
| 208 #endif |
| 209 |
| 210 #if ! defined __GNUC__ || __GNUC__ < 2 |
| 211 #define __alignof__(type) 0 |
| 212 #endif |
| 213 |
| 214 obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE, |
| 215 __alignof__ (ebitset_elt), |
| 216 OBSTACK_CHUNK_ALLOC, |
| 217 OBSTACK_CHUNK_FREE); |
| 218 } |
| 219 |
| 220 /* Perhaps we should add a number of new elements to the free |
| 221 list. */ |
| 222 elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack, |
| 223 sizeof (ebitset_elt)); |
| 224 } |
| 225 |
| 226 return elt; |
| 227 } |
| 228 |
| 229 |
| 230 /* Allocate a ebitset element. The bits are cleared. */ |
| 231 static inline ebitset_elt * |
| 232 ebitset_elt_calloc (void) |
| 233 { |
| 234 ebitset_elt *elt; |
| 235 |
| 236 elt = ebitset_elt_alloc (); |
| 237 memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt))); |
| 238 return elt; |
| 239 } |
| 240 |
| 241 |
| 242 static inline void |
| 243 ebitset_elt_free (ebitset_elt *elt) |
| 244 { |
| 245 EBITSET_NEXT (elt) = ebitset_free_list; |
| 246 ebitset_free_list = elt; |
| 247 } |
| 248 |
| 249 |
| 250 /* Remove element with index EINDEX from bitset BSET. */ |
| 251 static inline void |
| 252 ebitset_elt_remove (bitset bset, bitset_windex eindex) |
| 253 { |
| 254 ebitset_elts *elts; |
| 255 ebitset_elt *elt; |
| 256 |
| 257 elts = EBITSET_ELTS (bset); |
| 258 |
| 259 elt = elts[eindex]; |
| 260 |
| 261 elts[eindex] = 0; |
| 262 ebitset_elt_free (elt); |
| 263 } |
| 264 |
| 265 |
| 266 /* Add ELT into elts at index EINDEX of bitset BSET. */ |
| 267 static inline void |
| 268 ebitset_elt_add (bitset bset, ebitset_elt *elt, bitset_windex eindex) |
| 269 { |
| 270 ebitset_elts *elts; |
| 271 |
| 272 elts = EBITSET_ELTS (bset); |
| 273 /* Assume that the elts entry not allocated. */ |
| 274 elts[eindex] = elt; |
| 275 } |
| 276 |
| 277 |
| 278 /* Are all bits in an element zero? */ |
| 279 static inline bool |
| 280 ebitset_elt_zero_p (ebitset_elt *elt) |
| 281 { |
| 282 int i; |
| 283 |
| 284 for (i = 0; i < EBITSET_ELT_WORDS; i++) |
| 285 if (EBITSET_WORDS (elt)[i]) |
| 286 return false; |
| 287 |
| 288 return true; |
| 289 } |
| 290 |
| 291 |
| 292 static ebitset_elt * |
| 293 ebitset_elt_find (bitset bset, bitset_bindex bindex, |
| 294 enum ebitset_find_mode mode) |
| 295 { |
| 296 ebitset_elt *elt; |
| 297 bitset_windex size; |
| 298 bitset_windex eindex; |
| 299 ebitset_elts *elts; |
| 300 |
| 301 eindex = bindex / EBITSET_ELT_BITS; |
| 302 |
| 303 elts = EBITSET_ELTS (bset); |
| 304 size = EBITSET_SIZE (bset); |
| 305 |
| 306 if (eindex < size) |
| 307 { |
| 308 if ((elt = elts[eindex])) |
| 309 { |
| 310 if (EBITSET_WORDS (elt) == bset->b.cdata) |
| 311 return elt; |
| 312 |
| 313 EBITSET_CACHE_SET (bset, eindex); |
| 314 return elt; |
| 315 } |
| 316 } |
| 317 |
| 318 /* The element could not be found. */ |
| 319 |
| 320 switch (mode) |
| 321 { |
| 322 default: |
| 323 abort (); |
| 324 |
| 325 case EBITSET_FIND: |
| 326 return 0; |
| 327 |
| 328 case EBITSET_CREATE: |
| 329 if (eindex >= size) |
| 330 ebitset_resize (bset, bindex); |
| 331 |
| 332 /* Create a new element. */ |
| 333 elt = ebitset_elt_calloc (); |
| 334 ebitset_elt_add (bset, elt, eindex); |
| 335 EBITSET_CACHE_SET (bset, eindex); |
| 336 return elt; |
| 337 |
| 338 case EBITSET_SUBST: |
| 339 return &ebitset_zero_elts[0]; |
| 340 } |
| 341 } |
| 342 |
| 343 |
| 344 /* Weed out the zero elements from the elts. */ |
| 345 static inline bitset_windex |
| 346 ebitset_weed (bitset bset) |
| 347 { |
| 348 ebitset_elts *elts; |
| 349 bitset_windex j; |
| 350 bitset_windex count; |
| 351 |
| 352 if (EBITSET_ZERO_P (bset)) |
| 353 return 0; |
| 354 |
| 355 elts = EBITSET_ELTS (bset); |
| 356 count = 0; |
| 357 for (j = 0; j < EBITSET_SIZE (bset); j++) |
| 358 { |
| 359 ebitset_elt *elt = elts[j]; |
| 360 |
| 361 if (elt) |
| 362 { |
| 363 if (ebitset_elt_zero_p (elt)) |
| 364 { |
| 365 ebitset_elt_remove (bset, j); |
| 366 count++; |
| 367 } |
| 368 } |
| 369 else |
| 370 count++; |
| 371 } |
| 372 |
| 373 count = j - count; |
| 374 if (!count) |
| 375 { |
| 376 /* All the bits are zero. We could shrink the elts. |
| 377 For now just mark BSET as known to be zero. */ |
| 378 EBITSET_ZERO_SET (bset); |
| 379 } |
| 380 else |
| 381 EBITSET_NONZERO_SET (bset); |
| 382 |
| 383 return count; |
| 384 } |
| 385 |
| 386 |
| 387 /* Set all bits in the bitset to zero. */ |
| 388 static inline void |
| 389 ebitset_zero (bitset bset) |
| 390 { |
| 391 ebitset_elts *elts; |
| 392 bitset_windex j; |
| 393 |
| 394 if (EBITSET_ZERO_P (bset)) |
| 395 return; |
| 396 |
| 397 elts = EBITSET_ELTS (bset); |
| 398 for (j = 0; j < EBITSET_SIZE (bset); j++) |
| 399 { |
| 400 ebitset_elt *elt = elts[j]; |
| 401 |
| 402 if (elt) |
| 403 ebitset_elt_remove (bset, j); |
| 404 } |
| 405 |
| 406 /* All the bits are zero. We could shrink the elts. |
| 407 For now just mark BSET as known to be zero. */ |
| 408 EBITSET_ZERO_SET (bset); |
| 409 } |
| 410 |
| 411 |
| 412 static inline bool |
| 413 ebitset_equal_p (bitset dst, bitset src) |
| 414 { |
| 415 ebitset_elts *selts; |
| 416 ebitset_elts *delts; |
| 417 bitset_windex j; |
| 418 |
| 419 if (src == dst) |
| 420 return true; |
| 421 |
| 422 ebitset_weed (dst); |
| 423 ebitset_weed (src); |
| 424 |
| 425 if (EBITSET_SIZE (src) != EBITSET_SIZE (dst)) |
| 426 return false; |
| 427 |
| 428 selts = EBITSET_ELTS (src); |
| 429 delts = EBITSET_ELTS (dst); |
| 430 |
| 431 for (j = 0; j < EBITSET_SIZE (src); j++) |
| 432 { |
| 433 unsigned int i; |
| 434 ebitset_elt *selt = selts[j]; |
| 435 ebitset_elt *delt = delts[j]; |
| 436 |
| 437 if (!selt && !delt) |
| 438 continue; |
| 439 if ((selt && !delt) || (!selt && delt)) |
| 440 return false; |
| 441 |
| 442 for (i = 0; i < EBITSET_ELT_WORDS; i++) |
| 443 if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i]) |
| 444 return false; |
| 445 } |
| 446 return true; |
| 447 } |
| 448 |
| 449 |
| 450 /* Copy bits from bitset SRC to bitset DST. */ |
| 451 static inline void |
| 452 ebitset_copy_ (bitset dst, bitset src) |
| 453 { |
| 454 ebitset_elts *selts; |
| 455 ebitset_elts *delts; |
| 456 bitset_windex j; |
| 457 |
| 458 if (src == dst) |
| 459 return; |
| 460 |
| 461 ebitset_zero (dst); |
| 462 |
| 463 if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src)) |
| 464 ebitset_resize (dst, BITSET_NBITS_ (src)); |
| 465 |
| 466 selts = EBITSET_ELTS (src); |
| 467 delts = EBITSET_ELTS (dst); |
| 468 for (j = 0; j < EBITSET_SIZE (src); j++) |
| 469 { |
| 470 ebitset_elt *selt = selts[j]; |
| 471 |
| 472 if (selt) |
| 473 { |
| 474 ebitset_elt *tmp; |
| 475 |
| 476 tmp = ebitset_elt_alloc (); |
| 477 delts[j] = tmp; |
| 478 memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt), |
| 479 sizeof (EBITSET_WORDS (selt))); |
| 480 } |
| 481 } |
| 482 EBITSET_NONZERO_SET (dst); |
| 483 } |
| 484 |
| 485 |
| 486 /* Copy bits from bitset SRC to bitset DST. Return true if |
| 487 bitsets different. */ |
| 488 static inline bool |
| 489 ebitset_copy_cmp (bitset dst, bitset src) |
| 490 { |
| 491 if (src == dst) |
| 492 return false; |
| 493 |
| 494 if (EBITSET_ZERO_P (dst)) |
| 495 { |
| 496 ebitset_copy_ (dst, src); |
| 497 return !EBITSET_ZERO_P (src); |
| 498 } |
| 499 |
| 500 if (ebitset_equal_p (dst, src)) |
| 501 return false; |
| 502 |
| 503 ebitset_copy_ (dst, src); |
| 504 return true; |
| 505 } |
| 506 |
| 507 |
| 508 /* Set bit BITNO in bitset DST. */ |
| 509 static void |
| 510 ebitset_set (bitset dst, bitset_bindex bitno) |
| 511 { |
| 512 bitset_windex windex = bitno / BITSET_WORD_BITS; |
| 513 |
| 514 ebitset_elt_find (dst, bitno, EBITSET_CREATE); |
| 515 |
| 516 dst->b.cdata[windex - dst->b.cindex] |= |
| 517 (bitset_word) 1 << (bitno % BITSET_WORD_BITS); |
| 518 } |
| 519 |
| 520 |
| 521 /* Reset bit BITNO in bitset DST. */ |
| 522 static void |
| 523 ebitset_reset (bitset dst, bitset_bindex bitno) |
| 524 { |
| 525 bitset_windex windex = bitno / BITSET_WORD_BITS; |
| 526 |
| 527 if (!ebitset_elt_find (dst, bitno, EBITSET_FIND)) |
| 528 return; |
| 529 |
| 530 dst->b.cdata[windex - dst->b.cindex] &= |
| 531 ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS)); |
| 532 |
| 533 /* If all the data is zero, perhaps we should remove it now... |
| 534 However, there is a good chance that the element will be needed |
| 535 again soon. */ |
| 536 } |
| 537 |
| 538 |
| 539 /* Test bit BITNO in bitset SRC. */ |
| 540 static bool |
| 541 ebitset_test (bitset src, bitset_bindex bitno) |
| 542 { |
| 543 bitset_windex windex = bitno / BITSET_WORD_BITS; |
| 544 |
| 545 return (ebitset_elt_find (src, bitno, EBITSET_FIND) |
| 546 && ((src->b.cdata[windex - src->b.cindex] |
| 547 >> (bitno % BITSET_WORD_BITS)) |
| 548 & 1)); |
| 549 } |
| 550 |
| 551 |
| 552 static void |
| 553 ebitset_free (bitset bset) |
| 554 { |
| 555 ebitset_zero (bset); |
| 556 free (EBITSET_ELTS (bset)); |
| 557 } |
| 558 |
| 559 |
| 560 /* Find list of up to NUM bits set in BSET starting from and including |
| 561 *NEXT and store in array LIST. Return with actual number of bits |
| 562 found and with *NEXT indicating where search stopped. */ |
| 563 static bitset_bindex |
| 564 ebitset_list_reverse (bitset bset, bitset_bindex *list, |
| 565 bitset_bindex num, bitset_bindex *next) |
| 566 { |
| 567 bitset_bindex n_bits; |
| 568 bitset_bindex bitno; |
| 569 bitset_bindex rbitno; |
| 570 unsigned int bcount; |
| 571 bitset_bindex boffset; |
| 572 bitset_windex windex; |
| 573 bitset_windex eindex; |
| 574 bitset_windex woffset; |
| 575 bitset_bindex count; |
| 576 bitset_windex size; |
| 577 ebitset_elts *elts; |
| 578 |
| 579 if (EBITSET_ZERO_P (bset)) |
| 580 return 0; |
| 581 |
| 582 size = EBITSET_SIZE (bset); |
| 583 n_bits = size * EBITSET_ELT_BITS; |
| 584 rbitno = *next; |
| 585 |
| 586 if (rbitno >= n_bits) |
| 587 return 0; |
| 588 |
| 589 elts = EBITSET_ELTS (bset); |
| 590 |
| 591 bitno = n_bits - (rbitno + 1); |
| 592 |
| 593 windex = bitno / BITSET_WORD_BITS; |
| 594 eindex = bitno / EBITSET_ELT_BITS; |
| 595 woffset = windex - eindex * EBITSET_ELT_WORDS; |
| 596 |
| 597 /* If num is 1, we could speed things up with a binary search |
| 598 of the word of interest. */ |
| 599 |
| 600 count = 0; |
| 601 bcount = bitno % BITSET_WORD_BITS; |
| 602 boffset = windex * BITSET_WORD_BITS; |
| 603 |
| 604 do |
| 605 { |
| 606 ebitset_elt *elt; |
| 607 bitset_word *srcp; |
| 608 |
| 609 elt = elts[eindex]; |
| 610 if (elt) |
| 611 { |
| 612 srcp = EBITSET_WORDS (elt); |
| 613 |
| 614 do |
| 615 { |
| 616 bitset_word word; |
| 617 |
| 618 word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount); |
| 619 |
| 620 for (; word; bcount--) |
| 621 { |
| 622 if (word & BITSET_MSB) |
| 623 { |
| 624 list[count++] = boffset + bcount; |
| 625 if (count >= num) |
| 626 { |
| 627 *next = n_bits - (boffset + bcount); |
| 628 return count; |
| 629 } |
| 630 } |
| 631 word <<= 1; |
| 632 } |
| 633 boffset -= BITSET_WORD_BITS; |
| 634 bcount = BITSET_WORD_BITS - 1; |
| 635 } |
| 636 while (woffset--); |
| 637 } |
| 638 |
| 639 woffset = EBITSET_ELT_WORDS - 1; |
| 640 boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS; |
| 641 } |
| 642 while (eindex--); |
| 643 |
| 644 *next = n_bits - (boffset + 1); |
| 645 return count; |
| 646 } |
| 647 |
| 648 |
| 649 /* Find list of up to NUM bits set in BSET starting from and including |
| 650 *NEXT and store in array LIST. Return with actual number of bits |
| 651 found and with *NEXT indicating where search stopped. */ |
| 652 static bitset_bindex |
| 653 ebitset_list (bitset bset, bitset_bindex *list, |
| 654 bitset_bindex num, bitset_bindex *next) |
| 655 { |
| 656 bitset_bindex bitno; |
| 657 bitset_windex windex; |
| 658 bitset_windex eindex; |
| 659 bitset_bindex count; |
| 660 bitset_windex size; |
| 661 ebitset_elt *elt; |
| 662 bitset_word word; |
| 663 ebitset_elts *elts; |
| 664 |
| 665 if (EBITSET_ZERO_P (bset)) |
| 666 return 0; |
| 667 |
| 668 bitno = *next; |
| 669 count = 0; |
| 670 |
| 671 elts = EBITSET_ELTS (bset); |
| 672 size = EBITSET_SIZE (bset); |
| 673 eindex = bitno / EBITSET_ELT_BITS; |
| 674 |
| 675 if (bitno % EBITSET_ELT_BITS) |
| 676 { |
| 677 /* We need to start within an element. This is not very common. */ |
| 678 |
| 679 elt = elts[eindex]; |
| 680 if (elt) |
| 681 { |
| 682 bitset_windex woffset; |
| 683 bitset_word *srcp = EBITSET_WORDS (elt); |
| 684 |
| 685 windex = bitno / BITSET_WORD_BITS; |
| 686 woffset = eindex * EBITSET_ELT_WORDS; |
| 687 |
| 688 for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++) |
| 689 { |
| 690 word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS); |
| 691 |
| 692 for (; word; bitno++) |
| 693 { |
| 694 if (word & 1) |
| 695 { |
| 696 list[count++] = bitno; |
| 697 if (count >= num) |
| 698 { |
| 699 *next = bitno + 1; |
| 700 return count; |
| 701 } |
| 702 } |
| 703 word >>= 1; |
| 704 } |
| 705 bitno = (windex + 1) * BITSET_WORD_BITS; |
| 706 } |
| 707 } |
| 708 |
| 709 /* Skip to next element. */ |
| 710 eindex++; |
| 711 } |
| 712 |
| 713 /* If num is 1, we could speed things up with a binary search |
| 714 of the word of interest. */ |
| 715 |
| 716 for (; eindex < size; eindex++) |
| 717 { |
| 718 int i; |
| 719 bitset_word *srcp; |
| 720 |
| 721 elt = elts[eindex]; |
| 722 if (!elt) |
| 723 continue; |
| 724 |
| 725 srcp = EBITSET_WORDS (elt); |
| 726 windex = eindex * EBITSET_ELT_WORDS; |
| 727 |
| 728 if ((count + EBITSET_ELT_BITS) < num) |
| 729 { |
| 730 /* The coast is clear, plant boot! */ |
| 731 |
| 732 #if EBITSET_ELT_WORDS == 2 |
| 733 word = srcp[0]; |
| 734 if (word) |
| 735 { |
| 736 if (!(word & 0xffff)) |
| 737 { |
| 738 word >>= 16; |
| 739 bitno += 16; |
| 740 } |
| 741 if (!(word & 0xff)) |
| 742 { |
| 743 word >>= 8; |
| 744 bitno += 8; |
| 745 } |
| 746 for (; word; bitno++) |
| 747 { |
| 748 if (word & 1) |
| 749 list[count++] = bitno; |
| 750 word >>= 1; |
| 751 } |
| 752 } |
| 753 windex++; |
| 754 bitno = windex * BITSET_WORD_BITS; |
| 755 |
| 756 word = srcp[1]; |
| 757 if (word) |
| 758 { |
| 759 if (!(word & 0xffff)) |
| 760 { |
| 761 word >>= 16; |
| 762 bitno += 16; |
| 763 } |
| 764 for (; word; bitno++) |
| 765 { |
| 766 if (word & 1) |
| 767 list[count++] = bitno; |
| 768 word >>= 1; |
| 769 } |
| 770 } |
| 771 windex++; |
| 772 bitno = windex * BITSET_WORD_BITS; |
| 773 #else |
| 774 for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++) |
| 775 { |
| 776 bitno = windex * BITSET_WORD_BITS; |
| 777 |
| 778 word = srcp[i]; |
| 779 if (word) |
| 780 { |
| 781 if (!(word & 0xffff)) |
| 782 { |
| 783 word >>= 16; |
| 784 bitno += 16; |
| 785 } |
| 786 if (!(word & 0xff)) |
| 787 { |
| 788 word >>= 8; |
| 789 bitno += 8; |
| 790 } |
| 791 for (; word; bitno++) |
| 792 { |
| 793 if (word & 1) |
| 794 list[count++] = bitno; |
| 795 word >>= 1; |
| 796 } |
| 797 } |
| 798 } |
| 799 #endif |
| 800 } |
| 801 else |
| 802 { |
| 803 /* Tread more carefully since we need to check |
| 804 if array overflows. */ |
| 805 |
| 806 for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++) |
| 807 { |
| 808 bitno = windex * BITSET_WORD_BITS; |
| 809 |
| 810 for (word = srcp[i]; word; bitno++) |
| 811 { |
| 812 if (word & 1) |
| 813 { |
| 814 list[count++] = bitno; |
| 815 if (count >= num) |
| 816 { |
| 817 *next = bitno + 1; |
| 818 return count; |
| 819 } |
| 820 } |
| 821 word >>= 1; |
| 822 } |
| 823 } |
| 824 } |
| 825 } |
| 826 |
| 827 *next = bitno; |
| 828 return count; |
| 829 } |
| 830 |
| 831 |
| 832 /* Ensure that any unused bits within the last element are clear. */ |
| 833 static inline void |
| 834 ebitset_unused_clear (bitset dst) |
| 835 { |
| 836 unsigned int last_bit; |
| 837 bitset_bindex n_bits; |
| 838 |
| 839 n_bits = BITSET_NBITS_ (dst); |
| 840 last_bit = n_bits % EBITSET_ELT_BITS; |
| 841 |
| 842 if (last_bit) |
| 843 { |
| 844 bitset_windex eindex; |
| 845 ebitset_elts *elts; |
| 846 ebitset_elt *elt; |
| 847 |
| 848 elts = EBITSET_ELTS (dst); |
| 849 |
| 850 eindex = n_bits / EBITSET_ELT_BITS; |
| 851 |
| 852 elt = elts[eindex]; |
| 853 if (elt) |
| 854 { |
| 855 bitset_windex windex; |
| 856 bitset_windex woffset; |
| 857 bitset_word *srcp = EBITSET_WORDS (elt); |
| 858 |
| 859 windex = n_bits / BITSET_WORD_BITS; |
| 860 woffset = eindex * EBITSET_ELT_WORDS; |
| 861 |
| 862 srcp[windex - woffset] &= ((bitset_word) 1 << last_bit) - 1; |
| 863 windex++; |
| 864 for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++) |
| 865 srcp[windex - woffset] = 0; |
| 866 } |
| 867 } |
| 868 } |
| 869 |
| 870 |
| 871 static void |
| 872 ebitset_ones (bitset dst) |
| 873 { |
| 874 bitset_windex j; |
| 875 ebitset_elt *elt; |
| 876 |
| 877 for (j = 0; j < EBITSET_SIZE (dst); j++) |
| 878 { |
| 879 /* Create new elements if they cannot be found. Perhaps |
| 880 we should just add pointers to a ones element? */ |
| 881 elt = |
| 882 ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE); |
| 883 memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt))); |
| 884 } |
| 885 EBITSET_NONZERO_SET (dst); |
| 886 ebitset_unused_clear (dst); |
| 887 } |
| 888 |
| 889 |
| 890 static bool |
| 891 ebitset_empty_p (bitset dst) |
| 892 { |
| 893 ebitset_elts *elts; |
| 894 bitset_windex j; |
| 895 |
| 896 if (EBITSET_ZERO_P (dst)) |
| 897 return 1; |
| 898 |
| 899 elts = EBITSET_ELTS (dst); |
| 900 for (j = 0; j < EBITSET_SIZE (dst); j++) |
| 901 { |
| 902 ebitset_elt *elt = elts[j]; |
| 903 |
| 904 if (elt) |
| 905 { |
| 906 if (!ebitset_elt_zero_p (elt)) |
| 907 return 0; |
| 908 /* Do some weeding as we go. */ |
| 909 ebitset_elt_remove (dst, j); |
| 910 } |
| 911 } |
| 912 |
| 913 /* All the bits are zero. We could shrink the elts. |
| 914 For now just mark DST as known to be zero. */ |
| 915 EBITSET_ZERO_SET (dst); |
| 916 return 1; |
| 917 } |
| 918 |
| 919 |
| 920 static void |
| 921 ebitset_not (bitset dst, bitset src) |
| 922 { |
| 923 unsigned int i; |
| 924 ebitset_elt *selt; |
| 925 ebitset_elt *delt; |
| 926 bitset_windex j; |
| 927 |
| 928 ebitset_resize (dst, BITSET_NBITS_ (src)); |
| 929 |
| 930 for (j = 0; j < EBITSET_SIZE (src); j++) |
| 931 { |
| 932 /* Create new elements for dst if they cannot be found |
| 933 or substitute zero elements if src elements not found. */ |
| 934 selt = |
| 935 ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_SUBST); |
| 936 delt = |
| 937 ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE); |
| 938 |
| 939 for (i = 0; i < EBITSET_ELT_WORDS; i++) |
| 940 EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i]; |
| 941 } |
| 942 EBITSET_NONZERO_SET (dst); |
| 943 ebitset_unused_clear (dst); |
| 944 } |
| 945 |
| 946 |
| 947 /* Is DST == DST | SRC? */ |
| 948 static bool |
| 949 ebitset_subset_p (bitset dst, bitset src) |
| 950 { |
| 951 bitset_windex j; |
| 952 ebitset_elts *selts; |
| 953 ebitset_elts *delts; |
| 954 bitset_windex ssize; |
| 955 bitset_windex dsize; |
| 956 |
| 957 selts = EBITSET_ELTS (src); |
| 958 delts = EBITSET_ELTS (dst); |
| 959 |
| 960 ssize = EBITSET_SIZE (src); |
| 961 dsize = EBITSET_SIZE (dst); |
| 962 |
| 963 for (j = 0; j < ssize; j++) |
| 964 { |
| 965 unsigned int i; |
| 966 ebitset_elt *selt; |
| 967 ebitset_elt *delt; |
| 968 |
| 969 selt = j < ssize ? selts[j] : 0; |
| 970 delt = j < dsize ? delts[j] : 0; |
| 971 |
| 972 if (!selt && !delt) |
| 973 continue; |
| 974 |
| 975 if (!selt) |
| 976 selt = &ebitset_zero_elts[0]; |
| 977 if (!delt) |
| 978 delt = &ebitset_zero_elts[0]; |
| 979 |
| 980 for (i = 0; i < EBITSET_ELT_WORDS; i++) |
| 981 if (EBITSET_WORDS (delt)[i] |
| 982 != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i])) |
| 983 return false; |
| 984 } |
| 985 return true; |
| 986 } |
| 987 |
| 988 |
| 989 /* Is DST & SRC == 0? */ |
| 990 static bool |
| 991 ebitset_disjoint_p (bitset dst, bitset src) |
| 992 { |
| 993 bitset_windex j; |
| 994 ebitset_elts *selts; |
| 995 ebitset_elts *delts; |
| 996 bitset_windex ssize; |
| 997 bitset_windex dsize; |
| 998 |
| 999 selts = EBITSET_ELTS (src); |
| 1000 delts = EBITSET_ELTS (dst); |
| 1001 |
| 1002 ssize = EBITSET_SIZE (src); |
| 1003 dsize = EBITSET_SIZE (dst); |
| 1004 |
| 1005 for (j = 0; j < ssize; j++) |
| 1006 { |
| 1007 unsigned int i; |
| 1008 ebitset_elt *selt; |
| 1009 ebitset_elt *delt; |
| 1010 |
| 1011 selt = j < ssize ? selts[j] : 0; |
| 1012 delt = j < dsize ? delts[j] : 0; |
| 1013 |
| 1014 if (!selt || !delt) |
| 1015 continue; |
| 1016 |
| 1017 for (i = 0; i < EBITSET_ELT_WORDS; i++) |
| 1018 if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i])) |
| 1019 return false; |
| 1020 } |
| 1021 return true; |
| 1022 } |
| 1023 |
| 1024 |
| 1025 |
| 1026 static bool |
| 1027 ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) |
| 1028 { |
| 1029 bitset_windex ssize1; |
| 1030 bitset_windex ssize2; |
| 1031 bitset_windex dsize; |
| 1032 bitset_windex size; |
| 1033 ebitset_elts *selts1; |
| 1034 ebitset_elts *selts2; |
| 1035 ebitset_elts *delts; |
| 1036 bitset_word *srcp1; |
| 1037 bitset_word *srcp2; |
| 1038 bitset_word *dstp; |
| 1039 bool changed = false; |
| 1040 unsigned int i; |
| 1041 bitset_windex j; |
| 1042 |
| 1043 ebitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2))); |
| 1044 |
| 1045 ssize1 = EBITSET_SIZE (src1); |
| 1046 ssize2 = EBITSET_SIZE (src2); |
| 1047 dsize = EBITSET_SIZE (dst); |
| 1048 size = ssize1; |
| 1049 if (size < ssize2) |
| 1050 size = ssize2; |
| 1051 |
| 1052 selts1 = EBITSET_ELTS (src1); |
| 1053 selts2 = EBITSET_ELTS (src2); |
| 1054 delts = EBITSET_ELTS (dst); |
| 1055 |
| 1056 for (j = 0; j < size; j++) |
| 1057 { |
| 1058 ebitset_elt *selt1; |
| 1059 ebitset_elt *selt2; |
| 1060 ebitset_elt *delt; |
| 1061 |
| 1062 selt1 = j < ssize1 ? selts1[j] : 0; |
| 1063 selt2 = j < ssize2 ? selts2[j] : 0; |
| 1064 delt = j < dsize ? delts[j] : 0; |
| 1065 |
| 1066 if (!selt1 && !selt2) |
| 1067 { |
| 1068 if (delt) |
| 1069 { |
| 1070 changed = true; |
| 1071 ebitset_elt_remove (dst, j); |
| 1072 } |
| 1073 continue; |
| 1074 } |
| 1075 |
| 1076 if (!selt1) |
| 1077 selt1 = &ebitset_zero_elts[0]; |
| 1078 if (!selt2) |
| 1079 selt2 = &ebitset_zero_elts[0]; |
| 1080 if (!delt) |
| 1081 delt = ebitset_elt_calloc (); |
| 1082 else |
| 1083 delts[j] = 0; |
| 1084 |
| 1085 srcp1 = EBITSET_WORDS (selt1); |
| 1086 srcp2 = EBITSET_WORDS (selt2); |
| 1087 dstp = EBITSET_WORDS (delt); |
| 1088 switch (op) |
| 1089 { |
| 1090 default: |
| 1091 abort (); |
| 1092 |
| 1093 case BITSET_OP_OR: |
| 1094 for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) |
| 1095 { |
| 1096 bitset_word tmp = *srcp1++ | *srcp2++; |
| 1097 |
| 1098 if (*dstp != tmp) |
| 1099 { |
| 1100 changed = true; |
| 1101 *dstp = tmp; |
| 1102 } |
| 1103 } |
| 1104 break; |
| 1105 |
| 1106 case BITSET_OP_AND: |
| 1107 for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) |
| 1108 { |
| 1109 bitset_word tmp = *srcp1++ & *srcp2++; |
| 1110 |
| 1111 if (*dstp != tmp) |
| 1112 { |
| 1113 changed = true; |
| 1114 *dstp = tmp; |
| 1115 } |
| 1116 } |
| 1117 break; |
| 1118 |
| 1119 case BITSET_OP_XOR: |
| 1120 for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) |
| 1121 { |
| 1122 bitset_word tmp = *srcp1++ ^ *srcp2++; |
| 1123 |
| 1124 if (*dstp != tmp) |
| 1125 { |
| 1126 changed = true; |
| 1127 *dstp = tmp; |
| 1128 } |
| 1129 } |
| 1130 break; |
| 1131 |
| 1132 case BITSET_OP_ANDN: |
| 1133 for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) |
| 1134 { |
| 1135 bitset_word tmp = *srcp1++ & ~(*srcp2++); |
| 1136 |
| 1137 if (*dstp != tmp) |
| 1138 { |
| 1139 changed = true; |
| 1140 *dstp = tmp; |
| 1141 } |
| 1142 } |
| 1143 break; |
| 1144 } |
| 1145 |
| 1146 if (!ebitset_elt_zero_p (delt)) |
| 1147 { |
| 1148 ebitset_elt_add (dst, delt, j); |
| 1149 } |
| 1150 else |
| 1151 { |
| 1152 ebitset_elt_free (delt); |
| 1153 } |
| 1154 } |
| 1155 |
| 1156 /* If we have elements of DST left over, free them all. */ |
| 1157 for (; j < dsize; j++) |
| 1158 { |
| 1159 ebitset_elt *delt; |
| 1160 |
| 1161 changed = true; |
| 1162 |
| 1163 delt = delts[j]; |
| 1164 |
| 1165 if (delt) |
| 1166 ebitset_elt_remove (dst, j); |
| 1167 } |
| 1168 |
| 1169 EBITSET_NONZERO_SET (dst); |
| 1170 return changed; |
| 1171 } |
| 1172 |
| 1173 |
| 1174 static bool |
| 1175 ebitset_and_cmp (bitset dst, bitset src1, bitset src2) |
| 1176 { |
| 1177 bool changed; |
| 1178 |
| 1179 if (EBITSET_ZERO_P (src2)) |
| 1180 { |
| 1181 ebitset_weed (dst); |
| 1182 changed = EBITSET_ZERO_P (dst); |
| 1183 ebitset_zero (dst); |
| 1184 return changed; |
| 1185 } |
| 1186 else if (EBITSET_ZERO_P (src1)) |
| 1187 { |
| 1188 ebitset_weed (dst); |
| 1189 changed = EBITSET_ZERO_P (dst); |
| 1190 ebitset_zero (dst); |
| 1191 return changed; |
| 1192 } |
| 1193 return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_AND); |
| 1194 } |
| 1195 |
| 1196 |
| 1197 static void |
| 1198 ebitset_and (bitset dst, bitset src1, bitset src2) |
| 1199 { |
| 1200 ebitset_and_cmp (dst, src1, src2); |
| 1201 } |
| 1202 |
| 1203 |
| 1204 static bool |
| 1205 ebitset_andn_cmp (bitset dst, bitset src1, bitset src2) |
| 1206 { |
| 1207 bool changed; |
| 1208 |
| 1209 if (EBITSET_ZERO_P (src2)) |
| 1210 { |
| 1211 return ebitset_copy_cmp (dst, src1); |
| 1212 } |
| 1213 else if (EBITSET_ZERO_P (src1)) |
| 1214 { |
| 1215 ebitset_weed (dst); |
| 1216 changed = EBITSET_ZERO_P (dst); |
| 1217 ebitset_zero (dst); |
| 1218 return changed; |
| 1219 } |
| 1220 return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN); |
| 1221 } |
| 1222 |
| 1223 |
| 1224 static void |
| 1225 ebitset_andn (bitset dst, bitset src1, bitset src2) |
| 1226 { |
| 1227 ebitset_andn_cmp (dst, src1, src2); |
| 1228 } |
| 1229 |
| 1230 |
| 1231 static bool |
| 1232 ebitset_or_cmp (bitset dst, bitset src1, bitset src2) |
| 1233 { |
| 1234 if (EBITSET_ZERO_P (src2)) |
| 1235 { |
| 1236 return ebitset_copy_cmp (dst, src1); |
| 1237 } |
| 1238 else if (EBITSET_ZERO_P (src1)) |
| 1239 { |
| 1240 return ebitset_copy_cmp (dst, src2); |
| 1241 } |
| 1242 return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_OR); |
| 1243 } |
| 1244 |
| 1245 |
| 1246 static void |
| 1247 ebitset_or (bitset dst, bitset src1, bitset src2) |
| 1248 { |
| 1249 ebitset_or_cmp (dst, src1, src2); |
| 1250 } |
| 1251 |
| 1252 |
| 1253 static bool |
| 1254 ebitset_xor_cmp (bitset dst, bitset src1, bitset src2) |
| 1255 { |
| 1256 if (EBITSET_ZERO_P (src2)) |
| 1257 { |
| 1258 return ebitset_copy_cmp (dst, src1); |
| 1259 } |
| 1260 else if (EBITSET_ZERO_P (src1)) |
| 1261 { |
| 1262 return ebitset_copy_cmp (dst, src2); |
| 1263 } |
| 1264 return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR); |
| 1265 } |
| 1266 |
| 1267 |
| 1268 static void |
| 1269 ebitset_xor (bitset dst, bitset src1, bitset src2) |
| 1270 { |
| 1271 ebitset_xor_cmp (dst, src1, src2); |
| 1272 } |
| 1273 |
| 1274 |
| 1275 static void |
| 1276 ebitset_copy (bitset dst, bitset src) |
| 1277 { |
| 1278 if (BITSET_COMPATIBLE_ (dst, src)) |
| 1279 ebitset_copy_ (dst, src); |
| 1280 else |
| 1281 bitset_copy_ (dst, src); |
| 1282 } |
| 1283 |
| 1284 |
| 1285 /* Vector of operations for linked-list bitsets. */ |
| 1286 struct bitset_vtable ebitset_vtable = { |
| 1287 ebitset_set, |
| 1288 ebitset_reset, |
| 1289 bitset_toggle_, |
| 1290 ebitset_test, |
| 1291 ebitset_resize, |
| 1292 bitset_size_, |
| 1293 bitset_count_, |
| 1294 ebitset_empty_p, |
| 1295 ebitset_ones, |
| 1296 ebitset_zero, |
| 1297 ebitset_copy, |
| 1298 ebitset_disjoint_p, |
| 1299 ebitset_equal_p, |
| 1300 ebitset_not, |
| 1301 ebitset_subset_p, |
| 1302 ebitset_and, |
| 1303 ebitset_and_cmp, |
| 1304 ebitset_andn, |
| 1305 ebitset_andn_cmp, |
| 1306 ebitset_or, |
| 1307 ebitset_or_cmp, |
| 1308 ebitset_xor, |
| 1309 ebitset_xor_cmp, |
| 1310 bitset_and_or_, |
| 1311 bitset_and_or_cmp_, |
| 1312 bitset_andn_or_, |
| 1313 bitset_andn_or_cmp_, |
| 1314 bitset_or_and_, |
| 1315 bitset_or_and_cmp_, |
| 1316 ebitset_list, |
| 1317 ebitset_list_reverse, |
| 1318 ebitset_free, |
| 1319 BITSET_TABLE |
| 1320 }; |
| 1321 |
| 1322 |
| 1323 /* Return size of initial structure. */ |
| 1324 size_t |
| 1325 ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED) |
| 1326 { |
| 1327 return sizeof (struct ebitset_struct); |
| 1328 } |
| 1329 |
| 1330 |
| 1331 /* Initialize a bitset. */ |
| 1332 |
| 1333 bitset |
| 1334 ebitset_init (bitset bset, bitset_bindex n_bits) |
| 1335 { |
| 1336 bitset_windex size; |
| 1337 |
| 1338 bset->b.vtable = &ebitset_vtable; |
| 1339 |
| 1340 bset->b.csize = EBITSET_ELT_WORDS; |
| 1341 |
| 1342 EBITSET_ZERO_SET (bset); |
| 1343 |
| 1344 size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS |
| 1345 : EBITSET_INITIAL_SIZE; |
| 1346 |
| 1347 EBITSET_ASIZE (bset) = 0; |
| 1348 EBITSET_ELTS (bset) = 0; |
| 1349 ebitset_resize (bset, n_bits); |
| 1350 |
| 1351 return bset; |
| 1352 } |
| 1353 |
| 1354 |
| 1355 void |
| 1356 ebitset_release_memory (void) |
| 1357 { |
| 1358 ebitset_free_list = 0; |
| 1359 if (ebitset_obstack_init) |
| 1360 { |
| 1361 ebitset_obstack_init = false; |
| 1362 obstack_free (&ebitset_obstack, NULL); |
| 1363 } |
| 1364 } |
OLD | NEW |