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