lib/bitset.h

   1 /* Generic 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 #ifndef _BITSET_H
  20 #define _BITSET_H
  21
  22 /* This file is the public interface to the bitset abstract data type.
  23    Only use the functions and macros defined in this file.  */
  24
  25 #include "bbitset.h"
  26 #include "obstack.h"
  27 #include <stdio.h>
  28
  29 /* Attributes used to select a bitset implementation.  */
  30 enum bitset_attr {BITSET_FIXED = 1,    /* Bitset size fixed.  */
  31                   BITSET_VARIABLE = 2, /* Bitset size variable.  */
  32                   BITSET_DENSE = 4,    /* Bitset dense.  */
  33                   BITSET_SPARSE = 8,   /* Bitset sparse.  */
  34                   BITSET_FRUGAL = 16,  /* Prefer most compact.  */
  35                   BITSET_GREEDY = 32}; /* Prefer fastest at memory expense.  */
  36
  37 typedef unsigned int bitset_attrs;
  38
  39 /* The contents of the union should be considered to be private.
  40    While I would like to make this union opaque, it needs to be
  41    visible for the inline bit set/test functions, and for delegation
  42    to the proper implementation.  */
  43 union bitset_union
  44 {
  45   /* This must be the first member of every other structure that is a
  46      member of this union.  */
  47   struct bbitset_struct b;
  48
  49   struct abitset_struct
  50   {
  51     struct bbitset_struct b;
  52     bitset_bindex n_bits;               /* Number of bits.  */
  53     bitset_word words[1];               /* The array of bits.  */
  54   } a;
  55
  56   struct ebitset_struct
  57   {
  58     struct bbitset_struct b;
  59     bitset_windex size;                 /* Number of elements.  */
  60     struct ebitset_elt_struct **elts;   /* Expanding array of ptrs to elts.  */
  61   } e;
  62
  63   struct lbitset_struct
  64   {
  65     struct bbitset_struct b;
  66     struct lbitset_elt_struct *head;    /* First element in linked list.  */
  67     struct lbitset_elt_struct *tail;    /* Last element in linked list.  */
  68   } l;
  69
  70   struct bitset_stats_struct
  71   {
  72     struct bbitset_struct b;
  73     bitset bset;
  74   } s;
  75 };
  76
  77
  78 /* The contents of this structure should be considered private.
  79    It is used for iterating over set bits.  */
  80 typedef struct
  81 {
  82   bitset_bindex list[BITSET_LIST_SIZE];
  83   bitset_bindex next;
  84   bitset_bindex num;
  85   bitset_bindex i;
  86 } bitset_iterator;
  87
  88
  89 /* Return bytes required for bitset of desired type and size.  */
  90 extern size_t bitset_bytes PARAMS ((enum bitset_type, bitset_bindex));
  91
  92 /* Initialise a bitset with desired type and size.  */
  93 extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type));
  94
  95 /* Select an implementation type based on the desired bitset size
  96    and attributes.  */
  97 extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex,
  98                                                     bitset_attrs));
  99
 100 /* Create a bitset of desired type and size.  The bitset is zeroed.  */
 101 extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type));
 102
 103 /* Free bitset.  */
 104 extern void bitset_free PARAMS ((bitset));
 105
 106 /* Create a bitset of desired type and size using an obstack.  The
 107    bitset is zeroed.  */
 108 extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack,
 109                                             bitset_bindex, enum bitset_type));
 110
 111 /* Free bitset allocated on obstack.  */
 112 extern void bitset_obstack_free PARAMS ((bitset));
 113
 114 /* Create a bitset of desired size and attributes.  The bitset is zeroed.  */
 115 extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs));
 116
 117 /* Return bitset type.  */
 118 extern enum bitset_type bitset_type_get PARAMS ((bitset));
 119
 120 /* Return bitset type name.  */
 121 extern const char *bitset_type_name_get PARAMS ((bitset));
 122
 123
 124 /* Set bit BITNO in bitset BSET.  */
 125 static inline void
 126 bitset_set (bitset bset, bitset_bindex bitno)
 127 {
 128   bitset_windex windex = bitno / BITSET_WORD_BITS;
 129   bitset_windex offset = windex - bset->b.cindex;
 130
 131   if (offset < bset->b.csize)
 132     bset->b.cdata[offset] |= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 133   else
 134     BITSET_SET_ (bset, bitno);
 135 }
 136
 137
 138 /* Reset bit BITNO in bitset BSET.  */
 139 static inline void
 140 bitset_reset (bitset bset, bitset_bindex bitno)
 141 {
 142   bitset_windex windex = bitno / BITSET_WORD_BITS;
 143   bitset_windex offset = windex - bset->b.cindex;
 144
 145   if (offset < bset->b.csize)
 146     bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 147   else
 148     BITSET_RESET_ (bset, bitno);
 149 }
 150
 151
 152 /* Test bit BITNO in bitset BSET.  */
 153 static inline int
 154 bitset_test (bitset bset, bitset_bindex bitno)
 155 {
 156   bitset_windex windex = bitno / BITSET_WORD_BITS;
 157   bitset_windex offset = windex - bset->b.cindex;
 158
 159   if (offset < bset->b.csize)
 160     return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
 161   else
 162     return BITSET_TEST_ (bset, bitno);
 163 }
 164
 165
 166 /* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
 167 #define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)
 168
 169 /* Return size in bits of bitset SRC.  */
 170 #define bitset_size(SRC) BITSET_SIZE_ (SRC)
 171
 172 /* Return number of bits set in bitset SRC.  */
 173 #define bitset_count(SRC) BITSET_COUNT_ (SRC)
 174
 175
 176 /* Return SRC == 0.  */
 177 #define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
 178
 179 /* DST = ~0.  */
 180 #define bitset_ones(DST) BITSET_ONES_ (DST)
 181
 182 /* DST = 0.  */
 183 #define bitset_zero(DST) BITSET_ZERO_ (DST)
 184
 185
 186
 187 /* DST = SRC.  */
 188 #define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
 189
 190 /* Return DST & SRC == 0.  */
 191 #define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
 192
 193 /* Return DST == SRC.  */
 194 #define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
 195
 196 /* DST = ~SRC.  */
 197 #define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
 198
 199 /* Return DST == DST | SRC.  */
 200 #define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
 201
 202
 203
 204 /* DST = SRC1 & SRC2.  */
 205 #define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
 206
 207 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 208 #define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
 209
 210 /* DST = SRC1 & ~SRC2.  */
 211 #define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
 212
 213 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 214 #define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
 215
 216 /* DST = SRC1 | SRC2.  */
 217 #define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
 218
 219 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 220 #define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
 221
 222 /* DST = SRC1 ^ SRC2.  */
 223 #define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
 224
 225 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 226 #define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
 227
 228
 229
 230 /* DST = (SRC1 & SRC2) | SRC3.  */
 231 #define bitset_and_or(DST, SRC1, SRC2, SRC3) \
 232  BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
 233
 234 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 235    DST != (SRC1 & SRC2) | SRC3.  */
 236 #define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
 237  BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 238
 239 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 240 #define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
 241  BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
 242
 243 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 244    DST != (SRC1 & ~SRC2) | SRC3.  */
 245 #define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
 246  BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 247
 248 /* DST = (SRC1 | SRC2) & SRC3.  */
 249 #define bitset_or_and(DST, SRC1, SRC2, SRC3)\
 250  BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
 251
 252 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 253    DST != (SRC1 | SRC2) & SRC3.  */
 254 #define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
 255  BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
 256
 257 /* Find list of up to NUM bits set in BSET starting from and including
 258    *NEXT.  Return with actual number of bits found and with *NEXT
 259    indicating where search stopped.  */
 260 #define bitset_list(BSET, LIST, NUM, NEXT) \
 261  BITSET_LIST_ (BSET, LIST, NUM, NEXT)
 262
 263 /* Find reverse list of up to NUM bits set in BSET starting from and
 264    including NEXT.  Return with actual number of bits found and with
 265    *NEXT indicating where search stopped.  */
 266 #define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
 267  BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
 268
 269
 270 /* Find next set bit.  */
 271 extern bitset_bindex bitset_next PARAMS ((bitset, bitset_bindex));
 272
 273 /* Find previous set bit.  */
 274 extern bitset_bindex bitset_prev PARAMS ((bitset, bitset_bindex));
 275
 276 /* Find first set bit.  */
 277 extern bitset_bindex bitset_first PARAMS ((bitset));
 278
 279 /* Find last set bit.  */
 280 extern bitset_bindex bitset_last PARAMS ((bitset));
 281
 282 /* Return nonzero if this is the only set bit.  */
 283 extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
 284
 285 /* Dump bitset.  */
 286 extern void bitset_dump PARAMS ((FILE *, bitset));
 287
 288 /* Loop over all elements of BSET, starting with MIN, setting BIT
 289    to the index of each set bit.  For example, the following will print
 290    the bits set in a bitset:
 291
 292    bitset_bindex i;
 293    bitset_iterator iter;
 294
 295    bitset_zero (dst);
 296    BITSET_FOR_EACH (iter, src, i, 0)
 297    {
 298       printf ("%ld ", i);
 299    };
 300 */
 301 #define BITSET_FOR_EACH(ITER, BSET, BIT, MIN)                                 \
 302   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 303        (ITER.num == BITSET_LIST_SIZE)                                         \
 304        && (ITER.num = bitset_list (BSET, ITER.list,                           \
 305                                    BITSET_LIST_SIZE, &ITER.next));)           \
 306     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 307
 308
 309 /* Loop over all elements of BSET, in reverse order starting with
 310    MIN,  setting BIT to the index of each set bit. For example, the
 311    following will print the bits set in a bitset in reverse order:
 312
 313    bitset_bindex i;
 314    bitset_iterator iter;
 315
 316    bitset_zero (dst);
 317    BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
 318    {
 319       printf ("%ld ", i);
 320    };
 321 */
 322 #define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN)                         \
 323   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 324        (ITER.num == BITSET_LIST_SIZE)                                         \
 325        && (ITER.num = bitset_list_reverse (BSET, ITER.list,                   \
 326                                           BITSET_LIST_SIZE, &ITER.next));)    \
 327     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 328
 329
 330 /* Define set operations in terms of logical operations.  */
 331
 332 #define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
 333 #define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
 334
 335 #define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
 336 #define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)
 337
 338 #define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
 339 #define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
 340
 341 /* Symmetrical difference.  */
 342 #define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
 343 #define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
 344
 345 /* Union of difference.  */
 346 #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
 347   bitset_andn_or (DST, SRC1, SRC2, SRC3)
 348 #define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
 349   bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
 350
 351
 352
 353 /* Release any memory tied up with bitsets.  */
 354 extern void bitset_release_memory PARAMS ((void));
 355
 356 /* Enable bitset stats gathering.  */
 357 extern void bitset_stats_enable PARAMS ((void));
 358
 359 /* Disable bitset stats gathering.  */
 360 extern void bitset_stats_disable PARAMS ((void));
 361
 362 /* Read bitset stats file of accummulated stats.  */
 363 void bitset_stats_read PARAMS ((const char *filename));
 364
 365 /* Write bitset stats file of accummulated stats.  */
 366 void bitset_stats_write PARAMS ((const char *filename));
 367
 368 /* Dump bitset stats.  */
 369 extern void bitset_stats_dump PARAMS ((FILE *));
 370
 371 /* Function to debug bitset from debugger.  */
 372 extern void debug_bitset PARAMS ((bitset));
 373
 374 /* Function to debug bitset stats from debugger.  */
 375 extern void debug_bitset_stats PARAMS ((void));
 376
 377 #endif /* _BITSET_H  */
 378