[igt-dev] [PATCH i-g-t v18 02/31] lib/igt_map: Introduce igt_map

Chris Wilson chris at chris-wilson.co.uk
Mon Feb 1 15:54:20 UTC 2021


Quoting Zbigniew Kempczyński (2021-01-29 14:44:25)
> 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 +
>  lib/Makefile.sources                          |   2 +
>  lib/igt_map.c                                 | 132 ++++++++++++++++++
>  lib/igt_map.h                                 | 102 ++++++++++++++
>  lib/meson.build                               |   1 +
>  5 files changed, 238 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..6ed06e33a
> --- /dev/null
> +++ b/lib/igt_map.c
> @@ -0,0 +1,132 @@
> +// 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 map->capacity_bits == 0 ||
> +                       (IGT_MAP_CAPACITY(map) * 4 / 5 < map->size);

return IGT_MAP_CAPACITY(map) * 4 / 5 <= map->size;

also works for bits == 0

(1 << 0) * 4 / 5 == 0

and perhaps more importantly works for bits == 1 and size == 1.

Maybe valgrind/asan a test case that starts from 0 and adds a million
elements.

> +}
> +
> +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 0x9e37fffffffc0001UL

ULL

> +
> +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)

Do we care enough for initial_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)

#define igt_map_init(map) __igt_map_init(map, NULL, NULL, 8)

Is probably going to satisfy most.

> +{
> +       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 = calloc(1, sizeof(struct igt_map_entry));

calloc here is overkill

> +       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 (pos && map->equal_fn(pos->key, key))
> +                       break;

We could optimise equal_fn == default && hash_fn == default, but I guess
we will want an open addressing hash table with a better hash_fn if we
ever have to worry about the efficiency of the ht.

Wait. igt_map_for_each_possible() how do we have pos == NULL inside the
loop?

The inner hlist doesn't pass on a NULL, and the outer for() breaks if
the inner iteration stops and leaves pos != NULL.

> +       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;

bool already provides the !!
-Chris


More information about the igt-dev mailing list