gcc/ebitmap.h

   1 /* Sparse array based bitmaps.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  20
  21 #ifndef GCC_EBITMAP_H
  22 #define GCC_EBITMAP_H
  23
  24 #include "sbitmap.h"
  25
  26 #define EBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
  27 #define EBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
  28
  29 typedef struct ebitmap_def
  30 {
  31   unsigned int n_elts;          /* number of elements in the array.  */
  32   sbitmap wordmask;             /* wordmask saying which words are
  33                                    nonzero.  */
  34   unsigned int numwords;        /* number of nonzero words.  */
  35   unsigned int cacheindex;      /* which word cache is.  */
  36   EBITMAP_ELT_TYPE *elts;       /* nonzero element array.  */
  37   EBITMAP_ELT_TYPE *cache;      /* last tested element, or NULL.  */
  38 } *ebitmap;
  39
  40
  41 #define ebitmap_empty_p(MAP) ((MAP)->numwords == 0)
  42 #define ebitmap_free(MAP)  (free((MAP)->elts), \
  43                             sbitmap_free ((MAP)->wordmask),     \
  44                             free((MAP)))
  45
  46 extern void ebitmap_set_bit (ebitmap, unsigned int);
  47 extern void ebitmap_clear_bit (ebitmap, unsigned int);
  48 extern bool ebitmap_bit_p (ebitmap, unsigned int);
  49 extern void dump_ebitmap (FILE *, ebitmap);
  50 extern void dump_ebitmap_file (FILE *, ebitmap);
  51 extern void dump_ebitmap_vector (FILE *, const char *, const char *, ebitmap *,
  52                                  int);
  53 extern ebitmap ebitmap_alloc (unsigned int);
  54 extern ebitmap *ebitmap_vector_alloc (unsigned int, unsigned int);
  55 extern void ebitmap_copy (ebitmap, ebitmap);
  56 extern void ebitmap_and (ebitmap, ebitmap, ebitmap);
  57 extern void ebitmap_and_into (ebitmap, ebitmap);
  58 extern bool ebitmap_and_compl (ebitmap, ebitmap, ebitmap);
  59 extern bool ebitmap_and_compl_into (ebitmap, ebitmap);
  60 extern bool ebitmap_ior_into (ebitmap, ebitmap);
  61 extern bool ebitmap_ior (ebitmap, ebitmap, ebitmap);
  62 extern bool ebitmap_ior_and_compl (ebitmap, ebitmap, ebitmap, ebitmap);
  63 extern bool ebitmap_ior_and_compl_into (ebitmap, ebitmap, ebitmap);
  64 extern bool ebitmap_equal_p (ebitmap, ebitmap);
  65 extern void ebitmap_clear (ebitmap);
  66 extern int ebitmap_last_set_bit (ebitmap);
  67 extern void debug_ebitmap (ebitmap);
  68 extern void dump_ebitmap (FILE *, ebitmap);
  69 extern unsigned long ebitmap_popcount(ebitmap, unsigned long);
  70
  71 /* The iterator for ebitmap.  */
  72 typedef struct {
  73   /* The pointer to the first word of the bitmap.  */
  74   EBITMAP_ELT_TYPE *ptr;
  75
  76   /* Element number inside ptr that we are at.  */
  77   unsigned int eltnum;
  78
  79   /* The size of the bitmap.  */
  80   unsigned int size;
  81
  82   /* Current bit index.  */
  83   unsigned int bit_num;
  84
  85   /* The words currently visited.  */
  86   EBITMAP_ELT_TYPE word;
  87
  88   /* The word mask iterator.  */
  89   sbitmap_iterator maskiter;
  90 } ebitmap_iterator;
  91
  92 static inline void
  93 ebitmap_iter_init (ebitmap_iterator *i, ebitmap bmp, unsigned int min)
  94 {
  95   sbitmap_iter_init (&i->maskiter, bmp->wordmask,
  96                      min / EBITMAP_ELT_BITS);
  97   i->size = bmp->numwords;
  98   if (i->size == 0)
  99     return;
 100   i->ptr = bmp->elts;
 101   i->bit_num = min;
 102   i->eltnum = 0;
 103
 104   if ((min / EBITMAP_ELT_BITS) >= bmp->wordmask->n_bits)
 105     {
 106       i->word = 0;
 107     }
 108   else
 109     {
 110       if (TEST_BIT (bmp->wordmask, min / EBITMAP_ELT_BITS) == 0)
 111         i->word = 0;
 112       else
 113         {
 114           unsigned int wordindex = min / EBITMAP_ELT_BITS;
 115           unsigned int count = sbitmap_popcount (bmp->wordmask, wordindex);
 116           i->word = i->ptr[count] >> (i->bit_num % (unsigned int)EBITMAP_ELT_BITS);
 117           i->eltnum = count + 1;
 118         }
 119     }
 120 }
 121
 122 static inline bool
 123 ebitmap_iter_cond (ebitmap_iterator *i, unsigned int *n)
 124 {
 125   unsigned int ourn;
 126
 127   if (i->size == 0)
 128     return false;
 129
 130   if (i->word == 0)
 131     {
 132       sbitmap_iter_next (&i->maskiter);
 133       if (!sbitmap_iter_cond (&i->maskiter, &ourn))
 134         return false;
 135       i->bit_num = ourn * EBITMAP_ELT_BITS;
 136       i->word = i->ptr[i->eltnum++];
 137     }
 138
 139   /* Skip bits that are zero.  */
 140
 141   for (; (i->word & 1) == 0; i->word >>= 1)
 142     i->bit_num++;
 143
 144   *n = i->bit_num;
 145   return true;
 146 }
 147
 148 static inline void
 149 ebitmap_iter_next (ebitmap_iterator *i)
 150 {
 151   i->word >>= 1;
 152   i->bit_num++;
 153 }
 154
 155 /* Loop over all elements of EBITMAP, starting with MIN.  In each
 156    iteration, N is set to the index of the bit being visited.  ITER is
 157    an instance of ebitmap_iterator used to iterate the bitmap.  */
 158
 159 #define EXECUTE_IF_SET_IN_EBITMAP(EBITMAP, MIN, N, ITER)        \
 160   for (ebitmap_iter_init (&(ITER), (EBITMAP), (MIN));           \
 161        ebitmap_iter_cond (&(ITER), &(N));                       \
 162        ebitmap_iter_next (&(ITER)))
 163
 164
 165 #endif /* ! GCC_EBITMAP_H */