Atlas - SDL_hashtable.c
Home / ext / SDL / src
Lines: 1 | Size: 15238 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#include "SDL_internal.h"
22
23typedef struct SDL_HashItem
24{
25    // TODO: Splitting off values into a separate array might be more cache-friendly
26    const void *key;
27    const void *value;
28    Uint32 hash;
29    Uint32 probe_len : 31;
30    Uint32 live : 1;
31} SDL_HashItem;
32
33// Must be a power of 2 >= sizeof(SDL_HashItem)
34#define MAX_HASHITEM_SIZEOF 32u
35SDL_COMPILE_TIME_ASSERT(sizeof_SDL_HashItem, sizeof(SDL_HashItem) <= MAX_HASHITEM_SIZEOF);
36
37// Anything larger than this will cause integer overflows
38#define MAX_HASHTABLE_SIZE (0x80000000u / (MAX_HASHITEM_SIZEOF))
39
40struct SDL_HashTable
41{
42    SDL_RWLock *lock;  // NULL if not created threadsafe
43    SDL_HashItem *table;
44    SDL_HashCallback hash;
45    SDL_HashKeyMatchCallback keymatch;
46    SDL_HashDestroyCallback destroy;
47    void *userdata;
48    Uint32 hash_mask;
49    Uint32 max_probe_len;
50    Uint32 num_occupied_slots;
51};
52
53
54static Uint32 CalculateHashBucketsFromEstimate(int estimated_capacity)
55{
56    if (estimated_capacity <= 0) {
57        return 4;  // start small, grow as necessary.
58    }
59
60    const Uint32 estimated32 = (Uint32) estimated_capacity;
61    Uint32 buckets = ((Uint32) 1) << SDL_MostSignificantBitIndex32(estimated32);
62    if (!SDL_HasExactlyOneBitSet32(estimated32)) {
63        buckets <<= 1;  // need next power of two up to fit overflow capacity bits.
64    }
65
66    return SDL_min(buckets, MAX_HASHTABLE_SIZE);
67}
68
69SDL_HashTable *SDL_CreateHashTable(int estimated_capacity, bool threadsafe, SDL_HashCallback hash,
70                                   SDL_HashKeyMatchCallback keymatch,
71                                   SDL_HashDestroyCallback destroy, void *userdata)
72{
73    const Uint32 num_buckets = CalculateHashBucketsFromEstimate(estimated_capacity);
74    SDL_HashTable *table = (SDL_HashTable *)SDL_calloc(1, sizeof(SDL_HashTable));
75    if (!table) {
76        return NULL;
77    }
78
79    if (threadsafe) {
80        table->lock = SDL_CreateRWLock();
81        if (!table->lock) {
82            SDL_DestroyHashTable(table);
83            return NULL;
84        }
85    }
86
87    table->table = (SDL_HashItem *)SDL_calloc(num_buckets, sizeof(SDL_HashItem));
88    if (!table->table) {
89        SDL_DestroyHashTable(table);
90        return NULL;
91    }
92
93    table->hash_mask = num_buckets - 1;
94    table->userdata = userdata;
95    table->hash = hash;
96    table->keymatch = keymatch;
97    table->destroy = destroy;
98    return table;
99}
100
101static SDL_INLINE Uint32 calc_hash(const SDL_HashTable *table, const void *key)
102{
103    const Uint32 BitMixer = 0x9E3779B1u;
104    return table->hash(table->userdata, key) * BitMixer;
105}
106
107static SDL_INLINE Uint32 get_probe_length(Uint32 zero_idx, Uint32 actual_idx, Uint32 num_buckets)
108{
109    // returns the probe sequence length from zero_idx to actual_idx
110    if (actual_idx < zero_idx) {
111        return num_buckets - zero_idx + actual_idx;
112    }
113
114    return actual_idx - zero_idx;
115}
116
117static SDL_HashItem *find_item(const SDL_HashTable *ht, const void *key, Uint32 hash, Uint32 *i, Uint32 *probe_len)
118{
119    Uint32 hash_mask = ht->hash_mask;
120    Uint32 max_probe_len = ht->max_probe_len;
121
122    SDL_HashItem *table = ht->table;
123
124    while (true) {
125        SDL_HashItem *item = table + *i;
126        Uint32 item_hash = item->hash;
127
128        if (!item->live) {
129            return NULL;
130        }
131
132        if (item_hash == hash && ht->keymatch(ht->userdata, item->key, key)) {
133            return item;
134        }
135
136        Uint32 item_probe_len = item->probe_len;
137        SDL_assert(item_probe_len == get_probe_length(item_hash & hash_mask, (Uint32)(item - table), hash_mask + 1));
138
139        if (*probe_len > item_probe_len) {
140            return NULL;
141        }
142
143        if (++*probe_len > max_probe_len) {
144            return NULL;
145        }
146
147        *i = (*i + 1) & hash_mask;
148    }
149}
150
151static SDL_HashItem *find_first_item(const SDL_HashTable *ht, const void *key, Uint32 hash)
152{
153    Uint32 i = hash & ht->hash_mask;
154    Uint32 probe_len = 0;
155    return find_item(ht, key, hash, &i, &probe_len);
156}
157
158static SDL_HashItem *insert_item(SDL_HashItem *item_to_insert, SDL_HashItem *table, Uint32 hash_mask, Uint32 *max_probe_len_ptr)
159{
160    const Uint32 num_buckets = hash_mask + 1;
161    Uint32 idx = item_to_insert->hash & hash_mask;
162    SDL_HashItem *target = NULL;
163    SDL_HashItem temp_item;
164
165    while (true) {
166        SDL_HashItem *candidate = table + idx;
167
168        if (!candidate->live) {
169            // Found an empty slot. Put it here and we're done.
170            *candidate = *item_to_insert;
171
172            if (target == NULL) {
173                target = candidate;
174            }
175
176            const Uint32 probe_len = get_probe_length(candidate->hash & hash_mask, idx, num_buckets);
177            candidate->probe_len = probe_len;
178
179            if (*max_probe_len_ptr < probe_len) {
180                *max_probe_len_ptr = probe_len;
181            }
182
183            break;
184        }
185
186        const Uint32 candidate_probe_len = candidate->probe_len;
187        SDL_assert(candidate_probe_len == get_probe_length(candidate->hash & hash_mask, idx, num_buckets));
188        const Uint32 new_probe_len = get_probe_length(item_to_insert->hash & hash_mask, idx, num_buckets);
189
190        if (candidate_probe_len < new_probe_len) {
191            // Robin Hood hashing: the item at idx has a better probe length than our item would at this position.
192            // Evict it and put our item in its place, then continue looking for a new spot for the displaced item.
193            // This algorithm significantly reduces clustering in the table, making lookups take very few probes.
194
195            temp_item = *candidate;
196            *candidate = *item_to_insert;
197
198            if (target == NULL) {
199                target = candidate;
200            }
201
202            *item_to_insert = temp_item;
203
204            SDL_assert(new_probe_len == get_probe_length(candidate->hash & hash_mask, idx, num_buckets));
205            candidate->probe_len = new_probe_len;
206
207            if (*max_probe_len_ptr < new_probe_len) {
208                *max_probe_len_ptr = new_probe_len;
209            }
210        }
211
212        idx = (idx + 1) & hash_mask;
213    }
214
215    return target;
216}
217
218static void delete_item(SDL_HashTable *ht, SDL_HashItem *item)
219{
220    const Uint32 hash_mask = ht->hash_mask;
221    SDL_HashItem *table = ht->table;
222
223    if (ht->destroy) {
224        ht->destroy(ht->userdata, item->key, item->value);
225    }
226
227    SDL_assert(ht->num_occupied_slots > 0);
228    ht->num_occupied_slots--;
229
230    Uint32 idx = (Uint32)(item - ht->table);
231
232    while (true) {
233        idx = (idx + 1) & hash_mask;
234        SDL_HashItem *next_item = table + idx;
235
236        if (next_item->probe_len < 1) {
237            SDL_zerop(item);
238            return;
239        }
240
241        *item = *next_item;
242        item->probe_len -= 1;
243        SDL_assert(item->probe_len < ht->max_probe_len);
244        item = next_item;
245    }
246}
247
248static bool resize(SDL_HashTable *ht, Uint32 new_size)
249{
250    const Uint32 new_hash_mask = new_size - 1;
251    SDL_HashItem *new_table = SDL_calloc(new_size, sizeof(*new_table));
252
253    if (!new_table) {
254        return false;
255    }
256
257    SDL_HashItem *old_table = ht->table;
258    const Uint32 old_size = ht->hash_mask + 1;
259
260    ht->max_probe_len = 0;
261    ht->hash_mask = new_hash_mask;
262    ht->table = new_table;
263
264    for (Uint32 i = 0; i < old_size; ++i) {
265        SDL_HashItem *item = old_table + i;
266        if (item->live) {
267            insert_item(item, new_table, new_hash_mask, &ht->max_probe_len);
268        }
269    }
270
271    SDL_free(old_table);
272    return true;
273}
274
275static bool maybe_resize(SDL_HashTable *ht)
276{
277    const Uint32 capacity = ht->hash_mask + 1;
278
279    if (capacity >= MAX_HASHTABLE_SIZE) {
280        return false;
281    }
282
283    const Uint32 max_load_factor = 217; // range: 0-255; 217 is roughly 85%
284    const Uint32 resize_threshold = (Uint32)((max_load_factor * (Uint64)capacity) >> 8);
285
286    if (ht->num_occupied_slots > resize_threshold) {
287        return resize(ht, capacity * 2);
288    }
289
290    return true;
291}
292
293bool SDL_InsertIntoHashTable(SDL_HashTable *table, const void *key, const void *value, bool replace)
294{
295    CHECK_PARAM(!table) {
296        return SDL_InvalidParamError("table");
297    }
298
299    bool result = false;
300
301    SDL_LockRWLockForWriting(table->lock);
302
303    const Uint32 hash = calc_hash(table, key);
304    SDL_HashItem *item = find_first_item(table, key, hash);
305    bool do_insert = true;
306
307    if (item) {
308        if (replace) {
309            delete_item(table, item);
310        } else {
311            SDL_SetError("key already exists and replace is disabled");
312            do_insert = false;
313        }
314    }
315
316    if (do_insert) {
317        SDL_HashItem new_item;
318        new_item.key = key;
319        new_item.value = value;
320        new_item.hash = hash;
321        new_item.live = true;
322        new_item.probe_len = 0;
323
324        table->num_occupied_slots++;
325
326        if (!maybe_resize(table)) {
327            table->num_occupied_slots--;
328        } else {
329            // This never returns NULL
330            insert_item(&new_item, table->table, table->hash_mask, &table->max_probe_len);
331            result = true;
332        }
333    }
334
335    SDL_UnlockRWLock(table->lock);
336    return result;
337}
338
339bool SDL_FindInHashTable(const SDL_HashTable *table, const void *key, const void **value)
340{
341    CHECK_PARAM(!table) {
342        if (value) {
343            *value = NULL;
344        }
345        return SDL_InvalidParamError("table");
346    }
347
348    SDL_LockRWLockForReading(table->lock);
349
350    bool result = false;
351    const Uint32 hash = calc_hash(table, key);
352    SDL_HashItem *i = find_first_item(table, key, hash);
353    if (i) {
354        if (value) {
355            *value = i->value;
356        }
357        result = true;
358    }
359
360    SDL_UnlockRWLock(table->lock);
361
362    return result;
363}
364
365bool SDL_RemoveFromHashTable(SDL_HashTable *table, const void *key)
366{
367    CHECK_PARAM(!table) {
368        return SDL_InvalidParamError("table");
369    }
370
371    SDL_LockRWLockForWriting(table->lock);
372
373    bool result = false;
374    const Uint32 hash = calc_hash(table, key);
375    SDL_HashItem *item = find_first_item(table, key, hash);
376    if (item) {
377        delete_item(table, item);
378        result = true;
379    }
380
381    SDL_UnlockRWLock(table->lock);
382    return result;
383}
384
385bool SDL_IterateHashTable(const SDL_HashTable *table, SDL_HashTableIterateCallback callback, void *userdata)
386{
387    CHECK_PARAM(!table) {
388        return SDL_InvalidParamError("table");
389    }
390    CHECK_PARAM(!callback) {
391        return SDL_InvalidParamError("callback");
392    }
393
394    SDL_LockRWLockForReading(table->lock);
395    SDL_HashItem *end = table->table + (table->hash_mask + 1);
396    Uint32 num_iterated = 0;
397
398    for (SDL_HashItem *item = table->table; item < end; item++) {
399        if (item->live) {
400            if (!callback(userdata, table, item->key, item->value)) {
401                break;  // callback requested iteration stop.
402            } else if (++num_iterated >= table->num_occupied_slots) {
403                break;  // we can drop out early because we've seen all the live items.
404            }
405        }
406    }
407
408    SDL_UnlockRWLock(table->lock);
409    return true;
410}
411
412bool SDL_HashTableEmpty(SDL_HashTable *table)
413{
414    CHECK_PARAM(!table) {
415        return SDL_InvalidParamError("table");
416    }
417
418    SDL_LockRWLockForReading(table->lock);
419    const bool retval = (table->num_occupied_slots == 0);
420    SDL_UnlockRWLock(table->lock);
421    return retval;
422}
423
424
425static void destroy_all(SDL_HashTable *table)
426{
427    SDL_HashDestroyCallback destroy = table->destroy;
428    if (destroy) {
429        void *userdata = table->userdata;
430        SDL_HashItem *end = table->table + (table->hash_mask + 1);
431        for (SDL_HashItem *i = table->table; i < end; ++i) {
432            if (i->live) {
433                i->live = false;
434                destroy(userdata, i->key, i->value);
435            }
436        }
437    }
438}
439
440void SDL_ClearHashTable(SDL_HashTable *table)
441{
442    if (table) {
443        SDL_LockRWLockForWriting(table->lock);
444        {
445            destroy_all(table);
446            SDL_memset(table->table, 0, sizeof(*table->table) * (table->hash_mask + 1));
447            table->num_occupied_slots = 0;
448        }
449        SDL_UnlockRWLock(table->lock);
450    }
451}
452
453void SDL_DestroyHashTable(SDL_HashTable *table)
454{
455    if (table) {
456        destroy_all(table);
457        if (table->lock) {
458            SDL_DestroyRWLock(table->lock);
459        }
460        SDL_free(table->table);
461        SDL_free(table);
462    }
463}
464
465// this is djb's xor hashing function.
466static SDL_INLINE Uint32 hash_string_djbxor(const char *str, size_t len)
467{
468    Uint32 hash = 5381;
469    while (len--) {
470        hash = ((hash << 5) + hash) ^ *(str++);
471    }
472    return hash;
473}
474
475Uint32 SDL_HashPointer(void *unused, const void *key)
476{
477    (void)unused;
478    return SDL_murmur3_32(&key, sizeof(key), 0);
479}
480
481bool SDL_KeyMatchPointer(void *unused, const void *a, const void *b)
482{
483    (void)unused;
484    return (a == b);
485}
486
487Uint32 SDL_HashString(void *unused, const void *key)
488{
489    (void)unused;
490    const char *str = (const char *)key;
491    return hash_string_djbxor(str, SDL_strlen(str));
492}
493
494bool SDL_KeyMatchString(void *unused, const void *a, const void *b)
495{
496    const char *a_string = (const char *)a;
497    const char *b_string = (const char *)b;
498
499    (void)unused;
500    if (a == b) {
501        return true; // same pointer, must match.
502    } else if (!a || !b) {
503        return false; // one pointer is NULL (and first test shows they aren't the same pointer), must not match.
504    } else if (a_string[0] != b_string[0]) {
505        return false; // we know they don't match
506    }
507    return (SDL_strcmp(a_string, b_string) == 0); // Check against actual string contents.
508}
509
510// We assume we can fit the ID in the key directly
511SDL_COMPILE_TIME_ASSERT(SDL_HashID_KeySize, sizeof(Uint32) <= sizeof(const void *));
512
513Uint32 SDL_HashID(void *unused, const void *key)
514{
515    (void)unused;
516    return (Uint32)(uintptr_t)key;
517}
518
519bool SDL_KeyMatchID(void *unused, const void *a, const void *b)
520{
521    (void)unused;
522    return (a == b);
523}
524
525void SDL_DestroyHashKeyAndValue(void *unused, const void *key, const void *value)
526{
527    (void)unused;
528    SDL_free((void *)key);
529    SDL_free((void *)value);
530}
531
532void SDL_DestroyHashKey(void *unused, const void *key, const void *value)
533{
534    (void)value;
535    (void)unused;
536    SDL_free((void *)key);
537}
538
539void SDL_DestroyHashValue(void *unused, const void *key, const void *value)
540{
541    (void)key;
542    (void)unused;
543    SDL_free((void *)value);
544}
545
[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.