lib/abitset.c

   1 /* Array 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 "abitset.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 abitset_struct
  32 {
  33   unsigned int n_bits;  /* Number of bits.  */
  34   bitset_word words[1]; /* The array of bits.  */
  35 }
  36 *abitset;
  37
  38
  39 struct bitset_struct
  40 {
  41   struct bbitset_struct b;
  42   struct abitset_struct a;
  43 };
  44
  45 static void abitset_unused_clear PARAMS ((bitset));
  46
  47 static int abitset_small_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
  48                                        bitset_bindex *));
  49
  50 static void abitset_set PARAMS ((bitset, bitset_bindex));
  51 static void abitset_reset PARAMS ((bitset, bitset_bindex));
  52 static int abitset_test PARAMS ((bitset, bitset_bindex));
  53 static int abitset_size PARAMS ((bitset));
  54 static int abitset_op1 PARAMS ((bitset, enum bitset_ops));
  55 static int abitset_op2 PARAMS ((bitset, bitset, enum bitset_ops));
  56 static int abitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
  57 static int abitset_op4 PARAMS ((bitset, bitset, bitset, bitset,
  58                                 enum bitset_ops));
  59 static int abitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
  60                                  bitset_bindex *));
  61 static int abitset_reverse_list
  62 PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
  63
  64 #define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
  65 #define ABITSET_WORDS(X) ((X)->a.words)
  66 #define ABITSET_N_BITS(X) ((X)->a.n_bits)
  67
  68
  69 /* Return size in bits of bitset SRC.  */
  70 static int
  71 abitset_size (src)
  72      bitset src;
  73 {
  74   return ABITSET_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 abitset_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 = ABITSET_WORDS (src)[0];
  94
  95   /* Short circuit common case.  */
  96   if (!word)
  97     return 0;
  98
  99   size = ABITSET_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 abitset_set (dst, bitno)
 143      bitset dst ATTRIBUTE_UNUSED;
 144      bitset_bindex bitno ATTRIBUTE_UNUSED;
 145 {
 146   /* This should never occur for abitsets.  */
 147   abort ();
 148 }
 149
 150
 151 /* Reset bit BITNO in bitset DST.  */
 152 static void
 153 abitset_reset (dst, bitno)
 154      bitset dst ATTRIBUTE_UNUSED;
 155      bitset_bindex bitno ATTRIBUTE_UNUSED;
 156 {
 157   /* This should never occur for abitsets.  */
 158   abort ();
 159 }
 160
 161
 162 /* Test bit BITNO in bitset SRC.  */
 163 static int
 164 abitset_test (src, bitno)
 165      bitset src ATTRIBUTE_UNUSED;
 166      bitset_bindex bitno ATTRIBUTE_UNUSED;
 167 {
 168   /* This should never occur for abitsets.  */
 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 abitset_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 = ABITSET_WORDS (src);
 193   bitset_bindex n_bits = ABITSET_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   do
 212     {
 213       word = srcp[windex] << (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       bitoff -= BITSET_WORD_BITS;
 228       bitcnt = BITSET_WORD_BITS - 1;
 229     }
 230   while (windex--);
 231
 232   *next = n_bits - (bitoff + 1);
 233   return count;
 234 }
 235
 236
 237 /* Find list of up to NUM bits set in BSET starting from and including
 238  *NEXT and store in array LIST.  Return with actual number of bits
 239  found and with *NEXT indicating where search stopped.  */
 240 static int
 241 abitset_list (src, list, num, next)
 242      bitset src;
 243      bitset_bindex *list;
 244      bitset_bindex num;
 245      bitset_bindex *next;
 246 {
 247   bitset_bindex bitno;
 248   bitset_bindex count;
 249   bitset_windex windex;
 250   bitset_bindex bitoff;
 251   bitset_windex size = src->b.csize;
 252   bitset_word *srcp = ABITSET_WORDS (src);
 253   bitset_word word;
 254
 255   bitno = *next;
 256
 257   count = 0;
 258   if (!bitno)
 259     {
 260       /* Many bitsets are zero, so make this common case fast.  */
 261       for (windex = 0; windex < size && !srcp[windex]; windex++)
 262         continue;
 263       if (windex >= size)
 264         return 0;
 265
 266       /* If num is 1, we could speed things up with a binary search
 267          of the current word.  */
 268
 269       bitoff = windex * BITSET_WORD_BITS;
 270     }
 271   else
 272     {
 273       if (bitno >= ABITSET_N_BITS (src))
 274         return 0;
 275
 276       windex = bitno / BITSET_WORD_BITS;
 277       bitno = bitno % BITSET_WORD_BITS;
 278
 279       if (bitno)
 280         {
 281           /* Handle the case where we start within a word.
 282              Most often, this is executed with large bitsets
 283              with many set bits where we filled the array
 284              on the previous call to this function.  */
 285
 286           bitoff = windex * BITSET_WORD_BITS;
 287           word = srcp[windex] >> bitno;
 288           for (bitno = bitoff + bitno; word; bitno++)
 289             {
 290               if (word & 1)
 291                 {
 292                   list[count++] = bitno;
 293                   if (count >= num)
 294                     {
 295                       *next = bitno + 1;
 296                       return count;
 297                     }
 298                 }
 299               word >>= 1;
 300             }
 301           windex++;
 302         }
 303       bitoff = windex * BITSET_WORD_BITS;
 304     }
 305
 306   for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
 307     {
 308       if (!(word = srcp[windex]))
 309         continue;
 310
 311       if ((count + BITSET_WORD_BITS) < num)
 312         {
 313           for (bitno = bitoff; word; bitno++)
 314             {
 315               if (word & 1)
 316                 list[count++] = bitno;
 317               word >>= 1;
 318             }
 319         }
 320       else
 321         {
 322           for (bitno = bitoff; word; bitno++)
 323             {
 324               if (word & 1)
 325                 {
 326                   list[count++] = bitno;
 327                   if (count >= num)
 328                     {
 329                       *next = bitno + 1;
 330                       return count;
 331                     }
 332                 }
 333               word >>= 1;
 334             }
 335         }
 336     }
 337
 338   *next = bitoff;
 339   return count;
 340 }
 341
 342
 343 /* Ensure that any unused bits within the last word are clear.  */
 344 static inline void
 345 abitset_unused_clear (dst)
 346      bitset dst;
 347 {
 348   unsigned int last_bit;
 349
 350   last_bit = ABITSET_N_BITS (dst) % BITSET_WORD_BITS;
 351   if (last_bit)
 352     ABITSET_WORDS (dst)[dst->b.csize - 1] &=
 353       ((bitset_word) 1 << last_bit) - 1;
 354 }
 355
 356
 357 static int
 358 abitset_op1 (dst, op)
 359      bitset dst;
 360      enum bitset_ops op;
 361 {
 362   unsigned int i;
 363   bitset_word *dstp = ABITSET_WORDS (dst);
 364   unsigned int bytes;
 365
 366   bytes = sizeof (bitset_word) * dst->b.csize;
 367
 368   switch (op)
 369     {
 370     case BITSET_OP_ZERO:
 371       memset (dstp, 0, bytes);
 372       break;
 373
 374     case BITSET_OP_ONES:
 375       memset (dstp, -1, bytes);
 376       abitset_unused_clear (dst);
 377       break;
 378
 379     case BITSET_OP_EMPTY_P:
 380       for (i = 0; i < dst->b.csize; i++)
 381         if (dstp[i])
 382           return 0;
 383       break;
 384
 385     default:
 386       abort ();
 387     }
 388
 389   return 1;
 390 }
 391
 392
 393 static int
 394 abitset_op2 (dst, src, op)
 395      bitset dst;
 396      bitset src;
 397      enum bitset_ops op;
 398 {
 399   unsigned int i;
 400   bitset_word *srcp = ABITSET_WORDS (src);
 401   bitset_word *dstp = ABITSET_WORDS (dst);
 402   bitset_windex size = dst->b.csize;
 403
 404   switch (op)
 405     {
 406     case BITSET_OP_COPY:
 407       if (srcp == dstp)
 408         break;
 409       memcpy (dstp, srcp, sizeof (bitset_word) * size);
 410       break;
 411
 412     case BITSET_OP_NOT:
 413       for (i = 0; i < size; i++)
 414         *dstp++ = ~(*srcp++);
 415       abitset_unused_clear (dst);
 416       break;
 417
 418     case BITSET_OP_EQUAL_P:
 419       for (i = 0; i < size; i++)
 420         if (*srcp++ != *dstp++)
 421           return 0;
 422       break;
 423
 424     case BITSET_OP_SUBSET_P:
 425       for (i = 0; i < size; i++, dstp++, srcp++)
 426         if (*dstp != (*srcp | *dstp))
 427           return 0;
 428       break;
 429
 430     case BITSET_OP_DISJOINT_P:
 431       for (i = 0; i < size; i++)
 432         if (*srcp++ & *dstp++)
 433           return 0;
 434       break;
 435
 436     default:
 437       abort ();
 438     }
 439
 440   return 1;
 441 }
 442
 443
 444 static int
 445 abitset_op3 (dst, src1, src2, op)
 446      bitset dst;
 447      bitset src1;
 448      bitset src2;
 449      enum bitset_ops op;
 450 {
 451   unsigned int i;
 452   int changed = 0;
 453   bitset_word *src1p = ABITSET_WORDS (src1);
 454   bitset_word *src2p = ABITSET_WORDS (src2);
 455   bitset_word *dstp = ABITSET_WORDS (dst);
 456   bitset_windex size = dst->b.csize;
 457
 458   switch (op)
 459     {
 460     case BITSET_OP_OR:
 461       for (i = 0; i < size; i++, dstp++)
 462         {
 463           bitset_word tmp = *src1p++ | *src2p++;
 464
 465           if (*dstp != tmp)
 466             {
 467               changed = 1;
 468               *dstp = tmp;
 469             }
 470         }
 471       break;
 472
 473     case BITSET_OP_AND:
 474       for (i = 0; i < size; i++, dstp++)
 475         {
 476           bitset_word tmp = *src1p++ & *src2p++;
 477
 478           if (*dstp != tmp)
 479             {
 480               changed = 1;
 481               *dstp = tmp;
 482             }
 483         }
 484       break;
 485
 486     case BITSET_OP_XOR:
 487       for (i = 0; i < size; i++, dstp++)
 488         {
 489           bitset_word tmp = *src1p++ ^ *src2p++;
 490
 491           if (*dstp != tmp)
 492             {
 493               changed = 1;
 494               *dstp = tmp;
 495             }
 496         }
 497       break;
 498
 499     case BITSET_OP_ANDN:
 500       for (i = 0; i < size; i++, dstp++)
 501         {
 502           bitset_word tmp = *src1p++ & ~(*src2p++);
 503
 504           if (*dstp != tmp)
 505             {
 506               changed = 1;
 507               *dstp = tmp;
 508             }
 509         }
 510       break;
 511
 512     default:
 513       abort ();
 514     }
 515
 516   return changed;
 517 }
 518
 519
 520 static int
 521 abitset_op4 (dst, src1, src2, src3, op)
 522      bitset dst;
 523      bitset src1;
 524      bitset src2;
 525      bitset src3;
 526      enum bitset_ops op;
 527 {
 528   unsigned int i;
 529   int changed = 0;
 530   bitset_word *src1p = ABITSET_WORDS (src1);
 531   bitset_word *src2p = ABITSET_WORDS (src2);
 532   bitset_word *src3p = ABITSET_WORDS (src3);
 533   bitset_word *dstp = ABITSET_WORDS (dst);
 534   bitset_windex size = dst->b.csize;
 535
 536   switch (op)
 537     {
 538     case BITSET_OP_OR_AND:
 539       for (i = 0; i < size; i++, dstp++)
 540         {
 541           bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
 542
 543           if (*dstp != tmp)
 544             {
 545               changed = 1;
 546               *dstp = tmp;
 547             }
 548         }
 549       break;
 550
 551     case BITSET_OP_AND_OR:
 552       for (i = 0; i < size; i++, dstp++)
 553         {
 554           bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
 555
 556           if (*dstp != tmp)
 557             {
 558               changed = 1;
 559               *dstp = tmp;
 560             }
 561         }
 562       break;
 563
 564     case BITSET_OP_ANDN_OR:
 565       for (i = 0; i < size; i++, dstp++)
 566         {
 567           bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
 568
 569           if (*dstp != tmp)
 570             {
 571               changed = 1;
 572               *dstp = tmp;
 573             }
 574         }
 575       break;
 576
 577     default:
 578       abort ();
 579     }
 580
 581   return changed;
 582 }
 583
 584
 585 /* Vector of operations for single word bitsets.  */
 586 struct bitset_ops_struct abitset_small_ops = {
 587   abitset_set,
 588   abitset_reset,
 589   abitset_test,
 590   abitset_size,
 591   abitset_op1,
 592   abitset_op2,
 593   abitset_op3,
 594   abitset_op4,
 595   abitset_small_list,
 596   abitset_reverse_list,
 597   NULL,
 598   BITSET_ARRAY
 599 };
 600
 601
 602 /* Vector of operations for multiple word bitsets.  */
 603 struct bitset_ops_struct abitset_ops = {
 604   abitset_set,
 605   abitset_reset,
 606   abitset_test,
 607   abitset_size,
 608   abitset_op1,
 609   abitset_op2,
 610   abitset_op3,
 611   abitset_op4,
 612   abitset_list,
 613   abitset_reverse_list,
 614   NULL,
 615   BITSET_ARRAY
 616 };
 617
 618
 619 int
 620 abitset_bytes (n_bits)
 621      bitset_bindex n_bits;
 622 {
 623   unsigned int bytes, size;
 624
 625   size = ABITSET_N_WORDS (n_bits);
 626   bytes = size * sizeof (bitset_word);
 627   return sizeof (struct bitset_struct) + bytes - sizeof (bitset_word);
 628 }
 629
 630
 631 bitset
 632 abitset_init (bset, n_bits)
 633      bitset bset;
 634      bitset_bindex n_bits;
 635 {
 636   bitset_windex size;
 637
 638   size = ABITSET_N_WORDS (n_bits);
 639   ABITSET_N_BITS (bset) = n_bits;
 640
 641   /* Use optimized routines if bitset fits within a single word.
 642      There is probably little merit if using caching since
 643      the small bitset will always fit in the cache.  */
 644   if (size == 1)
 645     bset->b.ops = &abitset_small_ops;
 646   else
 647     bset->b.ops = &abitset_ops;
 648
 649   bset->b.cindex = 0;
 650   bset->b.csize = size;
 651   bset->b.cdata = ABITSET_WORDS (bset);
 652   return bset;
 653 }