Subversion Repositories openrisc_2011-10-31

/* 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 */