18#ifndef __STARPU_BITMAP_H__
19#define __STARPU_BITMAP_H__
36#ifndef _STARPU_LONG_BIT
37#define _STARPU_LONG_BIT ((int)(sizeof(unsigned long) * 8))
40#define _STARPU_BITMAP_SIZE ((STARPU_NMAXWORKERS - 1) / _STARPU_LONG_BIT) + 1
83 unsigned long bits[_STARPU_BITMAP_SIZE];
87#ifdef _STARPU_DEBUG_BITMAP
90 int card = b->cardinal;
93 for (j = 0; j < card; j++)
107#define _starpu_check_bitmap(b) 1
110static int _starpu_count_bit_static(
unsigned long e)
112#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__) >= 4)
113 return __builtin_popcountl(e);
132 memset(b, 0,
sizeof(*b));
147 b->bits[e / _STARPU_LONG_BIT] |= (1ul << (e % _STARPU_LONG_BIT));
157 if (e / _STARPU_LONG_BIT > _STARPU_BITMAP_SIZE)
159 b->bits[e / _STARPU_LONG_BIT] &= ~(1ul << (e % _STARPU_LONG_BIT));
165 memset(b->bits, 0, _STARPU_BITMAP_SIZE *
sizeof(
unsigned long));
172 for (i = 0; i < _STARPU_BITMAP_SIZE; i++)
174 a->bits[i] = b->bits[i] & c->bits[i];
175 a->cardinal += _starpu_count_bit_static(a->bits[i]);
182 if (e / _STARPU_LONG_BIT >= _STARPU_BITMAP_SIZE)
184 return (b->bits[e / _STARPU_LONG_BIT] & (1ul << (e % _STARPU_LONG_BIT))) ? 1 : 0;
191 for (i = 0; i < _STARPU_BITMAP_SIZE; i++)
193 a->bits[i] |= b->bits[i];
194 a->cardinal += _starpu_count_bit_static(a->bits[i]);
208static inline int _starpu_get_first_bit_rank(
unsigned long ms)
211#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))
212 return __builtin_ffsl(ms) - 1;
214 unsigned long m = 1ul;
222static inline int _starpu_get_last_bit_rank(
unsigned long l)
225#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))
226 return 8 *
sizeof(l) - __builtin_clzl(l);
228 int ibit = _STARPU_LONG_BIT - 1;
229 while ((!(1ul << ibit)) & l)
239 while (i < _STARPU_BITMAP_SIZE && !b->bits[i])
241 if (i == _STARPU_BITMAP_SIZE)
244 unsigned long ms = b->bits[i];
246 return (nb_long * _STARPU_LONG_BIT) + _starpu_get_first_bit_rank(ms);
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)
256 for (nb_long++; nb_long < _STARPU_BITMAP_SIZE; nb_long++)
257 if (b->bits[nb_long])
264 if (b->cardinal == 0)
267 for (ilong = _STARPU_BITMAP_SIZE - 1; ilong >= 0; ilong--)
273 unsigned long l = b->bits[ilong];
274 return ilong * _STARPU_LONG_BIT + _starpu_get_last_bit_rank(l);
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)
284 int i = _starpu_get_first_bit_rank(rest);
286 return (nb_long * _STARPU_LONG_BIT) + i;
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]);
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
Definition starpu_bitmap.h:82