Repository navigation
Expand file tree
/
Copy pathSDL_hashtable.h
More file actions
633 lines (592 loc) · 23.8 KB
/
Copy pathSDL_hashtable.h
File metadata and controls
633 lines (592 loc) · 23.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
/*
Simple DirectMedia Layer
Copyright (C) 1997-2025 Sam Lantinga <slouken@libsdl.org>
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 <SDL3/SDL_stdinc.h>
#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;
/**
* 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().
* \p
8000
aram 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,
<
8
div>
* 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 <SDL3/SDL_close_code.h>
#endif /* SDL_hashtable_h_ */