From cd7b005519ade8ab6c97fcb21590b71b7d1be6e3 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 11:54:46 +0200 Subject: Adding upstream version 0.8.0. Signed-off-by: Daniel Baumann --- third-party/tommyds/tommyhashtbl.c | 142 +++++++++++++++++++++++++++++++++++++ 1 file changed, 142 insertions(+) create mode 100644 third-party/tommyds/tommyhashtbl.c (limited to 'third-party/tommyds/tommyhashtbl.c') diff --git a/third-party/tommyds/tommyhashtbl.c b/third-party/tommyds/tommyhashtbl.c new file mode 100644 index 0000000..007b8ec --- /dev/null +++ b/third-party/tommyds/tommyhashtbl.c @@ -0,0 +1,142 @@ +/* + * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "tommyhashtbl.h" +#include "tommylist.h" + +#include /* for memset */ + +/******************************************************************************/ +/* hashtable */ + +void tommy_hashtable_init(tommy_hashtable* hashtable, tommy_count_t bucket_max) +{ + if (bucket_max < 16) + bucket_max = 16; + else + bucket_max = tommy_roundup_pow2_u32(bucket_max); + + hashtable->bucket_max = bucket_max; + hashtable->bucket_mask = hashtable->bucket_max - 1; + + /* initialize the vector using malloc()+memset() instead of calloc() */ + /* to ensure that all the memory in really allocated immediately */ + /* by the OS, and not deferred at later time. */ + /* this improves performance, because we start with a fully initialized hashtable. */ + hashtable->bucket = tommy_cast(tommy_hashtable_node**, tommy_malloc(hashtable->bucket_max * sizeof(tommy_hashtable_node*))); + memset(hashtable->bucket, 0, hashtable->bucket_max * sizeof(tommy_hashtable_node*)); + + hashtable->count = 0; +} + +void tommy_hashtable_done(tommy_hashtable* hashtable) +{ + tommy_free(hashtable->bucket); +} + +void tommy_hashtable_insert(tommy_hashtable* hashtable, tommy_hashtable_node* node, void* data, tommy_hash_t hash) +{ + tommy_count_t pos = hash & hashtable->bucket_mask; + + tommy_list_insert_tail(&hashtable->bucket[pos], node, data); + + node->key = hash; + + ++hashtable->count; +} + +void* tommy_hashtable_remove_existing(tommy_hashtable* hashtable, tommy_hashtable_node* node) +{ + tommy_count_t pos = node->key & hashtable->bucket_mask; + + tommy_list_remove_existing(&hashtable->bucket[pos], node); + + --hashtable->count; + + return node->data; +} + +void* tommy_hashtable_remove(tommy_hashtable* hashtable, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash) +{ + tommy_count_t pos = hash & hashtable->bucket_mask; + tommy_hashtable_node* node = hashtable->bucket[pos]; + + while (node) { + /* we first check if the hash matches, as in the same bucket we may have multiples hash values */ + if (node->key == hash && cmp(cmp_arg, node->data) == 0) { + tommy_list_remove_existing(&hashtable->bucket[pos], node); + + --hashtable->count; + + return node->data; + } + node = node->next; + } + + return 0; +} + +void tommy_hashtable_foreach(tommy_hashtable* hashtable, tommy_foreach_func* func) +{ + tommy_count_t bucket_max = hashtable->bucket_max; + tommy_hashtable_node** bucket = hashtable->bucket; + tommy_count_t pos; + + for (pos = 0; pos < bucket_max; ++pos) { + tommy_hashtable_node* node = bucket[pos]; + + while (node) { + void* data = node->data; + node = node->next; + func(data); + } + } +} + +void tommy_hashtable_foreach_arg(tommy_hashtable* hashtable, tommy_foreach_arg_func* func, void* arg) +{ + tommy_count_t bucket_max = hashtable->bucket_max; + tommy_hashtable_node** bucket = hashtable->bucket; + tommy_count_t pos; + + for (pos = 0; pos < bucket_max; ++pos) { + tommy_hashtable_node* node = bucket[pos]; + + while (node) { + void* data = node->data; + node = node->next; + func(arg, data); + } + } +} + +tommy_size_t tommy_hashtable_memory_usage(tommy_hashtable* hashtable) +{ + return hashtable->bucket_max * (tommy_size_t)sizeof(hashtable->bucket[0]) + + tommy_hashtable_count(hashtable) * (tommy_size_t)sizeof(tommy_hashtable_node); +} + -- cgit v1.2.3