1/* SparseSet implementation.
2   Copyright (C) 2007 Free Software Foundation, Inc.
3   Contributed by Peter Bergner <bergner@vnet.ibm.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3.  If not see
19<http://www.gnu.org/licenses/>.  */
20
21#ifndef GCC_SPARSESET_H
22#define GCC_SPARSESET_H
23
24#include <assert.h>
25
26#define SPARSESET_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
27#define SPARSESET_ELT_TYPE unsigned int
28
29/* Data Structure used for the SparseSet representation.  */
30
31typedef struct sparseset_def
32{
33  SPARSESET_ELT_TYPE *dense;	/* Dense array.  */
34  SPARSESET_ELT_TYPE *sparse;	/* Sparse array.  */
35  SPARSESET_ELT_TYPE members;	/* Number of elements.  */
36  SPARSESET_ELT_TYPE size;	/* Maximum number of elements.  */
37  SPARSESET_ELT_TYPE iter;	/* Iterator index.  */
38  unsigned char iter_inc;	/* Iteration increment amount.  */
39  bool iterating;
40  SPARSESET_ELT_TYPE elms[2];   /* Combined dense and sparse arrays.  */
41} *sparseset;
42
43#define sparseset_free(MAP)  free(MAP)
44extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms);
45extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE);
46extern void sparseset_copy (sparseset, sparseset);
47extern void sparseset_and (sparseset, sparseset, sparseset);
48extern void sparseset_and_compl (sparseset, sparseset, sparseset);
49extern void sparseset_ior (sparseset, sparseset, sparseset);
50extern bool sparseset_equal_p (sparseset, sparseset);
51
52/* Operation: S = {}
53   Clear the set of all elements.  */
54
55static inline void
56sparseset_clear (sparseset s)
57{
58  s->members = 0;
59  s->iterating = false;
60}
61
62/* Return the number of elements currently in the set.  */
63
64static inline SPARSESET_ELT_TYPE
65sparseset_cardinality (sparseset s)
66{
67  return s->members;
68}
69
70/* Return the maximum number of elements this set can hold.  */
71
72static inline SPARSESET_ELT_TYPE
73sparseset_size (sparseset s)
74{
75  return s->size;
76}
77
78/* Return true if e is a member of the set S, otherwise return false.  */
79
80static inline bool
81sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e)
82{
83  SPARSESET_ELT_TYPE idx;
84
85  gcc_assert (e < s->size);
86
87  idx = s->sparse[e];
88
89  return idx < s->members && s->dense[idx] == e;
90}
91
92/* Low level insertion routine not meant for use outside of sparseset.[ch].
93   Assumes E is valid and not already a member of the set S.  */
94
95static inline void
96sparseset_insert_bit (sparseset s, SPARSESET_ELT_TYPE e, SPARSESET_ELT_TYPE idx)
97{
98  s->sparse[e] = idx;
99  s->dense[idx] = e;
100}
101
102/* Operation: S = S + {e}
103   Insert E into the set S, if it isn't already a member.  */
104
105static inline void
106sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e)
107{
108  if (!sparseset_bit_p (s, e))
109    sparseset_insert_bit (s, e, s->members++);
110}
111
112/* Return and remove an arbitrary element from the set S.  */
113
114static inline SPARSESET_ELT_TYPE
115sparseset_pop (sparseset s)
116{
117  SPARSESET_ELT_TYPE mem = s->members;
118
119  gcc_assert (mem != 0);
120
121  s->members = mem - 1;
122  return s->dense[mem];
123}
124
125static inline void
126sparseset_iter_init (sparseset s)
127{
128  s->iter = 0;
129  s->iter_inc = 1;
130  s->iterating = true;
131}
132
133static inline bool
134sparseset_iter_p (sparseset s)
135{
136  if (s->iterating && s->iter < s->members)
137    return true;
138  else
139    return s->iterating = false;
140}
141
142static inline SPARSESET_ELT_TYPE
143sparseset_iter_elm (sparseset s)
144{
145  return s->dense[s->iter];
146}
147
148static inline void
149sparseset_iter_next (sparseset s)
150{
151  s->iter += s->iter_inc;
152  s->iter_inc = 1;
153}
154
155#define EXECUTE_IF_SET_IN_SPARSESET(SPARSESET, ITER)			\
156  for (sparseset_iter_init (SPARSESET);					\
157       sparseset_iter_p (SPARSESET)					\
158       && (((ITER) = sparseset_iter_elm (SPARSESET)) || 1);		\
159       sparseset_iter_next (SPARSESET))
160
161#endif /* GCC_SPARSESET_H */
162