/* Functions to support general ended bitmaps.
- Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004
+ Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005
Free Software Foundation, Inc.
This file is part of GCC.
#include "ggc.h"
#include "bitmap.h"
-/* Obstack to allocate bitmap elements from. */
-\f
-#ifndef INLINE
-#ifndef __GNUC__
-#define INLINE
-#else
-#define INLINE __inline__
-#endif
-#endif
-
/* Global data */
bitmap_element bitmap_zero_bits; /* An element of all zero bits. */
bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */
\f
/* Add ELEM to the appropriate freelist. */
-static INLINE void
+static inline void
bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
{
bitmap_obstack *bit_obstack = head->obstack;
+ elt->next = NULL;
if (bit_obstack)
{
- elt->next = bit_obstack->elements;
+ elt->prev = bit_obstack->elements;
bit_obstack->elements = elt;
}
else
{
- elt->next = bitmap_ggc_free;
+ elt->prev = bitmap_ggc_free;
bitmap_ggc_free = elt;
}
}
/* Free a bitmap element. Since these are allocated off the
bitmap_obstack, "free" actually means "put onto the freelist". */
-static INLINE void
+static inline void
bitmap_element_free (bitmap head, bitmap_element *elt)
{
bitmap_element *next = elt->next;
\f
/* Allocate a bitmap element. The bits are cleared, but nothing else is. */
-static INLINE bitmap_element *
+static inline bitmap_element *
bitmap_element_allocate (bitmap head)
{
bitmap_element *element;
element = bit_obstack->elements;
if (element)
- bit_obstack->elements = element->next;
+ /* Use up the inner list first before looking at the next
+ element of the outer list. */
+ if (element->next)
+ {
+ bit_obstack->elements = element->next;
+ bit_obstack->elements->prev = element->prev;
+ }
+ else
+ /* Inner list was just a singleton. */
+ bit_obstack->elements = element->prev;
else
element = XOBNEW (&bit_obstack->obstack, bitmap_element);
}
{
element = bitmap_ggc_free;
if (element)
- bitmap_ggc_free = element->next;
+ /* Use up the inner list first before looking at the next
+ element of the outer list. */
+ if (element->next)
+ {
+ bitmap_ggc_free = element->next;
+ bitmap_ggc_free->prev = element->prev;
+ }
+ else
+ /* Inner list was just a singleton. */
+ bitmap_ggc_free = element->prev;
else
element = GGC_NEW (bitmap_element);
}
void
bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
{
- bitmap_element *next;
+ bitmap_element *prev;
+ bitmap_obstack *bit_obstack = head->obstack;
+
+ if (!elt) return;
+
+ prev = elt->prev;
+ if (prev)
+ {
+ prev->next = NULL;
+ if (head->current->indx > prev->indx)
+ {
+ head->current = prev;
+ head->indx = prev->indx;
+ }
+ }
+ else
+ {
+ head->first = NULL;
+ head->current = NULL;
+ head->indx = 0;
+ }
- while (elt)
+ /* Put the entire list onto the free list in one operation. */
+ if (bit_obstack)
+ {
+ elt->prev = bit_obstack->elements;
+ bit_obstack->elements = elt;
+ }
+ else
{
- next = elt->next;
- bitmap_element_free (head, elt);
- elt = next;
+ elt->prev = bitmap_ggc_free;
+ bitmap_ggc_free = elt;
}
}
/* Clear a bitmap by freeing the linked list. */
-INLINE void
+inline void
bitmap_clear (bitmap head)
{
- bitmap_element *element, *next;
-
- for (element = head->first; element != 0; element = next)
- {
- next = element->next;
- bitmap_elem_to_freelist (head, element);
- }
-
- head->first = head->current = 0;
+ if (head->first)
+ bitmap_elt_clear_from (head, head->first);
}
\f
/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
return map;
}
-/* Create a new malloced bitmap. Elements will be allocated from the
- default bitmap obstack. */
-
-bitmap
-bitmap_malloc_alloc (void)
-{
- bitmap map;
-
- map = xmalloc (sizeof (bitmap_head));
- bitmap_initialize (map, &bitmap_default_obstack);
-
- return map;
-}
-
/* Release an obstack allocated bitmap. */
void
bitmap_obstack_free (bitmap map)
{
- bitmap_clear (map);
- map->first = (void *)map->obstack->heads;
- map->obstack->heads = map;
-}
-
-/* Release a malloc allocated bitmap. */
-
-void
-bitmap_malloc_free (bitmap map)
-{
- bitmap_clear (map);
- free (map);
+ if (map)
+ {
+ bitmap_clear (map);
+ map->first = (void *)map->obstack->heads;
+ map->obstack->heads = map;
+ }
}
\f
/* Return nonzero if all bits in an element are zero. */
-static INLINE int
+static inline int
bitmap_element_zerop (bitmap_element *element)
{
#if BITMAP_ELEMENT_WORDS == 2
\f
/* Link the bitmap element into the current bitmap linked list. */
-static INLINE void
+static inline void
bitmap_element_link (bitmap head, bitmap_element *element)
{
unsigned int indx = element->indx;
bitmap_copy (bitmap to, bitmap from)
{
bitmap_element *from_ptr, *to_ptr = 0;
-#if BITMAP_ELEMENT_WORDS != 2
- unsigned i;
-#endif
bitmap_clear (to);
bitmap_element *to_elt = bitmap_element_allocate (to);
to_elt->indx = from_ptr->indx;
-
-#if BITMAP_ELEMENT_WORDS == 2
- to_elt->bits[0] = from_ptr->bits[0];
- to_elt->bits[1] = from_ptr->bits[1];
-#else
- for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
- to_elt->bits[i] = from_ptr->bits[i];
-#endif
+ memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
/* Here we have a special case of bitmap_element_link, for the case
where we know the links are being entered in sequence. */
would hold the bitmap's bit to make eventual allocation
faster. */
-static INLINE bitmap_element *
+static inline bitmap_element *
bitmap_find_bit (bitmap head, unsigned int bit)
{
bitmap_element *element;
|| head->indx == indx)
return head->current;
- if (head->indx > indx)
+ if (head->indx < indx)
+ /* INDX is beyond head->indx. Search from head->current
+ forward. */
+ for (element = head->current;
+ element->next != 0 && element->indx < indx;
+ element = element->next)
+ ;
+
+ else if (head->indx / 2 < indx)
+ /* INDX is less than head->indx and closer to head->indx than to
+ 0. Search from head->current backward. */
for (element = head->current;
element->prev != 0 && element->indx > indx;
element = element->prev)
;
else
- for (element = head->current;
+ /* INDX is less than head->indx and closer to 0 than to
+ head->indx. Search from head->first forward. */
+ for (element = head->first;
element->next != 0 && element->indx < indx;
element = element->next)
;
dst->indx = dst->current->indx;
}
-/* A &= ~B */
+/* A &= ~B. Returns true if A changes */
-void
+bool
bitmap_and_compl_into (bitmap a, bitmap b)
{
bitmap_element *a_elt = a->first;
bitmap_element *b_elt = b->first;
bitmap_element *next;
+ BITMAP_WORD changed = 0;
gcc_assert (a != b);
while (a_elt && b_elt)
for (ix = BITMAP_ELEMENT_WORDS; ix--;)
{
- BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
+ BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
+ BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
a_elt->bits[ix] = r;
+ changed |= cleared;
ior |= r;
}
next = a_elt->next;
}
gcc_assert (!a->current == !a->first);
gcc_assert (!a->current || a->indx == a->current->indx);
+ return changed != 0;
}
/* DST = A | B. Return true if DST changes. */
OSDN Git Service
