OLD | NEW |
(Empty) | |
| 1 /* Functions to support link list bitsets. |
| 2 Copyright (C) 2002, 2003, 2004, 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 "lbitset.h" |
| 21 |
| 22 #include "obstack.h" |
| 23 #include <stddef.h> |
| 24 #include <stdlib.h> |
| 25 #include <stdio.h> |
| 26 #include <string.h> |
| 27 |
| 28 /* This file implements linked-list bitsets. These bitsets can be of |
| 29 arbitrary length and are more efficient than arrays of bits for |
| 30 large sparse sets. |
| 31 |
| 32 Usually if all the bits in an element are zero we remove the element |
| 33 from the list. However, a side effect of the bit caching is that we |
| 34 do not always notice when an element becomes zero. Hence the |
| 35 lbitset_weed function which removes zero elements. */ |
| 36 |
| 37 |
| 38 /* Number of words to use for each element. The larger the value the |
| 39 greater the size of the cache and the shorter the time to find a given bit |
| 40 but the more memory wasted for sparse bitsets and the longer the time |
| 41 to search for set bits. |
| 42 |
| 43 The routines that dominate timing profiles are lbitset_elt_find |
| 44 and lbitset_elt_link, especially when accessing the bits randomly. */ |
| 45 |
| 46 #define LBITSET_ELT_WORDS 2 |
| 47 |
| 48 typedef bitset_word lbitset_word; |
| 49 |
| 50 #define LBITSET_WORD_BITS BITSET_WORD_BITS |
| 51 |
| 52 /* Number of bits stored in each element. */ |
| 53 #define LBITSET_ELT_BITS \ |
| 54 ((unsigned int) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS)) |
| 55 |
| 56 /* Lbitset element. We use an array of bits for each element. |
| 57 These are linked together in a doubly-linked list. */ |
| 58 typedef struct lbitset_elt_struct |
| 59 { |
| 60 struct lbitset_elt_struct *next; /* Next element. */ |
| 61 struct lbitset_elt_struct *prev; /* Previous element. */ |
| 62 bitset_windex index; /* bitno / BITSET_WORD_BITS. */ |
| 63 bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set. */ |
| 64 } |
| 65 lbitset_elt; |
| 66 |
| 67 |
| 68 enum lbitset_find_mode |
| 69 { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST }; |
| 70 |
| 71 static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits. */ |
| 72 |
| 73 /* Obstack to allocate bitset elements from. */ |
| 74 static struct obstack lbitset_obstack; |
| 75 static bool lbitset_obstack_init = false; |
| 76 static lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */ |
| 77 |
| 78 extern void debug_lbitset (bitset); |
| 79 |
| 80 #define LBITSET_CURRENT1(X) \ |
| 81 ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words))) |
| 82 |
| 83 #define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata) |
| 84 |
| 85 #define LBITSET_HEAD(X) ((X)->l.head) |
| 86 #define LBITSET_TAIL(X) ((X)->l.tail) |
| 87 |
| 88 /* Allocate a lbitset element. The bits are not cleared. */ |
| 89 static inline lbitset_elt * |
| 90 lbitset_elt_alloc (void) |
| 91 { |
| 92 lbitset_elt *elt; |
| 93 |
| 94 if (lbitset_free_list != 0) |
| 95 { |
| 96 elt = lbitset_free_list; |
| 97 lbitset_free_list = elt->next; |
| 98 } |
| 99 else |
| 100 { |
| 101 if (!lbitset_obstack_init) |
| 102 { |
| 103 lbitset_obstack_init = true; |
| 104 |
| 105 /* Let particular systems override the size of a chunk. */ |
| 106 |
| 107 #ifndef OBSTACK_CHUNK_SIZE |
| 108 #define OBSTACK_CHUNK_SIZE 0 |
| 109 #endif |
| 110 |
| 111 /* Let them override the alloc and free routines too. */ |
| 112 |
| 113 #ifndef OBSTACK_CHUNK_ALLOC |
| 114 #define OBSTACK_CHUNK_ALLOC xmalloc |
| 115 #endif |
| 116 |
| 117 #ifndef OBSTACK_CHUNK_FREE |
| 118 #define OBSTACK_CHUNK_FREE free |
| 119 #endif |
| 120 |
| 121 #if ! defined __GNUC__ || __GNUC__ < 2 |
| 122 #define __alignof__(type) 0 |
| 123 #endif |
| 124 |
| 125 obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE, |
| 126 __alignof__ (lbitset_elt), |
| 127 OBSTACK_CHUNK_ALLOC, |
| 128 OBSTACK_CHUNK_FREE); |
| 129 } |
| 130 |
| 131 /* Perhaps we should add a number of new elements to the free |
| 132 list. */ |
| 133 elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack, |
| 134 sizeof (lbitset_elt)); |
| 135 } |
| 136 |
| 137 return elt; |
| 138 } |
| 139 |
| 140 |
| 141 /* Allocate a lbitset element. The bits are cleared. */ |
| 142 static inline lbitset_elt * |
| 143 lbitset_elt_calloc (void) |
| 144 { |
| 145 lbitset_elt *elt; |
| 146 |
| 147 elt = lbitset_elt_alloc (); |
| 148 memset (elt->words, 0, sizeof (elt->words)); |
| 149 return elt; |
| 150 } |
| 151 |
| 152 |
| 153 static inline void |
| 154 lbitset_elt_free (lbitset_elt *elt) |
| 155 { |
| 156 elt->next = lbitset_free_list; |
| 157 lbitset_free_list = elt; |
| 158 } |
| 159 |
| 160 |
| 161 /* Unlink element ELT from bitset BSET. */ |
| 162 static inline void |
| 163 lbitset_elt_unlink (bitset bset, lbitset_elt *elt) |
| 164 { |
| 165 lbitset_elt *next = elt->next; |
| 166 lbitset_elt *prev = elt->prev; |
| 167 |
| 168 if (prev) |
| 169 prev->next = next; |
| 170 |
| 171 if (next) |
| 172 next->prev = prev; |
| 173 |
| 174 if (LBITSET_HEAD (bset) == elt) |
| 175 LBITSET_HEAD (bset) = next; |
| 176 if (LBITSET_TAIL (bset) == elt) |
| 177 LBITSET_TAIL (bset) = prev; |
| 178 |
| 179 /* Update cache pointer. Since the first thing we try is to insert |
| 180 before current, make current the next entry in preference to the |
| 181 previous. */ |
| 182 if (LBITSET_CURRENT (bset) == elt) |
| 183 { |
| 184 if (next) |
| 185 { |
| 186 bset->b.cdata = next->words; |
| 187 bset->b.cindex = next->index; |
| 188 } |
| 189 else if (prev) |
| 190 { |
| 191 bset->b.cdata = prev->words; |
| 192 bset->b.cindex = prev->index; |
| 193 } |
| 194 else |
| 195 { |
| 196 bset->b.csize = 0; |
| 197 bset->b.cdata = 0; |
| 198 } |
| 199 } |
| 200 |
| 201 lbitset_elt_free (elt); |
| 202 } |
| 203 |
| 204 |
| 205 /* Cut the chain of bitset BSET before element ELT and free the |
| 206 elements. */ |
| 207 static inline void |
| 208 lbitset_prune (bitset bset, lbitset_elt *elt) |
| 209 { |
| 210 lbitset_elt *next; |
| 211 |
| 212 if (!elt) |
| 213 return; |
| 214 |
| 215 if (elt->prev) |
| 216 { |
| 217 LBITSET_TAIL (bset) = elt->prev; |
| 218 bset->b.cdata = elt->prev->words; |
| 219 bset->b.cindex = elt->prev->index; |
| 220 elt->prev->next = 0; |
| 221 } |
| 222 else |
| 223 { |
| 224 LBITSET_HEAD (bset) = 0; |
| 225 LBITSET_TAIL (bset) = 0; |
| 226 bset->b.cdata = 0; |
| 227 bset->b.csize = 0; |
| 228 } |
| 229 |
| 230 for (; elt; elt = next) |
| 231 { |
| 232 next = elt->next; |
| 233 lbitset_elt_free (elt); |
| 234 } |
| 235 } |
| 236 |
| 237 |
| 238 /* Are all bits in an element zero? */ |
| 239 static inline bool |
| 240 lbitset_elt_zero_p (lbitset_elt *elt) |
| 241 { |
| 242 int i; |
| 243 |
| 244 for (i = 0; i < LBITSET_ELT_WORDS; i++) |
| 245 if (elt->words[i]) |
| 246 return false; |
| 247 |
| 248 return true; |
| 249 } |
| 250 |
| 251 |
| 252 /* Link the bitset element into the current bitset linked list. */ |
| 253 static inline void |
| 254 lbitset_elt_link (bitset bset, lbitset_elt *elt) |
| 255 { |
| 256 bitset_windex windex = elt->index; |
| 257 lbitset_elt *ptr; |
| 258 lbitset_elt *current; |
| 259 |
| 260 if (bset->b.csize) |
| 261 current = LBITSET_CURRENT (bset); |
| 262 else |
| 263 current = LBITSET_HEAD (bset); |
| 264 |
| 265 /* If this is the first and only element, add it in. */ |
| 266 if (LBITSET_HEAD (bset) == 0) |
| 267 { |
| 268 elt->next = elt->prev = 0; |
| 269 LBITSET_HEAD (bset) = elt; |
| 270 LBITSET_TAIL (bset) = elt; |
| 271 } |
| 272 |
| 273 /* If this index is less than that of the current element, it goes |
| 274 somewhere before the current element. */ |
| 275 else if (windex < bset->b.cindex) |
| 276 { |
| 277 for (ptr = current; |
| 278 ptr->prev && ptr->prev->index > windex; ptr = ptr->prev) |
| 279 continue; |
| 280 |
| 281 if (ptr->prev) |
| 282 ptr->prev->next = elt; |
| 283 else |
| 284 LBITSET_HEAD (bset) = elt; |
| 285 |
| 286 elt->prev = ptr->prev; |
| 287 elt->next = ptr; |
| 288 ptr->prev = elt; |
| 289 } |
| 290 |
| 291 /* Otherwise, it must go somewhere after the current element. */ |
| 292 else |
| 293 { |
| 294 for (ptr = current; |
| 295 ptr->next && ptr->next->index < windex; ptr = ptr->next) |
| 296 continue; |
| 297 |
| 298 if (ptr->next) |
| 299 ptr->next->prev = elt; |
| 300 else |
| 301 LBITSET_TAIL (bset) = elt; |
| 302 |
| 303 elt->next = ptr->next; |
| 304 elt->prev = ptr; |
| 305 ptr->next = elt; |
| 306 } |
| 307 |
| 308 /* Set up so this is the first element searched. */ |
| 309 bset->b.cindex = windex; |
| 310 bset->b.csize = LBITSET_ELT_WORDS; |
| 311 bset->b.cdata = elt->words; |
| 312 } |
| 313 |
| 314 |
| 315 static lbitset_elt * |
| 316 lbitset_elt_find (bitset bset, bitset_windex windex, |
| 317 enum lbitset_find_mode mode) |
| 318 { |
| 319 lbitset_elt *elt; |
| 320 lbitset_elt *current; |
| 321 |
| 322 if (bset->b.csize) |
| 323 { |
| 324 current = LBITSET_CURRENT (bset); |
| 325 /* Check if element is the cached element. */ |
| 326 if ((windex - bset->b.cindex) < bset->b.csize) |
| 327 return current; |
| 328 } |
| 329 else |
| 330 { |
| 331 current = LBITSET_HEAD (bset); |
| 332 } |
| 333 |
| 334 if (current) |
| 335 { |
| 336 if (windex < bset->b.cindex) |
| 337 { |
| 338 for (elt = current; |
| 339 elt->prev && elt->index > windex; elt = elt->prev) |
| 340 continue; |
| 341 } |
| 342 else |
| 343 { |
| 344 for (elt = current; |
| 345 elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < windex; |
| 346 elt = elt->next) |
| 347 continue; |
| 348 } |
| 349 |
| 350 /* ELT is the nearest to the one we want. If it's not the one |
| 351 we want, the one we want does not exist. */ |
| 352 if (elt && (windex - elt->index) < LBITSET_ELT_WORDS) |
| 353 { |
| 354 bset->b.cindex = elt->index; |
| 355 bset->b.csize = LBITSET_ELT_WORDS; |
| 356 bset->b.cdata = elt->words; |
| 357 return elt; |
| 358 } |
| 359 } |
| 360 |
| 361 switch (mode) |
| 362 { |
| 363 default: |
| 364 abort (); |
| 365 |
| 366 case LBITSET_FIND: |
| 367 return 0; |
| 368 |
| 369 case LBITSET_CREATE: |
| 370 windex -= windex % LBITSET_ELT_WORDS; |
| 371 |
| 372 elt = lbitset_elt_calloc (); |
| 373 elt->index = windex; |
| 374 lbitset_elt_link (bset, elt); |
| 375 return elt; |
| 376 |
| 377 case LBITSET_SUBST: |
| 378 return &lbitset_zero_elts[0]; |
| 379 } |
| 380 } |
| 381 |
| 382 |
| 383 /* Weed out the zero elements from the list. */ |
| 384 static inline void |
| 385 lbitset_weed (bitset bset) |
| 386 { |
| 387 lbitset_elt *elt; |
| 388 lbitset_elt *next; |
| 389 |
| 390 for (elt = LBITSET_HEAD (bset); elt; elt = next) |
| 391 { |
| 392 next = elt->next; |
| 393 if (lbitset_elt_zero_p (elt)) |
| 394 lbitset_elt_unlink (bset, elt); |
| 395 } |
| 396 } |
| 397 |
| 398 |
| 399 /* Set all bits in the bitset to zero. */ |
| 400 static void |
| 401 lbitset_zero (bitset bset) |
| 402 { |
| 403 lbitset_elt *head; |
| 404 |
| 405 head = LBITSET_HEAD (bset); |
| 406 if (!head) |
| 407 return; |
| 408 |
| 409 /* Clear a bitset by freeing the linked list at the head element. */ |
| 410 lbitset_prune (bset, head); |
| 411 } |
| 412 |
| 413 |
| 414 /* Is DST == SRC? */ |
| 415 static inline bool |
| 416 lbitset_equal_p (bitset dst, bitset src) |
| 417 { |
| 418 lbitset_elt *selt; |
| 419 lbitset_elt *delt; |
| 420 int j; |
| 421 |
| 422 if (src == dst) |
| 423 return true; |
| 424 |
| 425 lbitset_weed (src); |
| 426 lbitset_weed (dst); |
| 427 for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); |
| 428 selt && delt; selt = selt->next, delt = delt->next) |
| 429 { |
| 430 if (selt->index != delt->index) |
| 431 return false; |
| 432 |
| 433 for (j = 0; j < LBITSET_ELT_WORDS; j++) |
| 434 if (delt->words[j] != selt->words[j]) |
| 435 return false; |
| 436 } |
| 437 return !selt && !delt; |
| 438 } |
| 439 |
| 440 |
| 441 /* Copy bits from bitset SRC to bitset DST. */ |
| 442 static inline void |
| 443 lbitset_copy (bitset dst, bitset src) |
| 444 { |
| 445 lbitset_elt *elt; |
| 446 lbitset_elt *head; |
| 447 lbitset_elt *prev; |
| 448 lbitset_elt *tmp; |
| 449 |
| 450 if (src == dst) |
| 451 return; |
| 452 |
| 453 lbitset_zero (dst); |
| 454 |
| 455 head = LBITSET_HEAD (src); |
| 456 if (!head) |
| 457 return; |
| 458 |
| 459 prev = 0; |
| 460 for (elt = head; elt; elt = elt->next) |
| 461 { |
| 462 tmp = lbitset_elt_alloc (); |
| 463 tmp->index = elt->index; |
| 464 tmp->prev = prev; |
| 465 tmp->next = 0; |
| 466 if (prev) |
| 467 prev->next = tmp; |
| 468 else |
| 469 LBITSET_HEAD (dst) = tmp; |
| 470 prev = tmp; |
| 471 |
| 472 memcpy (tmp->words, elt->words, sizeof (elt->words)); |
| 473 } |
| 474 LBITSET_TAIL (dst) = tmp; |
| 475 |
| 476 dst->b.csize = LBITSET_ELT_WORDS; |
| 477 dst->b.cdata = LBITSET_HEAD (dst)->words; |
| 478 dst->b.cindex = LBITSET_HEAD (dst)->index; |
| 479 } |
| 480 |
| 481 |
| 482 /* Copy bits from bitset SRC to bitset DST. Return true if |
| 483 bitsets different. */ |
| 484 static inline bool |
| 485 lbitset_copy_cmp (bitset dst, bitset src) |
| 486 { |
| 487 if (src == dst) |
| 488 return false; |
| 489 |
| 490 if (!LBITSET_HEAD (dst)) |
| 491 { |
| 492 lbitset_copy (dst, src); |
| 493 return LBITSET_HEAD (src) != 0; |
| 494 } |
| 495 |
| 496 if (lbitset_equal_p (dst, src)) |
| 497 return false; |
| 498 |
| 499 lbitset_copy (dst, src); |
| 500 return true; |
| 501 } |
| 502 |
| 503 |
| 504 static bitset_bindex |
| 505 lbitset_resize (bitset src, bitset_bindex size) |
| 506 { |
| 507 BITSET_NBITS_ (src) = size; |
| 508 |
| 509 /* Need to prune any excess bits. FIXME. */ |
| 510 return size; |
| 511 } |
| 512 |
| 513 /* Set bit BITNO in bitset DST. */ |
| 514 static void |
| 515 lbitset_set (bitset dst, bitset_bindex bitno) |
| 516 { |
| 517 bitset_windex windex = bitno / BITSET_WORD_BITS; |
| 518 |
| 519 lbitset_elt_find (dst, windex, LBITSET_CREATE); |
| 520 |
| 521 dst->b.cdata[windex - dst->b.cindex] |= |
| 522 (bitset_word) 1 << (bitno % BITSET_WORD_BITS); |
| 523 } |
| 524 |
| 525 |
| 526 /* Reset bit BITNO in bitset DST. */ |
| 527 static void |
| 528 lbitset_reset (bitset dst, bitset_bindex bitno) |
| 529 { |
| 530 bitset_windex windex = bitno / BITSET_WORD_BITS; |
| 531 |
| 532 if (!lbitset_elt_find (dst, windex, LBITSET_FIND)) |
| 533 return; |
| 534 |
| 535 dst->b.cdata[windex - dst->b.cindex] &= |
| 536 ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS)); |
| 537 |
| 538 /* If all the data is zero, perhaps we should unlink it now... */ |
| 539 } |
| 540 |
| 541 |
| 542 /* Test bit BITNO in bitset SRC. */ |
| 543 static bool |
| 544 lbitset_test (bitset src, bitset_bindex bitno) |
| 545 { |
| 546 bitset_windex windex = bitno / BITSET_WORD_BITS; |
| 547 |
| 548 return (lbitset_elt_find (src, windex, LBITSET_FIND) |
| 549 && ((src->b.cdata[windex - src->b.cindex] |
| 550 >> (bitno % BITSET_WORD_BITS)) |
| 551 & 1)); |
| 552 } |
| 553 |
| 554 |
| 555 static void |
| 556 lbitset_free (bitset bset) |
| 557 { |
| 558 lbitset_zero (bset); |
| 559 } |
| 560 |
| 561 |
| 562 /* Find list of up to NUM bits set in BSET starting from and including |
| 563 *NEXT and store in array LIST. Return with actual number of bits |
| 564 found and with *NEXT indicating where search stopped. */ |
| 565 static bitset_bindex |
| 566 lbitset_list_reverse (bitset bset, bitset_bindex *list, |
| 567 bitset_bindex num, bitset_bindex *next) |
| 568 { |
| 569 bitset_bindex rbitno; |
| 570 bitset_bindex bitno; |
| 571 unsigned int bcount; |
| 572 bitset_bindex boffset; |
| 573 bitset_windex windex; |
| 574 bitset_bindex count; |
| 575 lbitset_elt *elt; |
| 576 bitset_word word; |
| 577 bitset_bindex n_bits; |
| 578 |
| 579 elt = LBITSET_TAIL (bset); |
| 580 if (!elt) |
| 581 return 0; |
| 582 |
| 583 n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS; |
| 584 rbitno = *next; |
| 585 |
| 586 if (rbitno >= n_bits) |
| 587 return 0; |
| 588 |
| 589 bitno = n_bits - (rbitno + 1); |
| 590 |
| 591 windex = bitno / BITSET_WORD_BITS; |
| 592 |
| 593 /* Skip back to starting element. */ |
| 594 for (; elt && elt->index > windex; elt = elt->prev) |
| 595 continue; |
| 596 |
| 597 if (!elt) |
| 598 return 0; |
| 599 |
| 600 if (windex >= elt->index + LBITSET_ELT_WORDS) |
| 601 { |
| 602 /* We are trying to start in no-mans land so start |
| 603 at end of current elt. */ |
| 604 bcount = BITSET_WORD_BITS - 1; |
| 605 windex = elt->index + LBITSET_ELT_WORDS - 1; |
| 606 } |
| 607 else |
| 608 { |
| 609 bcount = bitno % BITSET_WORD_BITS; |
| 610 } |
| 611 |
| 612 count = 0; |
| 613 boffset = windex * BITSET_WORD_BITS; |
| 614 |
| 615 /* If num is 1, we could speed things up with a binary search |
| 616 of the word of interest. */ |
| 617 |
| 618 while (elt) |
| 619 { |
| 620 bitset_word *srcp = elt->words; |
| 621 |
| 622 for (; (windex - elt->index) < LBITSET_ELT_WORDS; |
| 623 windex--, boffset -= BITSET_WORD_BITS, |
| 624 bcount = BITSET_WORD_BITS - 1) |
| 625 { |
| 626 word = |
| 627 srcp[windex - elt->index] << (BITSET_WORD_BITS - 1 - bcount); |
| 628 |
| 629 for (; word; bcount--) |
| 630 { |
| 631 if (word & BITSET_MSB) |
| 632 { |
| 633 list[count++] = boffset + bcount; |
| 634 if (count >= num) |
| 635 { |
| 636 *next = n_bits - (boffset + bcount); |
| 637 return count; |
| 638 } |
| 639 } |
| 640 word <<= 1; |
| 641 } |
| 642 } |
| 643 |
| 644 elt = elt->prev; |
| 645 if (elt) |
| 646 { |
| 647 windex = elt->index + LBITSET_ELT_WORDS - 1; |
| 648 boffset = windex * BITSET_WORD_BITS; |
| 649 } |
| 650 } |
| 651 |
| 652 *next = n_bits - (boffset + 1); |
| 653 return count; |
| 654 } |
| 655 |
| 656 |
| 657 /* Find list of up to NUM bits set in BSET starting from and including |
| 658 *NEXT and store in array LIST. Return with actual number of bits |
| 659 found and with *NEXT indicating where search stopped. */ |
| 660 static bitset_bindex |
| 661 lbitset_list (bitset bset, bitset_bindex *list, |
| 662 bitset_bindex num, bitset_bindex *next) |
| 663 { |
| 664 bitset_bindex bitno; |
| 665 bitset_windex windex; |
| 666 bitset_bindex count; |
| 667 lbitset_elt *elt; |
| 668 lbitset_elt *head; |
| 669 bitset_word word; |
| 670 |
| 671 head = LBITSET_HEAD (bset); |
| 672 if (!head) |
| 673 return 0; |
| 674 |
| 675 bitno = *next; |
| 676 count = 0; |
| 677 |
| 678 if (!bitno) |
| 679 { |
| 680 /* This is the most common case. */ |
| 681 |
| 682 /* Start with the first element. */ |
| 683 elt = head; |
| 684 windex = elt->index; |
| 685 bitno = windex * BITSET_WORD_BITS; |
| 686 } |
| 687 else |
| 688 { |
| 689 windex = bitno / BITSET_WORD_BITS; |
| 690 |
| 691 /* Skip to starting element. */ |
| 692 for (elt = head; |
| 693 elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex; |
| 694 elt = elt->next) |
| 695 continue; |
| 696 |
| 697 if (!elt) |
| 698 return 0; |
| 699 |
| 700 if (windex < elt->index) |
| 701 { |
| 702 windex = elt->index; |
| 703 bitno = windex * BITSET_WORD_BITS; |
| 704 } |
| 705 else |
| 706 { |
| 707 bitset_word *srcp = elt->words; |
| 708 |
| 709 /* We are starting within an element. */ |
| 710 |
| 711 for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++) |
| 712 { |
| 713 word = srcp[windex - elt->index] >> (bitno % BITSET_WORD_BITS); |
| 714 |
| 715 for (; word; bitno++) |
| 716 { |
| 717 if (word & 1) |
| 718 { |
| 719 list[count++] = bitno; |
| 720 if (count >= num) |
| 721 { |
| 722 *next = bitno + 1; |
| 723 return count; |
| 724 } |
| 725 } |
| 726 word >>= 1; |
| 727 } |
| 728 bitno = (windex + 1) * BITSET_WORD_BITS; |
| 729 } |
| 730 |
| 731 elt = elt->next; |
| 732 if (elt) |
| 733 { |
| 734 windex = elt->index; |
| 735 bitno = windex * BITSET_WORD_BITS; |
| 736 } |
| 737 } |
| 738 } |
| 739 |
| 740 |
| 741 /* If num is 1, we could speed things up with a binary search |
| 742 of the word of interest. */ |
| 743 |
| 744 while (elt) |
| 745 { |
| 746 int i; |
| 747 bitset_word *srcp = elt->words; |
| 748 |
| 749 if ((count + LBITSET_ELT_BITS) < num) |
| 750 { |
| 751 /* The coast is clear, plant boot! */ |
| 752 |
| 753 #if LBITSET_ELT_WORDS == 2 |
| 754 word = srcp[0]; |
| 755 if (word) |
| 756 { |
| 757 if (!(word & 0xffff)) |
| 758 { |
| 759 word >>= 16; |
| 760 bitno += 16; |
| 761 } |
| 762 if (!(word & 0xff)) |
| 763 { |
| 764 word >>= 8; |
| 765 bitno += 8; |
| 766 } |
| 767 for (; word; bitno++) |
| 768 { |
| 769 if (word & 1) |
| 770 list[count++] = bitno; |
| 771 word >>= 1; |
| 772 } |
| 773 } |
| 774 windex++; |
| 775 bitno = windex * BITSET_WORD_BITS; |
| 776 |
| 777 word = srcp[1]; |
| 778 if (word) |
| 779 { |
| 780 if (!(word & 0xffff)) |
| 781 { |
| 782 word >>= 16; |
| 783 bitno += 16; |
| 784 } |
| 785 for (; word; bitno++) |
| 786 { |
| 787 if (word & 1) |
| 788 list[count++] = bitno; |
| 789 word >>= 1; |
| 790 } |
| 791 } |
| 792 windex++; |
| 793 bitno = windex * BITSET_WORD_BITS; |
| 794 #else |
| 795 for (i = 0; i < LBITSET_ELT_WORDS; i++) |
| 796 { |
| 797 word = srcp[i]; |
| 798 if (word) |
| 799 { |
| 800 if (!(word & 0xffff)) |
| 801 { |
| 802 word >>= 16; |
| 803 bitno += 16; |
| 804 } |
| 805 if (!(word & 0xff)) |
| 806 { |
| 807 word >>= 8; |
| 808 bitno += 8; |
| 809 } |
| 810 for (; word; bitno++) |
| 811 { |
| 812 if (word & 1) |
| 813 list[count++] = bitno; |
| 814 word >>= 1; |
| 815 } |
| 816 } |
| 817 windex++; |
| 818 bitno = windex * BITSET_WORD_BITS; |
| 819 } |
| 820 #endif |
| 821 } |
| 822 else |
| 823 { |
| 824 /* Tread more carefully since we need to check |
| 825 if array overflows. */ |
| 826 |
| 827 for (i = 0; i < LBITSET_ELT_WORDS; i++) |
| 828 { |
| 829 for (word = srcp[i]; word; bitno++) |
| 830 { |
| 831 if (word & 1) |
| 832 { |
| 833 list[count++] = bitno; |
| 834 if (count >= num) |
| 835 { |
| 836 *next = bitno + 1; |
| 837 return count; |
| 838 } |
| 839 } |
| 840 word >>= 1; |
| 841 } |
| 842 windex++; |
| 843 bitno = windex * BITSET_WORD_BITS; |
| 844 } |
| 845 } |
| 846 |
| 847 elt = elt->next; |
| 848 if (elt) |
| 849 { |
| 850 windex = elt->index; |
| 851 bitno = windex * BITSET_WORD_BITS; |
| 852 } |
| 853 } |
| 854 |
| 855 *next = bitno; |
| 856 return count; |
| 857 } |
| 858 |
| 859 |
| 860 static bool |
| 861 lbitset_empty_p (bitset dst) |
| 862 { |
| 863 lbitset_elt *elt; |
| 864 lbitset_elt *next; |
| 865 |
| 866 for (elt = LBITSET_HEAD (dst); elt; elt = next) |
| 867 { |
| 868 next = elt->next; |
| 869 if (!lbitset_elt_zero_p (elt)) |
| 870 return 0; |
| 871 /* Weed as we go. */ |
| 872 lbitset_elt_unlink (dst, elt); |
| 873 } |
| 874 |
| 875 return 1; |
| 876 } |
| 877 |
| 878 |
| 879 /* Ensure that any unused bits within the last element are clear. */ |
| 880 static inline void |
| 881 lbitset_unused_clear (bitset dst) |
| 882 { |
| 883 unsigned int last_bit; |
| 884 bitset_bindex n_bits; |
| 885 |
| 886 n_bits = BITSET_SIZE_ (dst); |
| 887 last_bit = n_bits % LBITSET_ELT_BITS; |
| 888 |
| 889 if (last_bit) |
| 890 { |
| 891 lbitset_elt *elt; |
| 892 bitset_windex windex; |
| 893 bitset_word *srcp; |
| 894 |
| 895 elt = LBITSET_TAIL (dst); |
| 896 srcp = elt->words; |
| 897 windex = n_bits / BITSET_WORD_BITS; |
| 898 |
| 899 srcp[windex - elt->index] &= ((bitset_word) 1 << last_bit) - 1; |
| 900 windex++; |
| 901 |
| 902 for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++) |
| 903 srcp[windex - elt->index] = 0; |
| 904 } |
| 905 } |
| 906 |
| 907 |
| 908 static void |
| 909 lbitset_ones (bitset dst) |
| 910 { |
| 911 bitset_windex i; |
| 912 bitset_windex windex; |
| 913 lbitset_elt *elt; |
| 914 |
| 915 /* This is a decidedly unfriendly operation for a linked list |
| 916 bitset! It makes a sparse bitset become dense. An alternative |
| 917 is to have a flag that indicates that the bitset stores the |
| 918 complement of what it indicates. */ |
| 919 |
| 920 windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS; |
| 921 |
| 922 for (i = 0; i < windex; i += LBITSET_ELT_WORDS) |
| 923 { |
| 924 /* Create new elements if they cannot be found. */ |
| 925 elt = lbitset_elt_find (dst, i, LBITSET_CREATE); |
| 926 memset (elt->words, -1, sizeof (elt->words)); |
| 927 } |
| 928 |
| 929 lbitset_unused_clear (dst); |
| 930 } |
| 931 |
| 932 |
| 933 static void |
| 934 lbitset_not (bitset dst, bitset src) |
| 935 { |
| 936 lbitset_elt *elt; |
| 937 lbitset_elt *selt; |
| 938 lbitset_elt *delt; |
| 939 bitset_windex i; |
| 940 unsigned int j; |
| 941 bitset_windex windex; |
| 942 |
| 943 /* This is another unfriendly operation for a linked list |
| 944 bitset! */ |
| 945 elt = LBITSET_TAIL (dst); |
| 946 |
| 947 windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS; |
| 948 |
| 949 for (i = 0; i < windex; i += LBITSET_ELT_WORDS) |
| 950 { |
| 951 /* Create new elements for dst if they cannot be found |
| 952 or substitute zero elements if src elements not found. */ |
| 953 selt = lbitset_elt_find (src, i, LBITSET_SUBST); |
| 954 delt = lbitset_elt_find (dst, i, LBITSET_CREATE); |
| 955 |
| 956 for (j = 0; j < LBITSET_ELT_WORDS; j++) |
| 957 delt->words[j] = ~selt->words[j]; |
| 958 } |
| 959 lbitset_unused_clear (dst); |
| 960 lbitset_weed (dst); |
| 961 return; |
| 962 } |
| 963 |
| 964 |
| 965 /* Is DST == DST | SRC? */ |
| 966 static bool |
| 967 lbitset_subset_p (bitset dst, bitset src) |
| 968 { |
| 969 lbitset_elt *selt; |
| 970 lbitset_elt *delt; |
| 971 unsigned int j; |
| 972 |
| 973 for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); |
| 974 selt || delt; selt = selt->next, delt = delt->next) |
| 975 { |
| 976 if (!selt) |
| 977 selt = &lbitset_zero_elts[0]; |
| 978 else if (!delt) |
| 979 delt = &lbitset_zero_elts[0]; |
| 980 else if (selt->index != delt->index) |
| 981 { |
| 982 if (selt->index < delt->index) |
| 983 { |
| 984 lbitset_zero_elts[2].next = delt; |
| 985 delt = &lbitset_zero_elts[2]; |
| 986 } |
| 987 else |
| 988 { |
| 989 lbitset_zero_elts[1].next = selt; |
| 990 selt = &lbitset_zero_elts[1]; |
| 991 } |
| 992 } |
| 993 |
| 994 for (j = 0; j < LBITSET_ELT_WORDS; j++) |
| 995 if (delt->words[j] != (selt->words[j] | delt->words[j])) |
| 996 return false; |
| 997 } |
| 998 return true; |
| 999 } |
| 1000 |
| 1001 |
| 1002 /* Is DST & SRC == 0? */ |
| 1003 static bool |
| 1004 lbitset_disjoint_p (bitset dst, bitset src) |
| 1005 { |
| 1006 lbitset_elt *selt; |
| 1007 lbitset_elt *delt; |
| 1008 unsigned int j; |
| 1009 |
| 1010 for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); |
| 1011 selt && delt; selt = selt->next, delt = delt->next) |
| 1012 { |
| 1013 if (selt->index != delt->index) |
| 1014 { |
| 1015 if (selt->index < delt->index) |
| 1016 { |
| 1017 lbitset_zero_elts[2].next = delt; |
| 1018 delt = &lbitset_zero_elts[2]; |
| 1019 } |
| 1020 else |
| 1021 { |
| 1022 lbitset_zero_elts[1].next = selt; |
| 1023 selt = &lbitset_zero_elts[1]; |
| 1024 } |
| 1025 /* Since the elements are different, there is no |
| 1026 intersection of these elements. */ |
| 1027 continue; |
| 1028 } |
| 1029 |
| 1030 for (j = 0; j < LBITSET_ELT_WORDS; j++) |
| 1031 if (selt->words[j] & delt->words[j]) |
| 1032 return false; |
| 1033 } |
| 1034 return true; |
| 1035 } |
| 1036 |
| 1037 |
| 1038 static bool |
| 1039 lbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) |
| 1040 { |
| 1041 lbitset_elt *selt1 = LBITSET_HEAD (src1); |
| 1042 lbitset_elt *selt2 = LBITSET_HEAD (src2); |
| 1043 lbitset_elt *delt = LBITSET_HEAD (dst); |
| 1044 bitset_windex windex1; |
| 1045 bitset_windex windex2; |
| 1046 bitset_windex windex; |
| 1047 lbitset_elt *stmp1; |
| 1048 lbitset_elt *stmp2; |
| 1049 lbitset_elt *dtmp; |
| 1050 bitset_word *srcp1; |
| 1051 bitset_word *srcp2; |
| 1052 bitset_word *dstp; |
| 1053 bool changed = false; |
| 1054 unsigned int i; |
| 1055 |
| 1056 LBITSET_HEAD (dst) = 0; |
| 1057 dst->b.csize = 0; |
| 1058 |
| 1059 windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; |
| 1060 windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; |
| 1061 |
| 1062 while (selt1 || selt2) |
| 1063 { |
| 1064 /* Figure out whether we need to substitute zero elements for |
| 1065 missing links. */ |
| 1066 if (windex1 == windex2) |
| 1067 { |
| 1068 windex = windex1; |
| 1069 stmp1 = selt1; |
| 1070 stmp2 = selt2; |
| 1071 selt1 = selt1->next; |
| 1072 windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; |
| 1073 selt2 = selt2->next; |
| 1074 windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; |
| 1075 } |
| 1076 else if (windex1 < windex2) |
| 1077 { |
| 1078 windex = windex1; |
| 1079 stmp1 = selt1; |
| 1080 stmp2 = &lbitset_zero_elts[0]; |
| 1081 selt1 = selt1->next; |
| 1082 windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; |
| 1083 } |
| 1084 else |
| 1085 { |
| 1086 windex = windex2; |
| 1087 stmp1 = &lbitset_zero_elts[0]; |
| 1088 stmp2 = selt2; |
| 1089 selt2 = selt2->next; |
| 1090 windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; |
| 1091 } |
| 1092 |
| 1093 /* Find the appropriate element from DST. Begin by discarding |
| 1094 elements that we've skipped. */ |
| 1095 while (delt && delt->index < windex) |
| 1096 { |
| 1097 changed = true; |
| 1098 dtmp = delt; |
| 1099 delt = delt->next; |
| 1100 lbitset_elt_free (dtmp); |
| 1101 } |
| 1102 if (delt && delt->index == windex) |
| 1103 { |
| 1104 dtmp = delt; |
| 1105 delt = delt->next; |
| 1106 } |
| 1107 else |
| 1108 dtmp = lbitset_elt_calloc (); |
| 1109 |
| 1110 /* Do the operation, and if any bits are set, link it into the |
| 1111 linked list. */ |
| 1112 srcp1 = stmp1->words; |
| 1113 srcp2 = stmp2->words; |
| 1114 dstp = dtmp->words; |
| 1115 switch (op) |
| 1116 { |
| 1117 default: |
| 1118 abort (); |
| 1119 |
| 1120 case BITSET_OP_OR: |
| 1121 for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) |
| 1122 { |
| 1123 bitset_word tmp = *srcp1++ | *srcp2++; |
| 1124 |
| 1125 if (*dstp != tmp) |
| 1126 { |
| 1127 changed = true; |
| 1128 *dstp = tmp; |
| 1129 } |
| 1130 } |
| 1131 break; |
| 1132 |
| 1133 case BITSET_OP_AND: |
| 1134 for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) |
| 1135 { |
| 1136 bitset_word tmp = *srcp1++ & *srcp2++; |
| 1137 |
| 1138 if (*dstp != tmp) |
| 1139 { |
| 1140 changed = true; |
| 1141 *dstp = tmp; |
| 1142 } |
| 1143 } |
| 1144 break; |
| 1145 |
| 1146 case BITSET_OP_XOR: |
| 1147 for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) |
| 1148 { |
| 1149 bitset_word tmp = *srcp1++ ^ *srcp2++; |
| 1150 |
| 1151 if (*dstp != tmp) |
| 1152 { |
| 1153 changed = true; |
| 1154 *dstp = tmp; |
| 1155 } |
| 1156 } |
| 1157 break; |
| 1158 |
| 1159 case BITSET_OP_ANDN: |
| 1160 for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) |
| 1161 { |
| 1162 bitset_word tmp = *srcp1++ & ~(*srcp2++); |
| 1163 |
| 1164 if (*dstp != tmp) |
| 1165 { |
| 1166 changed = true; |
| 1167 *dstp = tmp; |
| 1168 } |
| 1169 } |
| 1170 break; |
| 1171 } |
| 1172 |
| 1173 if (!lbitset_elt_zero_p (dtmp)) |
| 1174 { |
| 1175 dtmp->index = windex; |
| 1176 /* Perhaps this could be optimised... */ |
| 1177 lbitset_elt_link (dst, dtmp); |
| 1178 } |
| 1179 else |
| 1180 { |
| 1181 lbitset_elt_free (dtmp); |
| 1182 } |
| 1183 } |
| 1184 |
| 1185 /* If we have elements of DST left over, free them all. */ |
| 1186 if (delt) |
| 1187 { |
| 1188 changed = true; |
| 1189 lbitset_prune (dst, delt); |
| 1190 } |
| 1191 |
| 1192 return changed; |
| 1193 } |
| 1194 |
| 1195 |
| 1196 static bool |
| 1197 lbitset_and_cmp (bitset dst, bitset src1, bitset src2) |
| 1198 { |
| 1199 lbitset_elt *selt1 = LBITSET_HEAD (src1); |
| 1200 lbitset_elt *selt2 = LBITSET_HEAD (src2); |
| 1201 bool changed; |
| 1202 |
| 1203 if (!selt2) |
| 1204 { |
| 1205 lbitset_weed (dst); |
| 1206 changed = !LBITSET_HEAD (dst); |
| 1207 lbitset_zero (dst); |
| 1208 return changed; |
| 1209 } |
| 1210 else if (!selt1) |
| 1211 { |
| 1212 lbitset_weed (dst); |
| 1213 changed = !LBITSET_HEAD (dst); |
| 1214 lbitset_zero (dst); |
| 1215 return changed; |
| 1216 } |
| 1217 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND); |
| 1218 } |
| 1219 |
| 1220 |
| 1221 static void |
| 1222 lbitset_and (bitset dst, bitset src1, bitset src2) |
| 1223 { |
| 1224 lbitset_and_cmp (dst, src1, src2); |
| 1225 } |
| 1226 |
| 1227 |
| 1228 static bool |
| 1229 lbitset_andn_cmp (bitset dst, bitset src1, bitset src2) |
| 1230 { |
| 1231 lbitset_elt *selt1 = LBITSET_HEAD (src1); |
| 1232 lbitset_elt *selt2 = LBITSET_HEAD (src2); |
| 1233 bool changed; |
| 1234 |
| 1235 if (!selt2) |
| 1236 { |
| 1237 return lbitset_copy_cmp (dst, src1); |
| 1238 } |
| 1239 else if (!selt1) |
| 1240 { |
| 1241 lbitset_weed (dst); |
| 1242 changed = !LBITSET_HEAD (dst); |
| 1243 lbitset_zero (dst); |
| 1244 return changed; |
| 1245 } |
| 1246 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN); |
| 1247 } |
| 1248 |
| 1249 |
| 1250 static void |
| 1251 lbitset_andn (bitset dst, bitset src1, bitset src2) |
| 1252 { |
| 1253 lbitset_andn_cmp (dst, src1, src2); |
| 1254 } |
| 1255 |
| 1256 |
| 1257 static bool |
| 1258 lbitset_or_cmp (bitset dst, bitset src1, bitset src2) |
| 1259 { |
| 1260 lbitset_elt *selt1 = LBITSET_HEAD (src1); |
| 1261 lbitset_elt *selt2 = LBITSET_HEAD (src2); |
| 1262 |
| 1263 if (!selt2) |
| 1264 { |
| 1265 return lbitset_copy_cmp (dst, src1); |
| 1266 } |
| 1267 else if (!selt1) |
| 1268 { |
| 1269 return lbitset_copy_cmp (dst, src2); |
| 1270 } |
| 1271 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR); |
| 1272 } |
| 1273 |
| 1274 |
| 1275 static void |
| 1276 lbitset_or (bitset dst, bitset src1, bitset src2) |
| 1277 { |
| 1278 lbitset_or_cmp (dst, src1, src2); |
| 1279 } |
| 1280 |
| 1281 |
| 1282 static bool |
| 1283 lbitset_xor_cmp (bitset dst, bitset src1, bitset src2) |
| 1284 { |
| 1285 lbitset_elt *selt1 = LBITSET_HEAD (src1); |
| 1286 lbitset_elt *selt2 = LBITSET_HEAD (src2); |
| 1287 |
| 1288 if (!selt2) |
| 1289 { |
| 1290 return lbitset_copy_cmp (dst, src1); |
| 1291 } |
| 1292 else if (!selt1) |
| 1293 { |
| 1294 return lbitset_copy_cmp (dst, src2); |
| 1295 } |
| 1296 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR); |
| 1297 } |
| 1298 |
| 1299 |
| 1300 static void |
| 1301 lbitset_xor (bitset dst, bitset src1, bitset src2) |
| 1302 { |
| 1303 lbitset_xor_cmp (dst, src1, src2); |
| 1304 } |
| 1305 |
| 1306 |
| 1307 |
| 1308 /* Vector of operations for linked-list bitsets. */ |
| 1309 struct bitset_vtable lbitset_vtable = { |
| 1310 lbitset_set, |
| 1311 lbitset_reset, |
| 1312 bitset_toggle_, |
| 1313 lbitset_test, |
| 1314 lbitset_resize, |
| 1315 bitset_size_, |
| 1316 bitset_count_, |
| 1317 lbitset_empty_p, |
| 1318 lbitset_ones, |
| 1319 lbitset_zero, |
| 1320 lbitset_copy, |
| 1321 lbitset_disjoint_p, |
| 1322 lbitset_equal_p, |
| 1323 lbitset_not, |
| 1324 lbitset_subset_p, |
| 1325 lbitset_and, |
| 1326 lbitset_and_cmp, |
| 1327 lbitset_andn, |
| 1328 lbitset_andn_cmp, |
| 1329 lbitset_or, |
| 1330 lbitset_or_cmp, |
| 1331 lbitset_xor, |
| 1332 lbitset_xor_cmp, |
| 1333 bitset_and_or_, |
| 1334 bitset_and_or_cmp_, |
| 1335 bitset_andn_or_, |
| 1336 bitset_andn_or_cmp_, |
| 1337 bitset_or_and_, |
| 1338 bitset_or_and_cmp_, |
| 1339 lbitset_list, |
| 1340 lbitset_list_reverse, |
| 1341 lbitset_free, |
| 1342 BITSET_LIST |
| 1343 }; |
| 1344 |
| 1345 |
| 1346 /* Return size of initial structure. */ |
| 1347 size_t |
| 1348 lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED) |
| 1349 { |
| 1350 return sizeof (struct lbitset_struct); |
| 1351 } |
| 1352 |
| 1353 |
| 1354 /* Initialize a bitset. */ |
| 1355 bitset |
| 1356 lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED) |
| 1357 { |
| 1358 BITSET_NBITS_ (bset) = n_bits; |
| 1359 bset->b.vtable = &lbitset_vtable; |
| 1360 return bset; |
| 1361 } |
| 1362 |
| 1363 |
| 1364 void |
| 1365 lbitset_release_memory (void) |
| 1366 { |
| 1367 lbitset_free_list = 0; |
| 1368 if (lbitset_obstack_init) |
| 1369 { |
| 1370 lbitset_obstack_init = false; |
| 1371 obstack_free (&lbitset_obstack, NULL); |
| 1372 } |
| 1373 } |
| 1374 |
| 1375 |
| 1376 /* Function to be called from debugger to debug lbitset. */ |
| 1377 void |
| 1378 debug_lbitset (bitset bset) |
| 1379 { |
| 1380 lbitset_elt *elt; |
| 1381 unsigned int i; |
| 1382 |
| 1383 if (!bset) |
| 1384 return; |
| 1385 |
| 1386 for (elt = LBITSET_HEAD (bset); elt; elt = elt->next) |
| 1387 { |
| 1388 fprintf (stderr, "Elt %lu\n", (unsigned long int) elt->index); |
| 1389 for (i = 0; i < LBITSET_ELT_WORDS; i++) |
| 1390 { |
| 1391 unsigned int j; |
| 1392 bitset_word word; |
| 1393 |
| 1394 word = elt->words[i]; |
| 1395 |
| 1396 fprintf (stderr, " Word %u:", i); |
| 1397 for (j = 0; j < LBITSET_WORD_BITS; j++) |
| 1398 if ((word & ((bitset_word) 1 << j))) |
| 1399 fprintf (stderr, " %u", j); |
| 1400 fprintf (stderr, "\n"); |
| 1401 } |
| 1402 } |
| 1403 } |
OLD | NEW |