/builds/xfbs/passgen/src/container/hashmap.c

Source (jump to first uncovered line)
#include "passgen/container/hashmap.h"
#include "passgen/util/siphash.h"
#include <stdlib.h>
#define UNUSED(x) (void) x

static const size_t hashmap_sizes[] = {
    3,
    7,
    17,
    37,
    79,
    163,
    331,
    673,
    1361,
    2729,
    5471,
    10949,
    21911,
    43853,
    87719,
    175447,
    350899,
    701819,
    0};

struct siphash_keys {
    const char *first;
    const char *second;
};

static const struct siphash_keys utf8_keys = {
    .first = "someverylongpass",
    .second = "myotherverylongk",
};

static const struct siphash_keys utf32_keys = {
    .first = "someverylongpass",
    .second = "myotherverylongk",
};

void passgen_hashmap_init(
    passgen_hashmap *map,
    const passgen_hashmap_context *context) {
    // zero-out hashmap
    memset(map, 0, sizeof(*map));

    // set context or default to UTF-8 context
    if(context) {
        map->context = context;
    } else {
        map->context = &passgen_hashmap_context_utf8;
    }

    // initialize hashmap context
    map->context->init(map);
}

void passgen_hashmap_free(passgen_hashmap *map) {
    // deinitialize context
    map->context->fini(map);

    // deallocate data
    free(map->data);

    // set everything to zero
    memset(map, 0, sizeof(*map));
}

void passgen_hashmap_realloc(passgen_hashmap *map, size_t capacity) {
    // save previous hashmap
    passgen_hashmap old = *map;

    map->data = calloc(capacity, sizeof(passgen_hashmap_entry));
    map->capacity = capacity;
    map->len = 0;

    // copy data over
    for(size_t i = 0; i < old.capacity; i++87.5k) {
        if(old.data[i].key) {
            passgen_hashmap_insert(map, old.data[i].key, old.data[i].value);
        }
    }

    free(old.data);
}

static inline size_t passgen_hashmap_position(
    const passgen_hashmap *map,
    const void *key,
    bool first) {
    return map->context->hash(map, key, first) % map->capacity;
}

static inline bool passgen_hashmap_move(passgen_hashmap *map, size_t pos) {
    const void *key = map->data[pos].key;
    bool first = passgen_hashmap_position(map, key, true) == pos;
    size_t other_pos = passgen_hashmap_position(map, key, !first);
    if(!map->data[other_pos].key) {
        map->data[other_pos].key = map->data[pos].key;
        map->data[other_pos].value = map->data[pos].value;
        return true;
    }
    return false;
}

static inline size_t next_capacity(passgen_hashmap *map) {
    size_t i;
    for(i = 0; hashmap_sizes[i]; i++91) {
        if(hashmap_sizes[i] >= map->capacity) {
            break;
        }
    }
    if(hashmap_sizes[i] && hashmap_sizes[i + 1]) {
        return hashmap_sizes[i + 1];
    } else {
        return 2 * map->capacity - 1;
    }
}

passgen_hashmap_entry
passgen_hashmap_insert(passgen_hashmap *map, const void *key, void *value) {
    if(map->capacity == 0) {
        passgen_hashmap_realloc(map, hashmap_sizes[0]);
    }

    size_t hash;

    hash = passgen_hashmap_position(map, key, true);
    if(!map->data[hash].key) {
        map->data[hash].key = key;
        map->data[hash].value = value;
        map->len += 1;
        return (passgen_hashmap_entry){NULL, NULL};
    } else {
        if(map->context->equal(map, map->data[hash].key, key)) {
            passgen_hashmap_entry entry = map->data[hash];
            map->data[hash].key = key;
            map->data[hash].value = value;
            return entry;
        } else if(passgen_hashmap_move(map, hash)) {
            map->data[hash].key = key;
            map->data[hash].value = value;
            map->len += 1;
            return (passgen_hashmap_entry){NULL, NULL};
        }
    }

    hash = passgen_hashmap_position(map, key, false);
    if(!map->data[hash].key) {
        map->data[hash].key = key;
        map->data[hash].value = value;
        map->len += 1;
        return (passgen_hashmap_entry){NULL, NULL};
    } else {
        if(map->context->equal(map, map->data[hash].key, key)) {
            passgen_hashmap_entry entry = map->data[hash];
            map->data[hash].key = key;
            map->data[hash].value = value;
            return entry;
        } else if(passgen_hashmap_move(map, hash)) {
            map->data[hash].key = key;
            map->data[hash].value = value;
            map->len += 1;
            return (passgen_hashmap_entry){NULL, NULL};
        }
    }

    passgen_hashmap_realloc(map, next_capacity(map));
    return passgen_hashmap_insert(map, key, value);
}

passgen_hashmap_entry
passgen_hashmap_remove(passgen_hashmap *map, const void *key) {
    size_t hash;

    // if this key exists
    hash = passgen_hashmap_position(map, key, true);
    if(map->data[hash].key) {
        // and it matches
        if(map->context->equal(map, map->data[hash].key, key)) {
            passgen_hashmap_entry entry = map->data[hash];
            map->data[hash].key = NULL;
            map->data[hash].value = NULL;
            map->len -= 1;
            return entry;
        }
    }

    // if this key exists
    hash = passgen_hashmap_position(map, key, false);
    if(map->data[hash].key) {
        // and it matches
        if(map->context->equal(map, map->data[hash].key, key)) {
            passgen_hashmap_entry entry = map->data[hash];
            map->data[hash].key = NULL;
            map->data[hash].value = NULL;
            map->len -= 1;
            return entry;
        }
    }

    return (passgen_hashmap_entry){NULL, NULL};
}

passgen_hashmap_entry *
passgen_hashmap_lookup(const passgen_hashmap *map, const void *key) {
    // make sure the hashmap is not empty
    if(!map->data) {
        return NULL;
    }

    size_t hash;

    // lookup first possible location
    hash = passgen_hashmap_position(map, key, true);
    if(map->data[hash].key &&
       map->context->equal(map, map->data[hash].key, key)10.0k) {
        return &map->data[hash];
    }

    // lookup second possible location
    hash = passgen_hashmap_position(map, key, false);
    if(map->data[hash].key &&
       map->context->equal(map, map->data[hash].key, key)609) {
        return &map->data[hash];
    }

    return NULL;
}

int passgen_hashmap_foreach(
    const passgen_hashmap *map,
    void *user,
    int (*func)(void *user, passgen_hashmap_entry *entry)) {
    if(map->len) {
        for(size_t i = 0; i < map->capacity; i++87.7k) {
            if(map->data[i].key) {
                int ret = func(user, &map->data[i]);
                if(ret != 0) {
                    return ret;
                }
            }
        }
    }

    return 07;
}

static void utf8_init(passgen_hashmap *map) {
    map->context_data = (void *) &utf8_keys;
}

static void utf8_fini(passgen_hashmap *map) {
    map->context_data = NULL;
}

static uint64_t
utf8_hash(const passgen_hashmap *map, const void *key, bool first) {
    UNUSED(map);
    uint64_t output;
    const struct siphash_keys *keys = map->context_data;
    const char *siphash_key = first ? keys->first35.9k : keys->second2.65k;
    passgen_siphash(
        key,
        strlen(key),
        siphash_key,
        (uint8_t *) &output,
        sizeof(output));
    return output;
}

static bool
utf8_equal(const passgen_hashmap *map, const void *lhs, const void *rhs) {
    UNUSED(map);
    return strcmp(lhs, rhs) == 0;
}

const passgen_hashmap_context passgen_hashmap_context_utf8 = {
    .hash = utf8_hash,
    .equal = utf8_equal,
    .init = utf8_init,
    .fini = utf8_fini,
};

static size_t utf32_len(const void *data) {
    // cast void pointer to array of UTF-32 codepoints
    const int32_t *utf32 = data;

    // iterate over until we hit zero codepoint
    size_t len = 0;
    while(utf32[len]) {
        len++;
    }

    return len;
}

static uint64_t
utf32_hash(const passgen_hashmap *map, const void *key, bool first) {
    UNUSED(map);
    uint64_t output;
    const struct siphash_keys *keys = map->context_data;
    const char *siphash_key = first ? keys->first7 : keys->second2;
    passgen_siphash(
        key,
        utf32_len(key),
        siphash_key,
        (uint8_t *) &output,
        sizeof(output));
    return output;
}

static bool
utf32_equal(const passgen_hashmap *map, const void *lhs, const void *rhs) {
    UNUSED(map);
    // compute lengths of lhs and rhs
    size_t rhs_len = utf32_len(rhs);
    size_t lhs_len = utf32_len(lhs);

    // if lengths are not the same, the keys cannot be equal
    if(rhs_len != lhs_len) {
        return false;
    }

    // compare lhs and rhs
    int ret = memcmp(lhs, rhs, rhs_len * sizeof(uint32_t));

    // return true if comparison was equal
    return ret == 0;
}

static void utf32_init(passgen_hashmap *map) {
    map->context_data = (void *) &utf32_keys;
}

static void utf32_fini(passgen_hashmap *map) {
    map->context_data = NULL;
}

const passgen_hashmap_context passgen_hashmap_context_utf32 = {
    .hash = utf32_hash,
    .equal = utf32_equal,
    .init = utf32_init,
    .fini = utf32_fini,
};

int passgen_hashmap_entry_free(void *user, passgen_hashmap_entry *entry) {
    (void) user;
    free((void *) entry->key);
    free(entry->value);
    return 0;
}

Coverage Report

Created: 2024-05-03 06:05

Line	Count	Source (jump to first uncovered line)
1		#include "passgen/container/hashmap.h"
2		#include "passgen/util/siphash.h"
3		#include <stdlib.h>
4	51.1k	#define UNUSED(x) (void) x
5
6		static const size_t hashmap_sizes[] = {
7		3,
8		7,
9		17,
10		37,
11		79,
12		163,
13		331,
14		673,
15		1361,
16		2729,
17		5471,
18		10949,
19		21911,
20		43853,
21		87719,
22		175447,
23		350899,
24		701819,
25		0};
26
27		struct siphash_keys {
28		const char *first;
29		const char *second;
30		};
31
32		static const struct siphash_keys utf8_keys = {
33		.first = "someverylongpass",
34		.second = "myotherverylongk",
35		};
36
37		static const struct siphash_keys utf32_keys = {
38		.first = "someverylongpass",
39		.second = "myotherverylongk",
40		};
41
42		void passgen_hashmap_init(
43		passgen_hashmap *map,
44	95	const passgen_hashmap_context *context) {
45	95	// zero-out hashmap
46	95	memset(map, 0, sizeof(*map));
47	95
48	95	// set context or default to UTF-8 context
49	95	if(context) {
50	89	map->context = context;
51	89	} else {
52	6	map->context = &passgen_hashmap_context_utf8;
53	6	}
54	95
55	95	// initialize hashmap context
56	95	map->context->init(map);
57	95	}
58
59	19	void passgen_hashmap_free(passgen_hashmap *map) {
60	19	// deinitialize context
61	19	map->context->fini(map);
62	19
63	19	// deallocate data
64	19	free(map->data);
65	19
66	19	// set everything to zero
67	19	memset(map, 0, sizeof(*map));
68	19	}
69
70	20	void passgen_hashmap_realloc(passgen_hashmap *map, size_t capacity) {
71	20	// save previous hashmap
72	20	passgen_hashmap old = *map;
73	20
74	20	map->data = calloc(capacity, sizeof(passgen_hashmap_entry));
75	20	map->capacity = capacity;
76	20	map->len = 0;
77	20
78	20	// copy data over
79	87.6k	for(size_t i = 0; i < old.capacity; i++87.5k ) {
80	87.5k	if(old.data[i].key) {
81	13.9k	passgen_hashmap_insert(map, old.data[i].key, old.data[i].value);
82	13.9k	}
83	87.5k	}
84	20
85	20	free(old.data);
86	20	}
87
88		static inline size_t passgen_hashmap_position(
89		const passgen_hashmap *map,
90		const void *key,
91	38.6k	bool first) {
92	38.6k	return map->context->hash(map, key, first) % map->capacity;
93	38.6k	}
94
95	1.85k	static inline bool passgen_hashmap_move(passgen_hashmap *map, size_t pos) {
96	1.85k	const void *key = map->data[pos].key;
97	1.85k	bool first = passgen_hashmap_position(map, key, true) == pos;
98	1.85k	size_t other_pos = passgen_hashmap_position(map, key, !first);
99	1.85k	if(!map->data[other_pos].key) {
100	1.56k	map->data[other_pos].key = map->data[pos].key;
101	1.56k	map->data[other_pos].value = map->data[pos].value;
102	1.56k	return true;
103	1.56k	}
104	291	return false;
105	291	}
106
107	15	static inline size_t next_capacity(passgen_hashmap *map) {
108	15	size_t i;
109	106	for(i = 0; hashmap_sizes[i]; i++91 ) {
110	106	if(hashmap_sizes[i] >= map->capacity) {
111	15	break;
112	15	}
113	106	}
114	15	if(hashmap_sizes[i] && hashmap_sizes[i + 1]) {
115	15	return hashmap_sizes[i + 1];
116	15	} else {
117	0	return 2 * map->capacity - 1;
118	0	}
119	15	}
120
121		passgen_hashmap_entry
122	24.0k	passgen_hashmap_insert(passgen_hashmap map, const void key, void *value) {
123	24.0k	if(map->capacity == 0) {
124	5	passgen_hashmap_realloc(map, hashmap_sizes[0]);
125	5	}
126	24.0k
127	24.0k	size_t hash;
128	24.0k
129	24.0k	hash = passgen_hashmap_position(map, key, true);
130	24.0k	if(!map->data[hash].key) {
131	22.2k	map->data[hash].key = key;
132	22.2k	map->data[hash].value = value;
133	22.2k	map->len += 1;
134	22.2k	return (passgen_hashmap_entry){NULL, NULL};
135	22.2k	} else {
136	1.81k	if(map->context->equal(map, map->data[hash].key, key)) {
137	0	passgen_hashmap_entry entry = map->data[hash];
138	0	map->data[hash].key = key;
139	0	map->data[hash].value = value;
140	0	return entry;
141	1.81k	} else if(passgen_hashmap_move(map, hash)) {
142	1.53k	map->data[hash].key = key;
143	1.53k	map->data[hash].value = value;
144	1.53k	map->len += 1;
145	1.53k	return (passgen_hashmap_entry){NULL, NULL};
146	1.53k	}
147	276	}
148	276
149	276	hash = passgen_hashmap_position(map, key, false);
150	276	if(!map->data[hash].key) {
151	229	map->data[hash].key = key;
152	229	map->data[hash].value = value;
153	229	map->len += 1;
154	229	return (passgen_hashmap_entry){NULL, NULL};
155	229	} else {
156	47	if(map->context->equal(map, map->data[hash].key, key)) {
157	0	passgen_hashmap_entry entry = map->data[hash];
158	0	map->data[hash].key = key;
159	0	map->data[hash].value = value;
160	0	return entry;
161	47	} else if(passgen_hashmap_move(map, hash)) {
162	32	map->data[hash].key = key;
163	32	map->data[hash].value = value;
164	32	map->len += 1;
165	32	return (passgen_hashmap_entry){NULL, NULL};
166	32	}
167	15	}
168	15
169	15	passgen_hashmap_realloc(map, next_capacity(map));
170	15	return passgen_hashmap_insert(map, key, value);
171	15	}
172
173		passgen_hashmap_entry
174	2	passgen_hashmap_remove(passgen_hashmap map, const void key) {
175	2	size_t hash;
176	2
177	2	// if this key exists
178	2	hash = passgen_hashmap_position(map, key, true);
179	2	if(map->data[hash].key) {
180	2	// and it matches
181	2	if(map->context->equal(map, map->data[hash].key, key)) {
182	1	passgen_hashmap_entry entry = map->data[hash];
183	1	map->data[hash].key = NULL;
184	1	map->data[hash].value = NULL;
185	1	map->len -= 1;
186	1	return entry;
187	1	}
188	1	}
189	1
190	1	// if this key exists
191	1	hash = passgen_hashmap_position(map, key, false);
192	1	if(map->data[hash].key) {
193	1	// and it matches
194	1	if(map->context->equal(map, map->data[hash].key, key)) {
195	1	passgen_hashmap_entry entry = map->data[hash];
196	1	map->data[hash].key = NULL;
197	1	map->data[hash].value = NULL;
198	1	map->len -= 1;
199	1	return entry;
200	1	}
201	0	}
202	0
203	0	return (passgen_hashmap_entry){NULL, NULL};
204	0	}
205
206		passgen_hashmap_entry *
207	10.0k	passgen_hashmap_lookup(const passgen_hashmap map, const void key) {
208	10.0k	// make sure the hashmap is not empty
209	10.0k	if(!map->data) {
210	1	return NULL;
211	1	}
212	10.0k
213	10.0k	size_t hash;
214	10.0k
215	10.0k	// lookup first possible location
216	10.0k	hash = passgen_hashmap_position(map, key, true);
217	10.0k	if(map->data[hash].key &&
218	10.0k	map->context->equal(map, map->data[hash].key, key)10.0k ) {
219	9.39k	return &map->data[hash];
220	9.39k	}
221	616
222	616	// lookup second possible location
223	616	hash = passgen_hashmap_position(map, key, false);
224	616	if(map->data[hash].key &&
225	616	map->context->equal(map, map->data[hash].key, key)609 ) {
226	609	return &map->data[hash];
227	609	}
228	7
229	7	return NULL;
230	7	}
231
232		int passgen_hashmap_foreach(
233		const passgen_hashmap *map,
234		void *user,
235	8	int (func)(void user, passgen_hashmap_entry *entry)) {
236	8	if(map->len) {
237	87.7k	for(size_t i = 0; i < map->capacity; i++87.7k ) {
238	87.7k	if(map->data[i].key) {
239	10.0k	int ret = func(user, &map->data[i]);
240	10.0k	if(ret != 0) {
241	1	return ret;
242	1	}
243	10.0k	}
244	87.7k	}
245	3	}
246	8
247	8	return 07 ;
248	8	}
249
250	93	static void utf8_init(passgen_hashmap *map) {
251	93	map->context_data = (void *) &utf8_keys;
252	93	}
253
254	17	static void utf8_fini(passgen_hashmap *map) {
255	17	map->context_data = NULL;
256	17	}
257
258		static uint64_t
259	38.6k	utf8_hash(const passgen_hashmap map, const void key, bool first) {
260	38.6k	UNUSED(map);
261	38.6k	uint64_t output;
262	38.6k	const struct siphash_keys *keys = map->context_data;
263	38.6k	const char *siphash_key = first ? keys->first35.9k : keys->second2.65k ;
264	38.6k	passgen_siphash(
265	38.6k	key,
266	38.6k	strlen(key),
267	38.6k	siphash_key,
268	38.6k	(uint8_t *) &output,
269	38.6k	sizeof(output));
270	38.6k	return output;
271	38.6k	}
272
273		static bool
274	12.4k	utf8_equal(const passgen_hashmap map, const void lhs, const void *rhs) {
275	12.4k	UNUSED(map);
276	12.4k	return strcmp(lhs, rhs) == 0;
277	12.4k	}
278
279		const passgen_hashmap_context passgen_hashmap_context_utf8 = {
280		.hash = utf8_hash,
281		.equal = utf8_equal,
282		.init = utf8_init,
283		.fini = utf8_fini,
284		};
285
286	21	static size_t utf32_len(const void *data) {
287	21	// cast void pointer to array of UTF-32 codepoints
288	21	const int32_t *utf32 = data;
289	21
290	21	// iterate over until we hit zero codepoint
291	21	size_t len = 0;
292	117	while(utf32[len]) {
293	96	len++;
294	96	}
295	21
296	21	return len;
297	21	}
298
299		static uint64_t
300	9	utf32_hash(const passgen_hashmap map, const void key, bool first) {
301	9	UNUSED(map);
302	9	uint64_t output;
303	9	const struct siphash_keys *keys = map->context_data;
304	9	const char *siphash_key = first ? keys->first7 : keys->second2 ;
305	9	passgen_siphash(
306	9	key,
307	9	utf32_len(key),
308	9	siphash_key,
309	9	(uint8_t *) &output,
310	9	sizeof(output));
311	9	return output;
312	9	}
313
314		static bool
315	6	utf32_equal(const passgen_hashmap map, const void lhs, const void *rhs) {
316	6	UNUSED(map);
317	6	// compute lengths of lhs and rhs
318	6	size_t rhs_len = utf32_len(rhs);
319	6	size_t lhs_len = utf32_len(lhs);
320	6
321	6	// if lengths are not the same, the keys cannot be equal
322	6	if(rhs_len != lhs_len) {
323	1	return false;
324	1	}
325	5
326	5	// compare lhs and rhs
327	5	int ret = memcmp(lhs, rhs, rhs_len * sizeof(uint32_t));
328	5
329	5	// return true if comparison was equal
330	5	return ret == 0;
331	5	}
332
333	2	static void utf32_init(passgen_hashmap *map) {
334	2	map->context_data = (void *) &utf32_keys;
335	2	}
336
337	2	static void utf32_fini(passgen_hashmap *map) {
338	2	map->context_data = NULL;
339	2	}
340
341		const passgen_hashmap_context passgen_hashmap_context_utf32 = {
342		.hash = utf32_hash,
343		.equal = utf32_equal,
344		.init = utf32_init,
345		.fini = utf32_fini,
346		};
347
348	10.0k	int passgen_hashmap_entry_free(void user, passgen_hashmap_entry entry) {
349	10.0k	(void) user;
350	10.0k	free((void *) entry->key);
351	10.0k	free(entry->value);
352	10.0k	return 0;
353	10.0k	}