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