[igt-dev] [PATCH i-g-t v23 04/37] lib/igt_map: Introduce igt_map
Daniel Vetter
daniel at ffwll.ch
Tue Mar 16 13:26:12 UTC 2021
On Tue, Mar 16, 2021 at 01:25:44PM +0100, Zbigniew Kempczyński wrote:
> On Tue, Mar 16, 2021 at 11:30:39AM +0100, Daniel Vetter wrote:
> > On Mon, Mar 15, 2021 at 05:58:09PM +0100, Zbigniew Kempczyński wrote:
> > > From: Dominik Grzegorzek <dominik.grzegorzek at intel.com>
> > >
> > > Implementation of generic, non-thread safe, dynamic size hash map.
> > >
> > > Signed-off-by: Dominik Grzegorzek <dominik.grzegorzek at intel.com>
> > > Cc: Zbigniew Kempczyński <zbigniew.kempczynski at intel.com>
> > > Cc: Chris Wilson <chris at chris-wilson.co.uk>
> > > ---
> > > .../igt-gpu-tools/igt-gpu-tools-docs.xml | 1 +
> >
> > Similar here, there's a solid intro, that's good. But we try to at least
> > doc all the non-static functions that tests can use.
> > -Daniel
>
> Ok, I assume you got Ack here so Dominik is going to provide appropriate
> documentation soon.
Yup.
-Daniel
>
> --
> Zbigniew
>
> >
> > > lib/Makefile.sources | 2 +
> > > lib/igt_map.c | 131 ++++++++++++++++++
> > > lib/igt_map.h | 104 ++++++++++++++
> > > lib/meson.build | 1 +
> > > 5 files changed, 239 insertions(+)
> > > create mode 100644 lib/igt_map.c
> > > create mode 100644 lib/igt_map.h
> > >
> > > diff --git a/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml b/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
> > > index 9c9aa8f1d..bf5ac5428 100644
> > > --- a/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
> > > +++ b/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
> > > @@ -33,6 +33,7 @@
> > > <xi:include href="xml/igt_kmod.xml"/>
> > > <xi:include href="xml/igt_kms.xml"/>
> > > <xi:include href="xml/igt_list.xml"/>
> > > + <xi:include href="xml/igt_map.xml"/>
> > > <xi:include href="xml/igt_pm.xml"/>
> > > <xi:include href="xml/igt_primes.xml"/>
> > > <xi:include href="xml/igt_rand.xml"/>
> > > diff --git a/lib/Makefile.sources b/lib/Makefile.sources
> > > index 4f6389f8a..84fd7b49c 100644
> > > --- a/lib/Makefile.sources
> > > +++ b/lib/Makefile.sources
> > > @@ -48,6 +48,8 @@ lib_source_list = \
> > > igt_infoframe.h \
> > > igt_list.c \
> > > igt_list.h \
> > > + igt_map.c \
> > > + igt_map.h \
> > > igt_matrix.c \
> > > igt_matrix.h \
> > > igt_params.c \
> > > diff --git a/lib/igt_map.c b/lib/igt_map.c
> > > new file mode 100644
> > > index 000000000..12909ed5a
> > > --- /dev/null
> > > +++ b/lib/igt_map.c
> > > @@ -0,0 +1,131 @@
> > > +// SPDX-License-Identifier: MIT
> > > +/*
> > > + * Copyright © 2021 Intel Corporation
> > > + */
> > > +
> > > +#include <sys/ioctl.h>
> > > +#include <stdlib.h>
> > > +#include "igt_map.h"
> > > +#include "igt.h"
> > > +#include "igt_x86.h"
> > > +
> > > +#define MIN_CAPACITY_BITS 2
> > > +
> > > +static bool igt_map_filled(struct igt_map *map)
> > > +{
> > > + return IGT_MAP_CAPACITY(map) * 4 / 5 <= map->size;
> > > +}
> > > +
> > > +static void igt_map_extend(struct igt_map *map)
> > > +{
> > > + struct igt_hlist_head *new_heads;
> > > + struct igt_map_entry *pos;
> > > + struct igt_hlist_node *tmp;
> > > + uint32_t new_bits = map->capacity_bits + 1;
> > > + int i;
> > > +
> > > + new_heads = calloc(1ULL << new_bits,
> > > + sizeof(struct igt_hlist_head));
> > > + igt_assert(new_heads);
> > > +
> > > + igt_map_for_each_safe(map, i, tmp, pos)
> > > + igt_hlist_add_head(&pos->link, &new_heads[map->hash_fn(pos->key, new_bits)]);
> > > +
> > > + free(map->heads);
> > > + map->capacity_bits++;
> > > +
> > > + map->heads = new_heads;
> > > +}
> > > +
> > > +static bool equal_4bytes(const void *key1, const void *key2)
> > > +{
> > > + const uint32_t *k1 = key1, *k2 = key2;
> > > + return *k1 == *k2;
> > > +}
> > > +
> > > +/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
> > > +#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL
> > > +
> > > +static inline uint64_t hash_64_4bytes(const void *val, unsigned int bits)
> > > +{
> > > + uint64_t hash = *(uint32_t *)val;
> > > +
> > > + hash = hash * GOLDEN_RATIO_PRIME_64;
> > > + /* High bits are more random, so use them. */
> > > + return hash >> (64 - bits);
> > > +}
> > > +
> > > +void __igt_map_init(struct igt_map *map, igt_map_equal_fn eq_fn,
> > > + igt_map_hash_fn hash_fn, uint32_t initial_bits)
> > > +{
> > > + map->equal_fn = eq_fn == NULL ? equal_4bytes : eq_fn;
> > > + map->hash_fn = hash_fn == NULL ? hash_64_4bytes : hash_fn;
> > > + map->capacity_bits = initial_bits > 0 ? initial_bits
> > > + : MIN_CAPACITY_BITS;
> > > + map->heads = calloc(IGT_MAP_CAPACITY(map),
> > > + sizeof(struct igt_hlist_head));
> > > +
> > > + igt_assert(map->heads);
> > > + map->size = 0;
> > > +}
> > > +
> > > +void igt_map_add(struct igt_map *map, const void *key, void *value)
> > > +{
> > > + struct igt_map_entry *entry;
> > > +
> > > + if (igt_map_filled(map))
> > > + igt_map_extend(map);
> > > +
> > > + entry = malloc(sizeof(struct igt_map_entry));
> > > + entry->value = value;
> > > + entry->key = key;
> > > + igt_hlist_add_head(&entry->link,
> > > + &map->heads[map->hash_fn(key, map->capacity_bits)]);
> > > + map->size++;
> > > +}
> > > +
> > > +void *igt_map_del(struct igt_map *map, const void *key)
> > > +{
> > > + struct igt_map_entry *pos;
> > > + struct igt_hlist_node *tmp;
> > > + void *val = NULL;
> > > +
> > > + igt_map_for_each_possible_safe(map, pos, tmp, key) {
> > > + if (map->equal_fn(pos->key, key)) {
> > > + igt_hlist_del(&pos->link);
> > > + val = pos->value;
> > > + free(pos);
> > > + }
> > > + }
> > > + return val;
> > > +}
> > > +
> > > +void *igt_map_find(struct igt_map *map, const void *key)
> > > +{
> > > + struct igt_map_entry *pos = NULL;
> > > +
> > > + igt_map_for_each_possible(map, pos, key)
> > > + if (map->equal_fn(pos->key, key))
> > > + break;
> > > +
> > > + return pos ? pos->value : NULL;
> > > +}
> > > +
> > > +void igt_map_free(struct igt_map *map)
> > > +{
> > > + struct igt_map_entry *pos;
> > > + struct igt_hlist_node *tmp;
> > > + int i;
> > > +
> > > + igt_map_for_each_safe(map, i, tmp, pos) {
> > > + igt_hlist_del(&pos->link);
> > > + free(pos);
> > > + }
> > > +
> > > + free(map->heads);
> > > +}
> > > +
> > > +bool igt_map_empty(struct igt_map *map)
> > > +{
> > > + return map->size;
> > > +}
> > > diff --git a/lib/igt_map.h b/lib/igt_map.h
> > > new file mode 100644
> > > index 000000000..d47afdbbe
> > > --- /dev/null
> > > +++ b/lib/igt_map.h
> > > @@ -0,0 +1,104 @@
> > > +// SPDX-License-Identifier: MIT
> > > +/*
> > > + * Copyright © 2021 Intel Corporation
> > > + */
> > > +
> > > +#ifndef IGT_MAP_H
> > > +#define IGT_MAP_H
> > > +
> > > +#include <stdint.h>
> > > +#include "igt_list.h"
> > > +
> > > +/**
> > > + * SECTION:igt_map
> > > + * @short_description: a dynamic sized hashmap implementation
> > > + * @title: IGT Map
> > > + * @include: igt_map.h
> > > + *
> > > + * igt_map is a dynamic sized, non-thread-safe implementation of a hashmap.
> > > + * This map grows exponentially when it's over 80% filled. The structure allows
> > > + * indexing records by any key through the hash and equal functions.
> > > + * By default, hashmap compares and hashes the first four bytes of a key.
> > > + *
> > > + * Example usage:
> > > + *
> > > + * |[<!-- language="C" -->
> > > + * struct igt_map *map;
> > > + *
> > > + * struct record {
> > > + * int foo;
> > > + * uint32_t unique_identifier;
> > > + * };
> > > + *
> > > + * struct record r1, r2, *r_ptr;
> > > + *
> > > + * map = malloc(sizeof(*map));
> > > + * igt_map_init(map); // initiaize the map with default parameters
> > > + * igt_map_add(map, &r1.unique_identifier, &r1);
> > > + * igt_map_add(map, &r2.unique_identifier, &r2);
> > > + *
> > > + * struct igt_map_entry *pos; int i;
> > > + * igt_map_for_each(map, i, pos) {
> > > + * r_ptr = pos->value;
> > > + * printf("key: %u, foo: %d\n", *(uint32_t*) pos->key, r_ptr->foo);
> > > + * }
> > > + *
> > > + * uint32_t key = r1.unique_identifier;
> > > + * r_ptr = igt_map_find(map, &key); // get r1
> > > + *
> > > + * r_ptr = igt_map_del(map, &r2.unique_identifier);
> > > + * if (r_ptr)
> > > + * printf("record with key %u deleted\n", r_ptr->unique_identifier);
> > > + *
> > > + * igt_map_free(map);
> > > + * free(map);
> > > + * ]|
> > > + */
> > > +
> > > +typedef bool (*igt_map_equal_fn)(const void *key1, const void *key2);
> > > +typedef uint64_t (*igt_map_hash_fn)(const void *val, unsigned int bits);
> > > +struct igt_map {
> > > + uint32_t size;
> > > + uint32_t capacity_bits;
> > > + igt_map_equal_fn equal_fn;
> > > + igt_map_hash_fn hash_fn;
> > > + struct igt_hlist_head *heads;
> > > +};
> > > +
> > > +struct igt_map_entry {
> > > + const void *key;
> > > + void *value;
> > > + struct igt_hlist_node link;
> > > +};
> > > +
> > > +void __igt_map_init(struct igt_map *map, igt_map_equal_fn eq_fn,
> > > + igt_map_hash_fn hash_fn, uint32_t initial_bits);
> > > +void igt_map_add(struct igt_map *map, const void *key, void *value);
> > > +void *igt_map_del(struct igt_map *map, const void *key);
> > > +void *igt_map_find(struct igt_map *map, const void *key);
> > > +void igt_map_free(struct igt_map *map);
> > > +bool igt_map_empty(struct igt_map *map);
> > > +
> > > +#define igt_map_init(map) __igt_map_init(map, NULL, NULL, 8)
> > > +
> > > +#define IGT_MAP_CAPACITY(map) (1ULL << map->capacity_bits)
> > > +
> > > +#define igt_map_for_each_safe(map, bkt, tmp, obj) \
> > > + for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < IGT_MAP_CAPACITY(map); \
> > > + (bkt)++)\
> > > + igt_hlist_for_each_entry_safe(obj, tmp, &map->heads[bkt], link)
> > > +
> > > +#define igt_map_for_each(map, bkt, obj) \
> > > + for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < IGT_MAP_CAPACITY(map); \
> > > + (bkt)++)\
> > > + igt_hlist_for_each_entry(obj, &map->heads[bkt], link)
> > > +
> > > +#define igt_map_for_each_possible(map, obj, key) \
> > > + igt_hlist_for_each_entry(obj, \
> > > + &map->heads[map->hash_fn(key, map->capacity_bits)], link)
> > > +
> > > +#define igt_map_for_each_possible_safe(map, obj, tmp, key) \
> > > + igt_hlist_for_each_entry_safe(obj, tmp, \
> > > + &map->heads[map->hash_fn(key, map->capacity_bits)], link)
> > > +
> > > +#endif /* IGT_MAP_H */
> > > diff --git a/lib/meson.build b/lib/meson.build
> > > index 672b42062..7254faeac 100644
> > > --- a/lib/meson.build
> > > +++ b/lib/meson.build
> > > @@ -61,6 +61,7 @@ lib_sources = [
> > > 'igt_core.c',
> > > 'igt_draw.c',
> > > 'igt_list.c',
> > > + 'igt_map.c',
> > > 'igt_pm.c',
> > > 'igt_dummyload.c',
> > > 'uwildmat/uwildmat.c',
> > > --
> > > 2.26.0
> > >
> > > _______________________________________________
> > > igt-dev mailing list
> > > igt-dev at lists.freedesktop.org
> > > https://lists.freedesktop.org/mailman/listinfo/igt-dev
> >
> > --
> > Daniel Vetter
> > Software Engineer, Intel Corporation
> > http://blog.ffwll.ch
--
Daniel Vetter
Software Engineer, Intel Corporation
http://blog.ffwll.ch
More information about the igt-dev
mailing list