1
2 #pragma once
3
4 #ifndef hash_h_
5 #define hash_h_
6
7 #ifdef __cplusplus
8 extern "C" {
9 #endif
10
11 // Hash functions
12 #define DJB_MAGIC 5381u
13
14 typedef struct hashitem // size is 12/24 bytes.
15 {
16 char *string;
17 intptr_t key;
18 struct hashitem *next;
19 } hashitem_t;
20
21 typedef struct
22 {
23 int32_t size;
24 hashitem_t **items;
25 } hashtable_t;
26
27 // djb3 algorithm
hash_getcode(const char * s)28 static inline uint32_t hash_getcode(const char *s)
29 {
30 uint32_t h = DJB_MAGIC;
31 char ch;
32
33 while ((ch = Btolower(*s++)) != '\0')
34 h = ((h << 5) + h) ^ ch;
35
36 return h;
37 }
38
39 void hash_init(hashtable_t *t);
40 void hash_loop(hashtable_t *t, void (*func)(const char *, intptr_t));
41 void hash_free(hashtable_t *t);
42 void hash_add(hashtable_t *t, const char *s, intptr_t key, int32_t replace);
43 void hash_delete(hashtable_t *t, const char *s);
44
45 intptr_t hash_findcase(hashtable_t const *t, char const *s);
46 intptr_t hash_find(hashtable_t const *t, char const *s);
47
48 // Hash functions
49 // modified for raw binary keys and one big allocation, and maximum find() performance
50
51 typedef struct inthashitem
52 {
53 intptr_t key;
54 intptr_t value;
55 struct inthashitem *collision; // use NULL to signify empty and pointer identity to signify end of linked list
56 } inthashitem_t;
57
58 typedef struct
59 {
60 inthashitem_t *items;
61 uint32_t count;
62 } inthashtable_t;
63
64 // djb3 algorithm
inthash_getcode(intptr_t key)65 static inline uint32_t inthash_getcode(intptr_t key)
66 {
67 uint32_t h = DJB_MAGIC;
68
69 for (auto keybuf = (uint8_t const *) &key, keybuf_end = keybuf + sizeof(key); keybuf < keybuf_end; ++keybuf)
70 h = ((h << 5) + h) ^ (uint32_t) *keybuf;
71
72 return h;
73 }
74
75 void inthash_init(inthashtable_t *t);
76 void inthash_loop(inthashtable_t const *t, void (*func)(intptr_t, intptr_t));
77 void inthash_free(inthashtable_t *t);
78 void inthash_add(inthashtable_t *t, intptr_t key, intptr_t value, int32_t replace);
79 void inthash_delete(inthashtable_t *t, intptr_t key);
80
81 intptr_t inthash_find(inthashtable_t const *t, intptr_t key);
82
83 // keep the load factor below 0.75 and make sure the size is odd
84 // ideally we would find the next largest prime number
85 #define INTHASH_SIZE(size) ((size * 4u / 3u) | 1u)
86
87 #ifdef __cplusplus
88 }
89 #endif
90
91 #endif // hash_h_
92