From d611cd416fe262d74142bd8f9a3e0521024174af Mon Sep 17 00:00:00 2001
From: Sam Lantinga <[EMAIL REDACTED]>
Date: Mon, 17 Feb 2025 09:34:41 -0800
Subject: [PATCH] Updated hash table implementation to match SDL
Also redefine hash table functions so they don't collide with SDL when statically linking.
Fixes https://github.com/libsdl-org/SDL_ttf/issues/508
---
src/SDL_gpu_textengine.c | 8 +-
src/SDL_hashtable.c | 378 +++++++++-----------
src/SDL_hashtable.h | 634 +++++++++++++++++++++++++++++++---
src/SDL_hashtable_names.h | 38 ++
src/SDL_hashtable_ttf.c | 11 +-
src/SDL_renderer_textengine.c | 8 +-
src/SDL_surface_textengine.c | 8 +-
src/SDL_ttf.c | 72 ++--
8 files changed, 852 insertions(+), 305 deletions(-)
create mode 100644 src/SDL_hashtable_names.h
diff --git a/src/SDL_gpu_textengine.c b/src/SDL_gpu_textengine.c
index 580727df..9d3fe411 100644
--- a/src/SDL_gpu_textengine.c
+++ b/src/SDL_gpu_textengine.c
@@ -846,7 +846,7 @@ static TTF_GPUTextEngineFontData *CreateFontData(TTF_GPUTextEngineData *engineda
return NULL;
}
- if (!SDL_InsertIntoHashTable(enginedata->fonts, font, data)) {
+ if (!SDL_InsertIntoHashTable(enginedata->fonts, font, data, true)) {
DestroyFontData(data);
return NULL;
}
@@ -872,7 +872,7 @@ static void DestroyEngineData(TTF_GPUTextEngineData *data)
SDL_free(data);
}
-static void NukeFontData(const void *key, const void *value, void *unused)
+static void SDLCALL NukeFontData(void *unused, const void *key, const void *value)
{
TTF_GPUTextEngineFontData *data = (TTF_GPUTextEngineFontData *)value;
(void)key;
@@ -890,7 +890,7 @@ static TTF_GPUTextEngineData *CreateEngineData(SDL_GPUDevice *device, int atlas_
data->atlas_texture_size = atlas_texture_size;
data->winding = TTF_GPU_TEXTENGINE_WINDING_CLOCKWISE;
- data->fonts = SDL_CreateHashTable(NULL, 4, SDL_HashPointer, SDL_KeyMatchPointer, NukeFontData, false, false);
+ data->fonts = SDL_CreateHashTable(0, false, SDL_HashPointer, SDL_KeyMatchPointer, NukeFontData, NULL);
if (!data->fonts) {
DestroyEngineData(data);
return NULL;
@@ -914,7 +914,7 @@ static bool SDLCALL CreateText(void *userdata, TTF_Text *text)
return false;
}
} else if (font_generation != fontdata->generation) {
- SDL_EmptyHashTable(fontdata->glyphs);
+ SDL_ClearHashTable(fontdata->glyphs);
fontdata->generation = font_generation;
}
diff --git a/src/SDL_hashtable.c b/src/SDL_hashtable.c
index 8b1b8b93..3b10155e 100644
--- a/src/SDL_hashtable.c
+++ b/src/SDL_hashtable.c
@@ -21,10 +21,6 @@
#include <SDL3/SDL.h>
#include "SDL_hashtable.h"
-// XXX: We can't use SDL_assert here because it's going to call into hashtable code
-#include <assert.h>
-#define HT_ASSERT(x) assert(x)
-
typedef struct SDL_HashItem
{
// TODO: Splitting off values into a separate array might be more cache-friendly
@@ -44,47 +40,49 @@ SDL_COMPILE_TIME_ASSERT(sizeof_SDL_HashItem, sizeof(SDL_HashItem) <= MAX_HASHITE
struct SDL_HashTable
{
- SDL_RWLock *lock;
+ SDL_RWLock *lock; // NULL if not created threadsafe
SDL_HashItem *table;
- SDL_HashTable_HashFn hash;
- SDL_HashTable_KeyMatchFn keymatch;
- SDL_HashTable_NukeFn nuke;
- void *data;
+ SDL_HashCallback hash;
+ SDL_HashKeyMatchCallback keymatch;
+ SDL_HashDestroyCallback destroy;
+ void *userdata;
Uint32 hash_mask;
Uint32 max_probe_len;
Uint32 num_occupied_slots;
- bool stackable;
};
-SDL_HashTable *SDL_CreateHashTable(void *data,
- Uint32 num_buckets,
- SDL_HashTable_HashFn hashfn,
- SDL_HashTable_KeyMatchFn keymatchfn,
- SDL_HashTable_NukeFn nukefn,
- bool threadsafe,
- bool stackable)
-{
- SDL_HashTable *table;
- // num_buckets must be a power of two so we can derive the bucket index with just a bit-and.
- if ((num_buckets < 1) || !SDL_HasExactlyOneBitSet32(num_buckets)) {
- SDL_SetError("num_buckets must be a power of two");
- return NULL;
+static Uint32 CalculateHashBucketsFromEstimate(int estimated_capacity)
+{
+ if (estimated_capacity <= 0) {
+ return 4; // start small, grow as necessary.
}
- if (num_buckets > MAX_HASHTABLE_SIZE) {
- SDL_SetError("num_buckets is too large");
- return NULL;
+ 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.
}
- table = (SDL_HashTable *)SDL_calloc(1, sizeof(SDL_HashTable));
+ 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) {
- // Don't fail if we can't create a lock (single threaded environment?)
table->lock = SDL_CreateRWLock();
+ if (!table->lock) {
+ SDL_DestroyHashTable(table);
+ return NULL;
+ }
}
table->table = (SDL_HashItem *)SDL_calloc(num_buckets, sizeof(SDL_HashItem));
@@ -94,24 +92,22 @@ SDL_HashTable *SDL_CreateHashTable(void *data,
}
table->hash_mask = num_buckets - 1;
- table->stackable = stackable;
- table->data = data;
- table->hash = hashfn;
- table->keymatch = keymatchfn;
- table->nuke = nukefn;
+ 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(key, table->data) * BitMixer;
+ 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;
}
@@ -126,7 +122,7 @@ static SDL_HashItem *find_item(const SDL_HashTable *ht, const void *key, Uint32
SDL_HashItem *table = ht->table;
- for (;;) {
+ while (true) {
SDL_HashItem *item = table + *i;
Uint32 item_hash = item->hash;
@@ -134,12 +130,12 @@ static SDL_HashItem *find_item(const SDL_HashTable *ht, const void *key, Uint32
return NULL;
}
- if (item_hash == hash && ht->keymatch(item->key, key, ht->data)) {
+ if (item_hash == hash && ht->keymatch(ht->userdata, item->key, key)) {
return item;
}
Uint32 item_probe_len = item->probe_len;
- HT_ASSERT(item_probe_len == get_probe_length(item_hash & hash_mask, (Uint32)(item - table), hash_mask + 1));
+ 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;
@@ -162,23 +158,23 @@ static SDL_HashItem *find_first_item(const SDL_HashTable *ht, const void *key, U
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 temp_item, *target = NULL;
- Uint32 num_buckets = hash_mask + 1;
+ SDL_HashItem *target = NULL;
+ SDL_HashItem temp_item;
- for (;;) {
+ 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;
}
- Uint32 probe_len = get_probe_length(candidate->hash & hash_mask, idx, num_buckets);
+ 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) {
@@ -188,9 +184,9 @@ static SDL_HashItem *insert_item(SDL_HashItem *item_to_insert, SDL_HashItem *tab
break;
}
- Uint32 candidate_probe_len = candidate->probe_len;
- HT_ASSERT(candidate_probe_len == get_probe_length(candidate->hash & hash_mask, idx, num_buckets));
- Uint32 new_probe_len = get_probe_length(item_to_insert->hash & hash_mask, idx, num_buckets);
+ 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.
@@ -206,7 +202,7 @@ static SDL_HashItem *insert_item(SDL_HashItem *item_to_insert, SDL_HashItem *tab
*item_to_insert = temp_item;
- HT_ASSERT(new_probe_len == get_probe_length(candidate->hash & hash_mask, idx, num_buckets));
+ 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) {
@@ -222,17 +218,19 @@ static SDL_HashItem *insert_item(SDL_HashItem *item_to_insert, SDL_HashItem *tab
static void delete_item(SDL_HashTable *ht, SDL_HashItem *item)
{
- Uint32 hash_mask = ht->hash_mask;
+ const Uint32 hash_mask = ht->hash_mask;
SDL_HashItem *table = ht->table;
- if (ht->nuke) {
- ht->nuke(item->key, item->value, ht->data);
+ 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);
- for (;;) {
+ while (true) {
idx = (idx + 1) & hash_mask;
SDL_HashItem *next_item = table + idx;
@@ -243,22 +241,23 @@ static void delete_item(SDL_HashTable *ht, SDL_HashItem *item)
*item = *next_item;
item->probe_len -= 1;
- HT_ASSERT(item->probe_len < ht->max_probe_len);
+ SDL_assert(item->probe_len < ht->max_probe_len);
item = next_item;
}
}
static bool resize(SDL_HashTable *ht, Uint32 new_size)
{
- SDL_HashItem *old_table = ht->table;
- Uint32 old_size = ht->hash_mask + 1;
- Uint32 new_hash_mask = new_size - 1;
+ 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;
@@ -276,14 +275,14 @@ static bool resize(SDL_HashTable *ht, Uint32 new_size)
static bool maybe_resize(SDL_HashTable *ht)
{
- Uint32 capacity = ht->hash_mask + 1;
+ const Uint32 capacity = ht->hash_mask + 1;
if (capacity >= MAX_HASHTABLE_SIZE) {
return false;
}
- Uint32 max_load_factor = 217; // range: 0-255; 217 is roughly 85%
- Uint32 resize_threshold = (Uint32)((max_load_factor * (Uint64)capacity) >> 8);
+ 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);
@@ -292,72 +291,66 @@ static bool maybe_resize(SDL_HashTable *ht)
return true;
}
-bool SDL_InsertIntoHashTable(SDL_HashTable *table, const void *key, const void *value)
+bool SDL_InsertIntoHashTable(SDL_HashTable *table, const void *key, const void *value, bool replace)
{
- SDL_HashItem *item;
- Uint32 hash;
- bool result = false;
-
if (!table) {
- return false;
+ return SDL_InvalidParamError("table");
}
- if (table->lock) {
- SDL_LockRWLockForWriting(table->lock);
- }
+ bool result = false;
- hash = calc_hash(table, key);
- item = find_first_item(table, key, hash);
+ SDL_LockRWLockForWriting(table->lock);
- if (item && !table->stackable) {
- // Allow overwrites, this might have been inserted on another thread
- delete_item(table, item);
+ 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;
+ }
}
- 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;
+ 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++;
+ table->num_occupied_slots++;
- if (!maybe_resize(table)) {
- table->num_occupied_slots--;
- goto done;
+ 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;
+ }
}
- // This never returns NULL
- insert_item(&new_item, table->table, table->hash_mask, &table->max_probe_len);
- result = true;
-
-done:
- if (table->lock) {
- SDL_UnlockRWLock(table->lock);
- }
+ SDL_UnlockRWLock(table->lock);
return result;
}
bool SDL_FindInHashTable(const SDL_HashTable *table, const void *key, const void **value)
{
- Uint32 hash;
- SDL_HashItem *i;
- bool result = false;
-
if (!table) {
if (value) {
*value = NULL;
}
- return false;
+ return SDL_InvalidParamError("table");
}
- if (table->lock) {
- SDL_LockRWLockForReading(table->lock);
- }
+ SDL_LockRWLockForReading(table->lock);
- hash = calc_hash(table, key);
- i = find_first_item(table, key, hash);
+ 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;
@@ -365,156 +358,91 @@ bool SDL_FindInHashTable(const SDL_HashTable *table, const void *key, const void
result = true;
}
- if (table->lock) {
- SDL_UnlockRWLock(table->lock);
- }
+ SDL_UnlockRWLock(table->lock);
+
return result;
}
bool SDL_RemoveFromHashTable(SDL_HashTable *table, const void *key)
{
- Uint32 hash;
- SDL_HashItem *item;
- bool result = false;
-
if (!table) {
- return false;
+ return SDL_InvalidParamError("table");
}
- if (table->lock) {
- SDL_LockRWLockForWriting(table->lock);
- }
-
- // FIXME: what to do for stacking hashtables?
- // The original code removes just one item.
- // This hashtable happens to preserve the insertion order of multi-value keys,
- // so deleting the first one will always delete the least-recently inserted one.
- // But maybe it makes more sense to remove all matching items?
+ SDL_LockRWLockForWriting(table->lock);
- hash = calc_hash(table, key);
- item = find_first_item(table, key, hash);
- if (!item) {
- goto done;
+ 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;
}
- delete_item(table, item);
- result = true;
-
-done:
- if (table->lock) {
- SDL_UnlockRWLock(table->lock);
- }
+ SDL_UnlockRWLock(table->lock);
return result;
}
-bool SDL_IterateHashTableKey(const SDL_HashTable *table, const void *key, const void **_value, void **iter)
+bool SDL_IterateHashTable(const SDL_HashTable *table, SDL_HashTableIterateCallback callback, void *userdata)
{
- SDL_HashItem *item = (SDL_HashItem *)*iter;
-
if (!table) {
- return false;
+ return SDL_InvalidParamError("table");
+ } else if (!callback) {
+ return SDL_InvalidParamError("callback");
}
- Uint32 i, probe_len, hash;
-
- if (item) {
- HT_ASSERT(item >= table->table);
- HT_ASSERT(item < table->table + (table->hash_mask + 1));
-
- hash = item->hash;
- probe_len = item->probe_len + 1;
- i = ((Uint32)(item - table->table) + 1) & table->hash_mask;
- item = table->table + i;
- } else {
- hash = calc_hash(table, key);
- i = hash & table->hash_mask;
- probe_len = 0;
- }
-
- item = find_item(table, key, hash, &i, &probe_len);
+ SDL_LockRWLockForReading(table->lock);
+ SDL_HashItem *end = table->table + (table->hash_mask + 1);
+ Uint32 num_iterated = 0;
- if (!item) {
- *_value = NULL;
- return false;
+ 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.
+ }
+ }
}
- *_value = item->value;
- *iter = item;
-
+ SDL_UnlockRWLock(table->lock);
return true;
}
-bool SDL_IterateHashTable(const SDL_HashTable *table, const void **_key, const void **_value, void **iter)
+bool SDL_HashTableEmpty(SDL_HashTable *table)
{
- SDL_HashItem *item = (SDL_HashItem *)*iter;
-
if (!table) {
- return false;
+ return SDL_InvalidParamError("table");
}
- if (!item) {
- item = table->table;
- } else {
- item++;
- }
-
- HT_ASSERT(item >= table->table);
- SDL_HashItem *end = table->table + (table->hash_mask + 1);
-
- while (item < end && !item->live) {
- ++item;
- }
-
- HT_ASSERT(item <= end);
-
- if (item == end) {
- if (_key) {
- *_key = NULL;
- }
- if (_value) {
- *_value = NULL;
- }
- return false;
- }
-
- if (_key) {
- *_key = item->key;
- }
- if (_value) {
- *_value = item->value;
- }
- *iter = item;
-
- return true;
+ SDL_LockRWLockForReading(table->lock);
+ const bool retval = (table->num_occupied_slots == 0);
+ SDL_UnlockRWLock(table->lock);
+ return retval;
}
-bool SDL_HashTableEmpty(SDL_HashTable *table)
-{
- return !(table && table->num_occupied_slots);
-}
-static void nuke_all(SDL_HashTable *table)
+static void destroy_all(SDL_HashTable *table)
{
- void *data = table->data;
- SDL_HashItem *end = table->table + (table->hash_mask + 1);
- SDL_HashItem *i;
-
- for (i = table->table; i < end; ++i) {
- if (i->live) {
- table->nuke(i->key, i->value, data);
+ 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_EmptyHashTable(SDL_HashTable *table)
+void SDL_ClearHashTable(SDL_HashTable *table)
{
if (table) {
SDL_LockRWLockForWriting(table->lock);
{
- if (table->nuke) {
- nuke_all(table);
- }
-
+ destroy_all(table);
SDL_memset(table->table, 0, sizeof(*table->table) * (table->hash_mask + 1));
table->num_occupied_slots = 0;
}
@@ -525,9 +453,10 @@ void SDL_EmptyHashTable(SDL_HashTable *table)
void SDL_DestroyHashTable(SDL_HashTable *table)
{
if (table) {
- SDL_EmptyHashTable(table);
-
- SDL_DestroyRWLock(table->lock);
+ destroy_all(table);
+ if (table->lock) {
+ SDL_DestroyRWLock(table->lock);
+ }
SDL_free(table->table);
SDL_free(table);
}
@@ -543,26 +472,26 @@ static SDL_INLINE Uint32 hash_string_djbxor(const char *str, size_t len)
return hash;
}
-Uint32 SDL_HashPointer(const void *key, void *unused)
+Uint32 SDL_HashPointer(void *unused, const void *key)
{
(void)unused;
return SDL_murmur3_32(&key, sizeof(key), 0);
}
-bool SDL_KeyMatchPointer(const void *a, const void *b, void *unused)
+bool SDL_KeyMatchPointer(void *unused, const void *a, const void *b)
{
(void)unused;
return (a == b);
}
-Uint32 SDL_HashString(const void *key, void *unused)
+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(const void *a, const void *b, void *unused)
+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;
@@ -581,26 +510,33 @@ bool SDL_KeyMatchString(const void *a, const void *b, void *unused)
// 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(const void *key, void *unused)
+Uint32 SDL_HashID(void *unused, const void *key)
{
(void)unused;
return (Uint32)(uintptr_t)key;
}
-bool SDL_KeyMatchID(const void *a, const void *b, void *unused)
+bool SDL_KeyMatchID(void *unused, const void *a, const void *b)
{
(void)unused;
return (a == b);
}
-void SDL_NukeFreeKey(const void *key, const void *value, void *unused)
+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_NukeFreeValue(const void *key, const void *value, void *unused)
+void SDL_DestroyHashValue(void *unused, const void *key, const void *value)
{
(void)key;
(void)unused;
diff --git a/src/SDL_hashtable.h b/src/SDL_hashtable.h
index 5983b8d3..76c4c741 100644
--- a/src/SDL_hashtable.h
+++ b/src/SDL_hashtable.h
@@ -18,61 +18,617 @@
misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/
+#include "SDL_hashtable_names.h"
+
+/* this is over-documented because it was almost a public API. Leaving the
+ full docs here in case it _does_ become public some day. */
+
+/* WIKI CATEGORY: HashTable */
+
+/**
+ * # CategoryHashTable
+ *
+ * SDL offers a hash table implementation, as a convenience for C code that
+ * needs efficient organization and access of arbitrary data.
+ *
+ * Hash tables are a popular data structure, designed to make it quick to
+ * store and look up arbitrary data. Data is stored with an associated "key."
+ * While one would look up an element of an array with an index, a hash table
+ * uses a unique key to find an element later.
+ *
+ * A key can be anything, as long as its unique and in a format that the table
+ * understands. For example, it's popular to use strings as keys: the key
+ * might be a username, and it is used to lookup account information for that
+ * user, etc.
+ *
+ * Hash tables are named because they "hash" their keys down into simple
+ * integers that can be used to efficiently organize and access the associated
+ * data.
+ *
+ * As this is a C API, there is one generic interface that is intended to work
+ * with different data types. This can be a little awkward to set up, but is
+ * easy to use after that.
+ *
+ * Hashtables are generated by a call to SDL_CreateHashTable(). This function
+ * requires several callbacks to be provided (for hashing keys, comparing
+ * entries, and cleaning up entries when removed). These are necessary to
+ * allow the hash to manage any arbitrary data type.
+ *
+ * Once a hash table is created, the common tasks are inserting data into the
+ * table, (SDL_InsertIntoHashTable), looking up previously inserted data
+ * (SDL_FindInHashTable), and removing data (SDL_RemoveFromHashTable and
+ * SDL_ClearHashTable). Less common but still useful is the ability to
+ * iterate through all the items in the table (SDL_IterateHashTable).
+ *
+ * The underlying hash table implementation is always subject to change, but
+ * at the time of writing, it uses open addressing and Robin Hood hashing.
+ * The technical details are explained [here](https://github.com/libsdl-org/SDL/pull/10897).
+ *
+ * Hashtables keep an SDL_RWLock internally, so multiple threads can perform
+ * hash lookups in parallel, while changes to the table will safely serialize
+ * access between threads.
+ *
+ * SDL provides a layer on top of this hash table implementation that might be
+ * more pleasant to use. SDL_PropertiesID maps a string to arbitrary data of
+ * various types in the same table, which could be both easier to use and more
+ * flexible. Refer to [CategoryProperties](CategoryProperties) for details.
+ */
+
#ifndef SDL_hashtable_h_
#define SDL_hashtable_h_
-// this is not (currently) a public API. But maybe it should be!
+#include <SDL3/SDL_stdinc.h>
-struct SDL_HashTable;
+#include <SDL3/SDL_begin_code.h>
+/* Set up for C function definitions, even when using C++ */
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * The opaque type that represents a hash table.
+ *
+ * This is hidden behind an opaque pointer because not only does the table
+ * need to store arbitrary data types, but the hash table implementation may
+ * change in the future.
+ *
+ * \since This struct is available since SDL 3.4.0.
+ *
+ * \sa SDL_CreateHashTable
+ */
typedef struct SDL_HashTable SDL_HashTable;
-typedef Uint32 (*SDL_HashTable_HashFn)(const void *key, void *data);
-typedef bool (*SDL_HashTable_KeyMatchFn)(const void *a, const void *b, void *data);
-typedef void (*SDL_HashTable_NukeFn)(const void *key, const void *value, void *data);
-
-extern SDL_HashTable *SDL_CreateHashTable(void *data,
- Uint32 num_buckets,
- SDL_HashTable_HashFn hashfn,
- SDL_HashTable_KeyMatchFn keymatchfn,
- SDL_HashTable_NukeFn nukefn,
- bool threadsafe,
- bool stackable);
-
-// This function is thread-safe if the hashtable was created with threadsafe = true
-extern void SDL_EmptyHashTable(SDL_HashTable *table);
-
-// This function is not thread-safe.
+
+/**
+ * A function pointer representing a hash table hashing callback.
+ *
+ * This is called by SDL_HashTable when it needs to look up a key in
+ * its dataset. It generates a hash value from that key, and then uses that
+ * value as a basis for an index into an internal array.
+ *
+ * There are no rules on what hashing algorithm is used, so long as it
+ * can produce a reliable 32-bit value from `key`, and ideally distributes
+ * those values well across the 32-bit value space. The quality of a
+ * hashing algorithm is directly related to how well a hash table performs.
+ *
+ * Hashing can be a complicated subject, and often times what works best
+ * for one dataset will be suboptimal for another. There is a good discussion
+ * of the field [on Wikipedia](https://en.wikipedia.org/wiki/Hash_function).
+ *
+ * Also: do you _need_ to write a hashing function? SDL provides generic
+ * functions for strings (SDL_HashString), generic integer IDs (SDL_HashID),
+ * and generic pointers (SDL_HashPointer). Often you should use one of these
+ * before writing your own.
+ *
+ * \param userdata what was passed as `userdata` to SDL_CreateHashTable().
+ * \param key the key to be hashed.
+ * \returns a 32-bit value that represents a hash of `key`.
+ *
+ * \threadsafety This function must be thread safe if the hash table is used
+ * from multiple threads at the same time.
+ *
+ * \since This datatype is available since SDL 3.4.0.
+ *
+ * \sa SDL_CreateHashTable
+ * \sa SDL_HashString
+ * \sa SDL_HashID
+ * \sa SDL_HashPointer
+ */
+typedef Uint32 (SDLCALL *SDL_HashCallback)(void *userdata, const void *key);
+
+
+/**
+ * A function pointer representing a hash table matching callback.
+ *
+ * This is called by SDL_HashTable when it needs to look up a key in its
+ * dataset. After hashing the key, it looks for items stored in relation to
+ * that hash value. Since there can be more than one item found through the
+ * same hash value, this function verifies a specific value is actually
+ * correct before choosing it.
+ *
+ * So this function needs to compare the keys at `a` and `b` and decide if
+ * they are actually the same.
+ *
+ * For example, if the keys are C strings, this function might just be:
+ *
+ * ```c
+ * return (SDL_strcmp((const char *) a, const char *b) == 0);`
+ * ```
+ *
+ * Also: do you _need_ to write a matching function? SDL provides generic
+ * functions for strings (SDL_KeyMatchString), generic integer IDs
+ * (SDL_KeyMatchID), and generic pointers (SDL_KeyMatchPointer). Often you
+ * should use one of these before writing your own.
+ *
+ * \param userdata what was passed as `userdata` to SDL_CreateHashTable().
+ * \param a the first key to be compared.
+ * \param b the second key to be compared.
+ * \returns true if two keys are identical, false otherwise.
+ *
+ * \threadsafety This function must be thread safe if the hash table is used
+ * from multiple threads at the same time.
+ *
+ * \since This datatype is available since SDL 3.4.0.
+ *
+ * \sa SDL_CreateHashTable
+ */
+typedef bool (SDLCALL *SDL_HashKeyMatchCallback)(void *userdata, const void *a, const void *b);
+
+
+/**
+ * A function pointer representing a hash table cleanup callback.
+ *
+ * This is called by SDL_HashTable when removing items from the hash, or
+ * destroying the hash table. It is used to optionally deallocate the
+ * key/value pairs.
+ *
+ * This is not required to do anything, if all the data in the table is
+ * static or POD data, but it can also do more than a simple free: for
+ * example, if the hash table is storing open files, it can close them here.
+ * I
(Patch may be truncated, please check the link at the top of this post.)