1 /* SparseSet implementation. 2 Copyright (C) 2007-2017 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 sparseset set = XNEWVAR (struct sparseset_def, n_bytes); 34 35 /* Mark the sparseset as defined to silence some valgrind uninitialized 36 read errors when accessing set->sparse[n] when "n" is not, and never has 37 been, in the set. These uninitialized reads are expected, by design and 38 harmless. */ 39 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (set, n_bytes)); 40 41 set->dense = &(set->elms[0]); 42 set->sparse = &(set->elms[n_elms]); 43 set->size = n_elms; 44 sparseset_clear (set); 45 return set; 46 } 47 48 /* Low level routine not meant for use outside of sparseset.[ch]. 49 Assumes idx1 < s->members and idx2 < s->members. */ 50 51 static inline void 52 sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2) 53 { 54 SPARSESET_ELT_TYPE tmp = s->dense[idx2]; 55 sparseset_insert_bit (s, s->dense[idx1], idx2); 56 sparseset_insert_bit (s, tmp, idx1); 57 } 58 59 /* Operation: S = S - {e} 60 Delete e from the set S if it is a member of S. */ 61 62 void 63 sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e) 64 { 65 if (sparseset_bit_p (s, e)) 66 { 67 SPARSESET_ELT_TYPE idx = s->sparse[e]; 68 SPARSESET_ELT_TYPE iter = s->iter; 69 SPARSESET_ELT_TYPE mem = s->members - 1; 70 71 /* If we are iterating over this set and we want to delete a 72 member we've already visited, then we swap the element we 73 want to delete with the element at the current iteration 74 index so that it plays well together with the code below 75 that actually removes the element. */ 76 if (s->iterating && idx <= iter) 77 { 78 if (idx < iter) 79 { 80 sparseset_swap (s, idx, iter); 81 idx = iter; 82 } 83 s->iter_inc = 0; 84 } 85 86 /* Replace the element we want to delete with the last element 87 in the dense array and then decrement s->members, effectively 88 removing the element we want to delete. */ 89 sparseset_insert_bit (s, s->dense[mem], idx); 90 s->members = mem; 91 } 92 } 93 94 /* Operation: D = S 95 Restrictions: none. */ 96 97 void 98 sparseset_copy (sparseset d, sparseset s) 99 { 100 SPARSESET_ELT_TYPE i; 101 102 if (d == s) 103 return; 104 105 sparseset_clear (d); 106 for (i = 0; i < s->members; i++) 107 sparseset_insert_bit (d, s->dense[i], i); 108 d->members = s->members; 109 } 110 111 /* Operation: D = A & B. 112 Restrictions: none. */ 113 114 void 115 sparseset_and (sparseset d, sparseset a, sparseset b) 116 { 117 SPARSESET_ELT_TYPE e; 118 119 if (a == b) 120 { 121 if (d != a) 122 sparseset_copy (d, a); 123 return; 124 } 125 126 if (d == a || d == b) 127 { 128 sparseset s = (d == a) ? b : a; 129 130 EXECUTE_IF_SET_IN_SPARSESET (d, e) 131 if (!sparseset_bit_p (s, e)) 132 sparseset_clear_bit (d, e); 133 } 134 else 135 { 136 sparseset sml, lrg; 137 138 if (sparseset_cardinality (a) < sparseset_cardinality (b)) 139 { 140 sml = a; 141 lrg = b; 142 } 143 else 144 { 145 sml = b; 146 lrg = a; 147 } 148 149 sparseset_clear (d); 150 EXECUTE_IF_SET_IN_SPARSESET (sml, e) 151 if (sparseset_bit_p (lrg, e)) 152 sparseset_set_bit (d, e); 153 } 154 } 155 156 /* Operation: D = A & ~B. 157 Restrictions: D != B, unless D == A == B. */ 158 159 void 160 sparseset_and_compl (sparseset d, sparseset a, sparseset b) 161 { 162 SPARSESET_ELT_TYPE e; 163 164 if (a == b) 165 { 166 sparseset_clear (d); 167 return; 168 } 169 170 gcc_assert (d != b); 171 172 if (d == a) 173 { 174 if (sparseset_cardinality (d) < sparseset_cardinality (b)) 175 { 176 EXECUTE_IF_SET_IN_SPARSESET (d, e) 177 if (sparseset_bit_p (b, e)) 178 sparseset_clear_bit (d, e); 179 } 180 else 181 { 182 EXECUTE_IF_SET_IN_SPARSESET (b, e) 183 sparseset_clear_bit (d, e); 184 } 185 } 186 else 187 { 188 sparseset_clear (d); 189 EXECUTE_IF_SET_IN_SPARSESET (a, e) 190 if (!sparseset_bit_p (b, e)) 191 sparseset_set_bit (d, e); 192 } 193 } 194 195 /* Operation: D = A | B. 196 Restrictions: none. */ 197 198 void 199 sparseset_ior (sparseset d, sparseset a, sparseset b) 200 { 201 SPARSESET_ELT_TYPE e; 202 203 if (a == b) 204 sparseset_copy (d, a); 205 else if (d == b) 206 { 207 EXECUTE_IF_SET_IN_SPARSESET (a, e) 208 sparseset_set_bit (d, e); 209 } 210 else 211 { 212 if (d != a) 213 sparseset_copy (d, a); 214 EXECUTE_IF_SET_IN_SPARSESET (b, e) 215 sparseset_set_bit (d, e); 216 } 217 } 218 219 /* Operation: A == B 220 Restrictions: none. */ 221 222 bool 223 sparseset_equal_p (sparseset a, sparseset b) 224 { 225 SPARSESET_ELT_TYPE e; 226 227 if (a == b) 228 return true; 229 230 if (sparseset_cardinality (a) != sparseset_cardinality (b)) 231 return false; 232 233 EXECUTE_IF_SET_IN_SPARSESET (a, e) 234 if (!sparseset_bit_p (b, e)) 235 return false; 236 237 return true; 238 } 239 240