/* SparseSet implementation.
|
/* SparseSet implementation.
|
Copyright (C) 2007, 2008 Free Software Foundation, Inc.
|
Copyright (C) 2007, 2008 Free Software Foundation, Inc.
|
Contributed by Peter Bergner <bergner@vnet.ibm.com>
|
Contributed by Peter Bergner <bergner@vnet.ibm.com>
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
GCC is free software; you can redistribute it and/or modify it under
|
the terms of the GNU General Public License as published by the Free
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "sparseset.h"
|
#include "sparseset.h"
|
|
|
/* Allocate and clear a n_elms SparseSet. */
|
/* Allocate and clear a n_elms SparseSet. */
|
|
|
sparseset
|
sparseset
|
sparseset_alloc (SPARSESET_ELT_TYPE n_elms)
|
sparseset_alloc (SPARSESET_ELT_TYPE n_elms)
|
{
|
{
|
unsigned int n_bytes = sizeof (struct sparseset_def)
|
unsigned int n_bytes = sizeof (struct sparseset_def)
|
+ ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));
|
+ ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));
|
|
|
/* We use xcalloc rather than xmalloc to silence some valgrind uninitialized
|
/* We use xcalloc rather than xmalloc to silence some valgrind uninitialized
|
read errors when accessing set->sparse[n] when "n" is not, and never has
|
read errors when accessing set->sparse[n] when "n" is not, and never has
|
been, in the set. These uninitialized reads are expected, by design and
|
been, in the set. These uninitialized reads are expected, by design and
|
harmless. If this turns into a performance problem due to some future
|
harmless. If this turns into a performance problem due to some future
|
additional users of sparseset, we can revisit this decision. */
|
additional users of sparseset, we can revisit this decision. */
|
sparseset set = (sparseset) xcalloc (1, n_bytes);
|
sparseset set = (sparseset) xcalloc (1, n_bytes);
|
set->dense = &(set->elms[0]);
|
set->dense = &(set->elms[0]);
|
set->sparse = &(set->elms[n_elms]);
|
set->sparse = &(set->elms[n_elms]);
|
set->size = n_elms;
|
set->size = n_elms;
|
sparseset_clear (set);
|
sparseset_clear (set);
|
return set;
|
return set;
|
}
|
}
|
|
|
/* Low level routine not meant for use outside of sparseset.[ch].
|
/* Low level routine not meant for use outside of sparseset.[ch].
|
Assumes idx1 < s->members and idx2 < s->members. */
|
Assumes idx1 < s->members and idx2 < s->members. */
|
|
|
static inline void
|
static inline void
|
sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2)
|
sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2)
|
{
|
{
|
SPARSESET_ELT_TYPE tmp = s->dense[idx2];
|
SPARSESET_ELT_TYPE tmp = s->dense[idx2];
|
sparseset_insert_bit (s, s->dense[idx1], idx2);
|
sparseset_insert_bit (s, s->dense[idx1], idx2);
|
sparseset_insert_bit (s, tmp, idx1);
|
sparseset_insert_bit (s, tmp, idx1);
|
}
|
}
|
|
|
/* Operation: S = S - {e}
|
/* Operation: S = S - {e}
|
Delete e from the set S if it is a member of S. */
|
Delete e from the set S if it is a member of S. */
|
|
|
void
|
void
|
sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e)
|
sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e)
|
{
|
{
|
if (sparseset_bit_p (s, e))
|
if (sparseset_bit_p (s, e))
|
{
|
{
|
SPARSESET_ELT_TYPE idx = s->sparse[e];
|
SPARSESET_ELT_TYPE idx = s->sparse[e];
|
SPARSESET_ELT_TYPE iter = s->iter;
|
SPARSESET_ELT_TYPE iter = s->iter;
|
SPARSESET_ELT_TYPE mem = s->members - 1;
|
SPARSESET_ELT_TYPE mem = s->members - 1;
|
|
|
/* If we are iterating over this set and we want to delete a
|
/* If we are iterating over this set and we want to delete a
|
member we've already visited, then we swap the element we
|
member we've already visited, then we swap the element we
|
want to delete with the element at the current iteration
|
want to delete with the element at the current iteration
|
index so that it plays well together with the code below
|
index so that it plays well together with the code below
|
that actually removes the element. */
|
that actually removes the element. */
|
if (s->iterating && idx <= iter)
|
if (s->iterating && idx <= iter)
|
{
|
{
|
if (idx < iter)
|
if (idx < iter)
|
{
|
{
|
sparseset_swap (s, idx, iter);
|
sparseset_swap (s, idx, iter);
|
idx = iter;
|
idx = iter;
|
}
|
}
|
s->iter_inc = 0;
|
s->iter_inc = 0;
|
}
|
}
|
|
|
/* Replace the element we want to delete with the last element
|
/* Replace the element we want to delete with the last element
|
in the dense array and then decrement s->members, effectively
|
in the dense array and then decrement s->members, effectively
|
removing the element we want to delete. */
|
removing the element we want to delete. */
|
sparseset_insert_bit (s, s->dense[mem], idx);
|
sparseset_insert_bit (s, s->dense[mem], idx);
|
s->members = mem;
|
s->members = mem;
|
}
|
}
|
}
|
}
|
|
|
/* Operation: D = S
|
/* Operation: D = S
|
Restrictions: none. */
|
Restrictions: none. */
|
|
|
void
|
void
|
sparseset_copy (sparseset d, sparseset s)
|
sparseset_copy (sparseset d, sparseset s)
|
{
|
{
|
SPARSESET_ELT_TYPE i;
|
SPARSESET_ELT_TYPE i;
|
|
|
if (d == s)
|
if (d == s)
|
return;
|
return;
|
|
|
sparseset_clear (d);
|
sparseset_clear (d);
|
for (i = 0; i < s->members; i++)
|
for (i = 0; i < s->members; i++)
|
sparseset_insert_bit (d, s->dense[i], i);
|
sparseset_insert_bit (d, s->dense[i], i);
|
d->members = s->members;
|
d->members = s->members;
|
}
|
}
|
|
|
/* Operation: D = A & B.
|
/* Operation: D = A & B.
|
Restrictions: none. */
|
Restrictions: none. */
|
|
|
void
|
void
|
sparseset_and (sparseset d, sparseset a, sparseset b)
|
sparseset_and (sparseset d, sparseset a, sparseset b)
|
{
|
{
|
SPARSESET_ELT_TYPE e;
|
SPARSESET_ELT_TYPE e;
|
|
|
if (a == b)
|
if (a == b)
|
{
|
{
|
if (d != a)
|
if (d != a)
|
sparseset_copy (d, a);
|
sparseset_copy (d, a);
|
return;
|
return;
|
}
|
}
|
|
|
if (d == a || d == b)
|
if (d == a || d == b)
|
{
|
{
|
sparseset s = (d == a) ? b : a;
|
sparseset s = (d == a) ? b : a;
|
|
|
EXECUTE_IF_SET_IN_SPARSESET (d, e)
|
EXECUTE_IF_SET_IN_SPARSESET (d, e)
|
if (!sparseset_bit_p (s, e))
|
if (!sparseset_bit_p (s, e))
|
sparseset_clear_bit (d, e);
|
sparseset_clear_bit (d, e);
|
}
|
}
|
else
|
else
|
{
|
{
|
sparseset sml, lrg;
|
sparseset sml, lrg;
|
|
|
if (sparseset_cardinality (a) < sparseset_cardinality (b))
|
if (sparseset_cardinality (a) < sparseset_cardinality (b))
|
{
|
{
|
sml = a;
|
sml = a;
|
lrg = b;
|
lrg = b;
|
}
|
}
|
else
|
else
|
{
|
{
|
sml = b;
|
sml = b;
|
lrg = a;
|
lrg = a;
|
}
|
}
|
|
|
sparseset_clear (d);
|
sparseset_clear (d);
|
EXECUTE_IF_SET_IN_SPARSESET (sml, e)
|
EXECUTE_IF_SET_IN_SPARSESET (sml, e)
|
if (sparseset_bit_p (lrg, e))
|
if (sparseset_bit_p (lrg, e))
|
sparseset_set_bit (d, e);
|
sparseset_set_bit (d, e);
|
}
|
}
|
}
|
}
|
|
|
/* Operation: D = A & ~B.
|
/* Operation: D = A & ~B.
|
Restrictions: D != B, unless D == A == B. */
|
Restrictions: D != B, unless D == A == B. */
|
|
|
void
|
void
|
sparseset_and_compl (sparseset d, sparseset a, sparseset b)
|
sparseset_and_compl (sparseset d, sparseset a, sparseset b)
|
{
|
{
|
SPARSESET_ELT_TYPE e;
|
SPARSESET_ELT_TYPE e;
|
|
|
if (a == b)
|
if (a == b)
|
{
|
{
|
sparseset_clear (d);
|
sparseset_clear (d);
|
return;
|
return;
|
}
|
}
|
|
|
gcc_assert (d != b);
|
gcc_assert (d != b);
|
|
|
if (d == a)
|
if (d == a)
|
{
|
{
|
if (sparseset_cardinality (d) < sparseset_cardinality (b))
|
if (sparseset_cardinality (d) < sparseset_cardinality (b))
|
{
|
{
|
EXECUTE_IF_SET_IN_SPARSESET (d, e)
|
EXECUTE_IF_SET_IN_SPARSESET (d, e)
|
if (sparseset_bit_p (b, e))
|
if (sparseset_bit_p (b, e))
|
sparseset_clear_bit (d, e);
|
sparseset_clear_bit (d, e);
|
}
|
}
|
else
|
else
|
{
|
{
|
EXECUTE_IF_SET_IN_SPARSESET (b, e)
|
EXECUTE_IF_SET_IN_SPARSESET (b, e)
|
sparseset_clear_bit (d, e);
|
sparseset_clear_bit (d, e);
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
sparseset_clear (d);
|
sparseset_clear (d);
|
EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
if (!sparseset_bit_p (b, e))
|
if (!sparseset_bit_p (b, e))
|
sparseset_set_bit (d, e);
|
sparseset_set_bit (d, e);
|
}
|
}
|
}
|
}
|
|
|
/* Operation: D = A | B.
|
/* Operation: D = A | B.
|
Restrictions: none. */
|
Restrictions: none. */
|
|
|
void
|
void
|
sparseset_ior (sparseset d, sparseset a, sparseset b)
|
sparseset_ior (sparseset d, sparseset a, sparseset b)
|
{
|
{
|
SPARSESET_ELT_TYPE e;
|
SPARSESET_ELT_TYPE e;
|
|
|
if (a == b)
|
if (a == b)
|
sparseset_copy (d, a);
|
sparseset_copy (d, a);
|
else if (d == b)
|
else if (d == b)
|
{
|
{
|
EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
sparseset_set_bit (d, e);
|
sparseset_set_bit (d, e);
|
}
|
}
|
else
|
else
|
{
|
{
|
if (d != a)
|
if (d != a)
|
sparseset_copy (d, a);
|
sparseset_copy (d, a);
|
EXECUTE_IF_SET_IN_SPARSESET (b, e)
|
EXECUTE_IF_SET_IN_SPARSESET (b, e)
|
sparseset_set_bit (d, e);
|
sparseset_set_bit (d, e);
|
}
|
}
|
}
|
}
|
|
|
/* Operation: A == B
|
/* Operation: A == B
|
Restrictions: none. */
|
Restrictions: none. */
|
|
|
bool
|
bool
|
sparseset_equal_p (sparseset a, sparseset b)
|
sparseset_equal_p (sparseset a, sparseset b)
|
{
|
{
|
SPARSESET_ELT_TYPE e;
|
SPARSESET_ELT_TYPE e;
|
|
|
if (a == b)
|
if (a == b)
|
return true;
|
return true;
|
|
|
if (sparseset_cardinality (a) != sparseset_cardinality (b))
|
if (sparseset_cardinality (a) != sparseset_cardinality (b))
|
return false;
|
return false;
|
|
|
EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
if (!sparseset_bit_p (b, e))
|
if (!sparseset_bit_p (b, e))
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
|
|
