OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [ebitmap.h] - Blame information for rev 684

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* 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
#define ebitmap_empty_p(MAP) ((MAP)->numwords == 0)
41
#define ebitmap_free(MAP)  (free((MAP)->elts), \
42
                            sbitmap_free ((MAP)->wordmask),     \
43
                            free((MAP)))
44
 
45
extern void ebitmap_set_bit (ebitmap, unsigned int);
46
extern void ebitmap_clear_bit (ebitmap, unsigned int);
47
extern bool ebitmap_bit_p (ebitmap, unsigned int);
48
extern void dump_ebitmap (FILE *, ebitmap);
49
extern void dump_ebitmap_file (FILE *, ebitmap);
50
extern void dump_ebitmap_vector (FILE *, const char *, const char *, ebitmap *,
51
                                 int);
52
extern ebitmap ebitmap_alloc (unsigned int);
53
extern ebitmap *ebitmap_vector_alloc (unsigned int, unsigned int);
54
extern void ebitmap_copy (ebitmap, ebitmap);
55
extern void ebitmap_and (ebitmap, ebitmap, ebitmap);
56
extern void ebitmap_and_into (ebitmap, ebitmap);
57
extern bool ebitmap_and_compl (ebitmap, ebitmap, ebitmap);
58
extern bool ebitmap_and_compl_into (ebitmap, ebitmap);
59
extern bool ebitmap_ior_into (ebitmap, ebitmap);
60
extern bool ebitmap_ior (ebitmap, ebitmap, ebitmap);
61
extern bool ebitmap_ior_and_compl (ebitmap, ebitmap, ebitmap, ebitmap);
62
extern bool ebitmap_ior_and_compl_into (ebitmap, ebitmap, ebitmap);
63
extern bool ebitmap_equal_p (ebitmap, ebitmap);
64
extern void ebitmap_clear (ebitmap);
65
extern int ebitmap_last_set_bit (ebitmap);
66
extern void debug_ebitmap (ebitmap);
67
extern unsigned long ebitmap_popcount(ebitmap, unsigned long);
68
 
69
/* The iterator for ebitmap.  */
70
typedef struct {
71
  /* The pointer to the first word of the bitmap.  */
72
  EBITMAP_ELT_TYPE *ptr;
73
 
74
  /* Element number inside ptr that we are at.  */
75
  unsigned int eltnum;
76
 
77
  /* The size of the bitmap.  */
78
  unsigned int size;
79
 
80
  /* Current bit index.  */
81
  unsigned int bit_num;
82
 
83
  /* The words currently visited.  */
84
  EBITMAP_ELT_TYPE word;
85
 
86
  /* The word mask iterator.  */
87
  sbitmap_iterator maskiter;
88
} ebitmap_iterator;
89
 
90
static inline void
91
ebitmap_iter_init (ebitmap_iterator *i, ebitmap bmp, unsigned int min)
92
{
93
  sbitmap_iter_init (&i->maskiter, bmp->wordmask,
94
                     min / EBITMAP_ELT_BITS);
95
  i->size = bmp->numwords;
96
  if (i->size == 0)
97
    {
98
      i->ptr = NULL;
99
      i->eltnum = 0;
100
      i->bit_num = 0;
101
      i->word = 0;
102
      return;
103
    }
104
  i->ptr = bmp->elts;
105
  i->bit_num = min;
106
  i->eltnum = 0;
107
 
108
  if ((min / EBITMAP_ELT_BITS) >= bmp->wordmask->n_bits)
109
    {
110
      i->word = 0;
111
    }
112
  else
113
    {
114
      if (TEST_BIT (bmp->wordmask, min / EBITMAP_ELT_BITS) == 0)
115
        i->word = 0;
116
      else
117
        {
118
          unsigned int wordindex = min / EBITMAP_ELT_BITS;
119
          unsigned int count = sbitmap_popcount (bmp->wordmask, wordindex);
120
          i->word = i->ptr[count] >> (i->bit_num % (unsigned int)EBITMAP_ELT_BITS);
121
          i->eltnum = count + 1;
122
        }
123
    }
124
}
125
 
126
static inline bool
127
ebitmap_iter_cond (ebitmap_iterator *i, unsigned int *n)
128
{
129
  unsigned int ourn = 0;
130
 
131
  if (i->size == 0)
132
    return false;
133
 
134
  if (i->word == 0)
135
    {
136
      sbitmap_iter_next (&i->maskiter);
137
      if (!sbitmap_iter_cond (&i->maskiter, &ourn))
138
        return false;
139
      i->bit_num = ourn * EBITMAP_ELT_BITS;
140
      i->word = i->ptr[i->eltnum++];
141
    }
142
 
143
  /* Skip bits that are zero.  */
144
 
145
  for (; (i->word & 1) == 0; i->word >>= 1)
146
    i->bit_num++;
147
 
148
  *n = i->bit_num;
149
  return true;
150
}
151
 
152
static inline void
153
ebitmap_iter_next (ebitmap_iterator *i)
154
{
155
  i->word >>= 1;
156
  i->bit_num++;
157
}
158
 
159
/* Loop over all elements of EBITMAP, starting with MIN.  In each
160
   iteration, N is set to the index of the bit being visited.  ITER is
161
   an instance of ebitmap_iterator used to iterate the bitmap.  */
162
 
163
#define EXECUTE_IF_SET_IN_EBITMAP(EBITMAP, MIN, N, ITER)        \
164
  for (ebitmap_iter_init (&(ITER), (EBITMAP), (MIN));           \
165
       ebitmap_iter_cond (&(ITER), &(N));                       \
166
       ebitmap_iter_next (&(ITER)))
167
 
168
 
169
#endif /* ! GCC_EBITMAP_H */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.