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