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