From 5a079a2d114f96d4847d1ee305d5b7c16eeec50e Mon Sep 17 00:00:00 2001 From: 3gg <3gg@shellblade.net> Date: Sat, 27 Dec 2025 12:03:39 -0800 Subject: Initial commit --- contrib/SDL-3.2.8/src/SDL_hashtable.h | 633 ++++++++++++++++++++++++++++++++++ 1 file changed, 633 insertions(+) create mode 100644 contrib/SDL-3.2.8/src/SDL_hashtable.h (limited to 'contrib/SDL-3.2.8/src/SDL_hashtable.h') diff --git a/contrib/SDL-3.2.8/src/SDL_hashtable.h b/contrib/SDL-3.2.8/src/SDL_hashtable.h new file mode 100644 index 0000000..598a6d6 --- /dev/null +++ b/contrib/SDL-3.2.8/src/SDL_hashtable.h @@ -0,0 +1,633 @@ +/* + 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. +*/ + +/* 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_ + +#include + +#include +/* 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; + +/** + * 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. + * It can also free only the key or only the value; it depends on what the + * hash table contains. + * + * \param userdata what was passed as `userdata` to SDL_CreateHashTable(). + * \param key the key to deallocate. + * \param value the value to deallocate. + * + * \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 void (SDLCALL *SDL_HashDestroyCallback)(void *userdata, const void *key, const void *value); + + +/** + * A function pointer representing a hash table iterator callback. + * + * This function is called once for each key/value pair to be considered + * when iterating a hash table. + * + * Iteration continues as long as there are more items to examine and this + * callback continues to return true. + * + * Do not attempt to modify the hash table during this callback, as it will + * cause incorrect behavior and possibly crashes. + * + * \param userdata what was passed as `userdata` to an iterator function. + * \param table the hash table being iterated. + * \param key the current key being iterated. + * \param value the current value being iterated. + * \returns true to keep iterating, false to stop iteration. + * + * \threadsafety A read lock is held during iteration, so other threads can + * still access the the hash table, but threads attempting to + * make changes will be blocked until iteration completes. If + * this is a concern, do as little in the callback as possible + * and finish iteration quickly. + * + * \since This datatype is available since SDL 3.4.0. + * + * \sa SDL_IterateHashTable + */ +typedef bool (SDLCALL *SDL_HashTableIterateCallback)(void *userdata, const SDL_HashTable *table, const void *key, const void *value); + + +/** + * Create a new hash table. + * + * To deal with different datatypes and needs of the caller, hash tables + * require several callbacks that deal with some specifics: how to hash a key, + * how to compare a key for equality, and how to clean up keys and values. + * SDL provides a few generic functions that can be used for these callbacks: + * + * - SDL_HashString and SDL_KeyMatchString for C strings. + * - SDL_HashPointer and SDL_KeyMatchPointer for generic pointers. + * - SDL_HashID and SDL_KeyMatchID for generic (possibly small) integers. + * + * Oftentimes, these are all you need for any hash table, but depending on + * your dataset, custom implementations might make more sense. + * + * You can specify an estimate of the number of items expected to be stored + * in the table, which can help make the table run more efficiently. The table + * will preallocate resources to accomodate this number of items, which is + * most useful if you intend to fill the table with a lot of data right after + * creating it. Otherwise, it might make more sense to specify the _minimum_ + * you expect the table to hold and let it grow as necessary from there. This + * number is only a hint, and the table will be able to handle any amount of + * data--as long as the system doesn't run out of resources--so a perfect + * answer is not required. A value of 0 signifies no guess at all, and the + * table will start small and reallocate as necessary; often this is the + * correct thing to do. + * + * !!! FIXME: add note about `threadsafe` here. And update `threadsafety` tags. + * !!! FIXME: note that `threadsafe` tables can't be recursively locked, so + * !!! FIXME: you can't use `destroy` callbacks that might end up relocking. + * + * Note that SDL provides a higher-level option built on its hash tables: + * SDL_PropertiesID lets you map strings to various datatypes, and this + * might be easier to use. It only allows strings for keys, however. Those are + * created with SDL_CreateProperties(). + * + * The returned hash table should be destroyed with SDL_DestroyHashTable() + * when no longer needed. + * + * \param estimated_capacity the approximate maximum number of items to be held + * in the hash table, or 0 for no estimate. + * \param threadsafe true to create an internal rwlock for this table. + * \param hash the function to use to hash keys. + * \param keymatch the function to use to compare keys. + * \param destroy the function to use to clean up keys and values, may be NULL. + * \param userdata a pointer that is passed to the callbacks. + * \returns a newly-created hash table, or NULL if there was an error; call + * SDL_GetError() for more information. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_DestroyHashTable + */ +extern SDL_HashTable * SDL_CreateHashTable(int estimated_capacity, + bool threadsafe, + SDL_HashCallback hash, + SDL_HashKeyMatchCallback keymatch, + SDL_HashDestroyCallback destroy, + void *userdata); + + +/** + * Destroy a hash table. + * + * This will call the hash table's SDL_HashDestroyCallback for each item in + * the table, removing all inserted items, before deallocating the table + * itself. + * + * The table becomes invalid once this function is called, and no other thread + * should be accessing this table once this function has started. + * + * \param table the hash table to destroy. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + */ +extern void SDL_DestroyHashTable(SDL_HashTable *table); + +/** + * Add an item to a hash table. + * + * All keys in the table must be unique. If attempting to insert a key that + * already exists in the hash table, what will be done depends on the + * `replace` value: + * + * - If `replace` is false, this function will return false without modifying + * the table. + * - If `replace` is true, SDL will remove the previous item first, so the new + * value is the only one associated with that key. This will call the hash + * table's SDL_HashDestroyCallback for the previous item. + * + * \param table the hash table to insert into. + * \param key the key of the new item to insert. + * \param value the value of the new item to insert. + * \param replace true if a duplicate key should replace the previous value. + * \returns true if the new item was inserted, false otherwise. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + */ +extern bool SDL_InsertIntoHashTable(SDL_HashTable *table, const void *key, const void *value, bool replace); + +/** + * Look up an item in a hash table. + * + * On return, the value associated with `key` is stored to `*value`. + * If the key does not exist in the table, `*value` will be set to NULL. + * + * It is legal for `value` to be NULL, to not retrieve the key's value. In + * this case, the return value is still useful for reporting if the key exists + * in the table at all. + * + * \param table the hash table to search. + * \param key the key to search for in the table. + * \param value the found value will be stored here. Can be NULL. + * \returns true if key exists in the table, false otherwise. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_InsertIntoHashTable + */ +extern bool SDL_FindInHashTable(const SDL_HashTable *table, const void *key, const void **value); + +/** + * Remove an item from a hash table. + * + * If there is an item that matches `key`, it is removed from the table. This + * will call the hash table's SDL_HashDestroyCallback for the item to be + * removed. + * + * \param table the hash table to remove from. + * \param key the key of the item to remove from the table. + * \returns true if a key was removed, false if the key was not found. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + */ +extern bool SDL_RemoveFromHashTable(SDL_HashTable *table, const void *key); + +/** + * Remove all items in a hash table. + * + * This will call the hash table's SDL_HashDestroyCallback for each item in + * the table, removing all inserted items. + * + * When this function returns, the hash table will be empty. + * + * \param table the hash table to clear. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + */ +extern void SDL_ClearHashTable(SDL_HashTable *table); + +/** + * Check if any items are currently stored in a hash table. + * + * If there are no items stored (the table is completely empty), this will + * return true. + * + * \param table the hash table to check. + * \returns true if the table is completely empty, false otherwise. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_ClearHashTable + */ +extern bool SDL_HashTableEmpty(SDL_HashTable *table); + +/** + * Iterate all key/value pairs in a hash table. + * + * This function will call `callback` once for each key/value pair in the + * table, until either all pairs have been presented to the callback, or the + * callback has returned false to signal it is done. + * + * There is no guarantee what order results will be returned in. + * + * \param table the hash table to iterate. + * \param callback the function pointer to call for each value. + * \param userdata a pointer that is passed to `callback`. + * \returns true if iteration happened, false if not (bogus parameter, etc). + * + * \since This function is available since SDL 3.4.0. + */ +extern bool SDL_IterateHashTable(const SDL_HashTable *table, SDL_HashTableIterateCallback callback, void *userdata); + + +/* Helper functions for SDL_CreateHashTable callbacks... */ + +/** + * Generate a hash from a generic pointer. + * + * The key is intended to be a unique pointer to any datatype. + * + * This is intended to be used as one of the callbacks to SDL_CreateHashTable, + * if this is useful to the type of keys to be used with the hash table. + * + * Note that the implementation may change in the future; do not expect + * the results to be stable vs future SDL releases. Use this in a hash table + * in the current process and don't store them to disk for the future. + * + * \param unused this parameter is ignored. + * \param key the key to hash as a generic pointer. + * \returns a 32-bit hash of the key. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_CreateHashTable + */ +extern Uint32 SDL_HashPointer(void *unused, const void *key); + +/** + * Compare two generic pointers as hash table keys. + * + * This is intended to be used as one of the callbacks to SDL_CreateHashTable, + * if this is useful to the type of keys to be used with the hash table. + * + * \param unused this parameter is ignored. + * \param a the first generic pointer to compare. + * \param b the second generic pointer to compare. + * \returns true if the pointers are the same, false otherwise. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_CreateHashTable + */ +extern bool SDL_KeyMatchPointer(void *unused, const void *a, const void *b); + +/** + * Generate a hash from a C string. + * + * The key is intended to be a NULL-terminated string, in UTF-8 format. + * + * This is intended to be used as one of the callbacks to SDL_CreateHashTable, + * if this is useful to the type of keys to be used with the hash table. + * + * Note that the implementation may change in the future; do not expect + * the results to be stable vs future SDL releases. Use this in a hash table + * in the current process and don't store them to disk for the future. + * + * \param unused this parameter is ignored. + * \param key the key to hash as a generic pointer. + * \returns a 32-bit hash of the key. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_CreateHashTable + */ +extern Uint32 SDL_HashString(void *unused, const void *key); + +/** + * Compare two C strings as hash table keys. + * + * Strings will be compared in a case-sensitive manner. More specifically, + * they'll be compared as NULL-terminated arrays of bytes. + * + * This is intended to be used as one of the callbacks to SDL_CreateHashTable, + * if this is useful to the type of keys to be used with the hash table. + * + * \param unused this parameter is ignored. + * \param a the first string to compare. + * \param b the second string to compare. + * \returns true if the strings are the same, false otherwise. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_CreateHashTable + */ +extern bool SDL_KeyMatchString(void *unused, const void *a, const void *b); + +/** + * Generate a hash from an integer ID. + * + * The key is intended to a unique integer, possibly within a small range. + * + * This is intended to be used as one of the callbacks to SDL_CreateHashTable, + * if this is useful to the type of keys to be used with the hash table. + * + * Note that the implementation may change in the future; do not expect + * the results to be stable vs future SDL releases. Use this in a hash table + * in the current process and don't store them to disk for the future. + * + * \param unused this parameter is ignored. + * \param key the key to hash as a generic pointer. + * \returns a 32-bit hash of the key. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_CreateHashTable + */ +extern Uint32 SDL_HashID(void *unused, const void *key); + +/** + * Compare two integer IDs as hash table keys. + * + * This is intended to be used as one of the callbacks to SDL_CreateHashTable, + * if this is useful to the type of keys to be used with the hash table. + * + * \param unused this parameter is ignored. + * \param a the first ID to compare. + * \param b the second ID to compare. + * \returns true if the IDs are the same, false otherwise. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_CreateHashTable + */ +extern bool SDL_KeyMatchID(void *unused, const void *a, const void *b); + +/** + * Free both the key and value pointers of a hash table item. + * + * This is intended to be used as one of the callbacks to SDL_CreateHashTable, + * if this is useful to the type of data to be used with the hash table. + * + * This literally calls `SDL_free(key);` and `SDL_free(value);`. + * + * \param unused this parameter is ignored. + * \param key the key to be destroyed. + * \param value the value to be destroyed. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_CreateHashTable + */ +extern void SDL_DestroyHashKeyAndValue(void *unused, const void *key, const void *value); + +/** + * Free just the value pointer of a hash table item. + * + * This is intended to be used as one of the callbacks to SDL_CreateHashTable, + * if this is useful to the type of data to be used with the hash table. + * + * This literally calls `SDL_free(key);` and leaves `value` alone. + * + * \param unused this parameter is ignored. + * \param key the key to be destroyed. + * \param value the value to be destroyed. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_CreateHashTable + */ +extern void SDL_DestroyHashKey(void *unused, const void *key, const void *value); + +/** + * Free just the value pointer of a hash table item. + * + * This is intended to be used as one of the callbacks to SDL_CreateHashTable, + * if this is useful to the type of data to be used with the hash table. + * + * This literally calls `SDL_free(value);` and leaves `key` alone. + * + * \param unused this parameter is ignored. + * \param key the key to be destroyed. + * \param value the value to be destroyed. + * + * \threadsafety It is safe to call this function from any thread. + * + * \since This function is available since SDL 3.4.0. + * + * \sa SDL_CreateHashTable + */ +extern void SDL_DestroyHashValue(void *unused, const void *key, const void *value); + + +/* Ends C function definitions when using C++ */ +#ifdef __cplusplus +} +#endif +#include + +#endif /* SDL_hashtable_h_ */ -- cgit v1.2.3