1 /* SparseSet implementation. 2 Copyright (C) 2007, 2010 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 #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 */ 160