gcc/sparseset.c

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