File Coverage

lib/SPVM/Builder/src/spvm_hash.c
Criterion Covered Total %
statement 193 205 94.1
branch 96 130 73.8
condition n/a
subroutine n/a
pod n/a
total 289 335 86.2


line stmt bran cond sub pod time code
1             // Copyright (c) 2023 Yuki Kimoto
2             // MIT License
3              
4             #include
5             #include
6             #include
7              
8             #include "spvm_hash.h"
9             #include "spvm_allocator.h"
10              
11 530498           SPVM_HASH* SPVM_HASH_new(SPVM_ALLOCATOR* allocator, int32_t table_capacity, int32_t memory_block_type) {
12            
13 530498 50         assert(table_capacity >= 0);
14              
15             // Create hash
16             SPVM_HASH* hash;
17 530498 100         if (memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_TMP) {
18 3740           hash = SPVM_ALLOCATOR_alloc_memory_block_tmp(allocator, sizeof(SPVM_HASH));
19             }
20 526758 50         else if (memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT) {
21 526758           hash = SPVM_ALLOCATOR_alloc_memory_block_permanent(allocator, sizeof(SPVM_HASH));
22             }
23             else {
24 0           assert(0);
25             }
26            
27             // Default table capacity
28 530498 100         if (table_capacity == 0) {
29 368751           hash->table_capacity = 1;
30             }
31             else {
32 161747           hash->table_capacity = table_capacity;
33             }
34            
35             // Initialize table
36 530498 100         if (memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_TMP) {
37 3740           hash->table = SPVM_ALLOCATOR_alloc_memory_block_tmp(allocator, hash->table_capacity * sizeof(int32_t));
38             }
39 526758 50         else if (memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT) {
40 526758           hash->table = SPVM_ALLOCATOR_alloc_memory_block_permanent(allocator, hash->table_capacity * sizeof(int32_t));
41             }
42             else {
43 0           assert(0);
44             }
45              
46 530498           memset(hash->table, -1, hash->table_capacity * sizeof(int32_t));
47            
48             // Initialize entries
49 530498           hash->entries_capacity = 1;
50              
51 530498 100         if (memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_TMP) {
52 3740           hash->entries = SPVM_ALLOCATOR_alloc_memory_block_tmp(allocator, hash->entries_capacity * sizeof(SPVM_HASH_ENTRY));
53             }
54 526758 50         else if (memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT) {
55 526758           hash->entries = SPVM_ALLOCATOR_alloc_memory_block_permanent(allocator, hash->entries_capacity * sizeof(SPVM_HASH_ENTRY));
56             }
57             else {
58 0           assert(0);
59             }
60 530498           hash->entries_length = 0;
61              
62             // Initialize key buffer
63 530498           hash->key_buffer_capacity = 1;
64 530498 100         if (memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_TMP) {
65 3740           hash->key_buffer = SPVM_ALLOCATOR_alloc_memory_block_tmp(allocator, hash->key_buffer_capacity);
66             }
67 526758 50         else if (memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT) {
68 526758           hash->key_buffer = SPVM_ALLOCATOR_alloc_memory_block_permanent(allocator, hash->key_buffer_capacity);
69             }
70             else {
71 0           assert(0);
72             }
73              
74 530498           hash->key_buffer_length = 0;
75              
76 530498           hash->allocator = allocator;
77            
78 530498           hash->memory_block_type = memory_block_type;
79            
80 530498           return hash;
81             }
82              
83 424677           SPVM_HASH* SPVM_HASH_new_hash_permanent(SPVM_ALLOCATOR* allocator, int32_t capacity) {
84             (void)allocator;
85              
86 424677           int32_t memory_block_type = SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT;
87 424677           SPVM_HASH* hash = SPVM_HASH_new(allocator, capacity, memory_block_type);
88            
89 424677           return hash;
90             }
91              
92 1900518           void SPVM_HASH_set(SPVM_HASH* hash, const char* key, int32_t length, void* value) {
93            
94 1900518 50         assert(hash);
95 1900518 50         assert(key);
96 1900518 50         assert(length >= 0);
97            
98             // Rehash
99 1900518 100         if (hash->entries_length > hash->table_capacity * 0.75) {
100 102083           int32_t new_table_capacity = (hash->table_capacity * 2) + 1;
101            
102 102083           SPVM_HASH_rehash(hash, new_table_capacity);
103             }
104            
105 1900518           SPVM_HASH_set_norehash(hash, key, length, value);
106 1900518           }
107              
108 18637023           void* SPVM_HASH_get(SPVM_HASH* hash, const char* key, int32_t length) {
109 18637023           int32_t exists = 0;
110 18637023           return SPVM_HASH_get_with_exists(hash, key, length, &exists);
111             }
112              
113 18637023           void* SPVM_HASH_get_with_exists(SPVM_HASH* hash, const char* key, int32_t length, int32_t* exists) {
114              
115 18637023 50         assert(hash);
116 18637023 50         assert(length >= 0);
117            
118 18637023           int32_t hash_value = SPVM_HASH_calc_hash_value(key, length);
119 18637023           int32_t table_index = hash_value % hash->table_capacity;
120            
121 18637023           int32_t entry_index = -1;
122 18637023 100         if (hash->table[table_index] != -1) {
123 16559848           entry_index = hash->table[table_index];
124             }
125             while (1) {
126 23758047 50         assert(entry_index >= -1);
127 23758047 100         if (entry_index != -1) {
128 20846893           int32_t match = 0;
129             int32_t key_length;
130 20846893           memcpy(&key_length, &hash->key_buffer[hash->entries[entry_index].key_index], sizeof(int32_t));
131 20846893 100         if (length == 0 && key_length == 0) {
    100          
132 129527           match = 1;
133             }
134 20717366 100         else if (key_length == length && memcmp(key, &hash->key_buffer[hash->entries[entry_index].key_index + sizeof(int32_t)], length) == 0) {
    100          
135 15596342           match = 1;
136             }
137            
138 20846893 100         if (match) {
139 15725869           *exists = 1;
140 15725869           return hash->entries[entry_index].value;
141             }
142             else {
143 5121024 100         if (hash->entries[entry_index].next_index == -1) {
144 833979           entry_index = -1;
145             }
146             else {
147 5121024           entry_index = hash->entries[entry_index].next_index;
148             }
149             }
150             }
151             else {
152 2911154           return NULL;
153             }
154 5121024           }
155             }
156              
157 3738           void SPVM_HASH_free(SPVM_HASH* hash) {
158              
159 3738           SPVM_ALLOCATOR* allocator = hash->allocator;
160            
161 3738 50         assert(hash);
162              
163 3738 50         if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_TMP) {
164 3738           SPVM_ALLOCATOR_free_memory_block_tmp(allocator, hash->table);
165 3738           SPVM_ALLOCATOR_free_memory_block_tmp(allocator, hash->entries);
166 3738           SPVM_ALLOCATOR_free_memory_block_tmp(allocator, hash->key_buffer);
167 3738           SPVM_ALLOCATOR_free_memory_block_tmp(allocator, hash);
168             }
169 0 0         else if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT) {
170             // Nothing
171             }
172             else {
173 0           assert(0);
174             }
175 3738           }
176              
177 3502019           void SPVM_HASH_maybe_extend_entries(SPVM_HASH* hash) {
178              
179 3502019           SPVM_ALLOCATOR* allocator = hash->allocator;
180            
181 3502019 50         assert(hash);
182            
183 3502019           int32_t entries_length = hash->entries_length;
184            
185 3502019 50         assert(entries_length >= 0);
186            
187 3502019           int32_t entries_capacity = hash->entries_capacity;
188            
189 3502019 100         if (entries_length >= entries_capacity) {
190 481079           int32_t new_entries_capacity = entries_capacity * 2;
191            
192             SPVM_HASH_ENTRY* new_entries;
193 481079 100         if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_TMP) {
194 2           new_entries = SPVM_ALLOCATOR_alloc_memory_block_tmp(allocator, new_entries_capacity * sizeof(SPVM_HASH_ENTRY));
195             }
196 481077 50         else if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT) {
197 481077           new_entries = SPVM_ALLOCATOR_alloc_memory_block_permanent(allocator, new_entries_capacity * sizeof(SPVM_HASH_ENTRY));
198             }
199             else {
200 0           assert(0);
201             }
202              
203 481079           memcpy(new_entries, hash->entries, entries_capacity * sizeof(SPVM_HASH_ENTRY));
204 481079 100         if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_TMP) {
205 2           SPVM_ALLOCATOR_free_memory_block_tmp(allocator, hash->entries);
206             }
207 481077 50         else if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT) {
208             // Nothing
209             }
210             else {
211 0           assert(0);
212             }
213              
214 481079           hash->entries = new_entries;
215            
216 481079           hash->entries_capacity = new_entries_capacity;
217             }
218 3502019           }
219              
220 3502019           void SPVM_HASH_maybe_extend_key_buffer(SPVM_HASH* hash, int32_t length) {
221            
222 3502019           SPVM_ALLOCATOR* allocator = hash->allocator;
223              
224 3502019 50         assert(hash);
225            
226 3502019           int32_t key_buffer_length = hash->key_buffer_length;
227            
228 3502019 50         assert(key_buffer_length >= 0);
229            
230 3502019           int32_t key_buffer_capacity = hash->key_buffer_capacity;
231            
232 3502019 100         if (key_buffer_length + length + (int32_t)sizeof(int32_t) >= key_buffer_capacity) {
233 571682           int32_t new_key_buffer_capacity = (key_buffer_length + length + sizeof(int32_t)) * 2;
234            
235             char* new_key_buffer;
236 571682 100         if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_TMP) {
237 19           new_key_buffer = SPVM_ALLOCATOR_alloc_memory_block_tmp(allocator, new_key_buffer_capacity);
238             }
239 571663 50         else if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT) {
240 571663           new_key_buffer = SPVM_ALLOCATOR_alloc_memory_block_permanent(allocator, new_key_buffer_capacity);
241             }
242             else {
243 0           assert(0);
244             }
245              
246 571682           memcpy(new_key_buffer, hash->key_buffer, key_buffer_capacity);
247 571682 100         if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_TMP) {
248 19           SPVM_ALLOCATOR_free_memory_block_tmp(allocator, hash->key_buffer);
249             }
250 571663 50         else if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT) {
251             // Nothing
252             }
253             else {
254 0           assert(0);
255             }
256              
257 571682           hash->key_buffer = new_key_buffer;
258              
259 571682           hash->key_buffer_capacity = new_key_buffer_capacity;
260             }
261 3502019           }
262              
263 3502019           int32_t SPVM_HASH_new_hash_entry(SPVM_HASH* hash, const char* key, int32_t key_length, void* value) {
264            
265 3502019 50         assert(hash);
266 3502019 50         assert(key);
267            
268 3502019           int32_t index = hash->entries_length;
269            
270 3502019           SPVM_HASH_maybe_extend_entries(hash);
271            
272 3502019           SPVM_HASH_maybe_extend_key_buffer(hash, key_length);
273            
274 3502019           hash->entries[index].key_index = hash->key_buffer_length;
275            
276             // Copy key length
277 3502019           memcpy(&hash->key_buffer[hash->key_buffer_length], &key_length, sizeof(int32_t));
278            
279             // Copy key
280 3502019           memcpy(&hash->key_buffer[hash->key_buffer_length + sizeof(int32_t)], key, key_length);
281            
282 3502019           hash->key_buffer_length += sizeof(int32_t) + key_length;
283            
284 3502019           hash->entries[index].value = value;
285 3502019           hash->entries[index].next_index = -1;
286            
287 3502019           hash->entries_length++;
288            
289 3502019           return index;
290             }
291              
292 102083           void SPVM_HASH_rehash(SPVM_HASH* hash, int32_t new_table_capacity) {
293            
294 102083 50         assert(hash);
295 102083 50         assert(new_table_capacity > 0);
296            
297 102083           SPVM_ALLOCATOR* allocator = hash->allocator;
298              
299             // Create new hash
300 102083           SPVM_HASH* new_hash = SPVM_HASH_new(allocator, new_table_capacity, hash->memory_block_type);
301            
302             // Rehash
303             {
304             int32_t i;
305 1758175 100         for (i = 0; i < hash->entries_length; i++) {
306             int32_t key_length;
307 1656092           memcpy(&key_length, &hash->key_buffer[hash->entries[i].key_index], sizeof(int32_t));
308 1656092           const char* key = &hash->key_buffer[hash->entries[i].key_index + sizeof(int32_t)];
309            
310 1656092           void* value = hash->entries[i].value;
311            
312 1656092           SPVM_HASH_set_norehash(new_hash, key, key_length, value);
313             }
314             }
315            
316             // Replace hash fields
317 102083 100         if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_TMP) {
318 2           SPVM_ALLOCATOR_free_memory_block_tmp(allocator, hash->table);
319 2           SPVM_ALLOCATOR_free_memory_block_tmp(allocator, hash->entries);
320 2           SPVM_ALLOCATOR_free_memory_block_tmp(allocator, hash->key_buffer);
321             }
322 102081 50         else if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT) {
323             // Nothing
324             }
325             else {
326 0           assert(0);
327             }
328              
329 102083           hash->entries_length = new_hash->entries_length;
330 102083           hash->table_capacity = new_hash->table_capacity;
331 102083           hash->entries_capacity = new_hash->entries_capacity;
332 102083           hash->table = new_hash->table;
333 102083           hash->entries = new_hash->entries;
334            
335 102083           hash->key_buffer_capacity = new_hash->key_buffer_capacity;
336 102083           hash->key_buffer_length = new_hash->key_buffer_length;
337 102083           hash->key_buffer = new_hash->key_buffer;
338            
339 102083 100         if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_TMP) {
340 2           SPVM_ALLOCATOR_free_memory_block_tmp(allocator, new_hash);
341             }
342 102081 50         else if (hash->memory_block_type == SPVM_ALLOCATOR_C_ALLOC_TYPE_PERMANENT) {
343             // Nothing
344             }
345             else {
346 0           assert(0);
347             }
348 102083           }
349              
350 3556610           void SPVM_HASH_set_norehash(SPVM_HASH* hash, const char* key, int32_t length, void* value) {
351            
352 3556610 50         assert(hash);
353 3556610 50         assert(key);
354 3556610 50         assert(length >= 0);
355            
356 3556610           int32_t hash_value = SPVM_HASH_calc_hash_value(key, length);
357 3556610           int32_t table_index = hash_value % hash->table_capacity;
358            
359 3556610 50         assert(hash->table[table_index] >= -1);
360            
361 3556610 100         if (hash->table[table_index] != -1) {
362            
363 852473           int32_t entry_index = hash->table[table_index];
364             while (1) {
365 1031139           int32_t match = 0;
366             int32_t key_length;
367 1031139           memcpy(&key_length, &hash->key_buffer[hash->entries[entry_index].key_index], sizeof(int32_t));
368 1031139 100         if (key_length == 0 && length == 0) {
    100          
369 18           match = 1;
370             }
371 1031121 100         else if (key_length == length && memcmp(key, &hash->key_buffer[hash->entries[entry_index].key_index + sizeof(int32_t)], length) == 0) {
    100          
372 54573           match = 1;
373             }
374            
375 1031139 100         if (match) {
376 54591           hash->entries[entry_index].value = value;
377 852473           break;
378             }
379             else {
380 976548 100         if (hash->entries[entry_index].next_index != -1) {
381 178666           entry_index = hash->entries[entry_index].next_index;
382             }
383             else {
384 797882           int32_t new_entry_index = SPVM_HASH_new_hash_entry(hash, key, length, value);
385 797882           hash->entries[entry_index].next_index = new_entry_index;
386 797882           break;
387             }
388             }
389 178666           }
390             }
391             else {
392 2704137           int32_t new_entry_index = SPVM_HASH_new_hash_entry(hash, key, length, value);
393 2704137           hash->table[table_index] = new_entry_index;
394             }
395 3556610           }
396              
397 22193633           int32_t SPVM_HASH_calc_hash_value(const char* str, int32_t len) {
398            
399 22193633 50         assert(len >= 0);
400            
401 22193633           const char* str_tmp = str;
402 22193633           int32_t hash = 5381;
403 247252758 100         while (len--) {
404 225059125           hash = ((hash << 5) + hash) + (uint8_t) *str_tmp++;
405             }
406            
407 22193633 100         if (hash < 0) {
408 6864154           hash = ~hash;
409             }
410            
411 22193633           return hash;
412             }