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   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 abitset_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 = ABITSET_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 >= ABITSET_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 abitset_unused_clear (dst)
 344      bitset dst;
 345 {
 346   unsigned int last_bit;
 347
 348   last_bit = ABITSET_N_BITS (dst) % BITSET_WORD_BITS;
 349   if (last_bit)
 350     ABITSET_WORDS (dst)[dst->b.csize - 1] &=
 351       (bitset_word) ((1 << last_bit) - 1);
 352 }
 353
 354
 355 static int
 356 abitset_op1 (dst, op)
 357      bitset dst;
 358      enum bitset_ops op;
 359 {
 360   unsigned int i;
 361   bitset_word *dstp = ABITSET_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       abitset_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 abitset_op2 (dst, src, op)
 393      bitset dst;
 394      bitset src;
 395      enum bitset_ops op;
 396 {
 397   unsigned int i;
 398   bitset_word *srcp = ABITSET_WORDS (src);
 399   bitset_word *dstp = ABITSET_WORDS (dst);
 400   bitset_windex size = dst->b.csize;
 401
 402   switch (op)
 403     {
 404     case BITSET_OP_COPY:
 405       if (srcp == dstp)
 406         break;
 407       memcpy (dstp, srcp, sizeof (bitset_word) * size);
 408       break;
 409
 410     case BITSET_OP_NOT:
 411       for (i = 0; i < size; i++)
 412         *dstp++ = ~(*srcp++);
 413       abitset_unused_clear (dst);
 414       break;
 415
 416     case BITSET_OP_EQUAL_P:
 417       for (i = 0; i < size; i++)
 418         if (*srcp++ != *dstp++)
 419           return 0;
 420       break;
 421
 422     case BITSET_OP_SUBSET_P:
 423       for (i = 0; i < size; i++, dstp++, srcp++)
 424         if (*dstp != (*srcp | *dstp))
 425           return 0;
 426       break;
 427
 428     case BITSET_OP_DISJOINT_P:
 429       for (i = 0; i < size; i++)
 430         if (*srcp++ & *dstp++)
 431           return 0;
 432       break;
 433
 434     default:
 435       abort ();
 436     }
 437
 438   return 1;
 439 }
 440
 441
 442 static int
 443 abitset_op3 (dst, src1, src2, op)
 444      bitset dst;
 445      bitset src1;
 446      bitset src2;
 447      enum bitset_ops op;
 448 {
 449   unsigned int i;
 450   int changed = 0;
 451   bitset_word *src1p = ABITSET_WORDS (src1);
 452   bitset_word *src2p = ABITSET_WORDS (src2);
 453   bitset_word *dstp = ABITSET_WORDS (dst);
 454   bitset_windex size = dst->b.csize;
 455
 456   switch (op)
 457     {
 458     case BITSET_OP_OR:
 459       for (i = 0; i < size; i++, dstp++)
 460         {
 461           bitset_word tmp = *src1p++ | *src2p++;
 462
 463           if (*dstp != tmp)
 464             {
 465               changed = 1;
 466               *dstp = tmp;
 467             }
 468         }
 469       break;
 470
 471     case BITSET_OP_AND:
 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_XOR:
 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_ANDN:
 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     default:
 511       abort ();
 512     }
 513
 514   return changed;
 515 }
 516
 517
 518 static int
 519 abitset_op4 (dst, src1, src2, src3, op)
 520      bitset dst;
 521      bitset src1;
 522      bitset src2;
 523      bitset src3;
 524      enum bitset_ops op;
 525 {
 526   unsigned int i;
 527   int changed = 0;
 528   bitset_word *src1p = ABITSET_WORDS (src1);
 529   bitset_word *src2p = ABITSET_WORDS (src2);
 530   bitset_word *src3p = ABITSET_WORDS (src3);
 531   bitset_word *dstp = ABITSET_WORDS (dst);
 532   bitset_windex size = dst->b.csize;
 533
 534   switch (op)
 535     {
 536     case BITSET_OP_OR_AND:
 537       for (i = 0; i < size; i++, dstp++)
 538         {
 539           bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
 540
 541           if (*dstp != tmp)
 542             {
 543               changed = 1;
 544               *dstp = tmp;
 545             }
 546         }
 547       break;
 548
 549     case BITSET_OP_AND_OR:
 550       for (i = 0; i < size; i++, dstp++)
 551         {
 552           bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
 553
 554           if (*dstp != tmp)
 555             {
 556               changed = 1;
 557               *dstp = tmp;
 558             }
 559         }
 560       break;
 561
 562     case BITSET_OP_ANDN_OR:
 563       for (i = 0; i < size; i++, dstp++)
 564         {
 565           bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
 566
 567           if (*dstp != tmp)
 568             {
 569               changed = 1;
 570               *dstp = tmp;
 571             }
 572         }
 573       break;
 574
 575     default:
 576       abort ();
 577     }
 578
 579   return changed;
 580 }
 581
 582
 583 /* Vector of operations for single word bitsets.  */
 584 struct bitset_ops_struct abitset_small_ops = {
 585   abitset_set,
 586   abitset_reset,
 587   abitset_test,
 588   abitset_size,
 589   abitset_op1,
 590   abitset_op2,
 591   abitset_op3,
 592   abitset_op4,
 593   abitset_small_list,
 594   abitset_reverse_list,
 595   NULL,
 596   BITSET_ARRAY
 597 };
 598
 599
 600 /* Vector of operations for multiple word bitsets.  */
 601 struct bitset_ops_struct abitset_ops = {
 602   abitset_set,
 603   abitset_reset,
 604   abitset_test,
 605   abitset_size,
 606   abitset_op1,
 607   abitset_op2,
 608   abitset_op3,
 609   abitset_op4,
 610   abitset_list,
 611   abitset_reverse_list,
 612   NULL,
 613   BITSET_ARRAY
 614 };
 615
 616
 617 int
 618 abitset_bytes (n_bits)
 619      bitset_bindex n_bits;
 620 {
 621   unsigned int bytes, size;
 622
 623   size = ABITSET_N_WORDS (n_bits);
 624   bytes = size * sizeof (bitset_word);
 625   return sizeof (struct bitset_struct) + bytes - sizeof (bitset_word);
 626 }
 627
 628
 629 bitset
 630 abitset_init (bset, n_bits)
 631      bitset bset;
 632      bitset_bindex n_bits;
 633 {
 634   bitset_windex size;
 635
 636   size = ABITSET_N_WORDS (n_bits);
 637   ABITSET_N_BITS (bset) = n_bits;
 638
 639   /* Use optimized routines if bitset fits within a single word.
 640      There is probably little merit if using caching since
 641      the small bitset will always fit in the cache.  */
 642   if (size == 1)
 643     bset->b.ops = &abitset_small_ops;
 644   else
 645     bset->b.ops = &abitset_ops;
 646
 647   bset->b.cindex = 0;
 648   bset->b.csize = size;
 649   bset->b.cdata = ABITSET_WORDS (bset);
 650   return bset;
 651 }