OLD | NEW |
(Empty) | |
| 1 /* Variable array 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 "vbitset.h" |
| 21 |
| 22 #include <stdlib.h> |
| 23 #include <string.h> |
| 24 |
| 25 /* This file implements variable size bitsets stored as a variable |
| 26 length array of words. Any unused bits in the last word must be |
| 27 zero. |
| 28 |
| 29 Note that binary or ternary operations assume that each bitset operand |
| 30 has the same size. |
| 31 */ |
| 32 |
| 33 static void vbitset_unused_clear (bitset); |
| 34 |
| 35 static void vbitset_set (bitset, bitset_bindex); |
| 36 static void vbitset_reset (bitset, bitset_bindex); |
| 37 static bool vbitset_test (bitset, bitset_bindex); |
| 38 static bitset_bindex vbitset_list (bitset, bitset_bindex *, |
| 39 bitset_bindex, bitset_bindex *); |
| 40 static bitset_bindex vbitset_list_reverse (bitset, bitset_bindex *, |
| 41 bitset_bindex, bitset_bindex *); |
| 42 |
| 43 #define VBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS) |
| 44 #define VBITSET_WORDS(X) ((X)->b.cdata) |
| 45 #define VBITSET_SIZE(X) ((X)->b.csize) |
| 46 #define VBITSET_ASIZE(X) ((X)->v.size) |
| 47 |
| 48 #undef min |
| 49 #undef max |
| 50 #define min(a, b) ((a) > (b) ? (b) : (a)) |
| 51 #define max(a, b) ((a) > (b) ? (a) : (b)) |
| 52 |
| 53 static bitset_bindex |
| 54 vbitset_resize (bitset src, bitset_bindex n_bits) |
| 55 { |
| 56 bitset_windex oldsize; |
| 57 bitset_windex newsize; |
| 58 |
| 59 if (n_bits == BITSET_NBITS_ (src)) |
| 60 return n_bits; |
| 61 |
| 62 oldsize = VBITSET_SIZE (src); |
| 63 newsize = VBITSET_N_WORDS (n_bits); |
| 64 |
| 65 if (oldsize < newsize) |
| 66 { |
| 67 bitset_windex size; |
| 68 |
| 69 /* The bitset needs to grow. If we already have enough memory |
| 70 allocated, then just zero what we need. */ |
| 71 if (newsize > VBITSET_ASIZE (src)) |
| 72 { |
| 73 /* We need to allocate more memory. When oldsize is |
| 74 non-zero this means that we are changing the size, so |
| 75 grow the bitset 25% larger than requested to reduce |
| 76 number of reallocations. */ |
| 77 |
| 78 if (oldsize == 0) |
| 79 size = newsize; |
| 80 else |
| 81 size = newsize + newsize / 4; |
| 82 |
| 83 VBITSET_WORDS (src) |
| 84 = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word)); |
| 85 VBITSET_ASIZE (src) = size; |
| 86 } |
| 87 |
| 88 memset (VBITSET_WORDS (src) + oldsize, 0, |
| 89 (newsize - oldsize) * sizeof (bitset_word)); |
| 90 VBITSET_SIZE (src) = newsize; |
| 91 } |
| 92 else |
| 93 { |
| 94 /* The bitset needs to shrink. There's no point deallocating |
| 95 the memory unless it is shrinking by a reasonable amount. */ |
| 96 if ((oldsize - newsize) >= oldsize / 2) |
| 97 { |
| 98 VBITSET_WORDS (src) |
| 99 = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word)); |
| 100 VBITSET_ASIZE (src) = newsize; |
| 101 } |
| 102 |
| 103 /* Need to prune any excess bits. FIXME. */ |
| 104 |
| 105 VBITSET_SIZE (src) = newsize; |
| 106 } |
| 107 |
| 108 BITSET_NBITS_ (src) = n_bits; |
| 109 return n_bits; |
| 110 } |
| 111 |
| 112 |
| 113 /* Set bit BITNO in bitset DST. */ |
| 114 static void |
| 115 vbitset_set (dst, bitno) |
| 116 bitset dst; |
| 117 bitset_bindex bitno; |
| 118 { |
| 119 bitset_windex windex = bitno / BITSET_WORD_BITS; |
| 120 |
| 121 /* Perhaps we should abort. The user should explicitly call |
| 122 bitset_resize since this will not catch the case when we set a |
| 123 bit larger than the current size but smaller than the allocated |
| 124 size. */ |
| 125 vbitset_resize (dst, bitno); |
| 126 |
| 127 dst->b.cdata[windex - dst->b.cindex] |= |
| 128 (bitset_word) 1 << (bitno % BITSET_WORD_BITS); |
| 129 } |
| 130 |
| 131 |
| 132 /* Reset bit BITNO in bitset DST. */ |
| 133 static void |
| 134 vbitset_reset (dst, bitno) |
| 135 bitset dst ATTRIBUTE_UNUSED; |
| 136 bitset_bindex bitno ATTRIBUTE_UNUSED; |
| 137 { |
| 138 /* We must be accessing outside the cache so the bit is |
| 139 zero anyway. */ |
| 140 } |
| 141 |
| 142 |
| 143 /* Test bit BITNO in bitset SRC. */ |
| 144 static bool |
| 145 vbitset_test (src, bitno) |
| 146 bitset src ATTRIBUTE_UNUSED; |
| 147 bitset_bindex bitno ATTRIBUTE_UNUSED; |
| 148 { |
| 149 /* We must be accessing outside the cache so the bit is |
| 150 zero anyway. */ |
| 151 return 0; |
| 152 } |
| 153 |
| 154 |
| 155 /* Find list of up to NUM bits set in BSET in reverse order, starting |
| 156 from and including NEXT and store in array LIST. Return with |
| 157 actual number of bits found and with *NEXT indicating where search |
| 158 stopped. */ |
| 159 static bitset_bindex |
| 160 vbitset_list_reverse (src, list, num, next) |
| 161 bitset src; |
| 162 bitset_bindex *list; |
| 163 bitset_bindex num; |
| 164 bitset_bindex *next; |
| 165 { |
| 166 bitset_bindex bitno; |
| 167 bitset_bindex rbitno; |
| 168 bitset_bindex count; |
| 169 bitset_windex windex; |
| 170 unsigned int bitcnt; |
| 171 bitset_bindex bitoff; |
| 172 bitset_word *srcp = VBITSET_WORDS (src); |
| 173 bitset_bindex n_bits = BITSET_SIZE_ (src); |
| 174 |
| 175 rbitno = *next; |
| 176 |
| 177 /* If num is 1, we could speed things up with a binary search |
| 178 of the word of interest. */ |
| 179 |
| 180 if (rbitno >= n_bits) |
| 181 return 0; |
| 182 |
| 183 count = 0; |
| 184 |
| 185 bitno = n_bits - (rbitno + 1); |
| 186 |
| 187 windex = bitno / BITSET_WORD_BITS; |
| 188 bitcnt = bitno % BITSET_WORD_BITS; |
| 189 bitoff = windex * BITSET_WORD_BITS; |
| 190 |
| 191 do |
| 192 { |
| 193 bitset_word word; |
| 194 |
| 195 word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); |
| 196 for (; word; bitcnt--) |
| 197 { |
| 198 if (word & BITSET_MSB) |
| 199 { |
| 200 list[count++] = bitoff + bitcnt; |
| 201 if (count >= num) |
| 202 { |
| 203 *next = n_bits - (bitoff + bitcnt); |
| 204 return count; |
| 205 } |
| 206 } |
| 207 word <<= 1; |
| 208 } |
| 209 bitoff -= BITSET_WORD_BITS; |
| 210 bitcnt = BITSET_WORD_BITS - 1; |
| 211 } |
| 212 while (windex--); |
| 213 |
| 214 *next = n_bits - (bitoff + 1); |
| 215 return count; |
| 216 } |
| 217 |
| 218 |
| 219 /* Find list of up to NUM bits set in BSET starting from and including |
| 220 *NEXT and store in array LIST. Return with actual number of bits |
| 221 found and with *NEXT indicating where search stopped. */ |
| 222 static bitset_bindex |
| 223 vbitset_list (src, list, num, next) |
| 224 bitset src; |
| 225 bitset_bindex *list; |
| 226 bitset_bindex num; |
| 227 bitset_bindex *next; |
| 228 { |
| 229 bitset_bindex bitno; |
| 230 bitset_bindex count; |
| 231 bitset_windex windex; |
| 232 bitset_bindex bitoff; |
| 233 bitset_windex size = VBITSET_SIZE (src); |
| 234 bitset_word *srcp = VBITSET_WORDS (src); |
| 235 bitset_word word; |
| 236 |
| 237 bitno = *next; |
| 238 |
| 239 count = 0; |
| 240 if (!bitno) |
| 241 { |
| 242 /* Many bitsets are zero, so make this common case fast. */ |
| 243 for (windex = 0; windex < size && !srcp[windex]; windex++) |
| 244 continue; |
| 245 if (windex >= size) |
| 246 return 0; |
| 247 |
| 248 /* If num is 1, we could speed things up with a binary search |
| 249 of the current word. */ |
| 250 |
| 251 bitoff = windex * BITSET_WORD_BITS; |
| 252 } |
| 253 else |
| 254 { |
| 255 if (bitno >= BITSET_SIZE_ (src)) |
| 256 return 0; |
| 257 |
| 258 windex = bitno / BITSET_WORD_BITS; |
| 259 bitno = bitno % BITSET_WORD_BITS; |
| 260 |
| 261 if (bitno) |
| 262 { |
| 263 /* Handle the case where we start within a word. |
| 264 Most often, this is executed with large bitsets |
| 265 with many set bits where we filled the array |
| 266 on the previous call to this function. */ |
| 267 |
| 268 bitoff = windex * BITSET_WORD_BITS; |
| 269 word = srcp[windex] >> bitno; |
| 270 for (bitno = bitoff + bitno; word; bitno++) |
| 271 { |
| 272 if (word & 1) |
| 273 { |
| 274 list[count++] = bitno; |
| 275 if (count >= num) |
| 276 { |
| 277 *next = bitno + 1; |
| 278 return count; |
| 279 } |
| 280 } |
| 281 word >>= 1; |
| 282 } |
| 283 windex++; |
| 284 } |
| 285 bitoff = windex * BITSET_WORD_BITS; |
| 286 } |
| 287 |
| 288 for (; windex < size; windex++, bitoff += BITSET_WORD_BITS) |
| 289 { |
| 290 if (!(word = srcp[windex])) |
| 291 continue; |
| 292 |
| 293 if ((count + BITSET_WORD_BITS) < num) |
| 294 { |
| 295 for (bitno = bitoff; word; bitno++) |
| 296 { |
| 297 if (word & 1) |
| 298 list[count++] = bitno; |
| 299 word >>= 1; |
| 300 } |
| 301 } |
| 302 else |
| 303 { |
| 304 for (bitno = bitoff; word; bitno++) |
| 305 { |
| 306 if (word & 1) |
| 307 { |
| 308 list[count++] = bitno; |
| 309 if (count >= num) |
| 310 { |
| 311 *next = bitno + 1; |
| 312 return count; |
| 313 } |
| 314 } |
| 315 word >>= 1; |
| 316 } |
| 317 } |
| 318 } |
| 319 |
| 320 *next = bitoff; |
| 321 return count; |
| 322 } |
| 323 |
| 324 |
| 325 /* Ensure that any unused bits within the last word are clear. */ |
| 326 static inline void |
| 327 vbitset_unused_clear (dst) |
| 328 bitset dst; |
| 329 { |
| 330 unsigned int last_bit; |
| 331 |
| 332 last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS; |
| 333 if (last_bit) |
| 334 VBITSET_WORDS (dst)[VBITSET_SIZE (dst) - 1] &= |
| 335 ((bitset_word) 1 << last_bit) - 1; |
| 336 } |
| 337 |
| 338 |
| 339 static void |
| 340 vbitset_ones (bitset dst) |
| 341 { |
| 342 bitset_word *dstp = VBITSET_WORDS (dst); |
| 343 unsigned int bytes; |
| 344 |
| 345 bytes = sizeof (bitset_word) * VBITSET_SIZE (dst); |
| 346 |
| 347 memset (dstp, -1, bytes); |
| 348 vbitset_unused_clear (dst); |
| 349 } |
| 350 |
| 351 |
| 352 static void |
| 353 vbitset_zero (bitset dst) |
| 354 { |
| 355 bitset_word *dstp = VBITSET_WORDS (dst); |
| 356 unsigned int bytes; |
| 357 |
| 358 bytes = sizeof (bitset_word) * VBITSET_SIZE (dst); |
| 359 |
| 360 memset (dstp, 0, bytes); |
| 361 } |
| 362 |
| 363 |
| 364 static bool |
| 365 vbitset_empty_p (bitset dst) |
| 366 { |
| 367 unsigned int i; |
| 368 bitset_word *dstp = VBITSET_WORDS (dst); |
| 369 |
| 370 for (i = 0; i < VBITSET_SIZE (dst); i++) |
| 371 if (dstp[i]) |
| 372 return 0; |
| 373 |
| 374 return 1; |
| 375 } |
| 376 |
| 377 |
| 378 static void |
| 379 vbitset_copy1 (bitset dst, bitset src) |
| 380 { |
| 381 bitset_word *srcp; |
| 382 bitset_word *dstp; |
| 383 bitset_windex ssize; |
| 384 bitset_windex dsize; |
| 385 |
| 386 if (src == dst) |
| 387 return; |
| 388 |
| 389 vbitset_resize (dst, BITSET_SIZE_ (src)); |
| 390 |
| 391 srcp = VBITSET_WORDS (src); |
| 392 dstp = VBITSET_WORDS (dst); |
| 393 ssize = VBITSET_SIZE (src); |
| 394 dsize = VBITSET_SIZE (dst); |
| 395 |
| 396 memcpy (dstp, srcp, sizeof (bitset_word) * ssize); |
| 397 |
| 398 memset (dstp + sizeof (bitset_word) * ssize, 0, |
| 399 sizeof (bitset_word) * (dsize - ssize)); |
| 400 } |
| 401 |
| 402 |
| 403 static void |
| 404 vbitset_not (bitset dst, bitset src) |
| 405 { |
| 406 unsigned int i; |
| 407 bitset_word *srcp; |
| 408 bitset_word *dstp; |
| 409 bitset_windex ssize; |
| 410 bitset_windex dsize; |
| 411 |
| 412 vbitset_resize (dst, BITSET_SIZE_ (src)); |
| 413 |
| 414 srcp = VBITSET_WORDS (src); |
| 415 dstp = VBITSET_WORDS (dst); |
| 416 ssize = VBITSET_SIZE (src); |
| 417 dsize = VBITSET_SIZE (dst); |
| 418 |
| 419 for (i = 0; i < ssize; i++) |
| 420 *dstp++ = ~(*srcp++); |
| 421 |
| 422 vbitset_unused_clear (dst); |
| 423 memset (dstp + sizeof (bitset_word) * ssize, 0, |
| 424 sizeof (bitset_word) * (dsize - ssize)); |
| 425 } |
| 426 |
| 427 |
| 428 static bool |
| 429 vbitset_equal_p (bitset dst, bitset src) |
| 430 { |
| 431 unsigned int i; |
| 432 bitset_word *srcp = VBITSET_WORDS (src); |
| 433 bitset_word *dstp = VBITSET_WORDS (dst); |
| 434 bitset_windex ssize = VBITSET_SIZE (src); |
| 435 bitset_windex dsize = VBITSET_SIZE (dst); |
| 436 |
| 437 for (i = 0; i < min (ssize, dsize); i++) |
| 438 if (*srcp++ != *dstp++) |
| 439 return 0; |
| 440 |
| 441 if (ssize > dsize) |
| 442 { |
| 443 for (; i < ssize; i++) |
| 444 if (*srcp++) |
| 445 return 0; |
| 446 } |
| 447 else |
| 448 { |
| 449 for (; i < dsize; i++) |
| 450 if (*dstp++) |
| 451 return 0; |
| 452 } |
| 453 |
| 454 return 1; |
| 455 } |
| 456 |
| 457 |
| 458 static bool |
| 459 vbitset_subset_p (bitset dst, bitset src) |
| 460 { |
| 461 unsigned int i; |
| 462 bitset_word *srcp = VBITSET_WORDS (src); |
| 463 bitset_word *dstp = VBITSET_WORDS (dst); |
| 464 bitset_windex ssize = VBITSET_SIZE (src); |
| 465 bitset_windex dsize = VBITSET_SIZE (dst); |
| 466 |
| 467 for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++) |
| 468 if (*dstp != (*srcp | *dstp)) |
| 469 return 0; |
| 470 |
| 471 if (ssize > dsize) |
| 472 { |
| 473 for (; i < ssize; i++) |
| 474 if (*srcp++) |
| 475 return 0; |
| 476 } |
| 477 |
| 478 return 1; |
| 479 } |
| 480 |
| 481 |
| 482 static bool |
| 483 vbitset_disjoint_p (bitset dst, bitset src) |
| 484 { |
| 485 unsigned int i; |
| 486 bitset_word *srcp = VBITSET_WORDS (src); |
| 487 bitset_word *dstp = VBITSET_WORDS (dst); |
| 488 bitset_windex ssize = VBITSET_SIZE (src); |
| 489 bitset_windex dsize = VBITSET_SIZE (dst); |
| 490 |
| 491 for (i = 0; i < min (ssize, dsize); i++) |
| 492 if (*srcp++ & *dstp++) |
| 493 return 0; |
| 494 |
| 495 return 1; |
| 496 } |
| 497 |
| 498 |
| 499 static void |
| 500 vbitset_and (bitset dst, bitset src1, bitset src2) |
| 501 { |
| 502 unsigned int i; |
| 503 bitset_word *src1p; |
| 504 bitset_word *src2p; |
| 505 bitset_word *dstp; |
| 506 bitset_windex ssize1; |
| 507 bitset_windex ssize2; |
| 508 bitset_windex dsize; |
| 509 |
| 510 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); |
| 511 |
| 512 dsize = VBITSET_SIZE (dst); |
| 513 ssize1 = VBITSET_SIZE (src1); |
| 514 ssize2 = VBITSET_SIZE (src2); |
| 515 dstp = VBITSET_WORDS (dst); |
| 516 src1p = VBITSET_WORDS (src1); |
| 517 src2p = VBITSET_WORDS (src2); |
| 518 |
| 519 for (i = 0; i < min (ssize1, ssize2); i++) |
| 520 *dstp++ = *src1p++ & *src2p++; |
| 521 |
| 522 memset (dstp, 0, sizeof (bitset_word) * (dsize - min (ssize1, ssize2))); |
| 523 } |
| 524 |
| 525 |
| 526 static bool |
| 527 vbitset_and_cmp (bitset dst, bitset src1, bitset src2) |
| 528 { |
| 529 unsigned int i; |
| 530 int changed = 0; |
| 531 bitset_word *src1p; |
| 532 bitset_word *src2p; |
| 533 bitset_word *dstp; |
| 534 bitset_windex ssize1; |
| 535 bitset_windex ssize2; |
| 536 bitset_windex dsize; |
| 537 |
| 538 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); |
| 539 |
| 540 dsize = VBITSET_SIZE (dst); |
| 541 ssize1 = VBITSET_SIZE (src1); |
| 542 ssize2 = VBITSET_SIZE (src2); |
| 543 dstp = VBITSET_WORDS (dst); |
| 544 src1p = VBITSET_WORDS (src1); |
| 545 src2p = VBITSET_WORDS (src2); |
| 546 |
| 547 for (i = 0; i < min (ssize1, ssize2); i++, dstp++) |
| 548 { |
| 549 bitset_word tmp = *src1p++ & *src2p++; |
| 550 |
| 551 if (*dstp != tmp) |
| 552 { |
| 553 changed = 1; |
| 554 *dstp = tmp; |
| 555 } |
| 556 } |
| 557 |
| 558 if (ssize2 > ssize1) |
| 559 { |
| 560 src1p = src2p; |
| 561 ssize1 = ssize2; |
| 562 } |
| 563 |
| 564 for (; i < ssize1; i++, dstp++) |
| 565 { |
| 566 if (*dstp != 0) |
| 567 { |
| 568 changed = 1; |
| 569 *dstp = 0; |
| 570 } |
| 571 } |
| 572 |
| 573 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); |
| 574 |
| 575 return changed; |
| 576 } |
| 577 |
| 578 |
| 579 static void |
| 580 vbitset_andn (bitset dst, bitset src1, bitset src2) |
| 581 { |
| 582 unsigned int i; |
| 583 bitset_word *src1p; |
| 584 bitset_word *src2p; |
| 585 bitset_word *dstp; |
| 586 bitset_windex ssize1; |
| 587 bitset_windex ssize2; |
| 588 bitset_windex dsize; |
| 589 |
| 590 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); |
| 591 |
| 592 dsize = VBITSET_SIZE (dst); |
| 593 ssize1 = VBITSET_SIZE (src1); |
| 594 ssize2 = VBITSET_SIZE (src2); |
| 595 dstp = VBITSET_WORDS (dst); |
| 596 src1p = VBITSET_WORDS (src1); |
| 597 src2p = VBITSET_WORDS (src2); |
| 598 |
| 599 for (i = 0; i < min (ssize1, ssize2); i++) |
| 600 *dstp++ = *src1p++ & ~(*src2p++); |
| 601 |
| 602 if (ssize2 > ssize1) |
| 603 { |
| 604 for (; i < ssize2; i++) |
| 605 *dstp++ = 0; |
| 606 |
| 607 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2)); |
| 608 } |
| 609 else |
| 610 { |
| 611 for (; i < ssize1; i++) |
| 612 *dstp++ = *src1p++; |
| 613 |
| 614 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); |
| 615 } |
| 616 } |
| 617 |
| 618 |
| 619 static bool |
| 620 vbitset_andn_cmp (bitset dst, bitset src1, bitset src2) |
| 621 { |
| 622 unsigned int i; |
| 623 int changed = 0; |
| 624 bitset_word *src1p; |
| 625 bitset_word *src2p; |
| 626 bitset_word *dstp; |
| 627 bitset_windex ssize1; |
| 628 bitset_windex ssize2; |
| 629 bitset_windex dsize; |
| 630 |
| 631 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); |
| 632 |
| 633 dsize = VBITSET_SIZE (dst); |
| 634 ssize1 = VBITSET_SIZE (src1); |
| 635 ssize2 = VBITSET_SIZE (src2); |
| 636 dstp = VBITSET_WORDS (dst); |
| 637 src1p = VBITSET_WORDS (src1); |
| 638 src2p = VBITSET_WORDS (src2); |
| 639 |
| 640 for (i = 0; i < min (ssize1, ssize2); i++, dstp++) |
| 641 { |
| 642 bitset_word tmp = *src1p++ & ~(*src2p++); |
| 643 |
| 644 if (*dstp != tmp) |
| 645 { |
| 646 changed = 1; |
| 647 *dstp = tmp; |
| 648 } |
| 649 } |
| 650 |
| 651 if (ssize2 > ssize1) |
| 652 { |
| 653 for (; i < ssize2; i++, dstp++) |
| 654 { |
| 655 if (*dstp != 0) |
| 656 { |
| 657 changed = 1; |
| 658 *dstp = 0; |
| 659 } |
| 660 } |
| 661 |
| 662 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2)); |
| 663 } |
| 664 else |
| 665 { |
| 666 for (; i < ssize1; i++, dstp++) |
| 667 { |
| 668 bitset_word tmp = *src1p++; |
| 669 |
| 670 if (*dstp != tmp) |
| 671 { |
| 672 changed = 1; |
| 673 *dstp = tmp; |
| 674 } |
| 675 } |
| 676 |
| 677 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); |
| 678 } |
| 679 |
| 680 return changed; |
| 681 } |
| 682 |
| 683 |
| 684 static void |
| 685 vbitset_or (bitset dst, bitset src1, bitset src2) |
| 686 { |
| 687 unsigned int i; |
| 688 bitset_word *src1p; |
| 689 bitset_word *src2p; |
| 690 bitset_word *dstp; |
| 691 bitset_windex ssize1; |
| 692 bitset_windex ssize2; |
| 693 bitset_windex dsize; |
| 694 |
| 695 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); |
| 696 |
| 697 dsize = VBITSET_SIZE (dst); |
| 698 ssize1 = VBITSET_SIZE (src1); |
| 699 ssize2 = VBITSET_SIZE (src2); |
| 700 dstp = VBITSET_WORDS (dst); |
| 701 src1p = VBITSET_WORDS (src1); |
| 702 src2p = VBITSET_WORDS (src2); |
| 703 |
| 704 for (i = 0; i < min (ssize1, ssize2); i++) |
| 705 *dstp++ = *src1p++ | *src2p++; |
| 706 |
| 707 if (ssize2 > ssize1) |
| 708 { |
| 709 src1p = src2p; |
| 710 ssize1 = ssize2; |
| 711 } |
| 712 |
| 713 for (; i < ssize1; i++) |
| 714 *dstp++ = *src1p++; |
| 715 |
| 716 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); |
| 717 } |
| 718 |
| 719 |
| 720 static bool |
| 721 vbitset_or_cmp (bitset dst, bitset src1, bitset src2) |
| 722 { |
| 723 unsigned int i; |
| 724 int changed = 0; |
| 725 bitset_word *src1p; |
| 726 bitset_word *src2p; |
| 727 bitset_word *dstp; |
| 728 bitset_windex ssize1; |
| 729 bitset_windex ssize2; |
| 730 bitset_windex dsize; |
| 731 |
| 732 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); |
| 733 |
| 734 dsize = VBITSET_SIZE (dst); |
| 735 ssize1 = VBITSET_SIZE (src1); |
| 736 ssize2 = VBITSET_SIZE (src2); |
| 737 dstp = VBITSET_WORDS (dst); |
| 738 src1p = VBITSET_WORDS (src1); |
| 739 src2p = VBITSET_WORDS (src2); |
| 740 |
| 741 for (i = 0; i < min (ssize1, ssize2); i++, dstp++) |
| 742 { |
| 743 bitset_word tmp = *src1p++ | *src2p++; |
| 744 |
| 745 if (*dstp != tmp) |
| 746 { |
| 747 changed = 1; |
| 748 *dstp = tmp; |
| 749 } |
| 750 } |
| 751 |
| 752 if (ssize2 > ssize1) |
| 753 { |
| 754 src1p = src2p; |
| 755 ssize1 = ssize2; |
| 756 } |
| 757 |
| 758 for (; i < ssize1; i++, dstp++) |
| 759 { |
| 760 bitset_word tmp = *src1p++; |
| 761 |
| 762 if (*dstp != tmp) |
| 763 { |
| 764 changed = 1; |
| 765 *dstp = tmp; |
| 766 } |
| 767 } |
| 768 |
| 769 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); |
| 770 |
| 771 return changed; |
| 772 } |
| 773 |
| 774 |
| 775 static void |
| 776 vbitset_xor (bitset dst, bitset src1, bitset src2) |
| 777 { |
| 778 unsigned int i; |
| 779 bitset_word *src1p; |
| 780 bitset_word *src2p; |
| 781 bitset_word *dstp; |
| 782 bitset_windex ssize1; |
| 783 bitset_windex ssize2; |
| 784 bitset_windex dsize; |
| 785 |
| 786 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); |
| 787 |
| 788 dsize = VBITSET_SIZE (dst); |
| 789 ssize1 = VBITSET_SIZE (src1); |
| 790 ssize2 = VBITSET_SIZE (src2); |
| 791 dstp = VBITSET_WORDS (dst); |
| 792 src1p = VBITSET_WORDS (src1); |
| 793 src2p = VBITSET_WORDS (src2); |
| 794 |
| 795 for (i = 0; i < min (ssize1, ssize2); i++) |
| 796 *dstp++ = *src1p++ ^ *src2p++; |
| 797 |
| 798 if (ssize2 > ssize1) |
| 799 { |
| 800 src1p = src2p; |
| 801 ssize1 = ssize2; |
| 802 } |
| 803 |
| 804 for (; i < ssize1; i++) |
| 805 *dstp++ = *src1p++; |
| 806 |
| 807 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); |
| 808 } |
| 809 |
| 810 |
| 811 static bool |
| 812 vbitset_xor_cmp (bitset dst, bitset src1, bitset src2) |
| 813 { |
| 814 unsigned int i; |
| 815 int changed = 0; |
| 816 bitset_word *src1p; |
| 817 bitset_word *src2p; |
| 818 bitset_word *dstp; |
| 819 bitset_windex ssize1; |
| 820 bitset_windex ssize2; |
| 821 bitset_windex dsize; |
| 822 |
| 823 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); |
| 824 |
| 825 dsize = VBITSET_SIZE (dst); |
| 826 ssize1 = VBITSET_SIZE (src1); |
| 827 ssize2 = VBITSET_SIZE (src2); |
| 828 dstp = VBITSET_WORDS (dst); |
| 829 src1p = VBITSET_WORDS (src1); |
| 830 src2p = VBITSET_WORDS (src2); |
| 831 |
| 832 for (i = 0; i < min (ssize1, ssize2); i++, dstp++) |
| 833 { |
| 834 bitset_word tmp = *src1p++ ^ *src2p++; |
| 835 |
| 836 if (*dstp != tmp) |
| 837 { |
| 838 changed = 1; |
| 839 *dstp = tmp; |
| 840 } |
| 841 } |
| 842 |
| 843 if (ssize2 > ssize1) |
| 844 { |
| 845 src1p = src2p; |
| 846 ssize1 = ssize2; |
| 847 } |
| 848 |
| 849 for (; i < ssize1; i++, dstp++) |
| 850 { |
| 851 bitset_word tmp = *src1p++; |
| 852 |
| 853 if (*dstp != tmp) |
| 854 { |
| 855 changed = 1; |
| 856 *dstp = tmp; |
| 857 } |
| 858 } |
| 859 |
| 860 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); |
| 861 |
| 862 return changed; |
| 863 } |
| 864 |
| 865 |
| 866 /* FIXME, these operations need fixing for different size |
| 867 bitsets. */ |
| 868 |
| 869 static void |
| 870 vbitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3) |
| 871 { |
| 872 unsigned int i; |
| 873 bitset_word *src1p; |
| 874 bitset_word *src2p; |
| 875 bitset_word *src3p; |
| 876 bitset_word *dstp; |
| 877 bitset_windex size; |
| 878 |
| 879 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) |
| 880 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) |
| 881 { |
| 882 bitset_and_or_ (dst, src1, src2, src3); |
| 883 return; |
| 884 } |
| 885 |
| 886 vbitset_resize (dst, BITSET_NBITS_ (src1)); |
| 887 |
| 888 src1p = VBITSET_WORDS (src1); |
| 889 src2p = VBITSET_WORDS (src2); |
| 890 src3p = VBITSET_WORDS (src3); |
| 891 dstp = VBITSET_WORDS (dst); |
| 892 size = VBITSET_SIZE (dst); |
| 893 |
| 894 for (i = 0; i < size; i++) |
| 895 *dstp++ = (*src1p++ & *src2p++) | *src3p++; |
| 896 } |
| 897 |
| 898 |
| 899 static bool |
| 900 vbitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) |
| 901 { |
| 902 unsigned int i; |
| 903 int changed = 0; |
| 904 bitset_word *src1p; |
| 905 bitset_word *src2p; |
| 906 bitset_word *src3p; |
| 907 bitset_word *dstp; |
| 908 bitset_windex size; |
| 909 |
| 910 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) |
| 911 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) |
| 912 return bitset_and_or_cmp_ (dst, src1, src2, src3); |
| 913 |
| 914 vbitset_resize (dst, BITSET_NBITS_ (src1)); |
| 915 |
| 916 src1p = VBITSET_WORDS (src1); |
| 917 src2p = VBITSET_WORDS (src2); |
| 918 src3p = VBITSET_WORDS (src3); |
| 919 dstp = VBITSET_WORDS (dst); |
| 920 size = VBITSET_SIZE (dst); |
| 921 |
| 922 for (i = 0; i < size; i++, dstp++) |
| 923 { |
| 924 bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; |
| 925 |
| 926 if (*dstp != tmp) |
| 927 { |
| 928 changed = 1; |
| 929 *dstp = tmp; |
| 930 } |
| 931 } |
| 932 return changed; |
| 933 } |
| 934 |
| 935 |
| 936 static void |
| 937 vbitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3) |
| 938 { |
| 939 unsigned int i; |
| 940 bitset_word *src1p; |
| 941 bitset_word *src2p; |
| 942 bitset_word *src3p; |
| 943 bitset_word *dstp; |
| 944 bitset_windex size; |
| 945 |
| 946 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) |
| 947 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) |
| 948 { |
| 949 bitset_andn_or_ (dst, src1, src2, src3); |
| 950 return; |
| 951 } |
| 952 |
| 953 vbitset_resize (dst, BITSET_NBITS_ (src1)); |
| 954 |
| 955 src1p = VBITSET_WORDS (src1); |
| 956 src2p = VBITSET_WORDS (src2); |
| 957 src3p = VBITSET_WORDS (src3); |
| 958 dstp = VBITSET_WORDS (dst); |
| 959 size = VBITSET_SIZE (dst); |
| 960 |
| 961 for (i = 0; i < size; i++) |
| 962 *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++; |
| 963 } |
| 964 |
| 965 |
| 966 static bool |
| 967 vbitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) |
| 968 { |
| 969 unsigned int i; |
| 970 int changed = 0; |
| 971 bitset_word *src1p; |
| 972 bitset_word *src2p; |
| 973 bitset_word *src3p; |
| 974 bitset_word *dstp; |
| 975 bitset_windex size; |
| 976 |
| 977 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) |
| 978 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) |
| 979 return bitset_andn_or_cmp_ (dst, src1, src2, src3); |
| 980 |
| 981 vbitset_resize (dst, BITSET_NBITS_ (src1)); |
| 982 |
| 983 src1p = VBITSET_WORDS (src1); |
| 984 src2p = VBITSET_WORDS (src2); |
| 985 src3p = VBITSET_WORDS (src3); |
| 986 dstp = VBITSET_WORDS (dst); |
| 987 size = VBITSET_SIZE (dst); |
| 988 |
| 989 for (i = 0; i < size; i++, dstp++) |
| 990 { |
| 991 bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; |
| 992 |
| 993 if (*dstp != tmp) |
| 994 { |
| 995 changed = 1; |
| 996 *dstp = tmp; |
| 997 } |
| 998 } |
| 999 return changed; |
| 1000 } |
| 1001 |
| 1002 |
| 1003 static void |
| 1004 vbitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3) |
| 1005 { |
| 1006 unsigned int i; |
| 1007 bitset_word *src1p; |
| 1008 bitset_word *src2p; |
| 1009 bitset_word *src3p; |
| 1010 bitset_word *dstp; |
| 1011 bitset_windex size; |
| 1012 |
| 1013 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) |
| 1014 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) |
| 1015 { |
| 1016 bitset_or_and_ (dst, src1, src2, src3); |
| 1017 return; |
| 1018 } |
| 1019 |
| 1020 vbitset_resize (dst, BITSET_NBITS_ (src1)); |
| 1021 |
| 1022 src1p = VBITSET_WORDS (src1); |
| 1023 src2p = VBITSET_WORDS (src2); |
| 1024 src3p = VBITSET_WORDS (src3); |
| 1025 dstp = VBITSET_WORDS (dst); |
| 1026 size = VBITSET_SIZE (dst); |
| 1027 |
| 1028 for (i = 0; i < size; i++) |
| 1029 *dstp++ = (*src1p++ | *src2p++) & *src3p++; |
| 1030 } |
| 1031 |
| 1032 |
| 1033 static bool |
| 1034 vbitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3) |
| 1035 { |
| 1036 unsigned int i; |
| 1037 int changed = 0; |
| 1038 bitset_word *src1p; |
| 1039 bitset_word *src2p; |
| 1040 bitset_word *src3p; |
| 1041 bitset_word *dstp; |
| 1042 bitset_windex size; |
| 1043 |
| 1044 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) |
| 1045 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) |
| 1046 return bitset_or_and_cmp_ (dst, src1, src2, src3); |
| 1047 |
| 1048 vbitset_resize (dst, BITSET_NBITS_ (src1)); |
| 1049 |
| 1050 src1p = VBITSET_WORDS (src1); |
| 1051 src2p = VBITSET_WORDS (src2); |
| 1052 src3p = VBITSET_WORDS (src3); |
| 1053 dstp = VBITSET_WORDS (dst); |
| 1054 size = VBITSET_SIZE (dst); |
| 1055 |
| 1056 for (i = 0; i < size; i++, dstp++) |
| 1057 { |
| 1058 bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; |
| 1059 |
| 1060 if (*dstp != tmp) |
| 1061 { |
| 1062 changed = 1; |
| 1063 *dstp = tmp; |
| 1064 } |
| 1065 } |
| 1066 return changed; |
| 1067 } |
| 1068 |
| 1069 |
| 1070 static void |
| 1071 vbitset_copy (bitset dst, bitset src) |
| 1072 { |
| 1073 if (BITSET_COMPATIBLE_ (dst, src)) |
| 1074 vbitset_copy1 (dst, src); |
| 1075 else |
| 1076 bitset_copy_ (dst, src); |
| 1077 } |
| 1078 |
| 1079 |
| 1080 /* Vector of operations for multiple word bitsets. */ |
| 1081 struct bitset_vtable vbitset_vtable = { |
| 1082 vbitset_set, |
| 1083 vbitset_reset, |
| 1084 bitset_toggle_, |
| 1085 vbitset_test, |
| 1086 vbitset_resize, |
| 1087 bitset_size_, |
| 1088 bitset_count_, |
| 1089 vbitset_empty_p, |
| 1090 vbitset_ones, |
| 1091 vbitset_zero, |
| 1092 vbitset_copy, |
| 1093 vbitset_disjoint_p, |
| 1094 vbitset_equal_p, |
| 1095 vbitset_not, |
| 1096 vbitset_subset_p, |
| 1097 vbitset_and, |
| 1098 vbitset_and_cmp, |
| 1099 vbitset_andn, |
| 1100 vbitset_andn_cmp, |
| 1101 vbitset_or, |
| 1102 vbitset_or_cmp, |
| 1103 vbitset_xor, |
| 1104 vbitset_xor_cmp, |
| 1105 vbitset_and_or, |
| 1106 vbitset_and_or_cmp, |
| 1107 vbitset_andn_or, |
| 1108 vbitset_andn_or_cmp, |
| 1109 vbitset_or_and, |
| 1110 vbitset_or_and_cmp, |
| 1111 vbitset_list, |
| 1112 vbitset_list_reverse, |
| 1113 NULL, |
| 1114 BITSET_VARRAY |
| 1115 }; |
| 1116 |
| 1117 |
| 1118 size_t |
| 1119 vbitset_bytes (n_bits) |
| 1120 bitset_bindex n_bits ATTRIBUTE_UNUSED; |
| 1121 { |
| 1122 return sizeof (struct vbitset_struct); |
| 1123 } |
| 1124 |
| 1125 |
| 1126 bitset |
| 1127 vbitset_init (bset, n_bits) |
| 1128 bitset bset; |
| 1129 bitset_bindex n_bits; |
| 1130 { |
| 1131 bset->b.vtable = &vbitset_vtable; |
| 1132 |
| 1133 bset->b.cindex = 0; |
| 1134 |
| 1135 VBITSET_SIZE (bset) = 0; |
| 1136 vbitset_resize (bset, n_bits); |
| 1137 return bset; |
| 1138 } |
OLD | NEW |