diff options
author | Bad Diode <bd@badd10de.dev> | 2021-10-21 17:55:04 +0200 |
---|---|---|
committer | Bad Diode <bd@badd10de.dev> | 2021-10-21 17:55:04 +0200 |
commit | 61f617fe39f891f3dfc5b4815e20ef70a0497a64 (patch) | |
tree | ea20270cd6f2bdb1d94854a705940a83dcd2986d | |
parent | 528bcf1eaf7ec6a4441ce792733c9c5a649f61f9 (diff) | |
download | bdl-61f617fe39f891f3dfc5b4815e20ef70a0497a64.tar.gz bdl-61f617fe39f891f3dfc5b4815e20ef70a0497a64.zip |
Finalize initial hash table implementation for Objects
-rw-r--r-- | src/bootstrap/hashtable.h | 73 |
1 files changed, 41 insertions, 32 deletions
diff --git a/src/bootstrap/hashtable.h b/src/bootstrap/hashtable.h index 59f0660..ca4ced8 100644 --- a/src/bootstrap/hashtable.h +++ b/src/bootstrap/hashtable.h | |||
@@ -29,6 +29,19 @@ typedef struct HashTable { | |||
29 | uint8_t shift_amount; | 29 | uint8_t shift_amount; |
30 | } HashTable; | 30 | } HashTable; |
31 | 31 | ||
32 | // Hash a byte stream using a circular shift + XOR hash function. | ||
33 | static inline uint64_t | ||
34 | _xor_shift_hash(const char *key, size_t n) { | ||
35 | uint64_t hash = 0x65d9d65f6a19574f; | ||
36 | char *last = (char *)key + n; | ||
37 | while (key != last) { | ||
38 | putchar(*key); | ||
39 | hash ^= (uint64_t)*key++; | ||
40 | hash = (hash << 8) | (hash >> (64 - 8)); | ||
41 | } | ||
42 | return hash; | ||
43 | } | ||
44 | |||
32 | // Use Fibonacci hashing to map a hash to a value in range of the table. | 45 | // Use Fibonacci hashing to map a hash to a value in range of the table. |
33 | static inline uint64_t | 46 | static inline uint64_t |
34 | _fibonacci_hash(uint64_t hash, size_t shift_amount) { | 47 | _fibonacci_hash(uint64_t hash, size_t shift_amount) { |
@@ -37,11 +50,28 @@ _fibonacci_hash(uint64_t hash, size_t shift_amount) { | |||
37 | 50 | ||
38 | uint64_t | 51 | uint64_t |
39 | ht_hash(const HashTable *table, const Object *key) { | 52 | ht_hash(const HashTable *table, const Object *key) { |
40 | uint64_t hash = 0x65d9d65f6a19574f; | 53 | uint64_t hash; |
41 | // printf("HASHING: "); | 54 | switch (key->type) { |
42 | // display(key); | 55 | case OBJ_TYPE_FIXNUM: { |
43 | // printf("\n"); | 56 | hash = key->fixnum; |
44 | return 0; | 57 | } break; |
58 | case OBJ_TYPE_STRING: { | ||
59 | hash = _xor_shift_hash(key->string, array_size(key->string)); | ||
60 | } break; | ||
61 | case OBJ_TYPE_SYMBOL: { | ||
62 | hash = _xor_shift_hash(key->symbol, array_size(key->symbol)); | ||
63 | } break; | ||
64 | case OBJ_TYPE_BOOL: | ||
65 | case OBJ_TYPE_NIL: | ||
66 | case OBJ_TYPE_PAIR: | ||
67 | case OBJ_TYPE_LAMBDA: | ||
68 | case OBJ_TYPE_PROCEDURE: | ||
69 | case OBJ_TYPE_ERR: { | ||
70 | hash = (uintptr_t)key; | ||
71 | } break; | ||
72 | } | ||
73 | hash = _fibonacci_hash(hash, table->shift_amount); | ||
74 | return hash; | ||
45 | } | 75 | } |
46 | 76 | ||
47 | static inline float | 77 | static inline float |
@@ -88,7 +118,7 @@ _ht_insert(HashTable *table, const Object *key, const Object *value) { | |||
88 | } | 118 | } |
89 | 119 | ||
90 | void | 120 | void |
91 | ht_maybe_grow(HashTable *table) { | 121 | _ht_maybe_grow(HashTable *table) { |
92 | HashTablePair *pairs = table->pairs; | 122 | HashTablePair *pairs = table->pairs; |
93 | if (ht_load_factor(table) < HT_LOAD_THRESHOLD) { | 123 | if (ht_load_factor(table) < HT_LOAD_THRESHOLD) { |
94 | return; | 124 | return; |
@@ -100,6 +130,7 @@ ht_maybe_grow(HashTable *table) { | |||
100 | for (size_t i = 0; i < array_cap(table->pairs); i++) { | 130 | for (size_t i = 0; i < array_cap(table->pairs); i++) { |
101 | table->pairs[i] = (HashTablePair){NULL, NULL}; | 131 | table->pairs[i] = (HashTablePair){NULL, NULL}; |
102 | } | 132 | } |
133 | table->shift_amount++; | ||
103 | 134 | ||
104 | // Hash everything in the table for the new array capacity. | 135 | // Hash everything in the table for the new array capacity. |
105 | for (size_t i = 0; i < array_cap(pairs); i++) { | 136 | for (size_t i = 0; i < array_cap(pairs); i++) { |
@@ -114,7 +145,7 @@ ht_maybe_grow(HashTable *table) { | |||
114 | 145 | ||
115 | void | 146 | void |
116 | ht_insert(HashTable *table, const Object *key, const Object *value) { | 147 | ht_insert(HashTable *table, const Object *key, const Object *value) { |
117 | ht_maybe_grow(table); | 148 | _ht_maybe_grow(table); |
118 | _ht_insert(table, key, value); | 149 | _ht_insert(table, key, value); |
119 | return; | 150 | return; |
120 | } | 151 | } |
@@ -139,6 +170,9 @@ ht_lookup(const HashTable *table, const Object *key) { | |||
139 | } else { | 170 | } else { |
140 | probe_position++; | 171 | probe_position++; |
141 | } | 172 | } |
173 | if (probe_position == position) { | ||
174 | return NULL; | ||
175 | } | ||
142 | } | 176 | } |
143 | return pairs[probe_position].value; | 177 | return pairs[probe_position].value; |
144 | } | 178 | } |
@@ -172,29 +206,4 @@ ht_free(HashTable *table) { | |||
172 | free(table); | 206 | free(table); |
173 | } | 207 | } |
174 | 208 | ||
175 | // // Use Fibonacci hashing to map a hash to a value in range of the table. | ||
176 | // static inline | ||
177 | // uint64_t _fibonacci_hash(uint64_t hash, size_t shift_amount) { | ||
178 | // return (hash * UINT64_C(11400714819323198485)) >> (64 - shift_amount); | ||
179 | // } | ||
180 | |||
181 | // // Hash a null terminated string using a circular shift + XOR hash function. | ||
182 | // static inline | ||
183 | // uint64_t _string_hash(const HashStash *table, const char *key) { | ||
184 | // uint64_t hash = 0x65d9d65f6a19574f; | ||
185 | // while (*key) { | ||
186 | // hash ^= (uint64_t)*key++; | ||
187 | // hash = (hash << 8) | (hash >> (64 - 8)); | ||
188 | // } | ||
189 | // return _fibonacci_hash(hash, table->shift_amount); | ||
190 | // } | ||
191 | |||
192 | // // Return the key as an unsigned integer. | ||
193 | // static inline | ||
194 | // uint64_t _number_hash(const HashStash *table, const char *key) { | ||
195 | // uint64_t hash = 0; | ||
196 | // memcpy(&hash, key, table->key_length); | ||
197 | // return _fibonacci_hash(hash, table->shift_amount); | ||
198 | // } | ||
199 | |||
200 | #endif // BDL_HASHTABLE_H | 209 | #endif // BDL_HASHTABLE_H |