[igt-dev] [PATCH i-g-t v29 03/36] lib/igt_map: Adopt Mesa hash table
Zbigniew Kempczyński
zbigniew.kempczynski at intel.com
Thu Mar 25 07:05:49 UTC 2021
On Wed, Mar 24, 2021 at 01:59:41PM -0500, Jason Ekstrand wrote:
> On Wed, Mar 24, 2021 at 12:36 PM Zbigniew Kempczyński
> <zbigniew.kempczynski at intel.com> wrote:
> >
> > From: Dominik Grzegorzek <dominik.grzegorzek at intel.com>
>
> Is this still from Dominik? Assuming it's a direct import of the Mesa
> code, without ralloc,
This was taken not directly from Mesa but from Eric repository,
so maybe commit message is confusing but we wanted to point out
Mesa also use same hash table (apart of some improvements).
--
Zbigniew
>
> Acked-by: Jason Ekstrand <jason at jlekstrand.net>
>
> > The _search function has been changed to return a pointer to
> > the stored data instead of the entry struct. The _search_entry function,
> > which acts as the original search has been added. Additionally _remove function
> > has an optional delete_function param, to make it more usable.
> >
> > For more information, see:
> > http://cgit.freedesktop.org/~anholt/hash_table/tree/README
> >
> > 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>
> > Cc: Daniel Vetter <daniel.vetter at ffwll.ch>
> > Cc: Jason Ekstrand <jason at jlekstrand.net>
> > ---
> > .../igt-gpu-tools/igt-gpu-tools-docs.xml | 1 +
> > lib/Makefile.sources | 2 +
> > lib/igt_map.c | 502 ++++++++++++++++++
> > lib/igt_map.h | 174 ++++++
> > lib/meson.build | 1 +
> > 5 files changed, 680 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..da8713a18
> > --- /dev/null
> > +++ b/lib/igt_map.c
> > @@ -0,0 +1,502 @@
> > +/*
> > + * Copyright © 2009, 2021 Intel Corporation
> > + * Copyright © 1988-2004 Keith Packard and Bart Massey.
> > + *
> > + * Permission is hereby granted, free of charge, to any person obtaining a
> > + * copy of this software and associated documentation files (the "Software"),
> > + * to deal in the Software without restriction, including without limitation
> > + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
> > + * and/or sell copies of the Software, and to permit persons to whom the
> > + * Software is furnished to do so, subject to the following conditions:
> > + *
> > + * The above copyright notice and this permission notice (including the next
> > + * paragraph) shall be included in all copies or substantial portions of the
> > + * Software.
> > + *
> > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
> > + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> > + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
> > + * IN THE SOFTWARE.
> > + *
> > + * Except as contained in this notice, the names of the authors
> > + * or their institutions shall not be used in advertising or
> > + * otherwise to promote the sale, use or other dealings in this
> > + * Software without prior written authorization from the
> > + * authors.
> > + *
> > + * Authors:
> > + * Eric Anholt <eric at anholt.net>
> > + * Keith Packard <keithp at keithp.com>
> > + */
> > +
> > +#include <assert.h>
> > +#include <stdlib.h>
> > +
> > +#include "igt_map.h"
> > +
> > +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0]))
> > +
> > +/*
> > + * From Knuth -- a good choice for hash/rehash values is p, p-2 where
> > + * p and p-2 are both prime. These tables are sized to have an extra 10%
> > + * free to avoid exponential performance degradation as the hash table fills
> > + */
> > +
> > +static const uint32_t deleted_key_value;
> > +static const void *deleted_key = &deleted_key_value;
> > +
> > +static const struct {
> > + uint32_t max_entries, size, rehash;
> > +} hash_sizes[] = {
> > + { 2, 5, 3 },
> > + { 4, 7, 5 },
> > + { 8, 13, 11 },
> > + { 16, 19, 17 },
> > + { 32, 43, 41 },
> > + { 64, 73, 71 },
> > + { 128, 151, 149 },
> > + { 256, 283, 281 },
> > + { 512, 571, 569 },
> > + { 1024, 1153, 1151 },
> > + { 2048, 2269, 2267 },
> > + { 4096, 4519, 4517 },
> > + { 8192, 9013, 9011 },
> > + { 16384, 18043, 18041 },
> > + { 32768, 36109, 36107 },
> > + { 65536, 72091, 72089 },
> > + { 131072, 144409, 144407 },
> > + { 262144, 288361, 288359 },
> > + { 524288, 576883, 576881 },
> > + { 1048576, 1153459, 1153457 },
> > + { 2097152, 2307163, 2307161 },
> > + { 4194304, 4613893, 4613891 },
> > + { 8388608, 9227641, 9227639 },
> > + { 16777216, 18455029, 18455027 },
> > + { 33554432, 36911011, 36911009 },
> > + { 67108864, 73819861, 73819859 },
> > + { 134217728, 147639589, 147639587 },
> > + { 268435456, 295279081, 295279079 },
> > + { 536870912, 590559793, 590559791 },
> > + { 1073741824, 1181116273, 1181116271},
> > + { 2147483648ul, 2362232233ul, 2362232231ul}
> > +};
> > +
> > +static int
> > +entry_is_free(const struct igt_map_entry *entry)
> > +{
> > + return entry->key == NULL;
> > +}
> > +
> > +static int
> > +entry_is_deleted(const struct igt_map_entry *entry)
> > +{
> > + return entry->key == deleted_key;
> > +}
> > +
> > +static int
> > +entry_is_present(const struct igt_map_entry *entry)
> > +{
> > + return entry->key != NULL && entry->key != deleted_key;
> > +}
> > +
> > +/**
> > + * igt_map_create:
> > + * @hash_function: function that maps key to 32b hash
> > + * @key_equals_function: function that compares given hashes
> > + *
> > + * Function creates a map and initializes it with given @hash_function and
> > + * @key_equals_function.
> > + *
> > + * Returns: pointer to just created map
> > + */
> > +struct igt_map *
> > +igt_map_create(uint32_t (*hash_function)(const void *key),
> > + int (*key_equals_function)(const void *a, const void *b))
> > +{
> > + struct igt_map *map;
> > +
> > + map = malloc(sizeof(*map));
> > + if (map == NULL)
> > + return NULL;
> > +
> > + map->size_index = 0;
> > + map->size = hash_sizes[map->size_index].size;
> > + map->rehash = hash_sizes[map->size_index].rehash;
> > + map->max_entries = hash_sizes[map->size_index].max_entries;
> > + map->hash_function = hash_function;
> > + map->key_equals_function = key_equals_function;
> > + map->table = calloc(map->size, sizeof(*map->table));
> > + map->entries = 0;
> > + map->deleted_entries = 0;
> > +
> > + if (map->table == NULL) {
> > + free(map);
> > + return NULL;
> > + }
> > +
> > + return map;
> > +}
> > +
> > +/**
> > + * igt_map_destroy:
> > + * @map: igt_map pointer
> > + * @delete_function: function that frees data in igt_map_entry
> > + *
> > + * Frees the given hash table. If @delete_function is passed, it gets called
> > + * on each entry present before freeing.
> > + */
> > +void
> > +igt_map_destroy(struct igt_map *map,
> > + void (*delete_function)(struct igt_map_entry *entry))
> > +{
> > + if (!map)
> > + return;
> > +
> > + if (delete_function) {
> > + struct igt_map_entry *entry;
> > +
> > + igt_map_foreach(map, entry) {
> > + delete_function(entry);
> > + }
> > + }
> > + free(map->table);
> > + free(map);
> > +}
> > +
> > +/**
> > + * igt_map_search:
> > + * @map: igt_map pointer
> > + * @key: pointer to searched key
> > + *
> > + * Finds a map entry's data with the given @key.
> > + *
> > + * Returns: data pointer if the entry was found, %NULL otherwise.
> > + * Note that it may be modified by the user.
> > + */
> > +void *
> > +igt_map_search(struct igt_map *map, const void *key)
> > +{
> > + uint32_t hash = map->hash_function(key);
> > + struct igt_map_entry *entry;
> > +
> > + entry = igt_map_search_pre_hashed(map, hash, key);
> > + return entry ? entry->data : NULL;
> > +}
> > +
> > +/**
> > + * igt_map_search_entry:
> > + * @map: igt_map pointer
> > + * @key: pointer to searched key
> > + *
> > + * Finds a map entry with the given @key.
> > + *
> > + * Returns: map entry or %NULL if no entry is found.
> > + * Note that the data pointer may be modified by the user.
> > + */
> > +struct igt_map_entry *
> > +igt_map_search_entry(struct igt_map *map, const void *key)
> > +{
> > + uint32_t hash = map->hash_function(key);
> > +
> > + return igt_map_search_pre_hashed(map, hash, key);
> > +}
> > +
> > +/**
> > + * igt_map_search_pre_hashed:
> > + * @map: igt_map pointer
> > + * @hash: hash of @key
> > + * @key: pointer to searched key
> > + *
> > + * Finds a map entry with the given @key and @hash of that key.
> > + *
> > + * Returns: map entry or %NULL if no entry is found.
> > + * Note that the data pointer may be modified by the user.
> > + */
> > +struct igt_map_entry *
> > +igt_map_search_pre_hashed(struct igt_map *map, uint32_t hash,
> > + const void *key)
> > +{
> > + uint32_t start_hash_address = hash % map->size;
> > + uint32_t hash_address = start_hash_address;
> > +
> > + do {
> > + uint32_t double_hash;
> > +
> > + struct igt_map_entry *entry = map->table + hash_address;
> > +
> > + if (entry_is_free(entry)) {
> > + return NULL;
> > + } else if (entry_is_present(entry) && entry->hash == hash) {
> > + if (map->key_equals_function(key, entry->key)) {
> > + return entry;
> > + }
> > + }
> > +
> > + double_hash = 1 + hash % map->rehash;
> > +
> > + hash_address = (hash_address + double_hash) % map->size;
> > + } while (hash_address != start_hash_address);
> > +
> > + return NULL;
> > +}
> > +
> > +static void
> > +igt_map_rehash(struct igt_map *map, int new_size_index)
> > +{
> > + struct igt_map old_map;
> > + struct igt_map_entry *table, *entry;
> > +
> > + if (new_size_index >= ARRAY_SIZE(hash_sizes))
> > + return;
> > +
> > + table = calloc(hash_sizes[new_size_index].size, sizeof(*map->table));
> > + if (table == NULL)
> > + return;
> > +
> > + old_map = *map;
> > +
> > + map->table = table;
> > + map->size_index = new_size_index;
> > + map->size = hash_sizes[map->size_index].size;
> > + map->rehash = hash_sizes[map->size_index].rehash;
> > + map->max_entries = hash_sizes[map->size_index].max_entries;
> > + map->entries = 0;
> > + map->deleted_entries = 0;
> > +
> > + igt_map_foreach(&old_map, entry) {
> > + igt_map_insert_pre_hashed(map, entry->hash,
> > + entry->key, entry->data);
> > + }
> > +
> > + free(old_map.table);
> > +}
> > +
> > +/**
> > + * igt_map_insert:
> > + * @map: igt_map pointer
> > + * @data: data to be store
> > + * @key: pointer to searched key
> > + *
> > + * Inserts the @data indexed by given @key into the map. If the @map already
> > + * contains an entry with the @key, it will be replaced. To avoid memory leaks,
> > + * perform a search before inserting.
> > + *
> > + * Note that insertion may rearrange the table on a resize or rehash,
> > + * so previously found hash entries are no longer valid after this function.
> > + *
> > + * Returns: pointer to just inserted entry
> > + */
> > +struct igt_map_entry *
> > +igt_map_insert(struct igt_map *map, const void *key, void *data)
> > +{
> > + uint32_t hash = map->hash_function(key);
> > +
> > + /* Make sure nobody tries to add one of the magic values as a
> > + * key. If you need to do so, either do so in a wrapper, or
> > + * store keys with the magic values separately in the struct
> > + * igt_map.
> > + */
> > + assert(key != NULL);
> > +
> > + return igt_map_insert_pre_hashed(map, hash, key, data);
> > +}
> > +
> > +/**
> > + * igt_map_insert_pre_hashed:
> > + * @map: igt_map pointer
> > + * @hash: hash of @key
> > + * @data: data to be store
> > + * @key: pointer to searched key
> > + *
> > + * Inserts the @data indexed by given @key and @hash of that @key into the map.
> > + * If the @map already contains an entry with the @key, it will be replaced.
> > + * To avoid memory leaks, perform a search before inserting.
> > + *
> > + * Note that insertion may rearrange the table on a resize or rehash,
> > + * so previously found hash entries are no longer valid after this function.
> > + *
> > + * Returns: pointer to just inserted entry
> > + */
> > +struct igt_map_entry *
> > +igt_map_insert_pre_hashed(struct igt_map *map, uint32_t hash,
> > + const void *key, void *data)
> > +{
> > + uint32_t start_hash_address, hash_address;
> > + struct igt_map_entry *available_entry = NULL;
> > +
> > + if (map->entries >= map->max_entries) {
> > + igt_map_rehash(map, map->size_index + 1);
> > + } else if (map->deleted_entries + map->entries >= map->max_entries) {
> > + igt_map_rehash(map, map->size_index);
> > + }
> > +
> > + start_hash_address = hash % map->size;
> > + hash_address = start_hash_address;
> > + do {
> > + struct igt_map_entry *entry = map->table + hash_address;
> > + uint32_t double_hash;
> > +
> > + if (!entry_is_present(entry)) {
> > + /* Stash the first available entry we find */
> > + if (available_entry == NULL)
> > + available_entry = entry;
> > + if (entry_is_free(entry))
> > + break;
> > + }
> > +
> > + /* Implement replacement when another insert happens
> > + * with a matching key. This is a relatively common
> > + * feature of hash tables, with the alternative
> > + * generally being "insert the new value as well, and
> > + * return it first when the key is searched for".
> > + *
> > + * Note that the hash table doesn't have a delete
> > + * callback. If freeing of old data pointers is
> > + * required to avoid memory leaks, perform a search
> > + * before inserting.
> > + */
> > + if (!entry_is_deleted(entry) &&
> > + entry->hash == hash &&
> > + map->key_equals_function(key, entry->key)) {
> > + entry->key = key;
> > + entry->data = data;
> > + return entry;
> > + }
> > +
> > +
> > + double_hash = 1 + hash % map->rehash;
> > +
> > + hash_address = (hash_address + double_hash) % map->size;
> > + } while (hash_address != start_hash_address);
> > +
> > + if (available_entry) {
> > + if (entry_is_deleted(available_entry))
> > + map->deleted_entries--;
> > + available_entry->hash = hash;
> > + available_entry->key = key;
> > + available_entry->data = data;
> > + map->entries++;
> > + return available_entry;
> > + }
> > +
> > + /* We could hit here if a required resize failed. An unchecked-malloc
> > + * application could ignore this result.
> > + */
> > + return NULL;
> > +}
> > +
> > +/**
> > + * igt_map_remove:
> > + * @map: igt_map pointer
> > + * @key: pointer to searched key
> > + * @delete_function: function that frees data in igt_map_entry
> > + *
> > + * Function searches for an entry with a given @key, and removes it from
> > + * the map. If @delete_function is passed, it will be called on removed entry.
> > + *
> > + * If the caller has previously found a struct igt_map_entry pointer,
> > + * (from calling igt_map_search() or remembering it from igt_map_insert()),
> > + * then igt_map_remove_entry() can be called instead to avoid an extra search.
> > + */
> > +void
> > +igt_map_remove(struct igt_map *map, const void *key,
> > + void (*delete_function)(struct igt_map_entry *entry))
> > +{
> > + struct igt_map_entry *entry;
> > +
> > + entry = igt_map_search_entry(map, key);
> > + if (delete_function)
> > + delete_function(entry);
> > +
> > + igt_map_remove_entry(map, entry);
> > +}
> > +
> > +/**
> > + * igt_map_remove_entry:
> > + * @map: igt_map pointer
> > + * @entry: pointer to map entry
> > + *
> > + * Function deletes the given hash entry.
> > + *
> > + * Note that deletion doesn't otherwise modify the table, so an iteration over
> > + * the map deleting entries is safe.
> > + */
> > +void
> > +igt_map_remove_entry(struct igt_map *map, struct igt_map_entry *entry)
> > +{
> > + if (!entry)
> > + return;
> > +
> > + entry->key = deleted_key;
> > + map->entries--;
> > + map->deleted_entries++;
> > +}
> > +
> > +/**
> > + * igt_map_next_entry:
> > + * @map: igt_map pointer
> > + * @entry: pointer to map entry, %NULL for the first map entry
> > + *
> > + * This function is an iterator over the hash table.
> > + * Note that an iteration over the table is O(table_size) not O(entries).
> > + *
> > + * Returns: pointer to the next entry
> > + */
> > +struct igt_map_entry *
> > +igt_map_next_entry(struct igt_map *map, struct igt_map_entry *entry)
> > +{
> > + if (entry == NULL)
> > + entry = map->table;
> > + else
> > + entry = entry + 1;
> > +
> > + for (; entry != map->table + map->size; entry++) {
> > + if (entry_is_present(entry)) {
> > + return entry;
> > + }
> > + }
> > +
> > + return NULL;
> > +}
> > +
> > +/**
> > + * igt_map_random_entry:
> > + * @map: igt_map pointer
> > + * @predicate: filtering entries function
> > + *
> > + * Functions returns random entry from the map. This may be useful in
> > + * implementing random replacement (as opposed to just removing everything)
> > + * in caches based on this hash table implementation. @predicate may be used to
> > + * filter entries, or may be set to %NULL for no filtering.
> > + *
> > + * Returns: pointer to the randomly chosen map entry
> > + */
> > +struct igt_map_entry *
> > +igt_map_random_entry(struct igt_map *map,
> > + int (*predicate)(struct igt_map_entry *entry))
> > +{
> > + struct igt_map_entry *entry;
> > + uint32_t i = random() % map->size;
> > +
> > + if (map->entries == 0)
> > + return NULL;
> > +
> > + for (entry = map->table + i; entry != map->table + map->size; entry++) {
> > + if (entry_is_present(entry) &&
> > + (!predicate || predicate(entry))) {
> > + return entry;
> > + }
> > + }
> > +
> > + for (entry = map->table; entry != map->table + i; entry++) {
> > + if (entry_is_present(entry) &&
> > + (!predicate || predicate(entry))) {
> > + return entry;
> > + }
> > + }
> > +
> > + return NULL;
> > +}
> > diff --git a/lib/igt_map.h b/lib/igt_map.h
> > new file mode 100644
> > index 000000000..cadcd6e35
> > --- /dev/null
> > +++ b/lib/igt_map.h
> > @@ -0,0 +1,174 @@
> > +/*
> > + * Copyright © 2009,2021 Intel Corporation
> > + *
> > + * Permission is hereby granted, free of charge, to any person obtaining a
> > + * copy of this software and associated documentation files (the "Software"),
> > + * to deal in the Software without restriction, including without limitation
> > + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
> > + * and/or sell copies of the Software, and to permit persons to whom the
> > + * Software is furnished to do so, subject to the following conditions:
> > + *
> > + * The above copyright notice and this permission notice (including the next
> > + * paragraph) shall be included in all copies or substantial portions of the
> > + * Software.
> > + *
> > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
> > + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> > + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
> > + * IN THE SOFTWARE.
> > + *
> > + * Authors:
> > + * Eric Anholt <eric at anholt.net>
> > + *
> > + */
> > +
> > +#ifndef IGT_MAP_H
> > +#define IGT_MAP_H
> > +
> > +#include <inttypes.h>
> > +
> > +/**
> > + * SECTION:igt_map
> > + * @short_description: a linear-reprobing hashmap implementation
> > + * @title: IGT Map
> > + * @include: igt_map.h
> > + *
> > + * Implements an open-addressing, linear-reprobing hash table.
> > + *
> > + * For more information, see:
> > + * http://cgit.freedesktop.org/~anholt/hash_table/tree/README
> > + *
> > + * Example usage:
> > + *
> > + *|[<!-- language="C" -->
> > + * #define GOLDEN_RATIO_PRIME_32 0x9e370001UL
> > + *
> > + * static inline uint32_t hash_identifier(const void *val)
> > + * {
> > + * uint32_t hash = *(uint32_t *) val;
> > + *
> > + * hash = hash * GOLDEN_RATIO_PRIME_32;
> > + * return hash;
> > + * }
> > + *
> > + * static int equal_identifiers(const void *a, const void *b)
> > + * {
> > + * uint32_t *key1 = (uint32_t *) a, *key2 = (uint32_t *) b;
> > + *
> > + * return *key1 == *key2;
> > + * }
> > + *
> > + * static void free_func(struct igt_map_entry *entry)
> > + * {
> > + * free(entry->data);
> > + * }
> > + *
> > + * struct igt_map *map;
> > + *
> > + * struct record {
> > + * int foo;
> > + * uint32_t unique_identifier;
> > + * };
> > + *
> > + * struct record *r1, r2, *record;
> > + * struct igt_map_entry *entry;
> > + *
> > + * r1 = malloc(sizeof(struct record));
> > + * map = igt_map_create(hash_identifier, equal_identifiers);
> > + * igt_map_insert(map, &r1->unique_identifier, r1);
> > + * igt_map_insert(map, &r2.unique_identifier, &r2);
> > + *
> > + * igt_map_foreach(map, entry) {
> > + * record = entry->data;
> > + * printf("key: %u, foo: %d\n", *(uint32_t *) entry->key, record->foo);
> > + * }
> > + *
> > + * record = igt_map_search(map, &r1->unique_identifier);
> > + * entry = igt_map_search_entry(map, &r2.unique_identifier);
> > + *
> > + * igt_map_remove(map, &r1->unique_identifier, free_func);
> > + * igt_map_remove_entry(map, entry);
> > + *
> > + * igt_map_destroy(map, NULL);
> > + * ]|
> > + */
> > +
> > +struct igt_map_entry {
> > + uint32_t hash;
> > + const void *key;
> > + void *data;
> > +};
> > +
> > +struct igt_map {
> > + struct igt_map_entry *table;
> > + uint32_t (*hash_function)(const void *key);
> > + int (*key_equals_function)(const void *a, const void *b);
> > + uint32_t size;
> > + uint32_t rehash;
> > + uint32_t max_entries;
> > + uint32_t size_index;
> > + uint32_t entries;
> > + uint32_t deleted_entries;
> > +};
> > +
> > +struct igt_map *
> > +igt_map_create(uint32_t (*hash_function)(const void *key),
> > + int (*key_equals_function)(const void *a, const void *b));
> > +void
> > +igt_map_destroy(struct igt_map *map,
> > + void (*delete_function)(struct igt_map_entry *entry));
> > +
> > +struct igt_map_entry *
> > +igt_map_insert(struct igt_map *map, const void *key, void *data);
> > +
> > +void *
> > +igt_map_search(struct igt_map *map, const void *key);
> > +
> > +struct igt_map_entry *
> > +igt_map_search_entry(struct igt_map *map, const void *key);
> > +
> > +void
> > +igt_map_remove(struct igt_map *map, const void *key,
> > + void (*delete_function)(struct igt_map_entry *entry));
> > +
> > +void
> > +igt_map_remove_entry(struct igt_map *map, struct igt_map_entry *entry);
> > +
> > +struct igt_map_entry *
> > +igt_map_next_entry(struct igt_map *map, struct igt_map_entry *entry);
> > +
> > +struct igt_map_entry *
> > +igt_map_random_entry(struct igt_map *map,
> > + int (*predicate)(struct igt_map_entry *entry));
> > +/**
> > + * igt_map_foreach
> > + * @map: igt_map pointer
> > + * @entry: igt_map_entry pointer
> > + *
> > + * Macro is a loop, which iterates through each map entry. Inside a
> > + * loop block current element is accessible by the @entry pointer.
> > + *
> > + * This foreach function is safe against deletion (which just replaces
> > + * an entry's data with the deleted marker), but not against insertion
> > + * (which may rehash the table, making entry a dangling pointer).
> > + */
> > +#define igt_map_foreach(map, entry) \
> > + for (entry = igt_map_next_entry(map, NULL); \
> > + entry != NULL; \
> > + entry = igt_map_next_entry(map, entry))
> > +
> > +/* Alternate interfaces to reduce repeated calls to hash function. */
> > +struct igt_map_entry *
> > +igt_map_search_pre_hashed(struct igt_map *map,
> > + uint32_t hash,
> > + const void *key);
> > +
> > +struct igt_map_entry *
> > +igt_map_insert_pre_hashed(struct igt_map *map,
> > + uint32_t hash,
> > + const void *key, void *data);
> > +
> > +#endif
> > 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
> >
More information about the igt-dev
mailing list