lib/sbitset.c

   1 /* Simple bitsets.
   2    Copyright (C) 2002 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 2 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, write to the Free Software
  17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18 */
  19
  20 #ifdef HAVE_CONFIG_H
  21 #include "config.h"
  22 #endif
  23
  24 #include "sbitset.h"
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 /* This file implements fixed size bitsets stored as an array
  29    of words.  Any unused bits in the last word must be zero.  */
  30
  31 typedef struct sbitset_struct
  32 {
  33   unsigned int n_bits;  /* Number of bits.  */
  34   bitset_word words[1]; /* The array of bits.  */
  35 }
  36 *sbitset;
  37
  38
  39 struct bitset_struct
  40 {
  41   struct bbitset_struct b;
  42   struct sbitset_struct s;
  43 };
  44
  45 static void sbitset_unused_clear PARAMS ((bitset));
  46
  47 static int sbitset_small_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
  48                                        bitset_bindex *));
  49
  50 static void sbitset_set PARAMS ((bitset, bitset_bindex));
  51 static void sbitset_reset PARAMS ((bitset, bitset_bindex));
  52 static int sbitset_test PARAMS ((bitset, bitset_bindex));
  53 static int sbitset_size PARAMS ((bitset));
  54 static int sbitset_op1 PARAMS ((bitset, enum bitset_ops));
  55 static int sbitset_op2 PARAMS ((bitset, bitset, enum bitset_ops));
  56 static int sbitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
  57 static int sbitset_op4 PARAMS ((bitset, bitset, bitset, bitset,
  58                                 enum bitset_ops));
  59 static int sbitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
  60                                  bitset_bindex *));
  61 static int sbitset_reverse_list
  62 PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
  63
  64 #define SBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
  65 #define SBITSET_WORDS(X) ((X)->s.words)
  66 #define SBITSET_N_BITS(X) ((X)->s.n_bits)
  67
  68
  69 /* Return size in bits of bitset SRC.  */
  70 static int
  71 sbitset_size (src)
  72      bitset src;
  73 {
  74   return SBITSET_N_BITS (src);
  75 }
  76
  77
  78 /* Find list of up to NUM bits set in BSET starting from and including
  79  *NEXT and store in array LIST.  Return with actual number of bits
  80  found and with *NEXT indicating where search stopped.  */
  81 static int
  82 sbitset_small_list (src, list, num, next)
  83      bitset src;
  84      bitset_bindex *list;
  85      bitset_bindex num;
  86      bitset_bindex *next;
  87 {
  88   bitset_bindex bitno;
  89   bitset_bindex count;
  90   bitset_windex size;
  91   bitset_word word;
  92
  93   word = SBITSET_WORDS (src)[0];
  94
  95   /* Short circuit common case.  */
  96   if (!word)
  97     return 0;
  98
  99   size = SBITSET_N_BITS (src);
 100   bitno = *next;
 101   if (bitno >= size)
 102     return 0;
 103
 104   word >>= bitno;
 105
 106   /* If num is 1, we could speed things up with a binary search
 107      of the word of interest.  */
 108
 109   if (num >= BITSET_WORD_BITS)
 110     {
 111       for (count = 0; word; bitno++)
 112         {
 113           if (word & 1)
 114             list[count++] = bitno;
 115           word >>= 1;
 116         }
 117     }
 118   else
 119     {
 120       for (count = 0; word; bitno++)
 121         {
 122           if (word & 1)
 123             {
 124               list[count++] = bitno;
 125               if (count >= num)
 126                 {
 127                   bitno++;
 128                   break;
 129                 }
 130             }
 131           word >>= 1;
 132         }
 133     }
 134
 135   *next = bitno;
 136   return count;
 137 }
 138
 139
 140 /* Set bit BITNO in bitset DST.  */
 141 static void
 142 sbitset_set (dst, bitno)
 143      bitset dst ATTRIBUTE_UNUSED;
 144      bitset_bindex bitno ATTRIBUTE_UNUSED;
 145 {
 146   /* This should never occur for sbitsets.  */
 147   abort ();
 148 }
 149
 150
 151 /* Reset bit BITNO in bitset DST.  */
 152 static void
 153 sbitset_reset (dst, bitno)
 154      bitset dst ATTRIBUTE_UNUSED;
 155      bitset_bindex bitno ATTRIBUTE_UNUSED;
 156 {
 157   /* This should never occur for sbitsets.  */
 158   abort ();
 159 }
 160
 161
 162 /* Test bit BITNO in bitset SRC.  */
 163 static int
 164 sbitset_test (src, bitno)
 165      bitset src ATTRIBUTE_UNUSED;
 166      bitset_bindex bitno ATTRIBUTE_UNUSED;
 167 {
 168   /* This should never occur for sbitsets.  */
 169   abort ();
 170   return 0;
 171 }
 172
 173
 174 /* Find list of up to NUM bits set in BSET in reverse order, starting
 175    from and including NEXT and store in array LIST.  Return with
 176    actual number of bits found and with *NEXT indicating where search
 177    stopped.  */
 178 static int
 179 sbitset_reverse_list (src, list, num, next)
 180      bitset src;
 181      bitset_bindex *list;
 182      bitset_bindex num;
 183      bitset_bindex *next;
 184 {
 185   bitset_bindex bitno;
 186   bitset_bindex rbitno;
 187   bitset_bindex count;
 188   bitset_windex windex;
 189   unsigned int bitcnt;
 190   bitset_bindex bitoff;
 191   bitset_word word;
 192   bitset_word *srcp = SBITSET_WORDS (src);
 193   bitset_bindex n_bits = SBITSET_N_BITS (src);
 194
 195   rbitno = *next;
 196
 197   /* If num is 1, we could speed things up with a binary search
 198      of the word of interest.  */
 199
 200   if (rbitno >= n_bits)
 201     return 0;
 202
 203   count = 0;
 204
 205   bitno = n_bits - (rbitno + 1);
 206
 207   windex = bitno / BITSET_WORD_BITS;
 208   bitcnt = bitno % BITSET_WORD_BITS;
 209   bitoff = windex * BITSET_WORD_BITS;
 210
 211   for (; windex != ~0U; windex--, bitoff -= BITSET_WORD_BITS,
 212          bitcnt = BITSET_WORD_BITS - 1)
 213     {
 214       word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
 215       for (; word; bitcnt--)
 216         {
 217           if (word & BITSET_MSB)
 218             {
 219               list[count++] = bitoff + bitcnt;
 220               if (count >= num)
 221                 {
 222                   *next = n_bits - (bitoff + bitcnt);
 223                   return count;
 224                 }
 225             }
 226           word <<= 1;
 227         }
 228     }
 229
 230   *next = n_bits - (bitoff + 1);
 231   return count;
 232 }
 233
 234
 235 /* Find list of up to NUM bits set in BSET starting from and including
 236  *NEXT and store in array LIST.  Return with actual number of bits
 237  found and with *NEXT indicating where search stopped.  */
 238 static int
 239 sbitset_list (src, list, num, next)
 240      bitset src;
 241      bitset_bindex *list;
 242      bitset_bindex num;
 243      bitset_bindex *next;
 244 {
 245   bitset_bindex bitno;
 246   bitset_bindex count;
 247   bitset_windex windex;
 248   bitset_bindex bitoff;
 249   bitset_windex size = src->b.csize;
 250   bitset_word *srcp = SBITSET_WORDS (src);
 251   bitset_word word;
 252
 253   bitno = *next;
 254
 255   count = 0;
 256   if (!bitno)
 257     {
 258       /* Many bitsets are zero, so make this common case fast.  */
 259       for (windex = 0; windex < size && !srcp[windex]; windex++)
 260         continue;
 261       if (windex >= size)
 262         return 0;
 263
 264       /* If num is 1, we could speed things up with a binary search
 265          of the current word.  */
 266
 267       bitoff = windex * BITSET_WORD_BITS;
 268     }
 269   else
 270     {
 271       if (bitno >= SBITSET_N_BITS (src))
 272         return 0;
 273
 274       windex = bitno / BITSET_WORD_BITS;
 275       bitno = bitno % BITSET_WORD_BITS;
 276
 277       if (bitno)
 278         {
 279           /* Handle the case where we start within a word.
 280              Most often, this is executed with large bitsets
 281              with many set bits where we filled the array
 282              on the previous call to this function.  */
 283
 284           bitoff = windex * BITSET_WORD_BITS;
 285           word = srcp[windex] >> bitno;
 286           for (bitno = bitoff + bitno; word; bitno++)
 287             {
 288               if (word & 1)
 289                 {
 290                   list[count++] = bitno;
 291                   if (count >= num)
 292                     {
 293                       *next = bitno + 1;
 294                       return count;
 295                     }
 296                 }
 297               word >>= 1;
 298             }
 299           windex++;
 300         }
 301       bitoff = windex * BITSET_WORD_BITS;
 302     }
 303
 304   for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
 305     {
 306       if (!(word = srcp[windex]))
 307         continue;
 308
 309       if ((count + BITSET_WORD_BITS) < num)
 310         {
 311           for (bitno = bitoff; word; bitno++)
 312             {
 313               if (word & 1)
 314                 list[count++] = bitno;
 315               word >>= 1;
 316             }
 317         }
 318       else
 319         {
 320           for (bitno = bitoff; word; bitno++)
 321             {
 322               if (word & 1)
 323                 {
 324                   list[count++] = bitno;
 325                   if (count >= num)
 326                     {
 327                       *next = bitno + 1;
 328                       return count;
 329                     }
 330                 }
 331               word >>= 1;
 332             }
 333         }
 334     }
 335
 336   *next = bitoff;
 337   return count;
 338 }
 339
 340
 341 /* Ensure that any unused bits within the last word are clear.  */
 342 static inline void
 343 sbitset_unused_clear (dst)
 344      bitset dst;
 345 {
 346   unsigned int last_bit;
 347
 348   last_bit = SBITSET_N_BITS (dst) % BITSET_WORD_BITS;
 349   if (last_bit)
 350     SBITSET_WORDS (dst)[dst->b.csize - 1] &=
 351       (bitset_word) ((1 << last_bit) - 1);
 352 }
 353
 354
 355 static int
 356 sbitset_op1 (dst, op)
 357      bitset dst;
 358      enum bitset_ops op;
 359 {
 360   unsigned int i;
 361   bitset_word *dstp = SBITSET_WORDS (dst);
 362   unsigned int bytes;
 363
 364   bytes = sizeof (bitset_word) * dst->b.csize;
 365
 366   switch (op)
 367     {
 368     case BITSET_OP_ZERO:
 369       memset (dstp, 0, bytes);
 370       break;
 371
 372     case BITSET_OP_ONES:
 373       memset (dstp, ~0, bytes);
 374       sbitset_unused_clear (dst);
 375       break;
 376
 377     case BITSET_OP_EMPTY_P:
 378       for (i = 0; i < dst->b.csize; i++)
 379         if (dstp[i])
 380           return 0;
 381       break;
 382
 383     default:
 384       abort ();
 385     }
 386
 387   return 1;
 388 }
 389
 390
 391 static int
 392 sbitset_op2 (dst, src, op)
 393      bitset dst;
 394      bitset src;
 395      enum bitset_ops op;
 396 {
 397   unsigned int i;
 398   bitset_word *srcp = SBITSET_WORDS (src);
 399   bitset_word *dstp = SBITSET_WORDS (dst);
 400   bitset_windex size = dst->b.csize;
 401
 402 #ifdef ENABLE_CHECKING
 403   /* Check for compatiblity.  */
 404   if (SBITSET_N_BITS (src) != SBITSET_N_BITS (dst))
 405     abort ();
 406 #endif
 407
 408   switch (op)
 409     {
 410     case BITSET_OP_COPY:
 411       if (srcp == dstp)
 412         break;
 413       memcpy (dstp, srcp, sizeof (bitset_word) * size);
 414       break;
 415
 416     case BITSET_OP_NOT:
 417       for (i = 0; i < size; i++)
 418         *dstp++ = ~(*srcp++);
 419       sbitset_unused_clear (dst);
 420       break;
 421
 422     case BITSET_OP_EQUAL_P:
 423       for (i = 0; i < size; i++)
 424         if (*srcp++ != *dstp++)
 425           return 0;
 426       break;
 427
 428     case BITSET_OP_SUBSET_P:
 429       for (i = 0; i < size; i++, dstp++, srcp++)
 430         if (*dstp != (*srcp | *dstp))
 431           return 0;
 432       break;
 433
 434     case BITSET_OP_DISJOINT_P:
 435       for (i = 0; i < size; i++)
 436         if (*srcp++ & *dstp++)
 437           return 0;
 438       break;
 439
 440     default:
 441       abort ();
 442     }
 443
 444   return 1;
 445 }
 446
 447
 448 static int
 449 sbitset_op3 (dst, src1, src2, op)
 450      bitset dst;
 451      bitset src1;
 452      bitset src2;
 453      enum bitset_ops op;
 454 {
 455   unsigned int i;
 456   int changed = 0;
 457   bitset_word *src1p = SBITSET_WORDS (src1);
 458   bitset_word *src2p = SBITSET_WORDS (src2);
 459   bitset_word *dstp = SBITSET_WORDS (dst);
 460   bitset_windex size = dst->b.csize;
 461
 462 #ifdef ENABLE_CHECKING
 463   /* Check for compatiblity.  */
 464   if (SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst)
 465       SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst))
 466     abort ();
 467 #endif
 468
 469   switch (op)
 470     {
 471     case BITSET_OP_OR:
 472       for (i = 0; i < size; i++, dstp++)
 473         {
 474           bitset_word tmp = *src1p++ | *src2p++;
 475
 476           if (*dstp != tmp)
 477             {
 478               changed = 1;
 479               *dstp = tmp;
 480             }
 481         }
 482       break;
 483
 484     case BITSET_OP_AND:
 485       for (i = 0; i < size; i++, dstp++)
 486         {
 487           bitset_word tmp = *src1p++ & *src2p++;
 488
 489           if (*dstp != tmp)
 490             {
 491               changed = 1;
 492               *dstp = tmp;
 493             }
 494         }
 495       break;
 496
 497     case BITSET_OP_XOR:
 498       for (i = 0; i < size; i++, dstp++)
 499         {
 500           bitset_word tmp = *src1p++ ^ *src2p++;
 501
 502           if (*dstp != tmp)
 503             {
 504               changed = 1;
 505               *dstp = tmp;
 506             }
 507         }
 508       break;
 509
 510     case BITSET_OP_ANDN:
 511       for (i = 0; i < size; i++, dstp++)
 512         {
 513           bitset_word tmp = *src1p++ & ~(*src2p++);
 514
 515           if (*dstp != tmp)
 516             {
 517               changed = 1;
 518               *dstp = tmp;
 519             }
 520         }
 521       break;
 522
 523     default:
 524       abort ();
 525     }
 526
 527   return changed;
 528 }
 529
 530
 531 static int
 532 sbitset_op4 (dst, src1, src2, src3, op)
 533      bitset dst;
 534      bitset src1;
 535      bitset src2;
 536      bitset src3;
 537      enum bitset_ops op;
 538 {
 539   unsigned int i;
 540   int changed = 0;
 541   bitset_word *src1p = SBITSET_WORDS (src1);
 542   bitset_word *src2p = SBITSET_WORDS (src2);
 543   bitset_word *src3p = SBITSET_WORDS (src3);
 544   bitset_word *dstp = SBITSET_WORDS (dst);
 545   bitset_windex size = dst->b.csize;
 546
 547 #ifdef ENABLE_CHECKING
 548   /* Check for compatiblity.  */
 549   if (SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst)
 550       || SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst)
 551       || SBITSET_N_BITS (src3) != SBITSET_N_BITS (dst))
 552     abort ();
 553 #endif
 554
 555   switch (op)
 556     {
 557     case BITSET_OP_OR_AND:
 558       for (i = 0; i < size; i++, dstp++)
 559         {
 560           bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
 561
 562           if (*dstp != tmp)
 563             {
 564               changed = 1;
 565               *dstp = tmp;
 566             }
 567         }
 568       break;
 569
 570     case BITSET_OP_AND_OR:
 571       for (i = 0; i < size; i++, dstp++)
 572         {
 573           bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
 574
 575           if (*dstp != tmp)
 576             {
 577               changed = 1;
 578               *dstp = tmp;
 579             }
 580         }
 581       break;
 582
 583     case BITSET_OP_ANDN_OR:
 584       for (i = 0; i < size; i++, dstp++)
 585         {
 586           bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
 587
 588           if (*dstp != tmp)
 589             {
 590               changed = 1;
 591               *dstp = tmp;
 592             }
 593         }
 594       break;
 595
 596     default:
 597       abort ();
 598     }
 599
 600   return changed;
 601 }
 602
 603
 604 /* Vector of operations for single word bitsets.  */
 605 struct bitset_ops_struct sbitset_small_ops = {
 606   sbitset_set,
 607   sbitset_reset,
 608   sbitset_test,
 609   sbitset_size,
 610   sbitset_op1,
 611   sbitset_op2,
 612   sbitset_op3,
 613   sbitset_op4,
 614   sbitset_small_list,
 615   sbitset_reverse_list,
 616   NULL,
 617   BITSET_ARRAY
 618 };
 619
 620
 621 /* Vector of operations for multiple word bitsets.  */
 622 struct bitset_ops_struct sbitset_ops = {
 623   sbitset_set,
 624   sbitset_reset,
 625   sbitset_test,
 626   sbitset_size,
 627   sbitset_op1,
 628   sbitset_op2,
 629   sbitset_op3,
 630   sbitset_op4,
 631   sbitset_list,
 632   sbitset_reverse_list,
 633   NULL,
 634   BITSET_ARRAY
 635 };
 636
 637
 638 int
 639 sbitset_bytes (n_bits)
 640      bitset_bindex n_bits;
 641 {
 642   unsigned int bytes, size;
 643
 644   size = SBITSET_N_WORDS (n_bits);
 645   bytes = size * sizeof (bitset_word);
 646   return sizeof (struct bitset_struct) + bytes - sizeof (bitset_word);
 647 }
 648
 649
 650 bitset
 651 sbitset_init (bset, n_bits)
 652      bitset bset;
 653      bitset_bindex n_bits;
 654 {
 655   bitset_windex size;
 656
 657   size = SBITSET_N_WORDS (n_bits);
 658   SBITSET_N_BITS (bset) = n_bits;
 659
 660   /* Use optimized routines if bitset fits within a single word.
 661      There is probably little merit if using caching since
 662      the small bitset will always fit in the cache.  */
 663   if (size == 1)
 664     bset->b.ops = &sbitset_small_ops;
 665   else
 666     bset->b.ops = &sbitset_ops;
 667
 668   bset->b.cindex = 0;
 669   bset->b.csize = size;
 670   bset->b.cdata = SBITSET_WORDS (bset);
 671   return bset;
 672 }