OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [sparseset.c] - Blame information for rev 707

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* SparseSet implementation.
2
   Copyright (C) 2007, 2008 Free Software Foundation, Inc.
3
   Contributed by Peter Bergner <bergner@vnet.ibm.com>
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "sparseset.h"
24
 
25
/* Allocate and clear a n_elms SparseSet.  */
26
 
27
sparseset
28
sparseset_alloc (SPARSESET_ELT_TYPE n_elms)
29
{
30
  unsigned int n_bytes = sizeof (struct sparseset_def)
31
                         + ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));
32
 
33
  /* We use xcalloc rather than xmalloc to silence some valgrind uninitialized
34
     read errors when accessing set->sparse[n] when "n" is not, and never has
35
     been, in the set.  These uninitialized reads are expected, by design and
36
     harmless.  If this turns into a performance problem due to some future
37
     additional users of sparseset, we can revisit this decision.  */
38
  sparseset set = (sparseset) xcalloc (1, n_bytes);
39
  set->dense = &(set->elms[0]);
40
  set->sparse = &(set->elms[n_elms]);
41
  set->size = n_elms;
42
  sparseset_clear (set);
43
  return set;
44
}
45
 
46
/* Low level routine not meant for use outside of sparseset.[ch].
47
   Assumes idx1 < s->members and idx2 < s->members.  */
48
 
49
static inline void
50
sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2)
51
{
52
  SPARSESET_ELT_TYPE tmp = s->dense[idx2];
53
  sparseset_insert_bit (s, s->dense[idx1], idx2);
54
  sparseset_insert_bit (s, tmp, idx1);
55
}
56
 
57
/* Operation: S = S - {e}
58
   Delete e from the set S if it is a member of S.  */
59
 
60
void
61
sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e)
62
{
63
  if (sparseset_bit_p (s, e))
64
    {
65
      SPARSESET_ELT_TYPE idx = s->sparse[e];
66
      SPARSESET_ELT_TYPE iter = s->iter;
67
      SPARSESET_ELT_TYPE mem = s->members - 1;
68
 
69
      /* If we are iterating over this set and we want to delete a
70
         member we've already visited, then we swap the element we
71
         want to delete with the element at the current iteration
72
         index so that it plays well together with the code below
73
         that actually removes the element.  */
74
      if (s->iterating && idx <= iter)
75
        {
76
          if (idx < iter)
77
            {
78
              sparseset_swap (s, idx, iter);
79
              idx = iter;
80
            }
81
          s->iter_inc = 0;
82
        }
83
 
84
      /* Replace the element we want to delete with the last element
85
         in the dense array and then decrement s->members, effectively
86
         removing the element we want to delete.  */
87
      sparseset_insert_bit (s, s->dense[mem], idx);
88
      s->members = mem;
89
    }
90
}
91
 
92
/* Operation: D = S
93
   Restrictions: none.  */
94
 
95
void
96
sparseset_copy (sparseset d, sparseset s)
97
{
98
  SPARSESET_ELT_TYPE i;
99
 
100
  if (d == s)
101
    return;
102
 
103
  sparseset_clear (d);
104
  for (i = 0; i < s->members; i++)
105
    sparseset_insert_bit (d, s->dense[i], i);
106
  d->members = s->members;
107
}
108
 
109
/* Operation: D = A & B.
110
   Restrictions: none.  */
111
 
112
void
113
sparseset_and (sparseset d, sparseset a, sparseset b)
114
{
115
  SPARSESET_ELT_TYPE e;
116
 
117
  if (a == b)
118
    {
119
      if (d != a)
120
        sparseset_copy (d, a);
121
      return;
122
    }
123
 
124
  if (d == a || d == b)
125
    {
126
      sparseset s = (d == a) ? b : a;
127
 
128
      EXECUTE_IF_SET_IN_SPARSESET (d, e)
129
        if (!sparseset_bit_p (s, e))
130
          sparseset_clear_bit (d, e);
131
    }
132
  else
133
    {
134
      sparseset sml, lrg;
135
 
136
      if (sparseset_cardinality (a) < sparseset_cardinality (b))
137
        {
138
          sml = a;
139
          lrg = b;
140
        }
141
      else
142
        {
143
          sml = b;
144
          lrg = a;
145
        }
146
 
147
      sparseset_clear (d);
148
      EXECUTE_IF_SET_IN_SPARSESET (sml, e)
149
        if (sparseset_bit_p (lrg, e))
150
          sparseset_set_bit (d, e);
151
    }
152
}
153
 
154
/* Operation: D = A & ~B.
155
   Restrictions: D != B, unless D == A == B.  */
156
 
157
void
158
sparseset_and_compl (sparseset d, sparseset a, sparseset b)
159
{
160
  SPARSESET_ELT_TYPE e;
161
 
162
  if (a == b)
163
    {
164
      sparseset_clear (d);
165
      return;
166
    }
167
 
168
  gcc_assert (d != b);
169
 
170
  if (d == a)
171
    {
172
      if (sparseset_cardinality (d) < sparseset_cardinality (b))
173
        {
174
          EXECUTE_IF_SET_IN_SPARSESET (d, e)
175
            if (sparseset_bit_p (b, e))
176
              sparseset_clear_bit (d, e);
177
        }
178
      else
179
        {
180
          EXECUTE_IF_SET_IN_SPARSESET (b, e)
181
            sparseset_clear_bit (d, e);
182
        }
183
    }
184
  else
185
    {
186
      sparseset_clear (d);
187
      EXECUTE_IF_SET_IN_SPARSESET (a, e)
188
        if (!sparseset_bit_p (b, e))
189
          sparseset_set_bit (d, e);
190
    }
191
}
192
 
193
/* Operation: D = A | B.
194
   Restrictions: none.  */
195
 
196
void
197
sparseset_ior (sparseset d, sparseset a, sparseset b)
198
{
199
  SPARSESET_ELT_TYPE e;
200
 
201
  if (a == b)
202
    sparseset_copy (d, a);
203
  else if (d == b)
204
    {
205
      EXECUTE_IF_SET_IN_SPARSESET (a, e)
206
        sparseset_set_bit (d, e);
207
    }
208
  else
209
    {
210
      if (d != a)
211
        sparseset_copy (d, a);
212
      EXECUTE_IF_SET_IN_SPARSESET (b, e)
213
        sparseset_set_bit (d, e);
214
    }
215
}
216
 
217
/* Operation: A == B
218
   Restrictions: none.  */
219
 
220
bool
221
sparseset_equal_p (sparseset a, sparseset b)
222
{
223
  SPARSESET_ELT_TYPE e;
224
 
225
  if (a == b)
226
    return true;
227
 
228
  if (sparseset_cardinality (a) != sparseset_cardinality (b))
229
    return false;
230
 
231
  EXECUTE_IF_SET_IN_SPARSESET (a, e)
232
    if (!sparseset_bit_p (b, e))
233
      return false;
234
 
235
  return true;
236
}
237
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.