/src/hoextdown/src/hash.c

Source (jump to first uncovered line)
#include "hash.h"

#include <stdlib.h>
#include <string.h>

#define HOEDOWN_HASH_ITEM_SIZE 255
#define HOEDOWN_HASH_FNV_PRIME 0x01000193
#define HOEDOWN_HASH_FNV_OFFSET_BASIS 0x811c9dc5

static char *
hoedown_hash_strndup(const char* str, size_t n)
{
    if (str) {
        char *s = (char *)malloc(sizeof(char) * (n + 1));
        if (s) {
            memcpy(s, str, n);
            s[n] = '\0';
        }
        return s;
    }
    return NULL;
}

static char *
hoedown_hash_strdup(const char* str)
{
    if (str) {
        return hoedown_hash_strndup(str, strlen(str));
    }
    return NULL;
}

static unsigned int
hoedown_hash_fnv(const char *key, const char *max, size_t limit)
{
    unsigned int hash = HOEDOWN_HASH_FNV_OFFSET_BASIS;

    if (max == NULL) {
        if (key) {
            max = key + strlen(key);
        } else {
            max = key;
        }
    }

    while (key < max) {
        hash *= HOEDOWN_HASH_FNV_PRIME;
        hash ^= *key;
        key++;
    }

    hash %= limit;

    return hash;
}

static hoedown_hash_item *
hoedown_hash_item_new(void)
{
    hoedown_hash_item *item;

    item = (hoedown_hash_item *)malloc(sizeof(hoedown_hash_item));
    if (!item) {
        return NULL;
    }

    item->key = NULL;
    item->value = NULL;
    item->destruct = NULL;
    item->next = NULL;
    item->tail = NULL;

    return item;
}

static void
hoedown_hash_item_free(hoedown_hash_item *item)
{
    if (item) {
        if (item->next) {
            hoedown_hash_item_free(item->next);
        }
        if (item->key) {
            free(item->key);
        }
        if (item->destruct) {
            (item->destruct)(item->value);
        }
        free(item);
    }
}

static int
hoedown_hash_item_push(hoedown_hash_item *item, const char *key, size_t key_len,
                       void *value, hoedown_hash_value_destruct *destruct)
{
    hoedown_hash_item *entry;

    if (!item || !key || !value) {
        return 1;
    }

    if (item->key != NULL) {
        entry = hoedown_hash_item_new();
        if (!entry) {
            return 1;
        }
    } else {
        entry = item;
    }

    if (key_len > 0) {
        entry->key = hoedown_hash_strndup(key, key_len);
    } else {
        entry->key = hoedown_hash_strdup(key);
    }
    entry->value = value;
    entry->destruct = destruct;

    if (item->tail) {
        item->tail->next = entry;
    } else if (item != entry) {
        item->next = entry;
    }
    item->tail = entry;

    return 0;
}

hoedown_hash *
hoedown_hash_new(size_t size)
{
    hoedown_hash *hash;
    size_t items_size;

    hash = (hoedown_hash *)malloc(sizeof(hoedown_hash));
    if (!hash) {
        return NULL;
    }

    if (size == 0) {
        size = HOEDOWN_HASH_ITEM_SIZE;
    }

    items_size = sizeof(hoedown_hash_item *) * size;

    hash->items = (hoedown_hash_item **)malloc(items_size);
    if (!hash->items) {
        free(hash);
        return NULL;
    }

    memset(hash->items, 0, items_size);

    hash->asize = size;

    return hash;
}

void
hoedown_hash_free(hoedown_hash *hash)
{
    if (hash) {
        if (hash->items) {
            size_t i = 0;
            while (i < hash->asize) {
                if (hash->items[i]) {
                    hoedown_hash_item_free(hash->items[i]);
                }
                ++i;
            }
            free(hash->items);
        }
        free(hash);
    }
}

int
hoedown_hash_add(hoedown_hash *hash, const char *key, size_t key_len,
                 void *value, hoedown_hash_value_destruct *destruct)
{
    unsigned int h;

    if (!hash || !key || !value) {
        return 1;
    }

    h = hoedown_hash_fnv(key, key + key_len, hash->asize);

    if (!hash->items[h]) {
        hash->items[h] = hoedown_hash_item_new();
        if (!hash->items[h]) {
            return 1;
        }
    }

    if (hoedown_hash_item_push(hash->items[h], key, key_len,
                               value, destruct) != 0) {
        return 1;
    }

    return 0;
}

void *
hoedown_hash_find(hoedown_hash *hash, char *key, size_t key_len)
{
    unsigned int h;

    if (!hash || !key) {
        return NULL;
    }

    h = hoedown_hash_fnv(key, key + key_len, hash->asize);

    if (hash->items[h]) {
        hoedown_hash_item *item = hash->items[h];
        while (item != NULL) {
            if (item->key && strncmp(item->key, key, key_len) == 0) {
                return item->value;
            }
            item = item->next;
        }
    }

    return NULL;
}

Coverage Report

Created: 2025-06-22 06:49

Line	Count	Source (jump to first uncovered line)
1		#include "hash.h"
2
3		#include <stdlib.h>
4		#include <string.h>
5
6	9.67k	#define HOEDOWN_HASH_ITEM_SIZE 255
7	418M	#define HOEDOWN_HASH_FNV_PRIME 0x01000193
8	100k	#define HOEDOWN_HASH_FNV_OFFSET_BASIS 0x811c9dc5
9
10		static char *
11		hoedown_hash_strndup(const char* str, size_t n)
12	11.9k	{
13	11.9k	if (str) {
14	11.9k	char s = (char )malloc(sizeof(char) * (n + 1));
15	11.9k	if (s) {
16	11.9k	memcpy(s, str, n);
17	11.9k	s[n] = '\0';
18	11.9k	}
19	11.9k	return s;
20	11.9k	}
21	0	return NULL;
22	11.9k	}
23
24		static char *
25		hoedown_hash_strdup(const char* str)
26	0	{
27	0	if (str) {
28	0	return hoedown_hash_strndup(str, strlen(str));
29	0	}
30	0	return NULL;
31	0	}
32
33		static unsigned int
34		hoedown_hash_fnv(const char key, const char max, size_t limit)
35	100k	{
36	100k	unsigned int hash = HOEDOWN_HASH_FNV_OFFSET_BASIS;
37
38	100k	if (max == NULL) {
39	0	if (key) {
40	0	max = key + strlen(key);
41	0	} else {
42	0	max = key;
43	0	}
44	0	}
45
46	418M	while (key < max) {
47	418M	hash *= HOEDOWN_HASH_FNV_PRIME;
48	418M	hash ^= *key;
49	418M	key++;
50	418M	}
51
52	100k	hash %= limit;
53
54	100k	return hash;
55	100k	}
56
57		static hoedown_hash_item *
58		hoedown_hash_item_new(void)
59	11.9k	{
60	11.9k	hoedown_hash_item *item;
61
62	11.9k	item = (hoedown_hash_item *)malloc(sizeof(hoedown_hash_item));
63	11.9k	if (!item) {
64	0	return NULL;
65	0	}
66
67	11.9k	item->key = NULL;
68	11.9k	item->value = NULL;
69	11.9k	item->destruct = NULL;
70	11.9k	item->next = NULL;
71	11.9k	item->tail = NULL;
72
73	11.9k	return item;
74	11.9k	}
75
76		static void
77		hoedown_hash_item_free(hoedown_hash_item *item)
78	11.9k	{
79	11.9k	if (item) {
80	11.9k	if (item->next) {
81	1.16k	hoedown_hash_item_free(item->next);
82	1.16k	}
83	11.9k	if (item->key) {
84	11.9k	free(item->key);
85	11.9k	}
86	11.9k	if (item->destruct) {
87	11.9k	(item->destruct)(item->value);
88	11.9k	}
89	11.9k	free(item);
90	11.9k	}
91	11.9k	}
92
93		static int
94		hoedown_hash_item_push(hoedown_hash_item item, const char key, size_t key_len,
95		void value, hoedown_hash_value_destruct destruct)
96	11.9k	{
97	11.9k	hoedown_hash_item *entry;
98
99	11.9k	if (!item \|\| !key \|\| !value) {
100	0	return 1;
101	0	}
102
103	11.9k	if (item->key != NULL) {
104	1.16k	entry = hoedown_hash_item_new();
105	1.16k	if (!entry) {
106	0	return 1;
107	0	}
108	10.7k	} else {
109	10.7k	entry = item;
110	10.7k	}
111
112	11.9k	if (key_len > 0) {
113	11.9k	entry->key = hoedown_hash_strndup(key, key_len);
114	11.9k	} else {
115	0	entry->key = hoedown_hash_strdup(key);
116	0	}
117	11.9k	entry->value = value;
118	11.9k	entry->destruct = destruct;
119
120	11.9k	if (item->tail) {
121	1.16k	item->tail->next = entry;
122	10.7k	} else if (item != entry) {
123	0	item->next = entry;
124	0	}
125	11.9k	item->tail = entry;
126
127	11.9k	return 0;
128	11.9k	}
129
130		hoedown_hash *
131		hoedown_hash_new(size_t size)
132	9.67k	{
133	9.67k	hoedown_hash *hash;
134	9.67k	size_t items_size;
135
136	9.67k	hash = (hoedown_hash *)malloc(sizeof(hoedown_hash));
137	9.67k	if (!hash) {
138	0	return NULL;
139	0	}
140
141	9.67k	if (size == 0) {
142	9.67k	size = HOEDOWN_HASH_ITEM_SIZE;
143	9.67k	}
144
145	9.67k	items_size = sizeof(hoedown_hash_item ) size;
146
147	9.67k	hash->items = (hoedown_hash_item **)malloc(items_size);
148	9.67k	if (!hash->items) {
149	0	free(hash);
150	0	return NULL;
151	0	}
152
153	9.67k	memset(hash->items, 0, items_size);
154
155	9.67k	hash->asize = size;
156
157	9.67k	return hash;
158	9.67k	}
159
160		void
161		hoedown_hash_free(hoedown_hash *hash)
162	9.67k	{
163	9.67k	if (hash) {
164	9.67k	if (hash->items) {
165	9.67k	size_t i = 0;
166	2.47M	while (i < hash->asize) {
167	2.46M	if (hash->items[i]) {
168	10.7k	hoedown_hash_item_free(hash->items[i]);
169	10.7k	}
170	2.46M	++i;
171	2.46M	}
172	9.67k	free(hash->items);
173	9.67k	}
174	9.67k	free(hash);
175	9.67k	}
176	9.67k	}
177
178		int
179		hoedown_hash_add(hoedown_hash hash, const char key, size_t key_len,
180		void value, hoedown_hash_value_destruct destruct)
181	11.9k	{
182	11.9k	unsigned int h;
183
184	11.9k	if (!hash \|\| !key \|\| !value) {
185	0	return 1;
186	0	}
187
188	11.9k	h = hoedown_hash_fnv(key, key + key_len, hash->asize);
189
190	11.9k	if (!hash->items[h]) {
191	10.7k	hash->items[h] = hoedown_hash_item_new();
192	10.7k	if (!hash->items[h]) {
193	0	return 1;
194	0	}
195	10.7k	}
196
197	11.9k	if (hoedown_hash_item_push(hash->items[h], key, key_len,
198	11.9k	value, destruct) != 0) {
199	0	return 1;
200	0	}
201
202	11.9k	return 0;
203	11.9k	}
204
205		void *
206		hoedown_hash_find(hoedown_hash hash, char key, size_t key_len)
207	88.1k	{
208	88.1k	unsigned int h;
209
210	88.1k	if (!hash \|\| !key) {
211	0	return NULL;
212	0	}
213
214	88.1k	h = hoedown_hash_fnv(key, key + key_len, hash->asize);
215
216	88.1k	if (hash->items[h]) {
217	77.3k	hoedown_hash_item *item = hash->items[h];
218	81.1k	while (item != NULL) {
219	79.9k	if (item->key && strncmp(item->key, key, key_len) == 0) {
220	76.2k	return item->value;
221	76.2k	}
222	3.74k	item = item->next;
223	3.74k	}
224	77.3k	}
225
226	11.9k	return NULL;
227	88.1k	}