StarPU Handbook - StarPU Basics
Loading...
Searching...
No Matches
starpu_bitmap.h
Go to the documentation of this file.
1/* StarPU --- Runtime system for heterogeneous multicore architectures.
2 *
3 * Copyright (C) 2013-2021 Université de Bordeaux, CNRS (LaBRI UMR 5800), Inria
4 * Copyright (C) 2013 Simon Archipoff
5 *
6 * StarPU is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License as published by
8 * the Free Software Foundation; either version 2.1 of the License, or (at
9 * your option) any later version.
10 *
11 * StarPU is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
14 *
15 * See the GNU Lesser General Public License in COPYING.LGPL for more details.
16 */
17
18#ifndef __STARPU_BITMAP_H__
19#define __STARPU_BITMAP_H__
20
21#include <starpu_util.h>
22#include <starpu_config.h>
23
24#include <string.h>
25#include <stdlib.h>
26
27#ifdef __cplusplus
28extern "C" {
29#endif
30
36#ifndef _STARPU_LONG_BIT
37#define _STARPU_LONG_BIT ((int)(sizeof(unsigned long) * 8))
38#endif
39
40#define _STARPU_BITMAP_SIZE ((STARPU_NMAXWORKERS - 1) / _STARPU_LONG_BIT) + 1
41
45static inline void starpu_bitmap_init(struct starpu_bitmap *b);
47static inline void starpu_bitmap_destroy(struct starpu_bitmap *b);
48
50static inline void starpu_bitmap_set(struct starpu_bitmap *b, int e);
52static inline void starpu_bitmap_unset(struct starpu_bitmap *b, int e);
54static inline void starpu_bitmap_unset_all(struct starpu_bitmap *b);
55
57static inline int starpu_bitmap_get(struct starpu_bitmap *b, int e);
59static inline void starpu_bitmap_unset_and(struct starpu_bitmap *a, struct starpu_bitmap *b, struct starpu_bitmap *c);
61static inline void starpu_bitmap_or(struct starpu_bitmap *a, struct starpu_bitmap *b);
63static inline int starpu_bitmap_and_get(struct starpu_bitmap *b1, struct starpu_bitmap *b2, int e);
65static inline int starpu_bitmap_cardinal(struct starpu_bitmap *b);
66
68static inline int starpu_bitmap_first(struct starpu_bitmap *b);
70static inline int starpu_bitmap_last(struct starpu_bitmap *b);
72static inline int starpu_bitmap_next(struct starpu_bitmap *b, int e);
74static inline int starpu_bitmap_has_next(struct starpu_bitmap *b, int e);
75
79{
80 unsigned long bits[_STARPU_BITMAP_SIZE];
81 int cardinal;
82};
83
84#ifdef _STARPU_DEBUG_BITMAP
85static int _starpu_check_bitmap(struct starpu_bitmap *b)
86{
87 int card = b->cardinal;
88 int i = starpu_bitmap_first(b);
89 int j;
90 for (j = 0; j < card; j++)
91 {
92 if (i == -1)
93 return 0;
94 int tmp = starpu_bitmap_next(b, i);
95 if (tmp == i)
96 return 0;
97 i = tmp;
98 }
99 if (i != -1)
100 return 0;
101 return 1;
102}
103#else
104#define _starpu_check_bitmap(b) 1
105#endif
106
107static int _starpu_count_bit_static(unsigned long e)
108{
109#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__) >= 4)
110 return __builtin_popcountl(e);
111#else
112 int c = 0;
113 while (e)
114 {
115 c += e & 1;
116 e >>= 1;
117 }
118 return c;
119#endif
120}
121
122static inline struct starpu_bitmap *starpu_bitmap_create(void)
123{
124 return (struct starpu_bitmap *)calloc(1, sizeof(struct starpu_bitmap));
125}
126
127static inline void starpu_bitmap_init(struct starpu_bitmap *b)
128{
129 memset(b, 0, sizeof(*b));
130}
131
132static inline void starpu_bitmap_destroy(struct starpu_bitmap *b)
133{
134 free(b);
135}
136
137static inline void starpu_bitmap_set(struct starpu_bitmap *b, int e)
138{
139 if (!starpu_bitmap_get(b, e))
140 b->cardinal++;
141 else
142 return;
143 STARPU_ASSERT(e / _STARPU_LONG_BIT < _STARPU_BITMAP_SIZE);
144 b->bits[e / _STARPU_LONG_BIT] |= (1ul << (e % _STARPU_LONG_BIT));
145 STARPU_ASSERT(_starpu_check_bitmap(b));
146}
147static inline void starpu_bitmap_unset(struct starpu_bitmap *b, int e)
148{
149 if (starpu_bitmap_get(b, e))
150 b->cardinal--;
151 else
152 return;
153 STARPU_ASSERT(e / _STARPU_LONG_BIT < _STARPU_BITMAP_SIZE);
154 if (e / _STARPU_LONG_BIT > _STARPU_BITMAP_SIZE)
155 return;
156 b->bits[e / _STARPU_LONG_BIT] &= ~(1ul << (e % _STARPU_LONG_BIT));
157 STARPU_ASSERT(_starpu_check_bitmap(b));
158}
159
160static inline void starpu_bitmap_unset_all(struct starpu_bitmap *b)
161{
162 memset(b->bits, 0, _STARPU_BITMAP_SIZE * sizeof(unsigned long));
163}
164
165static inline void starpu_bitmap_unset_and(struct starpu_bitmap *a, struct starpu_bitmap *b, struct starpu_bitmap *c)
166{
167 a->cardinal = 0;
168 int i;
169 for (i = 0; i < _STARPU_BITMAP_SIZE; i++)
170 {
171 a->bits[i] = b->bits[i] & c->bits[i];
172 a->cardinal += _starpu_count_bit_static(a->bits[i]);
173 }
174}
175
176static inline int starpu_bitmap_get(struct starpu_bitmap *b, int e)
177{
178 STARPU_ASSERT(e / _STARPU_LONG_BIT < _STARPU_BITMAP_SIZE);
179 if (e / _STARPU_LONG_BIT >= _STARPU_BITMAP_SIZE)
180 return 0;
181 return (b->bits[e / _STARPU_LONG_BIT] & (1ul << (e % _STARPU_LONG_BIT))) ? 1 : 0;
182}
183
184static inline void starpu_bitmap_or(struct starpu_bitmap *a, struct starpu_bitmap *b)
185{
186 int i;
187 a->cardinal = 0;
188 for (i = 0; i < _STARPU_BITMAP_SIZE; i++)
189 {
190 a->bits[i] |= b->bits[i];
191 a->cardinal += _starpu_count_bit_static(a->bits[i]);
192 }
193}
194
195static inline int starpu_bitmap_and_get(struct starpu_bitmap *b1, struct starpu_bitmap *b2, int e)
196{
197 return starpu_bitmap_get(b1, e) && starpu_bitmap_get(b2, e);
198}
199
200static inline int starpu_bitmap_cardinal(struct starpu_bitmap *b)
201{
202 return b->cardinal;
203}
204
205static inline int _starpu_get_first_bit_rank(unsigned long ms)
206{
207 STARPU_ASSERT(ms != 0);
208#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))
209 return __builtin_ffsl(ms) - 1;
210#else
211 unsigned long m = 1ul;
212 int i = 0;
213 while (!(m & ms))
214 i++, m <<= 1;
215 return i;
216#endif
217}
218
219static inline int _starpu_get_last_bit_rank(unsigned long l)
220{
221 STARPU_ASSERT(l != 0);
222#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))
223 return 8 * sizeof(l) - __builtin_clzl(l);
224#else
225 int ibit = _STARPU_LONG_BIT - 1;
226 while ((!(1ul << ibit)) & l)
227 ibit--;
228 STARPU_ASSERT(ibit >= 0);
229 return ibit;
230#endif
231}
232
233static inline int starpu_bitmap_first(struct starpu_bitmap *b)
234{
235 int i = 0;
236 while (i < _STARPU_BITMAP_SIZE && !b->bits[i])
237 i++;
238 if (i == _STARPU_BITMAP_SIZE)
239 return -1;
240 int nb_long = i;
241 unsigned long ms = b->bits[i];
242
243 return (nb_long * _STARPU_LONG_BIT) + _starpu_get_first_bit_rank(ms);
244}
245
246static inline int starpu_bitmap_has_next(struct starpu_bitmap *b, int e)
247{
248 int nb_long = (e + 1) / _STARPU_LONG_BIT;
249 int nb_bit = (e + 1) % _STARPU_LONG_BIT;
250 unsigned long mask = (~0ul) << nb_bit;
251 if (b->bits[nb_long] & mask)
252 return 1;
253 for (nb_long++; nb_long < _STARPU_BITMAP_SIZE; nb_long++)
254 if (b->bits[nb_long])
255 return 1;
256 return 0;
257}
258
259static inline int starpu_bitmap_last(struct starpu_bitmap *b)
260{
261 if (b->cardinal == 0)
262 return -1;
263 int ilong;
264 for (ilong = _STARPU_BITMAP_SIZE - 1; ilong >= 0; ilong--)
265 {
266 if (b->bits[ilong])
267 break;
268 }
269 STARPU_ASSERT(ilong >= 0);
270 unsigned long l = b->bits[ilong];
271 return ilong * _STARPU_LONG_BIT + _starpu_get_last_bit_rank(l);
272}
273
274static inline int starpu_bitmap_next(struct starpu_bitmap *b, int e)
275{
276 int nb_long = e / _STARPU_LONG_BIT;
277 int nb_bit = e % _STARPU_LONG_BIT;
278 unsigned long rest = nb_bit == _STARPU_LONG_BIT - 1 ? 0 : (~0ul << (nb_bit + 1)) & b->bits[nb_long];
279 if (nb_bit != (_STARPU_LONG_BIT - 1) && rest)
280 {
281 int i = _starpu_get_first_bit_rank(rest);
282 STARPU_ASSERT(i >= 0 && i < _STARPU_LONG_BIT);
283 return (nb_long * _STARPU_LONG_BIT) + i;
284 }
285
286 for (nb_long++; nb_long < _STARPU_BITMAP_SIZE; nb_long++)
287 if (b->bits[nb_long])
288 return nb_long * _STARPU_LONG_BIT + _starpu_get_first_bit_rank(b->bits[nb_long]);
289 return -1;
290}
291
292#ifdef __cplusplus
293}
294#endif
295
296#endif /* __STARPU_BITMAP_H__ */
static void starpu_bitmap_set(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:137
static int starpu_bitmap_has_next(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:246
static int starpu_bitmap_first(struct starpu_bitmap *b)
Definition starpu_bitmap.h:233
static void starpu_bitmap_or(struct starpu_bitmap *a, struct starpu_bitmap *b)
Definition starpu_bitmap.h:184
static int starpu_bitmap_cardinal(struct starpu_bitmap *b)
Definition starpu_bitmap.h:200
static int starpu_bitmap_get(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:176
static void starpu_bitmap_unset_and(struct starpu_bitmap *a, struct starpu_bitmap *b, struct starpu_bitmap *c)
Definition starpu_bitmap.h:165
static int starpu_bitmap_next(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:274
static void starpu_bitmap_unset(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:147
static void starpu_bitmap_unset_all(struct starpu_bitmap *b)
Definition starpu_bitmap.h:160
static int starpu_bitmap_and_get(struct starpu_bitmap *b1, struct starpu_bitmap *b2, int e)
Definition starpu_bitmap.h:195
static void starpu_bitmap_destroy(struct starpu_bitmap *b)
Definition starpu_bitmap.h:132
static void starpu_bitmap_init(struct starpu_bitmap *b)
Definition starpu_bitmap.h:127
static struct starpu_bitmap * starpu_bitmap_create(void) STARPU_ATTRIBUTE_MALLOC
Definition starpu_bitmap.h:122
static int starpu_bitmap_last(struct starpu_bitmap *b)
Definition starpu_bitmap.h:259
#define STARPU_ASSERT(x)
Definition starpu_util.h:240
#define STARPU_ATTRIBUTE_MALLOC
Definition starpu_util.h:129
Definition starpu_bitmap.h:79