| Message ID | 1481280689-14223-4-git-send-email-yi.he@linaro.org |
|---|---|
| State | Superseded |
| Headers | show |
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.he@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 = 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 = p->pl; \
> + 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[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[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
>
O, missing this mail Hi, Maxim, for the error and warnings it seems the 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 On 5 January 2017 at 03:16, Maxim Uvarov <maxim.uvarov@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.he@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 = 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 = p->pl; \ > > + 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[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[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 > > > >
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.uvarov@linaro.org > <mailto:maxim.uvarov@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.he@linaro.org <mailto:yi.he@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 > > > >
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.uvarov@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.uvarov@linaro.org > > <mailto:maxim.uvarov@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.he@linaro.org <mailto:yi.he@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 > > > > > > > > >
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 = 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 = p->pl; \ + 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[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[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); +}
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.he@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 -- 2.7.4