Loading...
Searching...
No Matches
starpu_bitmap.h
Go to the documentation of this file.
/* StarPU --- Runtime system for heterogeneous multicore architectures.
*
* Copyright (C) 2013-2023 Université de Bordeaux, CNRS (LaBRI UMR 5800), Inria
* Copyright (C) 2013 Simon Archipoff
*
* StarPU is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation; either version 2.1 of the License, or (at
* your option) any later version.
*
* StarPU is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* See the GNU Lesser General Public License in COPYING.LGPL for more details.
*/
#ifndef __STARPU_BITMAP_H__
#define __STARPU_BITMAP_H__
#include <starpu_util.h>
#include <starpu_config.h>
#include <string.h>
#include <stdlib.h>
#ifdef __cplusplus
extern "C" {
#endif
#ifndef _STARPU_LONG_BIT
#define _STARPU_LONG_BIT ((int)(sizeof(unsigned long) * 8))
#endif
#define _STARPU_BITMAP_SIZE ((STARPU_NMAXWORKERS - 1) / _STARPU_LONG_BIT) + 1
static inline struct starpu_bitmap *starpu_bitmap_create(void) STARPU_ATTRIBUTE_MALLOC;
static inline void starpu_bitmap_init(struct starpu_bitmap *b);
static inline void starpu_bitmap_destroy(struct starpu_bitmap *b);
static inline void starpu_bitmap_set(struct starpu_bitmap *b, int e);
static inline void starpu_bitmap_unset(struct starpu_bitmap *b, int e);
static inline void starpu_bitmap_unset_all(struct starpu_bitmap *b);
static inline int starpu_bitmap_get(struct starpu_bitmap *b, int e);
static inline void starpu_bitmap_unset_and(struct starpu_bitmap *a, struct starpu_bitmap *b, struct starpu_bitmap *c);
static inline void starpu_bitmap_or(struct starpu_bitmap *a, struct starpu_bitmap *b);
static inline int starpu_bitmap_and_get(struct starpu_bitmap *b1, struct starpu_bitmap *b2, int e);
static inline int starpu_bitmap_cardinal(struct starpu_bitmap *b);
static inline int starpu_bitmap_first(struct starpu_bitmap *b);
static inline int starpu_bitmap_last(struct starpu_bitmap *b);
static inline int starpu_bitmap_next(struct starpu_bitmap *b, int e);
static inline int starpu_bitmap_has_next(struct starpu_bitmap *b, int e);
struct starpu_bitmap
{
unsigned long bits[_STARPU_BITMAP_SIZE];
int cardinal;
};
#ifdef _STARPU_DEBUG_BITMAP
static int _starpu_check_bitmap(struct starpu_bitmap *b)
{
int card = b->cardinal;
int i = starpu_bitmap_first(b);
int j;
for (j = 0; j < card; j++)
{
if (i == -1)
return 0;
int tmp = starpu_bitmap_next(b, i);
if (tmp == i)
return 0;
i = tmp;
}
if (i != -1)
return 0;
return 1;
}
#else
#define _starpu_check_bitmap(b) 1
#endif
static int _starpu_count_bit_static(unsigned long e)
{
#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__) >= 4)
return __builtin_popcountl(e);
#else
int c = 0;
while (e)
{
c += e & 1;
e >>= 1;
}
return c;
#endif
}
static inline struct starpu_bitmap *starpu_bitmap_create(void)
{
return (struct starpu_bitmap *)calloc(1, sizeof(struct starpu_bitmap));
}
static inline void starpu_bitmap_init(struct starpu_bitmap *b)
{
memset(b, 0, sizeof(*b));
}
static inline void starpu_bitmap_destroy(struct starpu_bitmap *b)
{
free(b);
}
static inline void starpu_bitmap_set(struct starpu_bitmap *b, int e)
{
if (!starpu_bitmap_get(b, e))
b->cardinal++;
else
return;
STARPU_ASSERT(e / _STARPU_LONG_BIT < _STARPU_BITMAP_SIZE);
b->bits[e / _STARPU_LONG_BIT] |= (1ul << (e % _STARPU_LONG_BIT));
STARPU_ASSERT(_starpu_check_bitmap(b));
}
static inline void starpu_bitmap_unset(struct starpu_bitmap *b, int e)
{
if (starpu_bitmap_get(b, e))
b->cardinal--;
else
return;
STARPU_ASSERT(e / _STARPU_LONG_BIT < _STARPU_BITMAP_SIZE);
if (e / _STARPU_LONG_BIT > _STARPU_BITMAP_SIZE)
return;
b->bits[e / _STARPU_LONG_BIT] &= ~(1ul << (e % _STARPU_LONG_BIT));
STARPU_ASSERT(_starpu_check_bitmap(b));
}
static inline void starpu_bitmap_unset_all(struct starpu_bitmap *b)
{
memset(b->bits, 0, _STARPU_BITMAP_SIZE * sizeof(unsigned long));
}
static inline void starpu_bitmap_unset_and(struct starpu_bitmap *a, struct starpu_bitmap *b, struct starpu_bitmap *c)
{
a->cardinal = 0;
int i;
for (i = 0; i < _STARPU_BITMAP_SIZE; i++)
{
a->bits[i] = b->bits[i] & c->bits[i];
a->cardinal += _starpu_count_bit_static(a->bits[i]);
}
}
static inline int starpu_bitmap_get(struct starpu_bitmap *b, int e)
{
STARPU_ASSERT(e / _STARPU_LONG_BIT < _STARPU_BITMAP_SIZE);
if (e / _STARPU_LONG_BIT >= _STARPU_BITMAP_SIZE)
return 0;
return (b->bits[e / _STARPU_LONG_BIT] & (1ul << (e % _STARPU_LONG_BIT))) ? 1 : 0;
}
static inline void starpu_bitmap_or(struct starpu_bitmap *a, struct starpu_bitmap *b)
{
int i;
a->cardinal = 0;
for (i = 0; i < _STARPU_BITMAP_SIZE; i++)
{
a->bits[i] |= b->bits[i];
a->cardinal += _starpu_count_bit_static(a->bits[i]);
}
}
static inline int starpu_bitmap_and_get(struct starpu_bitmap *b1, struct starpu_bitmap *b2, int e)
{
return starpu_bitmap_get(b1, e) && starpu_bitmap_get(b2, e);
}
static inline int starpu_bitmap_cardinal(struct starpu_bitmap *b)
{
return b->cardinal;
}
static inline int _starpu_get_first_bit_rank(unsigned long ms)
{
STARPU_ASSERT(ms != 0);
#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))
return __builtin_ffsl(ms) - 1;
#else
unsigned long m = 1ul;
int i = 0;
while (!(m & ms))
i++, m <<= 1;
return i;
#endif
}
static inline int _starpu_get_last_bit_rank(unsigned long l)
{
STARPU_ASSERT(l != 0);
#if (__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))
return 8 * sizeof(l) - __builtin_clzl(l);
#else
int ibit = _STARPU_LONG_BIT - 1;
while ((!(1ul << ibit)) & l)
ibit--;
STARPU_ASSERT(ibit >= 0);
return ibit;
#endif
}
static inline int starpu_bitmap_first(struct starpu_bitmap *b)
{
int i = 0;
while (i < _STARPU_BITMAP_SIZE && !b->bits[i])
i++;
if (i == _STARPU_BITMAP_SIZE)
return -1;
int nb_long = i;
unsigned long ms = b->bits[i];
return (nb_long * _STARPU_LONG_BIT) + _starpu_get_first_bit_rank(ms);
}
static inline int starpu_bitmap_has_next(struct starpu_bitmap *b, int e)
{
int nb_long = (e + 1) / _STARPU_LONG_BIT;
int nb_bit = (e + 1) % _STARPU_LONG_BIT;
unsigned long mask = (~0ul) << nb_bit;
if (b->bits[nb_long] & mask)
return 1;
for (nb_long++; nb_long < _STARPU_BITMAP_SIZE; nb_long++)
if (b->bits[nb_long])
return 1;
return 0;
}
static inline int starpu_bitmap_last(struct starpu_bitmap *b)
{
if (b->cardinal == 0)
return -1;
int ilong;
for (ilong = _STARPU_BITMAP_SIZE - 1; ilong >= 0; ilong--)
{
if (b->bits[ilong])
break;
}
STARPU_ASSERT(ilong >= 0);
unsigned long l = b->bits[ilong];
return ilong * _STARPU_LONG_BIT + _starpu_get_last_bit_rank(l);
}
static inline int starpu_bitmap_next(struct starpu_bitmap *b, int e)
{
int nb_long = e / _STARPU_LONG_BIT;
int nb_bit = e % _STARPU_LONG_BIT;
unsigned long rest = nb_bit == _STARPU_LONG_BIT - 1 ? 0 : (~0ul << (nb_bit + 1)) & b->bits[nb_long];
if (nb_bit != (_STARPU_LONG_BIT - 1) && rest)
{
int i = _starpu_get_first_bit_rank(rest);
STARPU_ASSERT(i >= 0 && i < _STARPU_LONG_BIT);
return (nb_long * _STARPU_LONG_BIT) + i;
}
for (nb_long++; nb_long < _STARPU_BITMAP_SIZE; nb_long++)
if (b->bits[nb_long])
return nb_long * _STARPU_LONG_BIT + _starpu_get_first_bit_rank(b->bits[nb_long]);
return -1;
}
#ifdef __cplusplus
}
#endif
#endif /* __STARPU_BITMAP_H__ */
starpu_bitmap_set
static void starpu_bitmap_set(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:140
starpu_bitmap_has_next
static int starpu_bitmap_has_next(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:249
starpu_bitmap_first
static int starpu_bitmap_first(struct starpu_bitmap *b)
Definition starpu_bitmap.h:236
starpu_bitmap_or
static void starpu_bitmap_or(struct starpu_bitmap *a, struct starpu_bitmap *b)
Definition starpu_bitmap.h:187
starpu_bitmap_cardinal
static int starpu_bitmap_cardinal(struct starpu_bitmap *b)
Definition starpu_bitmap.h:203
starpu_bitmap_get
static int starpu_bitmap_get(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:179
starpu_bitmap_unset_and
static void starpu_bitmap_unset_and(struct starpu_bitmap *a, struct starpu_bitmap *b, struct starpu_bitmap *c)
Definition starpu_bitmap.h:168
starpu_bitmap_next
static int starpu_bitmap_next(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:277
starpu_bitmap_unset
static void starpu_bitmap_unset(struct starpu_bitmap *b, int e)
Definition starpu_bitmap.h:150
starpu_bitmap_unset_all
static void starpu_bitmap_unset_all(struct starpu_bitmap *b)
Definition starpu_bitmap.h:163
starpu_bitmap_and_get
static int starpu_bitmap_and_get(struct starpu_bitmap *b1, struct starpu_bitmap *b2, int e)
Definition starpu_bitmap.h:198
starpu_bitmap_destroy
static void starpu_bitmap_destroy(struct starpu_bitmap *b)
Definition starpu_bitmap.h:135
starpu_bitmap_init
static void starpu_bitmap_init(struct starpu_bitmap *b)
Definition starpu_bitmap.h:130
starpu_bitmap_create
static struct starpu_bitmap * starpu_bitmap_create(void) STARPU_ATTRIBUTE_MALLOC
Definition starpu_bitmap.h:125
starpu_bitmap_last
static int starpu_bitmap_last(struct starpu_bitmap *b)
Definition starpu_bitmap.h:262
STARPU_ASSERT
#define STARPU_ASSERT(x)
Definition starpu_util.h:240
STARPU_ATTRIBUTE_MALLOC
#define STARPU_ATTRIBUTE_MALLOC
Definition starpu_util.h:129
starpu_bitmap
Definition starpu_bitmap.h:82
starpu_config.h
starpu_util.h