root/maint/gnulib/lib/bitset.c

/* */

DEFINITIONS

1. bitset_bytes
2. bitset_init
3. bitset_type_choose
4. bitset_alloc
5. bitset_obstack_alloc
6. bitset_create
7. bitset_free
8. bitset_obstack_free
9. bitset_type_get
10. bitset_type_name_get
11. bitset_next
12. bitset_compatible_p
13. bitset_prev
14. bitset_first
15. bitset_last
16. bitset_only_set_p
17. bitset_print
18. bitset_dump
19. bitset_release_memory
20. bitset_toggle_
21. bitset_size_
22. bitset_count_
23. bitset_copy_
24. bitset_op4_cmp
25. bitset_and_or_
26. bitset_and_or_cmp_
27. bitset_andn_or_
28. bitset_andn_or_cmp_
29. bitset_or_and_
30. bitset_or_and_cmp_
31. debug_bitset

   1 /* General bitsets.
   2 
   3    Copyright (C) 2002-2006, 2009-2015, 2018-2021 Free Software Foundation, Inc.
   4 
   5    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
   6 
   7    This program is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11 
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16 
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  19 
  20 #include <config.h>
  21 
  22 #include "bitset.h"
  23 
  24 #include <stdlib.h>
  25 #include <string.h>
  26 
  27 #include "obstack.h"
  28 
  29 #include "bitset/array.h"
  30 #include "bitset/list.h"
  31 #include "bitset/stats.h"
  32 #include "bitset/table.h"
  33 #include "bitset/vector.h"
  34 
  35 const char * const bitset_type_names[] = BITSET_TYPE_NAMES;
  36 
  37 
  38 /* Return number of bytes required to create a N_BIT bitset
  39    of TYPE.  The bitset may grow to require more bytes than this.  */
  40 size_t
  41 bitset_bytes (enum bitset_type type, bitset_bindex n_bits)
     /*  */
  42 {
  43   if (bitset_stats_enabled)
  44     return bitset_stats_bytes ();
  45 
  46   switch (type)
  47     {
  48     default:
  49       abort ();
  50 
  51     case BITSET_ARRAY:
  52       return abitset_bytes (n_bits);
  53 
  54     case BITSET_LIST:
  55       return lbitset_bytes (n_bits);
  56 
  57     case BITSET_TABLE:
  58       return tbitset_bytes (n_bits);
  59 
  60     case BITSET_VECTOR:
  61       return vbitset_bytes (n_bits);
  62     }
  63 }
  64 
  65 
  66 /* Initialise bitset BSET of TYPE for N_BITS.  */
  67 bitset
  68 bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
     /*  */
  69 {
  70   if (bitset_stats_enabled)
  71     return bitset_stats_init (bset, n_bits, type);
  72 
  73   switch (type)
  74     {
  75     default:
  76       abort ();
  77 
  78     case BITSET_ARRAY:
  79       return abitset_init (bset, n_bits);
  80 
  81     case BITSET_LIST:
  82       return lbitset_init (bset, n_bits);
  83 
  84     case BITSET_TABLE:
  85       return tbitset_init (bset, n_bits);
  86 
  87     case BITSET_VECTOR:
  88       return vbitset_init (bset, n_bits);
  89     }
  90 }
  91 
  92 
  93 /* Select a bitset type for a set of N_BITS and with attribute hints
  94    specified by ATTR.  For variable size bitsets, N_BITS is only a
  95    hint and may be zero.  */
  96 enum bitset_type
  97 bitset_type_choose (MAYBE_UNUSED bitset_bindex n_bits, unsigned attr)
     /*  */
  98 {
  99   /* Check attributes.  */
 100   if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
 101     abort ();
 102   if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
 103     abort ();
 104 
 105   /* Choose the type of bitset.  Note that sometimes we will be asked
 106   for a zero length fixed size bitset.  */
 107 
 108 
 109   /* If no attributes selected, choose a good compromise.  */
 110   if (!attr)
 111     return BITSET_VECTOR;
 112 
 113   if (attr & BITSET_SPARSE)
 114     return BITSET_LIST;
 115 
 116   if (attr & BITSET_FIXED)
 117     return BITSET_ARRAY;
 118 
 119   if (attr & BITSET_GREEDY)
 120     return BITSET_TABLE;
 121 
 122   return BITSET_VECTOR;
 123 }
 124 
 125 
 126 /* Create a bitset of N_BITS of type TYPE.  */
 127 bitset
 128 bitset_alloc (bitset_bindex n_bits, enum bitset_type type)
     /*  */
 129 {
 130   size_t bytes = bitset_bytes (type, n_bits);
 131 
 132   bitset bset = xzalloc (bytes);
 133 
 134   /* The cache is disabled until some elements are allocated.  If we
 135      have variable length arrays, then we may need to allocate a dummy
 136      element.  */
 137 
 138   return bitset_init (bset, n_bits, type);
 139 }
 140 
 141 
 142 /* Create a bitset of N_BITS of type TYPE.  */
 143 bitset
 144 bitset_obstack_alloc (struct obstack *bobstack,
     /*  */
 145                       bitset_bindex n_bits, enum bitset_type type)
 146 {
 147   size_t bytes = bitset_bytes (type, n_bits);
 148 
 149   bitset bset = obstack_alloc (bobstack, bytes);
 150   memset (bset, 0, bytes);
 151 
 152   return bitset_init (bset, n_bits, type);
 153 }
 154 
 155 
 156 /* Create a bitset of N_BITS and with attribute hints specified by
 157    ATTR.  */
 158 bitset
 159 bitset_create (bitset_bindex n_bits, unsigned attr)
     /*  */
 160 {
 161   enum bitset_type type = bitset_type_choose (n_bits, attr);
 162 
 163   return bitset_alloc (n_bits, type);
 164 }
 165 
 166 
 167 /* Free bitset BSET.  */
 168 void
 169 bitset_free (bitset bset)
     /*  */
 170 {
 171   if (bset)
 172     {
 173       BITSET_FREE_ (bset);
 174       free (bset);
 175     }
 176 }
 177 
 178 
 179 /* Free bitset BSET allocated on obstack.  */
 180 void
 181 bitset_obstack_free (bitset bset)
     /*  */
 182 {
 183   if (bset)
 184     BITSET_FREE_ (bset);
 185 }
 186 
 187 
 188 /* Return bitset type.  */
 189 enum bitset_type
 190 bitset_type_get (bitset bset)
     /*  */
 191 {
 192    enum bitset_type type = BITSET_TYPE_ (bset);
 193    if (type != BITSET_STATS)
 194      return type;
 195 
 196    return bitset_stats_type_get (bset);
 197 }
 198 
 199 
 200 /* Return name of bitset type.  */
 201 const char *
 202 bitset_type_name_get (bitset bset)
     /*  */
 203 {
 204   enum bitset_type type = bitset_type_get (bset);
 205 
 206   return bitset_type_names[type];
 207 }
 208 
 209 
 210 bitset_bindex
 211 bitset_next (bitset src, bitset_bindex bitno)
     /*  */
 212 {
 213   bitset_bindex next = bitno;
 214   bitset_bindex val;
 215   if (!bitset_list (src, &val, 1, &next))
 216     return BITSET_BINDEX_MAX;
 217   return val;
 218 }
 219 
 220 
 221 /* Return true if both bitsets are of the same type and size.  */
 222 extern bool
 223 bitset_compatible_p (bitset bset1, bitset bset2)
     /*  */
 224 {
 225   return BITSET_COMPATIBLE_ (bset1, bset2);
 226 }
 227 
 228 
 229 bitset_bindex
 230 bitset_prev (bitset src, bitset_bindex bitno)
     /*  */
 231 {
 232   bitset_bindex next = bitno;
 233   bitset_bindex val;
 234   if (!bitset_list_reverse (src, &val, 1, &next))
 235     return BITSET_BINDEX_MAX;
 236   return val;
 237 }
 238 
 239 
 240 /* Find first set bit.   */
 241 bitset_bindex
 242 bitset_first (bitset src)
     /*  */
 243 {
 244   return bitset_next (src, 0);
 245 }
 246 
 247 
 248 /* Find last set bit.   */
 249 bitset_bindex
 250 bitset_last (bitset src)
     /*  */
 251 {
 252   return bitset_prev (src, 0);
 253 }
 254 
 255 
 256 /* Is BITNO in SRC the only set bit?  */
 257 bool
 258 bitset_only_set_p (bitset src, bitset_bindex bitno)
     /*  */
 259 {
 260   bitset_bindex val[2];
 261   bitset_bindex next = 0;
 262 
 263   if (bitset_list (src, val, 2, &next) != 1)
 264     return false;
 265   return val[0] == bitno;
 266 }
 267 
 268 
 269 /* Print contents of bitset BSET to FILE.   */
 270 static void
 271 bitset_print (FILE *file, bitset bset, bool verbose)
     /*  */
 272 {
 273   if (verbose)
 274     fprintf (file, "%s{n_bits = %lu, set = {",
 275              bitset_type_name_get (bset),
 276              (unsigned long) bitset_size (bset));
 277 
 278   unsigned pos = 30;
 279   bitset_bindex i;
 280   bitset_iterator iter;
 281   BITSET_FOR_EACH (iter, bset, i, 0)
 282   {
 283     if (pos > 70)
 284       {
 285         fprintf (file, "\n");
 286         pos = 0;
 287       }
 288 
 289     fprintf (file, "%lu ", (unsigned long) i);
 290     pos += 1 + (i >= 10) + (i >= 100);
 291   }
 292 
 293   if (verbose)
 294     fprintf (file, "}}\n");
 295 }
 296 
 297 
 298 /* Dump bitset BSET to FILE.  */
 299 void
 300 bitset_dump (FILE *file, bitset bset)
     /*  */
 301 {
 302   bitset_print (file, bset, false);
 303 }
 304 
 305 
 306 /* Release memory associated with bitsets.  */
 307 void
 308 bitset_release_memory (void)
     /*  */
 309 {
 310   lbitset_release_memory ();
 311   tbitset_release_memory ();
 312 }
 313 
 314 
 315 /* Toggle bit BITNO in bitset BSET and the new value of the bit.  */
 316 bool
 317 bitset_toggle_ (bitset bset, bitset_bindex bitno)
     /*  */
 318 {
 319   /* This routine is for completeness.  It could be optimized if
 320      required.  */
 321   if (bitset_test (bset, bitno))
 322     {
 323       bitset_reset (bset, bitno);
 324       return false;
 325     }
 326   else
 327     {
 328       bitset_set (bset, bitno);
 329       return true;
 330     }
 331 }
 332 
 333 
 334 /* Return number of bits in bitset SRC.  */
 335 bitset_bindex
 336 bitset_size_ (bitset src)
     /*  */
 337 {
 338   return BITSET_NBITS_ (src);
 339 }
 340 
 341 
 342 /* Return number of bits set in bitset SRC.  */
 343 bitset_bindex
 344 bitset_count_ (bitset src)
     /*  */
 345 {
 346   bitset_bindex list[BITSET_LIST_SIZE];
 347   bitset_bindex count = 0;
 348 
 349   /* This could be greatly sped up by adding a count method for each
 350      bitset implementation that uses a direct technique (based on
 351      masks) for counting the number of bits set in a word.  */
 352 
 353   {
 354     bitset_bindex next = 0;
 355     bitset_bindex num;
 356     while ((num = bitset_list (src, list, BITSET_LIST_SIZE, &next)))
 357       count += num;
 358   }
 359 
 360   return count;
 361 }
 362 
 363 
 364 /* DST = SRC.  Return true if DST != SRC.
 365    This is a fallback for the case where SRC and DST are different
 366    bitset types.  */
 367 bool
 368 bitset_copy_ (bitset dst, bitset src)
     /*  */
 369 {
 370   bitset_bindex i;
 371   bitset_iterator iter;
 372 
 373   /* Convert bitset types.  We assume that the DST bitset
 374      is large enough to hold the SRC bitset.  */
 375   bitset_zero (dst);
 376   BITSET_FOR_EACH (iter, src, i, 0)
 377     bitset_set (dst, i);
 378 
 379   return true;
 380 }
 381 
 382 
 383 /* This is a fallback for implementations that do not support
 384    four operand operations.  */
 385 static inline bool
 386 bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3,
     /*  */
 387                 enum bitset_ops op)
 388 {
 389   bool changed = false;
 390 
 391   /* Create temporary bitset.  */
 392   bool stats_enabled_save = bitset_stats_enabled;
 393   bitset_stats_enabled = false;
 394   bitset tmp = bitset_alloc (0, bitset_type_get (dst));
 395   bitset_stats_enabled = stats_enabled_save;
 396 
 397   switch (op)
 398     {
 399     default:
 400       abort ();
 401 
 402     case BITSET_OP_OR_AND:
 403       bitset_or (tmp, src1, src2);
 404       changed = bitset_and_cmp (dst, src3, tmp);
 405       break;
 406 
 407     case BITSET_OP_AND_OR:
 408       bitset_and (tmp, src1, src2);
 409       changed = bitset_or_cmp (dst, src3, tmp);
 410       break;
 411 
 412     case BITSET_OP_ANDN_OR:
 413       bitset_andn (tmp, src1, src2);
 414       changed = bitset_or_cmp (dst, src3, tmp);
 415       break;
 416     }
 417 
 418   bitset_free (tmp);
 419   return changed;
 420 }
 421 
 422 
 423 /* DST = (SRC1 & SRC2) | SRC3.  */
 424 void
 425 bitset_and_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
     /*  */
 426 {
 427   bitset_and_or_cmp_ (dst, src1, src2, src3);
 428 }
 429 
 430 
 431 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 432    DST != (SRC1 & SRC2) | SRC3.  */
 433 bool
 434 bitset_and_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
     /*  */
 435 {
 436   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
 437 }
 438 
 439 
 440 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 441 void
 442 bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
     /*  */
 443 {
 444   bitset_andn_or_cmp_ (dst, src1, src2, src3);
 445 }
 446 
 447 
 448 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 449    DST != (SRC1 & ~SRC2) | SRC3.  */
 450 bool
 451 bitset_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
     /*  */
 452 {
 453   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
 454 }
 455 
 456 
 457 /* DST = (SRC1 | SRC2) & SRC3.  */
 458 void
 459 bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3)
     /*  */
 460 {
 461   bitset_or_and_cmp_ (dst, src1, src2, src3);
 462 }
 463 
 464 
 465 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 466    DST != (SRC1 | SRC2) & SRC3.  */
 467 bool
 468 bitset_or_and_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
     /*  */
 469 {
 470   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
 471 }
 472 
 473 
 474 /* Function to be called from debugger to print bitset.  */
 475 void
 476 debug_bitset (bitset bset)
     /*  */
 477 {
 478   if (bset)
 479     bitset_print (stderr, bset, true);
 480 }

/* */