Mercurial > hg > CbC > CbC_gcc
annotate gcc/sparseset.h @ 88:f214c1d5b862
merge 89
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 20 Dec 2011 18:53:46 +0900 |
| parents | f6334be47118 |
| children | 04ced10e8804 |
| rev | line source |
|---|---|
| 0 | 1 /* SparseSet implementation. |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2 Copyright (C) 2007, 2010 Free Software Foundation, Inc. |
| 0 | 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 #define SPARSESET_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT) | |
| 25 #define SPARSESET_ELT_TYPE unsigned int | |
| 26 | |
| 27 /* Data Structure used for the SparseSet representation. */ | |
| 28 | |
| 29 typedef struct sparseset_def | |
| 30 { | |
| 31 SPARSESET_ELT_TYPE *dense; /* Dense array. */ | |
| 32 SPARSESET_ELT_TYPE *sparse; /* Sparse array. */ | |
| 33 SPARSESET_ELT_TYPE members; /* Number of elements. */ | |
| 34 SPARSESET_ELT_TYPE size; /* Maximum number of elements. */ | |
| 35 SPARSESET_ELT_TYPE iter; /* Iterator index. */ | |
| 36 unsigned char iter_inc; /* Iteration increment amount. */ | |
| 37 bool iterating; | |
| 38 SPARSESET_ELT_TYPE elms[2]; /* Combined dense and sparse arrays. */ | |
| 39 } *sparseset; | |
| 40 | |
| 41 #define sparseset_free(MAP) free(MAP) | |
| 42 extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms); | |
| 43 extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE); | |
| 44 extern void sparseset_copy (sparseset, sparseset); | |
| 45 extern void sparseset_and (sparseset, sparseset, sparseset); | |
| 46 extern void sparseset_and_compl (sparseset, sparseset, sparseset); | |
| 47 extern void sparseset_ior (sparseset, sparseset, sparseset); | |
| 48 extern bool sparseset_equal_p (sparseset, sparseset); | |
| 49 | |
| 50 /* Operation: S = {} | |
| 51 Clear the set of all elements. */ | |
| 52 | |
| 53 static inline void | |
| 54 sparseset_clear (sparseset s) | |
| 55 { | |
| 56 s->members = 0; | |
| 57 s->iterating = false; | |
| 58 } | |
| 59 | |
| 60 /* Return the number of elements currently in the set. */ | |
| 61 | |
| 62 static inline SPARSESET_ELT_TYPE | |
| 63 sparseset_cardinality (sparseset s) | |
| 64 { | |
| 65 return s->members; | |
| 66 } | |
| 67 | |
| 68 /* Return the maximum number of elements this set can hold. */ | |
| 69 | |
| 70 static inline SPARSESET_ELT_TYPE | |
| 71 sparseset_size (sparseset s) | |
| 72 { | |
| 73 return s->size; | |
| 74 } | |
| 75 | |
| 76 /* Return true if e is a member of the set S, otherwise return false. */ | |
| 77 | |
| 78 static inline bool | |
| 79 sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e) | |
| 80 { | |
| 81 SPARSESET_ELT_TYPE idx; | |
| 82 | |
| 83 gcc_assert (e < s->size); | |
| 84 | |
| 85 idx = s->sparse[e]; | |
| 86 | |
| 87 return idx < s->members && s->dense[idx] == e; | |
| 88 } | |
| 89 | |
| 90 /* Low level insertion routine not meant for use outside of sparseset.[ch]. | |
| 91 Assumes E is valid and not already a member of the set S. */ | |
| 92 | |
| 93 static inline void | |
| 94 sparseset_insert_bit (sparseset s, SPARSESET_ELT_TYPE e, SPARSESET_ELT_TYPE idx) | |
| 95 { | |
| 96 s->sparse[e] = idx; | |
| 97 s->dense[idx] = e; | |
| 98 } | |
| 99 | |
| 100 /* Operation: S = S + {e} | |
| 101 Insert E into the set S, if it isn't already a member. */ | |
| 102 | |
| 103 static inline void | |
| 104 sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e) | |
| 105 { | |
| 106 if (!sparseset_bit_p (s, e)) | |
| 107 sparseset_insert_bit (s, e, s->members++); | |
| 108 } | |
| 109 | |
| 110 /* Return and remove an arbitrary element from the set S. */ | |
| 111 | |
| 112 static inline SPARSESET_ELT_TYPE | |
| 113 sparseset_pop (sparseset s) | |
| 114 { | |
| 115 SPARSESET_ELT_TYPE mem = s->members; | |
| 116 | |
| 117 gcc_assert (mem != 0); | |
| 118 | |
| 119 s->members = mem - 1; | |
| 120 return s->dense[mem]; | |
| 121 } | |
| 122 | |
| 123 static inline void | |
| 124 sparseset_iter_init (sparseset s) | |
| 125 { | |
| 126 s->iter = 0; | |
| 127 s->iter_inc = 1; | |
| 128 s->iterating = true; | |
| 129 } | |
| 130 | |
| 131 static inline bool | |
| 132 sparseset_iter_p (sparseset s) | |
| 133 { | |
| 134 if (s->iterating && s->iter < s->members) | |
| 135 return true; | |
| 136 else | |
| 137 return s->iterating = false; | |
| 138 } | |
| 139 | |
| 140 static inline SPARSESET_ELT_TYPE | |
| 141 sparseset_iter_elm (sparseset s) | |
| 142 { | |
| 143 return s->dense[s->iter]; | |
| 144 } | |
| 145 | |
| 146 static inline void | |
| 147 sparseset_iter_next (sparseset s) | |
| 148 { | |
| 149 s->iter += s->iter_inc; | |
| 150 s->iter_inc = 1; | |
| 151 } | |
| 152 | |
| 153 #define EXECUTE_IF_SET_IN_SPARSESET(SPARSESET, ITER) \ | |
| 154 for (sparseset_iter_init (SPARSESET); \ | |
| 155 sparseset_iter_p (SPARSESET) \ | |
| 156 && (((ITER) = sparseset_iter_elm (SPARSESET)) || 1); \ | |
| 157 sparseset_iter_next (SPARSESET)) | |
| 158 | |
| 159 #endif /* GCC_SPARSESET_H */ |