gcc/ebitmap.h

   1 /* Sparse array based bitmaps.
   2    Copyright (C) 2007, 2008, 2009 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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef GCC_EBITMAP_H
  21 #define GCC_EBITMAP_H
  22
  23 #include "sbitmap.h"
  24
  25 #define EBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
  26 #define EBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
  27
  28 typedef struct ebitmap_def
  29 {
  30   unsigned int n_elts;          /* number of elements in the array.  */
  31   sbitmap wordmask;             /* wordmask saying which words are
  32                                    nonzero.  */
  33   unsigned int numwords;        /* number of nonzero words.  */
  34   unsigned int cacheindex;      /* which word cache is.  */
  35   EBITMAP_ELT_TYPE *elts;       /* nonzero element array.  */
  36   EBITMAP_ELT_TYPE *cache;      /* last tested element, or NULL.  */
  37 } *ebitmap;
  38
  39
  40 inline bool bitmap_empty_p (ebitmap map)
  41 {
  42   return map->numwords == 0;
  43 }
  44
  45 #define ebitmap_free(MAP)  (free((MAP)->elts), \
  46                             sbitmap_free ((MAP)->wordmask),     \
  47                             free((MAP)))
  48
  49 extern void bitmap_set_bit (ebitmap, unsigned int);
  50 extern void bitmap_clear_bit (ebitmap, unsigned int);
  51 extern bool bitmap_bit_p (ebitmap, unsigned int);
  52 extern void dump_bitmap (FILE *, ebitmap);
  53 extern void dump_bitmap_file (FILE *, ebitmap);
  54 extern void dump_bitmap_vector (FILE *, const char *, const char *, ebitmap *,
  55                                 int);
  56 extern ebitmap ebitmap_alloc (unsigned int);
  57 extern ebitmap *ebitmap_vector_alloc (unsigned int, unsigned int);
  58 extern void bitmap_copy (ebitmap, ebitmap);
  59 extern void bitmap_and (ebitmap, ebitmap, ebitmap);
  60 extern void bitmap_and_into (ebitmap, ebitmap);
  61 extern bool bitmap_and_compl (ebitmap, ebitmap, ebitmap);
  62 extern bool bitmap_and_compl_into (ebitmap, ebitmap);
  63 extern bool bitmap_ior_into (ebitmap, ebitmap);
  64 extern bool bitmap_ior (ebitmap, ebitmap, ebitmap);
  65 extern bool bitmap_ior_and_compl (ebitmap, ebitmap, ebitmap, ebitmap);
  66 extern bool bitmap_ior_and_compl_into (ebitmap, ebitmap, ebitmap);
  67 extern bool bitmap_equal_p (ebitmap, ebitmap);
  68 extern void bitmap_clear (ebitmap);
  69 extern int bitmap_last_set_bit (ebitmap);
  70 extern void debug_bitmap (ebitmap);
  71 extern unsigned long bitmap_popcount(ebitmap, unsigned long);
  72
  73 /* The iterator for ebitmap.  */
  74 typedef struct {
  75   /* The pointer to the first word of the bitmap.  */
  76   EBITMAP_ELT_TYPE *ptr;
  77
  78   /* Element number inside ptr that we are at.  */
  79   unsigned int eltnum;
  80
  81   /* The size of the bitmap.  */
  82   unsigned int size;
  83
  84   /* Current bit index.  */
  85   unsigned int bit_num;
  86
  87   /* The words currently visited.  */
  88   EBITMAP_ELT_TYPE word;
  89
  90   /* The word mask iterator.  */
  91   sbitmap_iterator maskiter;
  92 } ebitmap_iterator;
  93
  94 static inline void
  95 ebitmap_iter_init (ebitmap_iterator *i, ebitmap bmp, unsigned int min)
  96 {
  97   unsigned unused;
  98   bmp_iter_set_init (&i->maskiter, bmp->wordmask,
  99                      min / EBITMAP_ELT_BITS, &unused);
 100   i->size = bmp->numwords;
 101   if (i->size == 0)
 102     {
 103       i->ptr = NULL;
 104       i->eltnum = 0;
 105       i->bit_num = 0;
 106       i->word = 0;
 107       return;
 108     }
 109   i->ptr = bmp->elts;
 110   i->bit_num = min;
 111   i->eltnum = 0;
 112
 113   if ((min / EBITMAP_ELT_BITS) >= bmp->wordmask->n_bits)
 114     {
 115       i->word = 0;
 116     }
 117   else
 118     {
 119       if (bitmap_bit_p (bmp->wordmask, min / EBITMAP_ELT_BITS) == 0)
 120         i->word = 0;
 121       else
 122         {
 123           unsigned int wordindex = min / EBITMAP_ELT_BITS;
 124           unsigned int count = sbitmap_popcount (bmp->wordmask, wordindex);
 125           i->word = i->ptr[count] >> (i->bit_num % (unsigned int)EBITMAP_ELT_BITS);
 126           i->eltnum = count + 1;
 127         }
 128     }
 129 }
 130
 131 static inline bool
 132 ebitmap_iter_cond (ebitmap_iterator *i, unsigned int *n)
 133 {
 134   unsigned int ourn = 0;
 135   unsigned unused;
 136
 137   if (i->size == 0)
 138     return false;
 139
 140   if (i->word == 0)
 141     {
 142       bmp_iter_next (&i->maskiter, &unused);
 143       if (!bmp_iter_set (&i->maskiter, &ourn))
 144         return false;
 145       i->bit_num = ourn * EBITMAP_ELT_BITS;
 146       i->word = i->ptr[i->eltnum++];
 147     }
 148
 149   /* Skip bits that are zero.  */
 150
 151   for (; (i->word & 1) == 0; i->word >>= 1)
 152     i->bit_num++;
 153
 154   *n = i->bit_num;
 155   return true;
 156 }
 157
 158 static inline void
 159 ebitmap_iter_next (ebitmap_iterator *i)
 160 {
 161   i->word >>= 1;
 162   i->bit_num++;
 163 }
 164
 165 /* Loop over all elements of EBITMAP, starting with MIN.  In each
 166    iteration, N is set to the index of the bit being visited.  ITER is
 167    an instance of ebitmap_iterator used to iterate the bitmap.  */
 168
 169 #define EXECUTE_IF_SET_IN_EBITMAP(EBITMAP, MIN, N, ITER)        \
 170   for (ebitmap_iter_init (&(ITER), (EBITMAP), (MIN));           \
 171        ebitmap_iter_cond (&(ITER), &(N));                       \
 172        ebitmap_iter_next (&(ITER)))
 173
 174
 175 #endif /* ! GCC_EBITMAP_H */