/* Sparse array-based bitmaps.
- Copyright (C) 2007 Free Software Foundation, Inc.
+ Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>
This file is part of GCC.
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
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "rtl.h"
-#include "flags.h"
-#include "obstack.h"
#include "ebitmap.h"
/* The ebitmap data structure is a sparse bitmap structure that works
by having two pieces:
- 1. An array of all non-zero words in the structures, organized as
+ 1. An array of all nonzero words in the structures, organized as
an array of HOST_WIDE_INT's.
2. A non-sparse bitmap saying which bitmap words are present in the
array.
unsigned int i = 0;
ebitmap_iterator ebi;
bool foundbit = false;
-
+
/* This is not the fastest way to do this, we could simply look for
the popcount, and start there, but this function is not used
anywhere speed critical. */
{
foundbit = true;
}
-
+
if (foundbit)
return i;
newsize += newsize / 4;
map->n_elts = newsize;
- map->elts = xrealloc (map->elts, sizeof (EBITMAP_ELT_TYPE) * newsize);
+ map->elts = XRESIZEVEC (EBITMAP_ELT_TYPE, map->elts, newsize);
}
/* Grow the internal word array for MAP so it is at least SIZE
{
if (size > 0)
{
- map->elts = xmalloc (sizeof (EBITMAP_ELT_TYPE) * size);
+ map->elts = XNEWVEC (EBITMAP_ELT_TYPE, size);
map->n_elts = size;
}
else
static inline void
ebitmap_array_clear (ebitmap map)
{
- if (map->elts)
+ if (map->elts)
{
free (map->elts);
map->elts = NULL;
ebitmap
ebitmap_alloc (unsigned int size)
{
- ebitmap ret = xmalloc (sizeof (struct ebitmap_def));
+ ebitmap ret = XNEW (struct ebitmap_def);
if (size == 0)
size = EBITMAP_ELT_BITS;
ebitmap_array_init (ret, (size + EBITMAP_ELT_BITS - 1) / EBITMAP_ELT_BITS);
unsigned int bitindex, shift;
bool have_eltwordindex = false;
EBITMAP_ELT_TYPE *elt_ptr;
-
+
/* If the bit can't exist in our bitmap, just return. */
if (map->numwords == 0)
return;
if (wordindex >= map->wordmask->n_bits
|| !TEST_BIT (map->wordmask, wordindex))
return;
-
+
if (map->cache != NULL && map->cacheindex == wordindex)
elt_ptr = map->cache;
else
elt_ptr = &map->elts[eltwordindex];
have_eltwordindex = true;
}
-
+
bitindex = bit % EBITMAP_ELT_BITS;
shift = bitindex;
-
+
*(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift);
/* Clear out the empty words. */
{
if (!have_eltwordindex)
eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
-
- if (map->cache != NULL && map->cacheindex == eltwordindex)
- map->cache = NULL;
+
+ if (map->cache != NULL)
+ {
+ if (map->cacheindex == wordindex)
+ map->cache = NULL;
+ else if (map->cacheindex > wordindex)
+ map->cache = map->cache - 1;
+ }
RESET_BIT (map->wordmask, wordindex);
/* Dump ebitmap BMAP to stderr. */
-void
+DEBUG_FUNCTION void
debug_ebitmap (ebitmap bmap)
{
dump_ebitmap (stderr, bmap);
for (i = 0; i < dst->numwords; i++)
gcc_assert (dst->elts[i] != 0);
- verify_popcount (dst->wordmask);
+ sbitmap_verify_popcount (dst->wordmask);
gcc_assert (sbitmap_popcount (dst->wordmask,
dst->wordmask->n_bits) == dst->numwords);
}
for (i = 0; i < dst->numwords; i++)
gcc_assert (dst->elts[i] != 0);
- verify_popcount (dst->wordmask);
+ sbitmap_verify_popcount (dst->wordmask);
gcc_assert (sbitmap_popcount (dst->wordmask,
dst->wordmask->n_bits) == dst->numwords);
}
}
}
newarraysize = src->numwords + dst->numwords;
- newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
+ newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
{
EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
gcc_assert (ebitmap_bit_p (dst, i));
- verify_popcount (dst->wordmask);
+ sbitmap_verify_popcount (dst->wordmask);
gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
gcc_assert (sbitmap_popcount (dst->wordmask,
dst->wordmask->n_bits) == dst->numwords);
}
}
newarraysize = src1->numwords + src2->numwords;
- newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
+ newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
{
EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi)
gcc_assert (ebitmap_bit_p (dst, i));
}
- verify_popcount (dst->wordmask);
+ sbitmap_verify_popcount (dst->wordmask);
gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
gcc_assert (sbitmap_popcount (dst->wordmask,
dst->wordmask->n_bits) == dst->numwords);
gcc_assert (sbitmap_popcount (dst->wordmask,
dst->wordmask->n_bits) == neweltindex);
- verify_popcount (dst->wordmask);
+ sbitmap_verify_popcount (dst->wordmask);
gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
gcc_assert (sbitmap_popcount (dst->wordmask,
dst->wordmask->n_bits) == dst->numwords);
sbitmap_copy (tempmask, src1->wordmask);
newarraysize = src1->numwords;
- newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
+ newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi)
{
for (i = 0; i < dst->numwords; i++)
gcc_assert (dst->elts[i] != 0);
- verify_popcount (dst->wordmask);
+ sbitmap_verify_popcount (dst->wordmask);
gcc_assert (sbitmap_popcount (dst->wordmask,
dst->wordmask->n_bits) == dst->numwords);
}