Yes, Maxim I'll revise and send an updated version tomorrow.
Thanks and best regards, Yi On 9 January 2017 at 21:05, Maxim Uvarov <maxim.uva...@linaro.org> wrote: > On 01/05/17 12:12, Yi He wrote: > > O, missing this mail > > > > Hi, Maxim, for the error and warnings it seems the checkpatch.pl > > <http://checkpatch.pl> cannot recognize function pointers usage in macro > > definition, but it is a must in this generic programming practice. For > > those checks are only one space or parenthesize, trying to make code > > looks more clear and easy-reading. > > > > Can we accept these? > > > > Thanks and best regards, Yi > > > > > Hello Yi, sorry for long response I was on winter holidays. > > how about removing METHOD_DECLARE define and declare functions natively? > > Patch for your patch: > > --- /dev/null > +++ b/platform/linux-generic/include/odp_bitmap_internal.h > -@@ -0,0 +1,320 @@ > +@@ -0,0 +1,317 @@ > +/* Copyright (c) 2016, Linaro Limited > + * All rights reserved. > + * > @@ -197,16 +197,13 @@ index 0000000..192c6f9 > + * ...operations on this bit index... > + * } > + */ > -+#define METHOD_DECLARE(_return, _name, _impl, ...) \ > -+ _return (*_name)(struct _impl ## _bitmap_ ## iterator *this) > -+ > +typedef struct wapl_bitmap_iterator { > + int _start, _next, _nbits; > + wapl_bitmap_t _base; > + > -+ METHOD_DECLARE(void, start, wapl); > -+ METHOD_DECLARE(bool, has_next, wapl); > -+ METHOD_DECLARE(unsigned int, next, wapl); > ++ void (*start)(struct wapl_bitmap_iterator *this); > ++ bool (*has_next)(struct wapl_bitmap_iterator *this); > ++ unsigned int (*next)(struct wapl_bitmap_iterator *this); > +} wapl_bitmap_iterator_t; > + > +/* > @@ -298,9 +295,9 @@ index 0000000..192c6f9 > + int _start, _next, _nbits; > + sparse_bitmap_t _base; > + > -+ METHOD_DECLARE(void, start, sparse); > -+ METHOD_DECLARE(bool, has_next, sparse); > -+ METHOD_DECLARE(unsigned int, next, sparse); > ++ void (*start)(struct sparse_bitmap_iterator *this); > ++ bool (*has_next)(struct sparse_bitmap_iterator *this); > ++ unsigned int (*next)(struct sparse_bitmap_iterator *this); > +} sparse_bitmap_iterator_t; > + > +/* > @@ -334,7 +331,7 @@ index 0000000..192c6f9 > +{ > + unsigned long tmp; > + > -+ if (start >= (int) nbits) > ++ if (start >= (int)nbits) > + start = 0; > + > + tmp = addr[BIT_WORD(start)]; > @@ -345,7 +342,7 @@ index 0000000..192c6f9 > + > + while (!tmp) { > + start += BITS_PER_LONG; > -+ if (start >= (int) nbits) > ++ if (start >= (int)nbits) > + start = 0; > + > + tmp = addr[BIT_WORD(start)]; > @@ -366,7 +363,7 @@ index 0000000..192c6f9 > +#endif > diff --git a/platform/linux-generic/odp_bitmap.c > b/platform/linux-generic/odp_bitmap.c > new file mode 100644 > -index 0000000..0f4d051 > +index 0000000..b991114 > --- /dev/null > +++ b/platform/linux-generic/odp_bitmap.c > @@ -0,0 +1,315 @@ > @@ -587,7 +584,7 @@ index 0000000..0f4d051 > + */ > +static void __sparse_iterator_start(sparse_bitmap_iterator_t *this) > +{ > -+ this->_nbits = (int) *(this->_base.last); > ++ this->_nbits = *this->_base.last; > + > + /* Advance to next queue index to start this > + * new round iteration. > > > > > > > > > > > > > > > > On 5 January 2017 at 03:16, Maxim Uvarov <maxim.uva...@linaro.org > > <mailto:maxim.uva...@linaro.org>> wrote: > > > > > > Using patch: 0003-linux-gen-add-generic-bitmaps-and-iterators.patch > > Trying to apply patch > > Patch applied > > WARNING: Prefer ARRAY_SIZE(array) > > #77: FILE: platform/linux-generic/include/odp_bitmap_internal.h:30: > > +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0])) > > > > ERROR: Macros with complex values should be enclosed in parentheses > > #201: FILE: platform/linux-generic/include/odp_bitmap_internal.h: > 154: > > +#define METHOD_DECLARE(_return, _name, _impl, ...) \ > > + _return (*_name)(struct _impl ## _bitmap_ ## iterator *this) > > > > WARNING: space prohibited between function name and open parenthesis > '(' > > #202: FILE: platform/linux-generic/include/odp_bitmap_internal.h: > 155: > > + _return (*_name)(struct _impl ## _bitmap_ ## iterator *this) > > > > CHECK: No space is necessary after a cast > > #338: FILE: platform/linux-generic/include/odp_bitmap_internal.h: > 291: > > + if (start >= (int) nbits) > > > > CHECK: No space is necessary after a cast > > #349: FILE: platform/linux-generic/include/odp_bitmap_internal.h: > 302: > > + if (start >= (int) nbits) > > > > CHECK: No space is necessary after a cast > > #591: FILE: platform/linux-generic/odp_bitmap.c:218: > > + this->_nbits = (int) *(this->_base.last); > > > > CHECK: Unnecessary parentheses around this->_base.last > > #591: FILE: platform/linux-generic/odp_bitmap.c:218: > > + this->_nbits = (int) *(this->_base.last); > > > > total: 1 errors, 2 warnings, 4 checks, 649 lines checked > > > > NOTE: Ignored message types: BIT_MACRO COMPARISON_TO_NULL > > DEPRECATED_VARIABLE NEW_TYPEDEFS SPLIT_STRING SSCANF_TO_KSTRTO > > > > 0001-linux-gen-add-generic-bitmaps-and-iterators.patch has style > > problems, please review. > > > > > > > > On 12/09/16 13:51, Yi He wrote: > > > Add C++ template alike bitmap<size> to allow > > > instantiate bitmap data structure of any size, > > > and provide iterators to help walking through > > > the bitmap objects. > > > > > > Signed-off-by: Yi He <yi...@linaro.org <mailto:yi...@linaro.org>> > > > --- > > > platform/linux-generic/Makefile.am | 2 + > > > .../linux-generic/include/odp_bitmap_internal.h | 320 > > +++++++++++++++++++++ > > > platform/linux-generic/odp_bitmap.c | 315 > > ++++++++++++++++++++ > > > 3 files changed, 637 insertions(+) > > > create mode 100644 > > platform/linux-generic/include/odp_bitmap_internal.h > > > create mode 100644 platform/linux-generic/odp_bitmap.c > > > > > > diff --git a/platform/linux-generic/Makefile.am > > b/platform/linux-generic/Makefile.am > > > index adbe24d..a6e62ef 100644 > > > --- a/platform/linux-generic/Makefile.am > > > +++ b/platform/linux-generic/Makefile.am > > > @@ -128,6 +128,7 @@ noinst_HEADERS = \ > > > ${srcdir}/include/odp_align_internal.h \ > > > ${srcdir}/include/odp_atomic_internal.h \ > > > ${srcdir}/include/odp_buffer_inlines.h \ > > > + ${srcdir}/include/odp_bitmap_internal.h \ > > > ${srcdir}/include/odp_buffer_internal.h \ > > > ${srcdir}/include/odp_classification_datamodel.h \ > > > ${srcdir}/include/odp_classification_inlines.h \ > > > @@ -171,6 +172,7 @@ __LIB__libodp_linux_la_SOURCES = \ > > > _ishmphy.c \ > > > odp_atomic.c \ > > > odp_barrier.c \ > > > + odp_bitmap.c \ > > > odp_buffer.c \ > > > odp_byteorder.c \ > > > odp_classification.c \ > > > diff --git a/platform/linux-generic/include/odp_bitmap_internal.h > > b/platform/linux-generic/include/odp_bitmap_internal.h > > > new file mode 100644 > > > index 0000000..192c6f9 > > > --- /dev/null > > > +++ b/platform/linux-generic/include/odp_bitmap_internal.h > > > @@ -0,0 +1,320 @@ > > > +/* Copyright (c) 2016, Linaro Limited > > > + * All rights reserved. > > > + * > > > + * SPDX-License-Identifier: BSD-3-Clause > > > + */ > > > + > > > +/** > > > + * @file > > > + * > > > + * ODP generic bitmap types and operations. > > > + */ > > > + > > > +#ifndef ODP_BITMAP_INTERNAL_H_ > > > +#define ODP_BITMAP_INTERNAL_H_ > > > + > > > +#ifdef __cplusplus > > > +extern "C" { > > > +#endif > > > + > > > +#include <stdint.h> > > > +#include <stdbool.h> > > > +#include <string.h> > > > +#include <odp/api/hints.h> > > > + > > > +/* Generate unique identifier for instantiated class */ > > > +#define TOKENIZE(template, line) \ > > > + template ## _ ## line ## _ ## __COUNTER__ > > > + > > > +/* Array size in general */ > > > +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0])) > > > + > > > +#define BITS_PER_BYTE (8) > > > +#define BITS_PER_LONG __WORDSIZE > > > +#define BYTES_PER_LONG (BITS_PER_LONG / BITS_PER_BYTE) > > > + > > > +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) > > > +#define BITS_TO_LONGS(nr) BIT_WORD(nr + BITS_PER_LONG - 1) > > > + > > > +#define BITMAP_FIRST_WORD_MASK(start) \ > > > + (~0UL << ((start) & (BITS_PER_LONG - 1))) > > > +#define BITMAP_LAST_WORD_MASK(nbits) \ > > > + (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) > > > + > > > +/* WAPL bitmap base class */ > > > +typedef struct { > > > + unsigned int nwords; > > > + unsigned int *pl; > > > + unsigned long *ul; > > > +} wapl_bitmap_t; > > > + > > > +/* > > > + * Word-Aligned Position List (WAPL) bitmap, which actually > > > + * is not a compression, but with an extra list of non-empty > > > + * word positions. > > > + * > > > + * WAPL accelerates bitwise operations and iterations by > > > + * applying only to non-empty positions instead of walking > > > + * through the whole bitmap. > > > + * > > > + * WAPL uses [1 ~ N] instead of [0 ~ N - 1] as position > > > + * values and an extra 0 as end indicator for position list. > > > + * This is the reason to allocate one extra room below. > > > + */ > > > +#define instantiate_wapl_bitmap(line, nbits) \ > > > + struct TOKENIZE(wapl_bitmap, line) { \ > > > + unsigned int pl[BITS_TO_LONGS(nbits) + 1]; \ > > > + unsigned long ul[BITS_TO_LONGS(nbits) + 1]; \ > > > + } > > > + > > > +#define WAPL_BITMAP(nbits) instantiate_wapl_bitmap(__LINE__, > nbits) > > > + > > > +/* > > > + * Upcast any derived WAPL bitmap class to its base class > > > + */ > > > +#define __wapl_upcast(base, derived) \ > > > + do { \ > > > + __typeof__(derived) p = derived; \ > > > + base.pl <http://base.pl> = p->pl; > > \ > > > + base.ul = p->ul; \ > > > + base.nwords = ARRAY_SIZE(p->ul) - 1; \ > > > + } while (0) > > > + > > > +/* > > > + * WAPL base class bitmap operations > > > + */ > > > +void __wapl_bitmap_and(wapl_bitmap_t *dst, > > > + wapl_bitmap_t *src, wapl_bitmap_t *and); > > > + > > > +void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or); > > > + > > > +void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit); > > > + > > > +void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit); > > > + > > > +/* > > > + * Generic WAPL bitmap operations > > > + */ > > > +#define wapl_bitmap_zero(map) > > \ > > > + ({ \ > > > + __typeof__(map) p = map; \ > > > + memset((void *)p, 0, sizeof(__typeof__(*p))); \ > > > + }) > > > + > > > +#define wapl_bitmap_copy(dst, src) \ > > > + ({ \ > > > + __typeof__(dst) d = dst; \ > > > + __typeof__(src) s = src; \ > > > + if (d != s) \ > > > + memcpy((void *)d, (void *)s, \ > > > + sizeof(__typeof__(*d))); \ > > > + }) > > > + > > > +#define wapl_bitmap_and(dst, src, and) > > \ > > > + ({ \ > > > + wapl_bitmap_t d, s, a; \ > > > + __wapl_upcast(d, dst); \ > > > + __wapl_upcast(s, src); \ > > > + __wapl_upcast(a, and); \ > > > + __wapl_bitmap_and(&d, &s, &a); \ > > > + }) > > > + > > > +#define wapl_bitmap_or(dst, src, or) \ > > > + ({ \ > > > + wapl_bitmap_t d, o; \ > > > + wapl_bitmap_copy(dst, src); \ > > > + __wapl_upcast(d, dst); \ > > > + __wapl_upcast(o, or); \ > > > + __wapl_bitmap_or(&d, &o); \ > > > + }) > > > + > > > +#define wapl_bitmap_set(map, bit) \ > > > + ({ \ > > > + wapl_bitmap_t b; \ > > > + __wapl_upcast(b, map); \ > > > + __wapl_bitmap_set(&b, bit); \ > > > + }) > > > + > > > +#define wapl_bitmap_clear(map, bit) \ > > > + ({ \ > > > + wapl_bitmap_t b; \ > > > + __wapl_upcast(b, map); \ > > > + __wapl_bitmap_clear(&b, bit); \ > > > + }) > > > + > > > +/* > > > + * Round robin iterator runs upon a WAPL bitmap: > > > + * > > > + * wapl_bitmap_iterator(iterator, WAPL bitmap); > > > + * for (iterator->start(); iterator->has_next(); ) { > > > + * unsigned int bit_index = iterator->next(); > > > + * ...operations on this bit index... > > > + * } > > > + */ > > > +#define METHOD_DECLARE(_return, _name, _impl, ...) \ > > > + _return (*_name)(struct _impl ## _bitmap_ ## iterator *this) > > > + > > > +typedef struct wapl_bitmap_iterator { > > > + int _start, _next, _nbits; > > > + wapl_bitmap_t _base; > > > + > > > + METHOD_DECLARE(void, start, wapl); > > > + METHOD_DECLARE(bool, has_next, wapl); > > > + METHOD_DECLARE(unsigned int, next, wapl); > > > +} wapl_bitmap_iterator_t; > > > + > > > +/* > > > + * WAPL bitmap iterator constructor > > > + */ > > > +void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this); > > > + > > > +/* > > > + * Generic constructor accepts any derived WAPL bitmap class > > > + */ > > > +#define wapl_bitmap_iterator(iterator, map) \ > > > + ({ \ > > > + __typeof__(iterator) __it = iterator; \ > > > + __wapl_upcast(__it->_base, map); \ > > > + __wapl_bitmap_iterator(__it); \ > > > + }) > > > + > > > +/* Sparse bitmap base class */ > > > +typedef struct { > > > + unsigned int nbits; > > > + unsigned int *last, *pl, *il; > > > +} sparse_bitmap_t; > > > + > > > +/* > > > + * Sparse bitmap, lists all bit indexes directly as an array. > > > + * Expected to be significantly straightforward iteration. > > > + */ > > > +#define instantiate_sparse_bitmap(line, nbits) > > \ > > > + struct TOKENIZE(sparse_bitmap, line) { \ > > > + unsigned int last; \ > > > + unsigned int pl[nbits]; \ > > > + unsigned int il[nbits]; \ > > > + } > > > + > > > +#define SPARSE_BITMAP(nbits) instantiate_sparse_bitmap(__LINE__, > > nbits) > > > + > > > +/* > > > + * Upcast any derived sparse bitmap class to its base class > > > + */ > > > +#define __sparse_upcast(base, derived) > > \ > > > + do { \ > > > + __typeof__(derived) p = derived; \ > > > + base.pl <http://base.pl> = p->pl; > > \ > > > + base.il <http://base.il> = p->il; > > \ > > > + base.last = &p->last; \ > > > + base.nbits = ARRAY_SIZE(p->il); \ > > > + } while (0) > > > + > > > +/* > > > + * Sparse base class bitmap operations > > > + */ > > > +void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit); > > > + > > > +void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int > bit); > > > + > > > +/* > > > + * Generic sparse bitmap operations > > > + */ > > > +#define sparse_bitmap_zero(map) > > \ > > > + ({ \ > > > + __typeof__(map) p = map; \ > > > + memset((void *)p, 0, sizeof(__typeof__(*p))); \ > > > + }) > > > + > > > +#define sparse_bitmap_set(map, bit) \ > > > + ({ \ > > > + sparse_bitmap_t b; \ > > > + __sparse_upcast(b, map); \ > > > + __sparse_bitmap_set(&b, bit); \ > > > + }) > > > + > > > +#define sparse_bitmap_clear(map, bit) > > \ > > > + ({ \ > > > + sparse_bitmap_t b; \ > > > + __sparse_upcast(b, map); \ > > > + __sparse_bitmap_clear(&b, bit); \ > > > + }) > > > + > > > +/* > > > + * Round robin iterator runs upon a sparse bitmap: > > > + * > > > + * sparse_bitmap_iterator(iterator, SPARSE bitmap); > > > + * for (iterator->start(); iterator->has_next(); ) { > > > + * unsigned int bit_index = iterator->next(); > > > + * ...operations on this bit index... > > > + * } > > > + */ > > > +typedef struct sparse_bitmap_iterator { > > > + int _start, _next, _nbits; > > > + sparse_bitmap_t _base; > > > + > > > + METHOD_DECLARE(void, start, sparse); > > > + METHOD_DECLARE(bool, has_next, sparse); > > > + METHOD_DECLARE(unsigned int, next, sparse); > > > +} sparse_bitmap_iterator_t; > > > + > > > +/* > > > + * Sparse bitmap iterator constructor > > > + */ > > > +void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this); > > > + > > > +/* > > > + * Generic constructor accepts any derived sparse bitmap class. > > > + */ > > > +#define sparse_bitmap_iterator(iterator, map) > > \ > > > + ({ \ > > > + __typeof__(iterator) __it = iterator; \ > > > + __sparse_upcast(__it->_base, map); \ > > > + __sparse_bitmap_iterator(__it); \ > > > + }) > > > + > > > +/* > > > + * Raw bitmap atomic set and clear. > > > + */ > > > +void raw_bitmap_set(unsigned long *map, unsigned int bit); > > > + > > > +void raw_bitmap_clear(unsigned long *map, unsigned int bit); > > > + > > > +/* > > > + * It will enter infinite loop incase that all bits are zero, > > > + * so please make sure the bitmap at least has one set. > > > + */ > > > +static inline int __bitmap_wraparound_next( > > > + unsigned long *addr, unsigned int nbits, int start) > > > +{ > > > + unsigned long tmp; > > > + > > > + if (start >= (int) nbits) > > > + start = 0; > > > + > > > + tmp = addr[BIT_WORD(start)]; > > > + > > > + /* Handle 1st word. */ > > > + tmp &= BITMAP_FIRST_WORD_MASK(start); > > > + start = start & ~(BITS_PER_LONG - 1); > > > + > > > + while (!tmp) { > > > + start += BITS_PER_LONG; > > > + if (start >= (int) nbits) > > > + start = 0; > > > + > > > + tmp = addr[BIT_WORD(start)]; > > > + } > > > + > > > + start += __builtin_ffsl(tmp) - 1; > > > + return start; > > > +} > > > + > > > +/** > > > + * @} > > > + */ > > > + > > > +#ifdef __cplusplus > > > +} > > > +#endif > > > + > > > +#endif > > > diff --git a/platform/linux-generic/odp_bitmap.c > > b/platform/linux-generic/odp_bitmap.c > > > new file mode 100644 > > > index 0000000..0f4d051 > > > --- /dev/null > > > +++ b/platform/linux-generic/odp_bitmap.c > > > @@ -0,0 +1,315 @@ > > > +/* Copyright (c) 2016, Linaro Limited > > > + * All rights reserved. > > > + * > > > + * SPDX-License-Identifier: BSD-3-Clause > > > + */ > > > + > > > +#include <string.h> > > > +#include <unistd.h> > > > +#include <odp/api/std_types.h> > > > +#include <odp/api/byteorder.h> > > > +#include <odp_bitmap_internal.h> > > > + > > > +/* > > > + * WAPL base class bitmap operations > > > + */ > > > +static inline void __wapl_add_pos( > > > + wapl_bitmap_t *map, unsigned int p) > > > +{ > > > + unsigned int s, k = 0; > > > + unsigned int *pl = map->pl; > > > + > > > + while (pl[k] && p > pl[k]) > > > + k++; > > > + > > > + if (p == pl[k]) > > > + return; > > > + > > > + /* sorted insertion */ > > > + for (; pl[k] && p < pl[k]; k++) { > > > + s = pl[k]; > > > + pl[k] = p; > > > + p = s; > > > + } > > > + > > > + if (k < map->nwords) > > > + pl[k++] = p; > > > + > > > + pl[k] = 0; > > > +} > > > + > > > +static inline void __wapl_remove_pos( > > > + wapl_bitmap_t *map, unsigned int p) > > > +{ > > > + unsigned int k = 0; > > > + unsigned int *pl = map->pl; > > > + > > > + while (pl[k] && p != pl[k]) > > > + k++; > > > + > > > + for (; pl[k]; k++) > > > + pl[k] = pl[k + 1]; > > > +} > > > + > > > +void __wapl_bitmap_and(wapl_bitmap_t *dst, > > > + wapl_bitmap_t *src, wapl_bitmap_t *and) > > > +{ > > > + unsigned int k = 0, p; > > > + unsigned int *pl = src->pl; > > > + > > > + while ((p = *pl++) != 0) { > > > + dst->ul[p] = src->ul[p] & and->ul[p]; > > > + if (dst->ul[p]) > > > + dst->pl[k++] = p; > > > + } > > > + > > > + dst->pl[k] = 0; > > > +} > > > + > > > +void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or) > > > +{ > > > + unsigned int p; > > > + unsigned int *pl = or->pl; > > > + > > > + while ((p = *pl++) != 0) { > > > + if (dst->ul[p] == 0) > > > + __wapl_add_pos(dst, p); > > > + > > > + dst->ul[p] |= or->ul[p]; > > > + } > > > +} > > > + > > > +void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit) > > > +{ > > > + unsigned int p = BIT_WORD(bit) + 1; > > > + unsigned long set = 1UL << (bit & (BITS_PER_LONG - 1)); > > > + > > > + if (p > map->nwords) > > > + return; > > > + > > > + if (map->ul[p] == 0) > > > + __wapl_add_pos(map, p); > > > + > > > + map->ul[p] |= set; > > > +} > > > + > > > +void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit) > > > +{ > > > + unsigned int p = BIT_WORD(bit) + 1; > > > + unsigned long clear = 1UL << (bit & (BITS_PER_LONG - 1)); > > > + > > > + if (p > map->nwords) > > > + return; > > > + > > > + map->ul[p] &= ~clear; > > > + > > > + if (map->ul[p] == 0) > > > + __wapl_remove_pos(map, p); > > > +} > > > + > > > +/* > > > + * WAPL bitmap iterator implementation > > > + */ > > > +static void __wapl_iterator_start(wapl_bitmap_iterator_t *this) > > > +{ > > > + this->_nbits = this->_base.nwords * BITS_PER_LONG; > > > + > > > + /* Advance to next queue index to start this > > > + * new round iteration. > > > + */ > > > + if (this->_base.pl <http://base.pl>[0] == 0) > > > + this->_start = -1; > > > + else > > > + this->_start = __bitmap_wraparound_next( > > > + &this->_base.ul[1], this->_nbits, > > this->_start + 1); > > > + > > > + this->_next = this->_start; > > > +} > > > + > > > +static bool __wapl_iterator_has_next(wapl_bitmap_iterator_t > *this) > > > +{ > > > + return (this->_next != -1); > > > +} > > > + > > > +static unsigned int __wapl_iterator_next(wapl_bitmap_iterator_t > > *this) > > > +{ > > > + int next = this->_next; > > > + > > > + this->_next = __bitmap_wraparound_next( > > > + &this->_base.ul[1], this->_nbits, > > this->_next + 1); > > > + > > > + if (this->_next == this->_start) > > > + this->_next = -1; > > > + > > > + return next; > > > +} > > > + > > > +void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this) > > > +{ > > > + this->start = __wapl_iterator_start; > > > + this->has_next = __wapl_iterator_has_next; > > > + this->next = __wapl_iterator_next; > > > + > > > + this->_start = -1; > > > + this->_next = this->_start; > > > +} > > > + > > > +/* > > > + * Sparse base class bitmap operations > > > + */ > > > +void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit) > > > +{ > > > + unsigned int last = *map->last; > > > + > > > + /* Index exceeds */ > > > + if (bit >= map->nbits) > > > + return; > > > + > > > + /* Full bitmap */ > > > + if (last >= map->nbits) > > > + return; > > > + > > > + /* Bit was not set previously, > > > + * also record where we set the bit > > > + */ > > > + if (!map->pl[bit]) { > > > + map->il[last++] = bit; > > > + map->pl[bit] = last; > > > + > > > + *map->last = last; > > > + } > > > +} > > > + > > > +void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int > bit) > > > +{ > > > + unsigned int p, i; > > > + unsigned int last = *map->last; > > > + > > > + /* Index exceeds */ > > > + if (bit >= map->nbits) > > > + return; > > > + > > > + /* Empty bitmap */ > > > + if (last == 0) > > > + return; > > > + > > > + /* Bit was set previously */ > > > + if (map->pl[bit]) { > > > + p = map->pl[bit] - 1; > > > + map->pl[bit] = 0; > > > + > > > + last--; > > > + *map->last = last; > > > + > > > + /* Fill the hole with the latest index */ > > > + if (p < last) { > > > + i = map->il[last]; > > > + map->pl[i] = p + 1; > > > + map->il[p] = i; > > > + } > > > + } > > > +} > > > + > > > +/* > > > + * Sparse bitmap iterator implementation > > > + */ > > > +static void __sparse_iterator_start(sparse_bitmap_iterator_t > *this) > > > +{ > > > + this->_nbits = (int) *(this->_base.last); > > > + > > > + /* Advance to next queue index to start this > > > + * new round iteration. > > > + */ > > > + if (this->_nbits == 0) > > > + this->_start = -1; > > > + else > > > + this->_start = (this->_start + 1) & (this->_nbits - > 1); > > > + > > > + this->_next = this->_start; > > > +} > > > + > > > +static bool __sparse_iterator_has_next(sparse_bitmap_iterator_t > > *this) > > > +{ > > > + return (this->_next != -1); > > > +} > > > + > > > +static unsigned int > > __sparse_iterator_next(sparse_bitmap_iterator_t *this) > > > +{ > > > + int next = this->_next; > > > + > > > + this->_next = (this->_next + 1) & (this->_nbits - 1); > > > + if (this->_next == this->_start) > > > + this->_next = -1; > > > + > > > + return this->_base.il <http://base.il>[next]; > > > +} > > > + > > > +void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this) > > > +{ > > > + this->start = __sparse_iterator_start; > > > + this->has_next = __sparse_iterator_has_next; > > > + this->next = __sparse_iterator_next; > > > + > > > + this->_start = -1; > > > + this->_next = this->_start; > > > +} > > > + > > > +/* > > > + * Generic byte-width atomic set/clear > > > + */ > > > +static inline void atomic_byte_set( > > > + unsigned char *addr, unsigned int bit) > > > +{ > > > + unsigned char load, store; > > > + unsigned char set = 1 << (bit & (BITS_PER_BYTE - 1)); > > > + > > > + do { > > > + load = *addr; > > > + store = load | set; > > > + } while (!__atomic_compare_exchange_n(addr, &load, store, > > > + 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED)); > > > +} > > > + > > > +static inline void atomic_byte_clear( > > > + unsigned char *addr, unsigned int bit) > > > +{ > > > + unsigned char load, store; > > > + unsigned char clear = 1 << (bit & (BITS_PER_BYTE - 1)); > > > + > > > + do { > > > + load = *addr; > > > + store = load & ~clear; > > > + } while (!__atomic_compare_exchange_n(addr, &load, store, > > > + 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED)); > > > +} > > > + > > > +static inline unsigned char *__bit_byte( > > > + unsigned long *word, unsigned int bit) > > > +{ > > > + unsigned int i; > > > + unsigned char *b; > > > + > > > + b = (unsigned char *)word; > > > + > > > + i = bit & (BITS_PER_LONG - 1); > > > + i = i / BITS_PER_BYTE; > > > + > > > +#if (ODP_BYTE_ORDER == ODP_BIG_ENDIAN) > > > + i = BYTES_PER_LONG - 1 - i; > > > +#endif > > > + return &b[i]; > > > +} > > > + > > > +void raw_bitmap_set(unsigned long *map, unsigned int bit) > > > +{ > > > + unsigned long *p = map + BIT_WORD(bit); > > > + > > > + atomic_byte_set(__bit_byte(p, bit), bit); > > > +} > > > + > > > +void raw_bitmap_clear(unsigned long *map, unsigned int bit) > > > +{ > > > + unsigned long *p = map + BIT_WORD(bit); > > > + > > > + atomic_byte_clear(__bit_byte(p, bit), bit); > > > +} > > > -- > > > 2.7.4 > > > > > > > > >
