StarPU Handbook
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-2023 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
82{
83 unsigned long bits[_STARPU_BITMAP_SIZE];
84 int cardinal;
85};
86
87#ifdef _STARPU_DEBUG_BITMAP
88static int _starpu_check_bitmap(struct starpu_bitmap *b)
89{
90 int card = b->cardinal;
91 int i = starpu_bitmap_first(b);
92 int j;
93 for (j = 0; j < card; j++)
94 {
95 if (i == -1)
96 return 0;
97 int tmp = starpu_bitmap_next(b, i);
98 if (tmp == i)
99 return 0;
100 i = tmp;
101 }
102 if (i != -1)
103 return 0;
104 return 1;
105}
106#else
107#define _starpu_check_bitmap(b) 1
108#endif
109
110static int _starpu_count_bit_static(unsigned long e)
111{
112#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__) >= 4)
113 return __builtin_popcountl(e);
114#else
115 int c = 0;
116 while (e)
117 {
118 c += e & 1;
119 e >>= 1;
120 }
121 return c;
122#endif
123}
124
125static inline struct starpu_bitmap *starpu_bitmap_create(void)
126{
127 return (struct starpu_bitmap *)calloc(1, sizeof(struct starpu_bitmap));
128}
129
130static inline void starpu_bitmap_init(struct starpu_bitmap *b)
131{
132 memset(b, 0, sizeof(*b));
133}
134
135static inline void starpu_bitmap_destroy(struct starpu_bitmap *b)
136{
137 free(b);
138}
139
140static inline void starpu_bitmap_set(struct starpu_bitmap *b, int e)
141{
142 if (!starpu_bitmap_get(b, e))
143 b->cardinal++;
144 else
145 return;
146 STARPU_ASSERT(e / _STARPU_LONG_BIT < _STARPU_BITMAP_SIZE);
147 b->bits[e / _STARPU_LONG_BIT] |= (1ul << (e % _STARPU_LONG_BIT));
148 STARPU_ASSERT(_starpu_check_bitmap(b));
149}
150static inline void starpu_bitmap_unset(struct starpu_bitmap *b, int e)
151{
152 if (starpu_bitmap_get(b, e))
153 b->cardinal--;
154 else
155 return;
156 STARPU_ASSERT(e / _STARPU_LONG_BIT < _STARPU_BITMAP_SIZE);
157 if (e / _STARPU_LONG_BIT > _STARPU_BITMAP_SIZE)
158 return;
159 b->bits[e / _STARPU_LONG_BIT] &= ~(1ul << (e % _STARPU_LONG_BIT));
160 STARPU_ASSERT(_starpu_check_bitmap(b));
161}
162
163static inline void starpu_bitmap_unset_all(struct starpu_bitmap *b)
164{
165 memset(b->bits, 0, _STARPU_BITMAP_SIZE * sizeof(unsigned long));
166}
167
168static inline void starpu_bitmap_unset_and(struct starpu_bitmap *a, struct starpu_bitmap *b, struct starpu_bitmap *c)
169{
170 a->cardinal = 0;
171 int i;
172 for (i = 0; i < _STARPU_BITMAP_SIZE; i++)
173 {
174 a->bits[i] = b->bits[i] & c->bits[i];
175 a->cardinal += _starpu_count_bit_static(a->bits[i]);
176 }
177}
178
179static inline int starpu_bitmap_get(struct starpu_bitmap *b, int e)
180{
181 STARPU_ASSERT(e / _STARPU_LONG_BIT < _STARPU_BITMAP_SIZE);
182 if (e / _STARPU_LONG_BIT >= _STARPU_BITMAP_SIZE)
183 return 0;
184 return (b->bits[e / _STARPU_LONG_BIT] & (1ul << (e % _STARPU_LONG_BIT))) ? 1 : 0;
185}
186
187static inline void starpu_bitmap_or(struct starpu_bitmap *a, struct starpu_bitmap *b)
188{
189 int i;
190 a->cardinal = 0;
191 for (i = 0; i < _STARPU_BITMAP_SIZE; i++)
192 {
193 a->bits[i] |= b->bits[i];
194 a->cardinal += _starpu_count_bit_static(a->bits[i]);
195 }
196}
197
198static inline int starpu_bitmap_and_get(struct starpu_bitmap *b1, struct starpu_bitmap *b2, int e)
199{
200 return starpu_bitmap_get(b1, e) && starpu_bitmap_get(b2, e);
201}
202
203static inline int starpu_bitmap_cardinal(struct starpu_bitmap *b)
204{
205 return b->cardinal;
206}
207
208static inline int _starpu_get_first_bit_rank(unsigned long ms)
209{
210 STARPU_ASSERT(ms != 0);
211#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))
212 return __builtin_ffsl(ms) - 1;
213#else
214 unsigned long m = 1ul;
215 int i = 0;
216 while (!(m & ms))
217 i++, m <<= 1;
218 return i;
219#endif
220}
221
222static inline int _starpu_get_last_bit_rank(unsigned long l)
223{
224 STARPU_ASSERT(l != 0);
225#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))
226 return 8 * sizeof(l) - __builtin_clzl(l);
227#else
228 int ibit = _STARPU_LONG_BIT - 1;
229 while ((!(1ul << ibit)) & l)
230 ibit--;
231 STARPU_ASSERT(ibit >= 0);
232 return ibit;
233#endif
234}
235
236static inline int starpu_bitmap_first(struct starpu_bitmap *b)
237{
238 int i = 0;
239 while (i < _STARPU_BITMAP_SIZE && !b->bits[i])
240 i++;
241 if (i == _STARPU_BITMAP_SIZE)
242 return -1;
243 int nb_long = i;
244 unsigned long ms = b->bits[i];
245
246 return (nb_long * _STARPU_LONG_BIT) + _starpu_get_first_bit_rank(ms);
247}
248
249static inline int starpu_bitmap_has_next(struct starpu_bitmap *b, int e)
250{
251 int nb_long = (e + 1) / _STARPU_LONG_BIT;
252 int nb_bit = (e + 1) % _STARPU_LONG_BIT;
253 unsigned long mask = (~0ul) << nb_bit;
254 if (b->bits[nb_long] & mask)
255 return 1;
256 for (nb_long++; nb_long < _STARPU_BITMAP_SIZE; nb_long++)
257 if (b->bits[nb_long])
258 return 1;
259 return 0;
260}
261
262static inline int starpu_bitmap_last(struct starpu_bitmap *b)
263{
264 if (b->cardinal == 0)
265 return -1;
266 int ilong;
267 for (ilong = _STARPU_BITMAP_SIZE - 1; ilong >= 0; ilong--)
268 {
269 if (b->bits[ilong])
270 break;
271 }
272 STARPU_ASSERT(ilong >= 0);
273 unsigned long l = b->bits[ilong];
274 return ilong * _STARPU_LONG_BIT + _starpu_get_last_bit_rank(l);
275}
276
277static inline int starpu_bitmap_next(struct starpu_bitmap *b, int e)
278{
279 int nb_long = e / _STARPU_LONG_BIT;
280 int nb_bit = e % _STARPU_LONG_BIT;
281 unsigned long rest = nb_bit == _STARPU_LONG_BIT - 1 ? 0 : (~0ul << (nb_bit + 1)) & b->bits[nb_long];
282 if (nb_bit != (_STARPU_LONG_BIT - 1) && rest)
283 {
284 int i = _starpu_get_first_bit_rank(rest);
285 STARPU_ASSERT(i >= 0 && i < _STARPU_LONG_BIT);
286 return (nb_long * _STARPU_LONG_BIT) + i;
287 }
288
289 for (nb_long++; nb_long < _STARPU_BITMAP_SIZE; nb_long++)
290 if (b->bits[nb_long])
291 return nb_long * _STARPU_LONG_BIT + _starpu_get_first_bit_rank(b->bits[nb_long]);
292 return -1;
293}
294
295#ifdef __cplusplus
296}
297#endif
298
299#endif /* __STARPU_BITMAP_H__ */
static void starpu_bitmap_set(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:140
static int starpu_bitmap_has_next(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:249
static int starpu_bitmap_first(struct starpu_bitmap *b)
Definition starpu_bitmap.h:236
static void starpu_bitmap_or(struct starpu_bitmap *a, struct starpu_bitmap *b)
Definition starpu_bitmap.h:187
static int starpu_bitmap_cardinal(struct starpu_bitmap *b)
Definition starpu_bitmap.h:203
static int starpu_bitmap_get(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:179
static void starpu_bitmap_unset_and(struct starpu_bitmap *a, struct starpu_bitmap *b, struct starpu_bitmap *c)
Definition starpu_bitmap.h:168
static int starpu_bitmap_next(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:277
static void starpu_bitmap_unset(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:150
static void starpu_bitmap_unset_all(struct starpu_bitmap *b)
Definition starpu_bitmap.h:163
static int starpu_bitmap_and_get(struct starpu_bitmap *b1, struct starpu_bitmap *b2, int e)
Definition starpu_bitmap.h:198
static void starpu_bitmap_destroy(struct starpu_bitmap *b)
Definition starpu_bitmap.h:135
static void starpu_bitmap_init(struct starpu_bitmap *b)
Definition starpu_bitmap.h:130
static struct starpu_bitmap * starpu_bitmap_create(void) STARPU_ATTRIBUTE_MALLOC
Definition starpu_bitmap.h:125
static int starpu_bitmap_last(struct starpu_bitmap *b)
Definition starpu_bitmap.h:262
#define STARPU_ASSERT(x)
Definition starpu_util.h:240
#define STARPU_ATTRIBUTE_MALLOC
Definition starpu_util.h:129
Definition starpu_bitmap.h:82