/* Functions to support general ended bitmaps.
- Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
+ Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
Free Software Foundation, Inc.
This file is part of GCC.
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, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#ifndef GCC_BITMAP_H
#define GCC_BITMAP_H
/* Fundamental storage type for bitmap. */
-/* typedef unsigned HOST_WIDE_INT BITMAP_WORD; */
-/* #define nBITMAP_WORD_BITS HOST_BITS_PER_WIDE_INT */
typedef unsigned long BITMAP_WORD;
-#define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG)
-#define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS
+/* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
+ it is used in preprocessor directives -- hence the 1u. */
+#define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
/* Number of words to use for each element in the linked list. */
#ifndef BITMAP_ELEMENT_WORDS
-#define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS)
+#define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
#endif
-/* Number of bits in each actual element of a bitmap. We get slightly better
- code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if
- bits is unsigned, assuming it is a power of 2. */
+/* Number of bits in each actual element of a bitmap. */
-#define BITMAP_ELEMENT_ALL_BITS \
- ((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS))
+#define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
+
+/* Obstack for allocating bitmaps and elements from. */
+typedef struct bitmap_obstack GTY (())
+{
+ struct bitmap_element_def *elements;
+ struct bitmap_head_def *heads;
+ struct obstack GTY ((skip)) obstack;
+} bitmap_obstack;
/* Bitmap set element. We use a linked list to hold only the bits that
are set. This allows for use to grow the bitset dynamically without
- having to realloc and copy a giant bit array. The `prev' field is
- undefined for an element on the free list. */
+ having to realloc and copy a giant bit array.
+
+ The free list is implemented as a list of lists. There is one
+ outer list connected together by prev fields. Each element of that
+ outer is an inner list (that may consist only of the outer list
+ element) that are connected by the next fields. The prev pointer
+ is undefined for interior elements. This allows
+ bitmap_elt_clear_from to be implemented in unit time rather than
+ linear in the number of elements to be freed. */
typedef struct bitmap_element_def GTY(())
{
bitmap_element *first; /* First element in linked list. */
bitmap_element *current; /* Last element looked at. */
unsigned int indx; /* Index of last element looked at. */
- int using_obstack; /* Are we using an obstack or ggc for
- allocation? */
+ bitmap_obstack *obstack; /* Obstack to allocate elements from.
+ If NULL, then use ggc_alloc. */
} bitmap_head;
-typedef struct bitmap_head_def *bitmap;
-/* Enumeration giving the various operations we support. */
-enum bitmap_bits {
- BITMAP_AND, /* TO = FROM1 & FROM2 */
- BITMAP_AND_COMPL, /* TO = FROM1 & ~ FROM2 */
- BITMAP_IOR, /* TO = FROM1 | FROM2 */
- BITMAP_XOR, /* TO = FROM1 ^ FROM2 */
- BITMAP_IOR_COMPL /* TO = FROM1 | ~FROM2 */
-};
+
+typedef struct bitmap_head_def *bitmap;
/* Global data */
extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
+extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */
/* Clear a bitmap by freeing up the linked list. */
extern void bitmap_clear (bitmap);
/* True if MAP is an empty bitmap. */
#define bitmap_empty_p(MAP) (!(MAP)->first)
-/* Perform an operation on two bitmaps, yielding a third. */
-extern int bitmap_operation (bitmap, bitmap, bitmap, enum bitmap_bits);
-
-#define bitmap_and(DST,A,B) (void)bitmap_operation (DST,A,B,BITMAP_AND)
-#define bitmap_and_into(DST_SRC,B) (void)bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_AND)
-#define bitmap_and_compl(DST,A,B) (void)bitmap_operation (DST,A,B,BITMAP_AND_COMPL)
-#define bitmap_and_compl_into(DST_SRC,B) (void)bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_AND_COMPL)
-#define bitmap_ior(DST,A,B) (void)bitmap_operation (DST,A,B,BITMAP_IOR)
-#define bitmap_ior_into(DST_SRC,B) (void)bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_IOR)
-#define bitmap_ior_compl(DST,A,B) (void)bitmap_operation (DST,A,Br,BITMAP_IOR_COMPL)
-#define bitmap_xor(DST,A,B) (void)bitmap_operation (DST,A,B,BITMAP_XOR)
-#define bitmap_xor_into(DST_SRC,B) (void)bitmap_operation (DST_SRC,DST_SRC,B,BITMAP_XOR)
-
-/* `or' into one bitmap the `and' of a second bitmap witih the complement
- of a third. Return nonzero if the bitmap changes. */
-extern bool bitmap_ior_and_compl_into (bitmap, bitmap, bitmap);
-extern bool bitmap_ior_and_compl (bitmap, bitmap, bitmap, bitmap);
+/* Boolean operations on bitmaps. The _into variants are two operand
+ versions that modify the first source operand. The other variants
+ are three operand versions that to not destroy the source bitmaps.
+ The operations supported are &, & ~, |, ^. */
+extern void bitmap_and (bitmap, bitmap, bitmap);
+extern void bitmap_and_into (bitmap, bitmap);
+extern void bitmap_and_compl (bitmap, bitmap, bitmap);
+extern bool bitmap_and_compl_into (bitmap, bitmap);
+extern bool bitmap_ior (bitmap, bitmap, bitmap);
+extern bool bitmap_ior_into (bitmap, bitmap);
+extern void bitmap_xor (bitmap, bitmap, bitmap);
+extern void bitmap_xor_into (bitmap, bitmap);
+
+/* DST = A | (B & ~C). Return true if DST changes. */
+extern bool bitmap_ior_and_compl (bitmap DST, bitmap A, bitmap B, bitmap C);
+/* A |= (B & ~C). Return true if A changes. */
+extern bool bitmap_ior_and_compl_into (bitmap DST, bitmap B, bitmap C);
/* Clear a single register in a register set. */
extern void bitmap_clear_bit (bitmap, int);
/* Print a bitmap. */
extern void bitmap_print (FILE *, bitmap, const char *, const char *);
-/* Initialize a bitmap header. If HEAD is NULL, a new header will be
- allocated. USING_OBSTACK indicates how elements should be allocated. */
-extern bitmap bitmap_initialize (bitmap head, int using_obstack);
+/* Initialize and release a bitmap obstack. */
+extern void bitmap_obstack_initialize (bitmap_obstack *);
+extern void bitmap_obstack_release (bitmap_obstack *);
-/* Release all memory used by the bitmap obstack. */
-extern void bitmap_release_memory (void);
+/* Initialize a bitmap header. OBSTACK indicates the bitmap obstack
+ to allocate from, NULL for GC'd bitmap. */
+
+static inline void
+bitmap_initialize (bitmap head, bitmap_obstack *obstack)
+{
+ head->first = head->current = NULL;
+ head->obstack = obstack;
+}
+
+/* Allocate and free bitmaps from obstack, malloc and gc'd memory. */
+extern bitmap bitmap_obstack_alloc (bitmap_obstack *obstack);
+extern bitmap bitmap_gc_alloc (void);
+extern void bitmap_obstack_free (bitmap);
/* A few compatibility/functions macros for compatibility with sbitmaps */
#define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
#define bitmap_zero(a) bitmap_clear (a)
-extern int bitmap_first_set_bit (bitmap);
-extern int bitmap_last_set_bit (bitmap);
-
-/* Allocate a bitmap with oballoc. */
-#define BITMAP_OBSTACK_ALLOC(OBSTACK) \
- bitmap_initialize (obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1)
+extern unsigned bitmap_first_set_bit (bitmap);
-/* Allocate a bitmap with ggc_alloc. */
-#define BITMAP_GGC_ALLOC() \
- bitmap_initialize (NULL, 0)
+/* Allocate a bitmap from a bit obstack. */
+#define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
-/* Allocate a bitmap with xmalloc. */
-#define BITMAP_XMALLOC() \
- bitmap_initialize (xmalloc (sizeof (bitmap_head)), 1)
+/* Allocate a gc'd bitmap. */
+#define BITMAP_GGC_ALLOC() bitmap_gc_alloc ()
/* Do any cleanup needed on a bitmap when it is no longer used. */
#define BITMAP_FREE(BITMAP) \
-do { \
- if (BITMAP) \
- { \
- bitmap_clear (BITMAP); \
- (BITMAP) = 0; \
- } \
-} while (0)
-
-/* Do any cleanup needed on an xmalloced bitmap when it is no longer used. */
-#define BITMAP_XFREE(BITMAP) \
-do { \
- if (BITMAP) \
- { \
- bitmap_clear (BITMAP); \
- free (BITMAP); \
- (BITMAP) = 0; \
- } \
-} while (0)
-
-/* Do any one-time initializations needed for bitmaps. */
-#define BITMAP_INIT_ONCE()
+ ((void)(bitmap_obstack_free (BITMAP), (BITMAP) = NULL))
/* Iterator for bitmaps. */
bi->elt2 = bi->elt2->next;
}
- /* If we're at the same index, then we have some intersecting bits. */
+ /* If we're at the same index, then we have some intersecting bits. */
if (bi->elt1->indx == bi->elt2->indx)
{
/* We might have advanced beyond the start_bit, so reinitialize
OSDN Git Service
