URL
https://opencores.org/ocsvn/openrisc_2011-10-31/openrisc_2011-10-31/trunk
Subversion Repositories openrisc_2011-10-31
[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [ebitmap.h] - Rev 518
Go to most recent revision | Compare with Previous | Blame | View Log
/* 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 <http://www.gnu.org/licenses/>. */ #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 */
Go to most recent revision | Compare with Previous | Blame | View Log