From 30f41c02aec763d32e62351452da9ef582bc3472 Mon Sep 17 00:00:00 2001 From: 3gg <3gg@shellblade.net> Date: Fri, 6 Mar 2026 13:30:59 -0800 Subject: Move contrib libraries to contrib repo --- contrib/SDL-3.2.8/src/SDL_hashtable.c | 543 ---------------------------------- 1 file changed, 543 deletions(-) delete mode 100644 contrib/SDL-3.2.8/src/SDL_hashtable.c (limited to 'contrib/SDL-3.2.8/src/SDL_hashtable.c') diff --git a/contrib/SDL-3.2.8/src/SDL_hashtable.c b/contrib/SDL-3.2.8/src/SDL_hashtable.c deleted file mode 100644 index 3124b41..0000000 --- a/contrib/SDL-3.2.8/src/SDL_hashtable.c +++ /dev/null @@ -1,543 +0,0 @@ -/* - Simple DirectMedia Layer - Copyright (C) 1997-2025 Sam Lantinga - - This software is provided 'as-is', without any express or implied - warranty. In no event will the authors be held liable for any damages - arising from the use of this software. - - Permission is granted to anyone to use this software for any purpose, - including commercial applications, and to alter it and redistribute it - freely, subject to the following restrictions: - - 1. The origin of this software must not be misrepresented; you must not - claim that you wrote the original software. If you use this software - in a product, an acknowledgment in the product documentation would be - appreciated but is not required. - 2. Altered source versions must be plainly marked as such, and must not be - misrepresented as being the original software. - 3. This notice may not be removed or altered from any source distribution. -*/ -#include "SDL_internal.h" - -typedef struct SDL_HashItem -{ - // TODO: Splitting off values into a separate array might be more cache-friendly - const void *key; - const void *value; - Uint32 hash; - Uint32 probe_len : 31; - Uint32 live : 1; -} SDL_HashItem; - -// Must be a power of 2 >= sizeof(SDL_HashItem) -#define MAX_HASHITEM_SIZEOF 32u -SDL_COMPILE_TIME_ASSERT(sizeof_SDL_HashItem, sizeof(SDL_HashItem) <= MAX_HASHITEM_SIZEOF); - -// Anything larger than this will cause integer overflows -#define MAX_HASHTABLE_SIZE (0x80000000u / (MAX_HASHITEM_SIZEOF)) - -struct SDL_HashTable -{ - SDL_RWLock *lock; // NULL if not created threadsafe - SDL_HashItem *table; - SDL_HashCallback hash; - SDL_HashKeyMatchCallback keymatch; - SDL_HashDestroyCallback destroy; - void *userdata; - Uint32 hash_mask; - Uint32 max_probe_len; - Uint32 num_occupied_slots; -}; - - -static Uint32 CalculateHashBucketsFromEstimate(int estimated_capacity) -{ - if (estimated_capacity <= 0) { - return 4; // start small, grow as necessary. - } - - const Uint32 estimated32 = (Uint32) estimated_capacity; - Uint32 buckets = ((Uint32) 1) << SDL_MostSignificantBitIndex32(estimated32); - if (!SDL_HasExactlyOneBitSet32(estimated32)) { - buckets <<= 1; // need next power of two up to fit overflow capacity bits. - } - - return SDL_min(buckets, MAX_HASHTABLE_SIZE); -} - -SDL_HashTable *SDL_CreateHashTable(int estimated_capacity, bool threadsafe, SDL_HashCallback hash, - SDL_HashKeyMatchCallback keymatch, - SDL_HashDestroyCallback destroy, void *userdata) -{ - const Uint32 num_buckets = CalculateHashBucketsFromEstimate(estimated_capacity); - SDL_HashTable *table = (SDL_HashTable *)SDL_calloc(1, sizeof(SDL_HashTable)); - if (!table) { - return NULL; - } - - if (threadsafe) { - table->lock = SDL_CreateRWLock(); - if (!table->lock) { - SDL_DestroyHashTable(table); - return NULL; - } - } - - table->table = (SDL_HashItem *)SDL_calloc(num_buckets, sizeof(SDL_HashItem)); - if (!table->table) { - SDL_DestroyHashTable(table); - return NULL; - } - - table->hash_mask = num_buckets - 1; - table->userdata = userdata; - table->hash = hash; - table->keymatch = keymatch; - table->destroy = destroy; - return table; -} - -static SDL_INLINE Uint32 calc_hash(const SDL_HashTable *table, const void *key) -{ - const Uint32 BitMixer = 0x9E3779B1u; - return table->hash(table->userdata, key) * BitMixer; -} - -static SDL_INLINE Uint32 get_probe_length(Uint32 zero_idx, Uint32 actual_idx, Uint32 num_buckets) -{ - // returns the probe sequence length from zero_idx to actual_idx - if (actual_idx < zero_idx) { - return num_buckets - zero_idx + actual_idx; - } - - return actual_idx - zero_idx; -} - -static SDL_HashItem *find_item(const SDL_HashTable *ht, const void *key, Uint32 hash, Uint32 *i, Uint32 *probe_len) -{ - Uint32 hash_mask = ht->hash_mask; - Uint32 max_probe_len = ht->max_probe_len; - - SDL_HashItem *table = ht->table; - - while (true) { - SDL_HashItem *item = table + *i; - Uint32 item_hash = item->hash; - - if (!item->live) { - return NULL; - } - - if (item_hash == hash && ht->keymatch(ht->userdata, item->key, key)) { - return item; - } - - Uint32 item_probe_len = item->probe_len; - SDL_assert(item_probe_len == get_probe_length(item_hash & hash_mask, (Uint32)(item - table), hash_mask + 1)); - - if (*probe_len > item_probe_len) { - return NULL; - } - - if (++*probe_len > max_probe_len) { - return NULL; - } - - *i = (*i + 1) & hash_mask; - } -} - -static SDL_HashItem *find_first_item(const SDL_HashTable *ht, const void *key, Uint32 hash) -{ - Uint32 i = hash & ht->hash_mask; - Uint32 probe_len = 0; - return find_item(ht, key, hash, &i, &probe_len); -} - -static SDL_HashItem *insert_item(SDL_HashItem *item_to_insert, SDL_HashItem *table, Uint32 hash_mask, Uint32 *max_probe_len_ptr) -{ - const Uint32 num_buckets = hash_mask + 1; - Uint32 idx = item_to_insert->hash & hash_mask; - SDL_HashItem *target = NULL; - SDL_HashItem temp_item; - - while (true) { - SDL_HashItem *candidate = table + idx; - - if (!candidate->live) { - // Found an empty slot. Put it here and we're done. - *candidate = *item_to_insert; - - if (target == NULL) { - target = candidate; - } - - const Uint32 probe_len = get_probe_length(candidate->hash & hash_mask, idx, num_buckets); - candidate->probe_len = probe_len; - - if (*max_probe_len_ptr < probe_len) { - *max_probe_len_ptr = probe_len; - } - - break; - } - - const Uint32 candidate_probe_len = candidate->probe_len; - SDL_assert(candidate_probe_len == get_probe_length(candidate->hash & hash_mask, idx, num_buckets)); - const Uint32 new_probe_len = get_probe_length(item_to_insert->hash & hash_mask, idx, num_buckets); - - if (candidate_probe_len < new_probe_len) { - // Robin Hood hashing: the item at idx has a better probe length than our item would at this position. - // Evict it and put our item in its place, then continue looking for a new spot for the displaced item. - // This algorithm significantly reduces clustering in the table, making lookups take very few probes. - - temp_item = *candidate; - *candidate = *item_to_insert; - - if (target == NULL) { - target = candidate; - } - - *item_to_insert = temp_item; - - SDL_assert(new_probe_len == get_probe_length(candidate->hash & hash_mask, idx, num_buckets)); - candidate->probe_len = new_probe_len; - - if (*max_probe_len_ptr < new_probe_len) { - *max_probe_len_ptr = new_probe_len; - } - } - - idx = (idx + 1) & hash_mask; - } - - return target; -} - -static void delete_item(SDL_HashTable *ht, SDL_HashItem *item) -{ - const Uint32 hash_mask = ht->hash_mask; - SDL_HashItem *table = ht->table; - - if (ht->destroy) { - ht->destroy(ht->userdata, item->key, item->value); - } - - SDL_assert(ht->num_occupied_slots > 0); - ht->num_occupied_slots--; - - Uint32 idx = (Uint32)(item - ht->table); - - while (true) { - idx = (idx + 1) & hash_mask; - SDL_HashItem *next_item = table + idx; - - if (next_item->probe_len < 1) { - SDL_zerop(item); - return; - } - - *item = *next_item; - item->probe_len -= 1; - SDL_assert(item->probe_len < ht->max_probe_len); - item = next_item; - } -} - -static bool resize(SDL_HashTable *ht, Uint32 new_size) -{ - const Uint32 new_hash_mask = new_size - 1; - SDL_HashItem *new_table = SDL_calloc(new_size, sizeof(*new_table)); - - if (!new_table) { - return false; - } - - SDL_HashItem *old_table = ht->table; - const Uint32 old_size = ht->hash_mask + 1; - - ht->max_probe_len = 0; - ht->hash_mask = new_hash_mask; - ht->table = new_table; - - for (Uint32 i = 0; i < old_size; ++i) { - SDL_HashItem *item = old_table + i; - if (item->live) { - insert_item(item, new_table, new_hash_mask, &ht->max_probe_len); - } - } - - SDL_free(old_table); - return true; -} - -static bool maybe_resize(SDL_HashTable *ht) -{ - const Uint32 capacity = ht->hash_mask + 1; - - if (capacity >= MAX_HASHTABLE_SIZE) { - return false; - } - - const Uint32 max_load_factor = 217; // range: 0-255; 217 is roughly 85% - const Uint32 resize_threshold = (Uint32)((max_load_factor * (Uint64)capacity) >> 8); - - if (ht->num_occupied_slots > resize_threshold) { - return resize(ht, capacity * 2); - } - - return true; -} - -bool SDL_InsertIntoHashTable(SDL_HashTable *table, const void *key, const void *value, bool replace) -{ - if (!table) { - return SDL_InvalidParamError("table"); - } - - bool result = false; - - SDL_LockRWLockForWriting(table->lock); - - const Uint32 hash = calc_hash(table, key); - SDL_HashItem *item = find_first_item(table, key, hash); - bool do_insert = true; - - if (item) { - if (replace) { - delete_item(table, item); - } else { - SDL_SetError("key already exists and replace is disabled"); - do_insert = false; - } - } - - if (do_insert) { - SDL_HashItem new_item; - new_item.key = key; - new_item.value = value; - new_item.hash = hash; - new_item.live = true; - new_item.probe_len = 0; - - table->num_occupied_slots++; - - if (!maybe_resize(table)) { - table->num_occupied_slots--; - } else { - // This never returns NULL - insert_item(&new_item, table->table, table->hash_mask, &table->max_probe_len); - result = true; - } - } - - SDL_UnlockRWLock(table->lock); - return result; -} - -bool SDL_FindInHashTable(const SDL_HashTable *table, const void *key, const void **value) -{ - if (!table) { - if (value) { - *value = NULL; - } - return SDL_InvalidParamError("table"); - } - - SDL_LockRWLockForReading(table->lock); - - bool result = false; - const Uint32 hash = calc_hash(table, key); - SDL_HashItem *i = find_first_item(table, key, hash); - if (i) { - if (value) { - *value = i->value; - } - result = true; - } - - SDL_UnlockRWLock(table->lock); - - return result; -} - -bool SDL_RemoveFromHashTable(SDL_HashTable *table, const void *key) -{ - if (!table) { - return SDL_InvalidParamError("table"); - } - - SDL_LockRWLockForWriting(table->lock); - - bool result = false; - const Uint32 hash = calc_hash(table, key); - SDL_HashItem *item = find_first_item(table, key, hash); - if (item) { - delete_item(table, item); - result = true; - } - - SDL_UnlockRWLock(table->lock); - return result; -} - -bool SDL_IterateHashTable(const SDL_HashTable *table, SDL_HashTableIterateCallback callback, void *userdata) -{ - if (!table) { - return SDL_InvalidParamError("table"); - } else if (!callback) { - return SDL_InvalidParamError("callback"); - } - - SDL_LockRWLockForReading(table->lock); - SDL_HashItem *end = table->table + (table->hash_mask + 1); - Uint32 num_iterated = 0; - - for (SDL_HashItem *item = table->table; item < end; item++) { - if (item->live) { - if (!callback(userdata, table, item->key, item->value)) { - break; // callback requested iteration stop. - } else if (++num_iterated >= table->num_occupied_slots) { - break; // we can drop out early because we've seen all the live items. - } - } - } - - SDL_UnlockRWLock(table->lock); - return true; -} - -bool SDL_HashTableEmpty(SDL_HashTable *table) -{ - if (!table) { - return SDL_InvalidParamError("table"); - } - - SDL_LockRWLockForReading(table->lock); - const bool retval = (table->num_occupied_slots == 0); - SDL_UnlockRWLock(table->lock); - return retval; -} - - -static void destroy_all(SDL_HashTable *table) -{ - SDL_HashDestroyCallback destroy = table->destroy; - if (destroy) { - void *userdata = table->userdata; - SDL_HashItem *end = table->table + (table->hash_mask + 1); - for (SDL_HashItem *i = table->table; i < end; ++i) { - if (i->live) { - i->live = false; - destroy(userdata, i->key, i->value); - } - } - } -} - -void SDL_ClearHashTable(SDL_HashTable *table) -{ - if (table) { - SDL_LockRWLockForWriting(table->lock); - { - destroy_all(table); - SDL_memset(table->table, 0, sizeof(*table->table) * (table->hash_mask + 1)); - table->num_occupied_slots = 0; - } - SDL_UnlockRWLock(table->lock); - } -} - -void SDL_DestroyHashTable(SDL_HashTable *table) -{ - if (table) { - destroy_all(table); - if (table->lock) { - SDL_DestroyRWLock(table->lock); - } - SDL_free(table->table); - SDL_free(table); - } -} - -// this is djb's xor hashing function. -static SDL_INLINE Uint32 hash_string_djbxor(const char *str, size_t len) -{ - Uint32 hash = 5381; - while (len--) { - hash = ((hash << 5) + hash) ^ *(str++); - } - return hash; -} - -Uint32 SDL_HashPointer(void *unused, const void *key) -{ - (void)unused; - return SDL_murmur3_32(&key, sizeof(key), 0); -} - -bool SDL_KeyMatchPointer(void *unused, const void *a, const void *b) -{ - (void)unused; - return (a == b); -} - -Uint32 SDL_HashString(void *unused, const void *key) -{ - (void)unused; - const char *str = (const char *)key; - return hash_string_djbxor(str, SDL_strlen(str)); -} - -bool SDL_KeyMatchString(void *unused, const void *a, const void *b) -{ - const char *a_string = (const char *)a; - const char *b_string = (const char *)b; - - (void)unused; - if (a == b) { - return true; // same pointer, must match. - } else if (!a || !b) { - return false; // one pointer is NULL (and first test shows they aren't the same pointer), must not match. - } else if (a_string[0] != b_string[0]) { - return false; // we know they don't match - } - return (SDL_strcmp(a_string, b_string) == 0); // Check against actual string contents. -} - -// We assume we can fit the ID in the key directly -SDL_COMPILE_TIME_ASSERT(SDL_HashID_KeySize, sizeof(Uint32) <= sizeof(const void *)); - -Uint32 SDL_HashID(void *unused, const void *key) -{ - (void)unused; - return (Uint32)(uintptr_t)key; -} - -bool SDL_KeyMatchID(void *unused, const void *a, const void *b) -{ - (void)unused; - return (a == b); -} - -void SDL_DestroyHashKeyAndValue(void *unused, const void *key, const void *value) -{ - (void)unused; - SDL_free((void *)key); - SDL_free((void *)value); -} - -void SDL_DestroyHashKey(void *unused, const void *key, const void *value) -{ - (void)value; - (void)unused; - SDL_free((void *)key); -} - -void SDL_DestroyHashValue(void *unused, const void *key, const void *value) -{ - (void)key; - (void)unused; - SDL_free((void *)value); -} -- cgit v1.2.3