Atlas - SDL_hashtable.h
Home / ext / SDL / src Lines: 1 | Size: 24380 bytes [Download] [Show on GitHub] [Search similar files] [Raw] [Raw (proxy)][FILE BEGIN]1/* 2 Simple DirectMedia Layer 3 Copyright (C) 1997-2025 Sam Lantinga <[email protected]> 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 hash table, but threads attempting to make 223 * changes will be blocked until iteration completes. If this 224 * is a concern, do as little in the callback as possible and 225 * 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 accommodate 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[FILE END](C) 2025 0x4248 (C) 2025 4248 Media and 4248 Systems, All part of 0x4248 See LICENCE files for more information. Not all files are by 0x4248 always check Licencing.