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
80 unsigned long bits[_STARPU_BITMAP_SIZE];
84#ifdef _STARPU_DEBUG_BITMAP
87 int card = b->cardinal;
90 for (j = 0; j < card; j++)
104#define _starpu_check_bitmap(b) 1
107static int _starpu_count_bit_static(
unsigned long e)
109#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__) >= 4)
110 return __builtin_popcountl(e);
129 memset(b, 0,
sizeof(*b));
144 b->bits[e / _STARPU_LONG_BIT] |= (1ul << (e % _STARPU_LONG_BIT));
154 if (e / _STARPU_LONG_BIT > _STARPU_BITMAP_SIZE)
156 b->bits[e / _STARPU_LONG_BIT] &= ~(1ul << (e % _STARPU_LONG_BIT));
162 memset(b->bits, 0, _STARPU_BITMAP_SIZE *
sizeof(
unsigned long));
169 for (i = 0; i < _STARPU_BITMAP_SIZE; i++)
171 a->bits[i] = b->bits[i] & c->bits[i];
172 a->cardinal += _starpu_count_bit_static(a->bits[i]);
179 if (e / _STARPU_LONG_BIT >= _STARPU_BITMAP_SIZE)
181 return (b->bits[e / _STARPU_LONG_BIT] & (1ul << (e % _STARPU_LONG_BIT))) ? 1 : 0;
188 for (i = 0; i < _STARPU_BITMAP_SIZE; i++)
190 a->bits[i] |= b->bits[i];
191 a->cardinal += _starpu_count_bit_static(a->bits[i]);
205static inline int _starpu_get_first_bit_rank(
unsigned long ms)
208#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))
209 return __builtin_ffsl(ms) - 1;
211 unsigned long m = 1ul;
219static inline int _starpu_get_last_bit_rank(
unsigned long l)
222#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))
223 return 8 *
sizeof(l) - __builtin_clzl(l);
225 int ibit = _STARPU_LONG_BIT - 1;
226 while ((!(1ul << ibit)) & l)
236 while (i < _STARPU_BITMAP_SIZE && !b->bits[i])
238 if (i == _STARPU_BITMAP_SIZE)
241 unsigned long ms = b->bits[i];
243 return (nb_long * _STARPU_LONG_BIT) + _starpu_get_first_bit_rank(ms);
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)
253 for (nb_long++; nb_long < _STARPU_BITMAP_SIZE; nb_long++)
254 if (b->bits[nb_long])
261 if (b->cardinal == 0)
264 for (ilong = _STARPU_BITMAP_SIZE - 1; ilong >= 0; ilong--)
270 unsigned long l = b->bits[ilong];
271 return ilong * _STARPU_LONG_BIT + _starpu_get_last_bit_rank(l);
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)
281 int i = _starpu_get_first_bit_rank(rest);
283 return (nb_long * _STARPU_LONG_BIT) + i;
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]);
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
Definition starpu_bitmap.h:79