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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [sparseset.h] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* SparseSet implementation.
2
   Copyright (C) 2007 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
#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
 
31
typedef 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)
44
extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms);
45
extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE);
46
extern void sparseset_copy (sparseset, sparseset);
47
extern void sparseset_and (sparseset, sparseset, sparseset);
48
extern void sparseset_and_compl (sparseset, sparseset, sparseset);
49
extern void sparseset_ior (sparseset, sparseset, sparseset);
50
extern bool sparseset_equal_p (sparseset, sparseset);
51
 
52
/* Operation: S = {}
53
   Clear the set of all elements.  */
54
 
55
static inline void
56
sparseset_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
 
64
static inline SPARSESET_ELT_TYPE
65
sparseset_cardinality (sparseset s)
66
{
67
  return s->members;
68
}
69
 
70
/* Return the maximum number of elements this set can hold.  */
71
 
72
static inline SPARSESET_ELT_TYPE
73
sparseset_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
 
80
static inline bool
81
sparseset_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
 
95
static inline void
96
sparseset_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
 
105
static inline void
106
sparseset_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
 
114
static inline SPARSESET_ELT_TYPE
115
sparseset_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
 
125
static inline void
126
sparseset_iter_init (sparseset s)
127
{
128
  s->iter = 0;
129
  s->iter_inc = 1;
130
  s->iterating = true;
131
}
132
 
133
static inline bool
134
sparseset_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
 
142
static inline SPARSESET_ELT_TYPE
143
sparseset_iter_elm (sparseset s)
144
{
145
  return s->dense[s->iter];
146
}
147
 
148
static inline void
149
sparseset_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 */

powered by: WebSVN 2.1.0

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