From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- gcc/ebitmap.h | 169 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 169 insertions(+) create mode 100644 gcc/ebitmap.h (limited to 'gcc/ebitmap.h') diff --git a/gcc/ebitmap.h b/gcc/ebitmap.h new file mode 100644 index 000000000..b067ddb89 --- /dev/null +++ b/gcc/ebitmap.h @@ -0,0 +1,169 @@ +/* Sparse array based bitmaps. + Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. + +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 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_EBITMAP_H +#define GCC_EBITMAP_H + +#include "sbitmap.h" + +#define EBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT) +#define EBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT + +typedef struct ebitmap_def +{ + unsigned int n_elts; /* number of elements in the array. */ + sbitmap wordmask; /* wordmask saying which words are + nonzero. */ + unsigned int numwords; /* number of nonzero words. */ + unsigned int cacheindex; /* which word cache is. */ + EBITMAP_ELT_TYPE *elts; /* nonzero element array. */ + EBITMAP_ELT_TYPE *cache; /* last tested element, or NULL. */ +} *ebitmap; + + +#define ebitmap_empty_p(MAP) ((MAP)->numwords == 0) +#define ebitmap_free(MAP) (free((MAP)->elts), \ + sbitmap_free ((MAP)->wordmask), \ + free((MAP))) + +extern void ebitmap_set_bit (ebitmap, unsigned int); +extern void ebitmap_clear_bit (ebitmap, unsigned int); +extern bool ebitmap_bit_p (ebitmap, unsigned int); +extern void dump_ebitmap (FILE *, ebitmap); +extern void dump_ebitmap_file (FILE *, ebitmap); +extern void dump_ebitmap_vector (FILE *, const char *, const char *, ebitmap *, + int); +extern ebitmap ebitmap_alloc (unsigned int); +extern ebitmap *ebitmap_vector_alloc (unsigned int, unsigned int); +extern void ebitmap_copy (ebitmap, ebitmap); +extern void ebitmap_and (ebitmap, ebitmap, ebitmap); +extern void ebitmap_and_into (ebitmap, ebitmap); +extern bool ebitmap_and_compl (ebitmap, ebitmap, ebitmap); +extern bool ebitmap_and_compl_into (ebitmap, ebitmap); +extern bool ebitmap_ior_into (ebitmap, ebitmap); +extern bool ebitmap_ior (ebitmap, ebitmap, ebitmap); +extern bool ebitmap_ior_and_compl (ebitmap, ebitmap, ebitmap, ebitmap); +extern bool ebitmap_ior_and_compl_into (ebitmap, ebitmap, ebitmap); +extern bool ebitmap_equal_p (ebitmap, ebitmap); +extern void ebitmap_clear (ebitmap); +extern int ebitmap_last_set_bit (ebitmap); +extern void debug_ebitmap (ebitmap); +extern unsigned long ebitmap_popcount(ebitmap, unsigned long); + +/* The iterator for ebitmap. */ +typedef struct { + /* The pointer to the first word of the bitmap. */ + EBITMAP_ELT_TYPE *ptr; + + /* Element number inside ptr that we are at. */ + unsigned int eltnum; + + /* The size of the bitmap. */ + unsigned int size; + + /* Current bit index. */ + unsigned int bit_num; + + /* The words currently visited. */ + EBITMAP_ELT_TYPE word; + + /* The word mask iterator. */ + sbitmap_iterator maskiter; +} ebitmap_iterator; + +static inline void +ebitmap_iter_init (ebitmap_iterator *i, ebitmap bmp, unsigned int min) +{ + sbitmap_iter_init (&i->maskiter, bmp->wordmask, + min / EBITMAP_ELT_BITS); + i->size = bmp->numwords; + if (i->size == 0) + { + i->ptr = NULL; + i->eltnum = 0; + i->bit_num = 0; + i->word = 0; + return; + } + i->ptr = bmp->elts; + i->bit_num = min; + i->eltnum = 0; + + if ((min / EBITMAP_ELT_BITS) >= bmp->wordmask->n_bits) + { + i->word = 0; + } + else + { + if (TEST_BIT (bmp->wordmask, min / EBITMAP_ELT_BITS) == 0) + i->word = 0; + else + { + unsigned int wordindex = min / EBITMAP_ELT_BITS; + unsigned int count = sbitmap_popcount (bmp->wordmask, wordindex); + i->word = i->ptr[count] >> (i->bit_num % (unsigned int)EBITMAP_ELT_BITS); + i->eltnum = count + 1; + } + } +} + +static inline bool +ebitmap_iter_cond (ebitmap_iterator *i, unsigned int *n) +{ + unsigned int ourn = 0; + + if (i->size == 0) + return false; + + if (i->word == 0) + { + sbitmap_iter_next (&i->maskiter); + if (!sbitmap_iter_cond (&i->maskiter, &ourn)) + return false; + i->bit_num = ourn * EBITMAP_ELT_BITS; + i->word = i->ptr[i->eltnum++]; + } + + /* Skip bits that are zero. */ + + for (; (i->word & 1) == 0; i->word >>= 1) + i->bit_num++; + + *n = i->bit_num; + return true; +} + +static inline void +ebitmap_iter_next (ebitmap_iterator *i) +{ + i->word >>= 1; + i->bit_num++; +} + +/* Loop over all elements of EBITMAP, starting with MIN. In each + iteration, N is set to the index of the bit being visited. ITER is + an instance of ebitmap_iterator used to iterate the bitmap. */ + +#define EXECUTE_IF_SET_IN_EBITMAP(EBITMAP, MIN, N, ITER) \ + for (ebitmap_iter_init (&(ITER), (EBITMAP), (MIN)); \ + ebitmap_iter_cond (&(ITER), &(N)); \ + ebitmap_iter_next (&(ITER))) + + +#endif /* ! GCC_EBITMAP_H */ -- cgit v1.2.3