1/*
2 Simple DirectMedia Layer
3 Copyright (C) 1997-2025 Sam Lantinga <slouken@libsdl.org>
4
5 This software is provided 'as-is', without any express or implied
6 warranty. In no event will the authors be held liable for any damages
7 arising from the use of this software.
8
9 Permission is granted to anyone to use this software for any purpose,
10 including commercial applications, and to alter it and redistribute it
11 freely, subject to the following restrictions:
12
13 1. The origin of this software must not be misrepresented; you must not
14 claim that you wrote the original software. If you use this software
15 in a product, an acknowledgment in the product documentation would be
16 appreciated but is not required.
17 2. Altered source versions must be plainly marked as such, and must not be
18 misrepresented as being the original software.
19 3. This notice may not be removed or altered from any source distribution.
20*/
21
22/* this is over-documented because it was almost a public API. Leaving the
23 full docs here in case it _does_ become public some day. */
24
25/* WIKI CATEGORY: HashTable */
26
27/**
28 * # CategoryHashTable
29 *
30 * SDL offers a hash table implementation, as a convenience for C code that
31 * needs efficient organization and access of arbitrary data.
32 *
33 * Hash tables are a popular data structure, designed to make it quick to
34 * store and look up arbitrary data. Data is stored with an associated "key."
35 * While one would look up an element of an array with an index, a hash table
36 * uses a unique key to find an element later.
37 *
38 * A key can be anything, as long as its unique and in a format that the table
39 * understands. For example, it's popular to use strings as keys: the key
40 * might be a username, and it is used to lookup account information for that
41 * user, etc.
42 *
43 * Hash tables are named because they "hash" their keys down into simple
44 * integers that can be used to efficiently organize and access the associated
45 * data.
46 *
47 * As this is a C API, there is one generic interface that is intended to work
48 * with different data types. This can be a little awkward to set up, but is
49 * easy to use after that.
50 *
51 * Hashtables are generated by a call to SDL_CreateHashTable(). This function
52 * requires several callbacks to be provided (for hashing keys, comparing
53 * entries, and cleaning up entries when removed). These are necessary to
54 * allow the hash to manage any arbitrary data type.
55 *
56 * Once a hash table is created, the common tasks are inserting data into the
57 * table, (SDL_InsertIntoHashTable), looking up previously inserted data
58 * (SDL_FindInHashTable), and removing data (SDL_RemoveFromHashTable and
59 * SDL_ClearHashTable). Less common but still useful is the ability to
60 * iterate through all the items in the table (SDL_IterateHashTable).
61 *
62 * The underlying hash table implementation is always subject to change, but
63 * at the time of writing, it uses open addressing and Robin Hood hashing.
64 * The technical details are explained [here](https://github.com/libsdl-org/SDL/pull/10897).
65 *
66 * Hashtables keep an SDL_RWLock internally, so multiple threads can perform
67 * hash lookups in parallel, while changes to the table will safely serialize
68 * access between threads.
69 *
70 * SDL provides a layer on top of this hash table implementation that might be
71 * more pleasant to use. SDL_PropertiesID maps a string to arbitrary data of
72 * various types in the same table, which could be both easier to use and more
73 * flexible. Refer to [CategoryProperties](CategoryProperties) for details.
74 */
75
76#ifndef SDL_hashtable_h_
77#define SDL_hashtable_h_
78
79#include <SDL3/SDL_stdinc.h>
80
81#include <SDL3/SDL_begin_code.h>
82/* Set up for C function definitions, even when using C++ */
83#ifdef __cplusplus
84extern "C" {
85#endif
86
87/**
88 * The opaque type that represents a hash table.
89 *
90 * This is hidden behind an opaque pointer because not only does the table
91 * need to store arbitrary data types, but the hash table implementation may
92 * change in the future.
93 *
94 * \since This struct is available since SDL 3.4.0.
95 *
96 * \sa SDL_CreateHashTable
97 */
98typedef struct SDL_HashTable SDL_HashTable;
99
100/**
101 * A function pointer representing a hash table hashing callback.
102 *
103 * This is called by SDL_HashTable when it needs to look up a key in
104 * its dataset. It generates a hash value from that key, and then uses that
105 * value as a basis for an index into an internal array.
106 *
107 * There are no rules on what hashing algorithm is used, so long as it
108 * can produce a reliable 32-bit value from `key`, and ideally distributes
109 * those values well across the 32-bit value space. The quality of a
110 * hashing algorithm is directly related to how well a hash table performs.
111 *
112 * Hashing can be a complicated subject, and often times what works best
113 * for one dataset will be suboptimal for another. There is a good discussion
114 * of the field [on Wikipedia](https://en.wikipedia.org/wiki/Hash_function).
115 *
116 * Also: do you _need_ to write a hashing function? SDL provides generic
117 * functions for strings (SDL_HashString), generic integer IDs (SDL_HashID),
118 * and generic pointers (SDL_HashPointer). Often you should use one of these
119 * before writing your own.
120 *
121 * \param userdata what was passed as `userdata` to SDL_CreateHashTable().
122 * \param key the key to be hashed.
123 * \returns a 32-bit value that represents a hash of `key`.
124 *
125 * \threadsafety This function must be thread safe if the hash table is used
126 * from multiple threads at the same time.
127 *
128 * \since This datatype is available since SDL 3.4.0.
129 *
130 * \sa SDL_CreateHashTable
131 * \sa SDL_HashString
132 * \sa SDL_HashID
133 * \sa SDL_HashPointer
134 */
135typedef Uint32 (SDLCALL *SDL_HashCallback)(void *userdata, const void *key);
136
137
138/**
139 * A function pointer representing a hash table matching callback.
140 *
141 * This is called by SDL_HashTable when it needs to look up a key in its
142 * dataset. After hashing the key, it looks for items stored in relation to
143 * that hash value. Since there can be more than one item found through the
144 * same hash value, this function verifies a specific value is actually
145 * correct before choosing it.
146 *
147 * So this function needs to compare the keys at `a` and `b` and decide if
148 * they are actually the same.
149 *
150 * For example, if the keys are C strings, this function might just be:
151 *
152 * ```c
153 * return (SDL_strcmp((const char *) a, const char *b) == 0);`
154 * ```
155 *
156 * Also: do you _need_ to write a matching function? SDL provides generic
157 * functions for strings (SDL_KeyMatchString), generic integer IDs
158 * (SDL_KeyMatchID), and generic pointers (SDL_KeyMatchPointer). Often you
159 * should use one of these before writing your own.
160 *
161 * \param userdata what was passed as `userdata` to SDL_CreateHashTable().
162 * \param a the first key to be compared.
163 * \param b the second key to be compared.
164 * \returns true if two keys are identical, false otherwise.
165 *
166 * \threadsafety This function must be thread safe if the hash table is used
167 * from multiple threads at the same time.
168 *
169 * \since This datatype is available since SDL 3.4.0.
170 *
171 * \sa SDL_CreateHashTable
172 */
173typedef bool (SDLCALL *SDL_HashKeyMatchCallback)(void *userdata, const void *a, const void *b);
174
175
176/**
177 * A function pointer representing a hash table cleanup callback.
178 *
179 * This is called by SDL_HashTable when removing items from the hash, or
180 * destroying the hash table. It is used to optionally deallocate the
181 * key/value pairs.
182 *
183 * This is not required to do anything, if all the data in the table is
184 * static or POD data, but it can also do more than a simple free: for
185 * example, if the hash table is storing open files, it can close them here.
186 * It can also free only the key or only the value; it depends on what the
187 * hash table contains.
188 *
189 * \param userdata what was passed as `userdata` to SDL_CreateHashTable().
190 * \param key the key to deallocate.
191 * \param value the value to deallocate.
192 *
193 * \threadsafety This function must be thread safe if the hash table is used
194 * from multiple threads at the same time.
195 *
196 * \since This datatype is available since SDL 3.4.0.
197 *
198 * \sa SDL_CreateHashTable
199 */
200typedef void (SDLCALL *SDL_HashDestroyCallback)(void *userdata, const void *key, const void *value);
201
202
203/**
204 * A function pointer representing a hash table iterator callback.
205 *
206 * This function is called once for each key/value pair to be considered
207 * when iterating a hash table.
208 *
209 * Iteration continues as long as there are more items to examine and this
210 * callback continues to return true.
211 *
212 * Do not attempt to modify the hash table during this callback, as it will
213 * cause incorrect behavior and possibly crashes.
214 *
215 * \param userdata what was passed as `userdata` to an iterator function.
216 * \param table the hash table being iterated.
217 * \param key the current key being iterated.
218 * \param value the current value being iterated.
219 * \returns true to keep iterating, false to stop iteration.
220 *
221 * \threadsafety A read lock is held during iteration, so other threads can
222 * still access the the hash table, but threads attempting to
223 * make changes will be blocked until iteration completes. If
224 * this is a concern, do as little in the callback as possible
225 * and finish iteration quickly.
226 *
227 * \since This datatype is available since SDL 3.4.0.
228 *
229 * \sa SDL_IterateHashTable
230 */
231typedef bool (SDLCALL *SDL_HashTableIterateCallback)(void *userdata, const SDL_HashTable *table, const void *key, const void *value);
232
233
234/**
235 * Create a new hash table.
236 *
237 * To deal with different datatypes and needs of the caller, hash tables
238 * require several callbacks that deal with some specifics: how to hash a key,
239 * how to compare a key for equality, and how to clean up keys and values.
240 * SDL provides a few generic functions that can be used for these callbacks:
241 *
242 * - SDL_HashString and SDL_KeyMatchString for C strings.
243 * - SDL_HashPointer and SDL_KeyMatchPointer for generic pointers.
244 * - SDL_HashID and SDL_KeyMatchID for generic (possibly small) integers.
245 *
246 * Oftentimes, these are all you need for any hash table, but depending on
247 * your dataset, custom implementations might make more sense.
248 *
249 * You can specify an estimate of the number of items expected to be stored
250 * in the table, which can help make the table run more efficiently. The table
251 * will preallocate resources to accomodate this number of items, which is
252 * most useful if you intend to fill the table with a lot of data right after
253 * creating it. Otherwise, it might make more sense to specify the _minimum_
254 * you expect the table to hold and let it grow as necessary from there. This
255 * number is only a hint, and the table will be able to handle any amount of
256 * data--as long as the system doesn't run out of resources--so a perfect
257 * answer is not required. A value of 0 signifies no guess at all, and the
258 * table will start small and reallocate as necessary; often this is the
259 * correct thing to do.
260 *
261 * !!! FIXME: add note about `threadsafe` here. And update `threadsafety` tags.
262 * !!! FIXME: note that `threadsafe` tables can't be recursively locked, so
263 * !!! FIXME: you can't use `destroy` callbacks that might end up relocking.
264 *
265 * Note that SDL provides a higher-level option built on its hash tables:
266 * SDL_PropertiesID lets you map strings to various datatypes, and this
267 * might be easier to use. It only allows strings for keys, however. Those are
268 * created with SDL_CreateProperties().
269 *
270 * The returned hash table should be destroyed with SDL_DestroyHashTable()
271 * when no longer needed.
272 *
273 * \param estimated_capacity the approximate maximum number of items to be held
274 * in the hash table, or 0 for no estimate.
275 * \param threadsafe true to create an internal rwlock for this table.
276 * \param hash the function to use to hash keys.
277 * \param keymatch the function to use to compare keys.
278 * \param destroy the function to use to clean up keys and values, may be NULL.
279 * \param userdata a pointer that is passed to the callbacks.
280 * \returns a newly-created hash table, or NULL if there was an error; call
281 * SDL_GetError() for more information.
282 *
283 * \threadsafety It is safe to call this function from any thread.
284 *
285 * \since This function is available since SDL 3.4.0.
286 *
287 * \sa SDL_DestroyHashTable
288 */
289extern SDL_HashTable * SDL_CreateHashTable(int estimated_capacity,
290 bool threadsafe,
291 SDL_HashCallback hash,
292 SDL_HashKeyMatchCallback keymatch,
293 SDL_HashDestroyCallback destroy,
294 void *userdata);
295
296
297/**
298 * Destroy a hash table.
299 *
300 * This will call the hash table's SDL_HashDestroyCallback for each item in
301 * the table, removing all inserted items, before deallocating the table
302 * itself.
303 *
304 * The table becomes invalid once this function is called, and no other thread
305 * should be accessing this table once this function has started.
306 *
307 * \param table the hash table to destroy.
308 *
309 * \threadsafety It is safe to call this function from any thread.
310 *
311 * \since This function is available since SDL 3.4.0.
312 */
313extern void SDL_DestroyHashTable(SDL_HashTable *table);
314
315/**
316 * Add an item to a hash table.
317 *
318 * All keys in the table must be unique. If attempting to insert a key that
319 * already exists in the hash table, what will be done depends on the
320 * `replace` value:
321 *
322 * - If `replace` is false, this function will return false without modifying
323 * the table.
324 * - If `replace` is true, SDL will remove the previous item first, so the new
325 * value is the only one associated with that key. This will call the hash
326 * table's SDL_HashDestroyCallback for the previous item.
327 *
328 * \param table the hash table to insert into.
329 * \param key the key of the new item to insert.
330 * \param value the value of the new item to insert.
331 * \param replace true if a duplicate key should replace the previous value.
332 * \returns true if the new item was inserted, false otherwise.
333 *
334 * \threadsafety It is safe to call this function from any thread.
335 *
336 * \since This function is available since SDL 3.4.0.
337 */
338extern bool SDL_InsertIntoHashTable(SDL_HashTable *table, const void *key, const void *value, bool replace);
339
340/**
341 * Look up an item in a hash table.
342 *
343 * On return, the value associated with `key` is stored to `*value`.
344 * If the key does not exist in the table, `*value` will be set to NULL.
345 *
346 * It is legal for `value` to be NULL, to not retrieve the key's value. In
347 * this case, the return value is still useful for reporting if the key exists
348 * in the table at all.
349 *
350 * \param table the hash table to search.
351 * \param key the key to search for in the table.
352 * \param value the found value will be stored here. Can be NULL.
353 * \returns true if key exists in the table, false otherwise.
354 *
355 * \threadsafety It is safe to call this function from any thread.
356 *
357 * \since This function is available since SDL 3.4.0.
358 *
359 * \sa SDL_InsertIntoHashTable
360 */
361extern bool SDL_FindInHashTable(const SDL_HashTable *table, const void *key, const void **value);
362
363/**
364 * Remove an item from a hash table.
365 *
366 * If there is an item that matches `key`, it is removed from the table. This
367 * will call the hash table's SDL_HashDestroyCallback for the item to be
368 * removed.
369 *
370 * \param table the hash table to remove from.
371 * \param key the key of the item to remove from the table.
372 * \returns true if a key was removed, false if the key was not found.
373 *
374 * \threadsafety It is safe to call this function from any thread.
375 *
376 * \since This function is available since SDL 3.4.0.
377 */
378extern bool SDL_RemoveFromHashTable(SDL_HashTable *table, const void *key);
379
380/**
381 * Remove all items in a hash table.
382 *
383 * This will call the hash table's SDL_HashDestroyCallback for each item in
384 * the table, removing all inserted items.
385 *
386 * When this function returns, the hash table will be empty.
387 *
388 * \param table the hash table to clear.
389 *
390 * \threadsafety It is safe to call this function from any thread.
391 *
392 * \since This function is available since SDL 3.4.0.
393 */
394extern void SDL_ClearHashTable(SDL_HashTable *table);
395
396/**
397 * Check if any items are currently stored in a hash table.
398 *
399 * If there are no items stored (the table is completely empty), this will
400 * return true.
401 *
402 * \param table the hash table to check.
403 * \returns true if the table is completely empty, false otherwise.
404 *
405 * \threadsafety It is safe to call this function from any thread.
406 *
407 * \since This function is available since SDL 3.4.0.
408 *
409 * \sa SDL_ClearHashTable
410 */
411extern bool SDL_HashTableEmpty(SDL_HashTable *table);
412
413/**
414 * Iterate all key/value pairs in a hash table.
415 *
416 * This function will call `callback` once for each key/value pair in the
417 * table, until either all pairs have been presented to the callback, or the
418 * callback has returned false to signal it is done.
419 *
420 * There is no guarantee what order results will be returned in.
421 *
422 * \param table the hash table to iterate.
423 * \param callback the function pointer to call for each value.
424 * \param userdata a pointer that is passed to `callback`.
425 * \returns true if iteration happened, false if not (bogus parameter, etc).
426 *
427 * \since This function is available since SDL 3.4.0.
428 */
429extern bool SDL_IterateHashTable(const SDL_HashTable *table, SDL_HashTableIterateCallback callback, void *userdata);
430
431
432/* Helper functions for SDL_CreateHashTable callbacks... */
433
434/**
435 * Generate a hash from a generic pointer.
436 *
437 * The key is intended to be a unique pointer to any datatype.
438 *
439 * This is intended to be used as one of the callbacks to SDL_CreateHashTable,
440 * if this is useful to the type of keys to be used with the hash table.
441 *
442 * Note that the implementation may change in the future; do not expect
443 * the results to be stable vs future SDL releases. Use this in a hash table
444 * in the current process and don't store them to disk for the future.
445 *
446 * \param unused this parameter is ignored.
447 * \param key the key to hash as a generic pointer.
448 * \returns a 32-bit hash of the key.
449 *
450 * \threadsafety It is safe to call this function from any thread.
451 *
452 * \since This function is available since SDL 3.4.0.
453 *
454 * \sa SDL_CreateHashTable
455 */
456extern Uint32 SDL_HashPointer(void *unused, const void *key);
457
458/**
459 * Compare two generic pointers as hash table keys.
460 *
461 * This is intended to be used as one of the callbacks to SDL_CreateHashTable,
462 * if this is useful to the type of keys to be used with the hash table.
463 *
464 * \param unused this parameter is ignored.
465 * \param a the first generic pointer to compare.
466 * \param b the second generic pointer to compare.
467 * \returns true if the pointers are the same, false otherwise.
468 *
469 * \threadsafety It is safe to call this function from any thread.
470 *
471 * \since This function is available since SDL 3.4.0.
472 *
473 * \sa SDL_CreateHashTable
474 */
475extern bool SDL_KeyMatchPointer(void *unused, const void *a, const void *b);
476
477/**
478 * Generate a hash from a C string.
479 *
480 * The key is intended to be a NULL-terminated string, in UTF-8 format.
481 *
482 * This is intended to be used as one of the callbacks to SDL_CreateHashTable,
483 * if this is useful to the type of keys to be used with the hash table.
484 *
485 * Note that the implementation may change in the future; do not expect
486 * the results to be stable vs future SDL releases. Use this in a hash table
487 * in the current process and don't store them to disk for the future.
488 *
489 * \param unused this parameter is ignored.
490 * \param key the key to hash as a generic pointer.
491 * \returns a 32-bit hash of the key.
492 *
493 * \threadsafety It is safe to call this function from any thread.
494 *
495 * \since This function is available since SDL 3.4.0.
496 *
497 * \sa SDL_CreateHashTable
498 */
499extern Uint32 SDL_HashString(void *unused, const void *key);
500
501/**
502 * Compare two C strings as hash table keys.
503 *
504 * Strings will be compared in a case-sensitive manner. More specifically,
505 * they'll be compared as NULL-terminated arrays of bytes.
506 *
507 * This is intended to be used as one of the callbacks to SDL_CreateHashTable,
508 * if this is useful to the type of keys to be used with the hash table.
509 *
510 * \param unused this parameter is ignored.
511 * \param a the first string to compare.
512 * \param b the second string to compare.
513 * \returns true if the strings are the same, false otherwise.
514 *
515 * \threadsafety It is safe to call this function from any thread.
516 *
517 * \since This function is available since SDL 3.4.0.
518 *
519 * \sa SDL_CreateHashTable
520 */
521extern bool SDL_KeyMatchString(void *unused, const void *a, const void *b);
522
523/**
524 * Generate a hash from an integer ID.
525 *
526 * The key is intended to a unique integer, possibly within a small range.
527 *
528 * This is intended to be used as one of the callbacks to SDL_CreateHashTable,
529 * if this is useful to the type of keys to be used with the hash table.
530 *
531 * Note that the implementation may change in the future; do not expect
532 * the results to be stable vs future SDL releases. Use this in a hash table
533 * in the current process and don't store them to disk for the future.
534 *
535 * \param unused this parameter is ignored.
536 * \param key the key to hash as a generic pointer.
537 * \returns a 32-bit hash of the key.
538 *
539 * \threadsafety It is safe to call this function from any thread.
540 *
541 * \since This function is available since SDL 3.4.0.
542 *
543 * \sa SDL_CreateHashTable
544 */
545extern Uint32 SDL_HashID(void *unused, const void *key);
546
547/**
548 * Compare two integer IDs as hash table keys.
549 *
550 * This is intended to be used as one of the callbacks to SDL_CreateHashTable,
551 * if this is useful to the type of keys to be used with the hash table.
552 *
553 * \param unused this parameter is ignored.
554 * \param a the first ID to compare.
555 * \param b the second ID to compare.
556 * \returns true if the IDs are the same, false otherwise.
557 *
558 * \threadsafety It is safe to call this function from any thread.
559 *
560 * \since This function is available since SDL 3.4.0.
561 *
562 * \sa SDL_CreateHashTable
563 */
564extern bool SDL_KeyMatchID(void *unused, const void *a, const void *b);
565
566/**
567 * Free both the key and value pointers of a hash table item.
568 *
569 * This is intended to be used as one of the callbacks to SDL_CreateHashTable,
570 * if this is useful to the type of data to be used with the hash table.
571 *
572 * This literally calls `SDL_free(key);` and `SDL_free(value);`.
573 *
574 * \param unused this parameter is ignored.
575 * \param key the key to be destroyed.
576 * \param value the value to be destroyed.
577 *
578 * \threadsafety It is safe to call this function from any thread.
579 *
580 * \since This function is available since SDL 3.4.0.
581 *
582 * \sa SDL_CreateHashTable
583 */
584extern void SDL_DestroyHashKeyAndValue(void *unused, const void *key, const void *value);
585
586/**
587 * Free just the value pointer of a hash table item.
588 *
589 * This is intended to be used as one of the callbacks to SDL_CreateHashTable,
590 * if this is useful to the type of data to be used with the hash table.
591 *
592 * This literally calls `SDL_free(key);` and leaves `value` alone.
593 *
594 * \param unused this parameter is ignored.
595 * \param key the key to be destroyed.
596 * \param value the value to be destroyed.
597 *
598 * \threadsafety It is safe to call this function from any thread.
599 *
600 * \since This function is available since SDL 3.4.0.
601 *
602 * \sa SDL_CreateHashTable
603 */
604extern void SDL_DestroyHashKey(void *unused, const void *key, const void *value);
605
606/**
607 * Free just the value pointer of a hash table item.
608 *
609 * This is intended to be used as one of the callbacks to SDL_CreateHashTable,
610 * if this is useful to the type of data to be used with the hash table.
611 *
612 * This literally calls `SDL_free(value);` and leaves `key` alone.
613 *
614 * \param unused this parameter is ignored.
615 * \param key the key to be destroyed.
616 * \param value the value to be destroyed.
617 *
618 * \threadsafety It is safe to call this function from any thread.
619 *
620 * \since This function is available since SDL 3.4.0.
621 *
622 * \sa SDL_CreateHashTable
623 */
624extern void SDL_DestroyHashValue(void *unused, const void *key, const void *value);
625
626
627/* Ends C function definitions when using C++ */
628#ifdef __cplusplus
629}
630#endif
631#include <SDL3/SDL_close_code.h>
632
633#endif /* SDL_hashtable_h_ */
634