gcc/sparseset.c

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