1 /* 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 238