Branch data Line data Source code
1 : : /*-
2 : : * Copyright (c) 2021 Baptiste Daroussin <bapt@FreeBSD.org>
3 : : *
4 : : * Redistribution and use in source and binary forms, with or without
5 : : * modification, are permitted provided that the following conditions
6 : : * are met:
7 : : * 1. Redistributions of source code must retain the above copyright
8 : : * notice, this list of conditions and the following disclaimer
9 : : * in this position and unchanged.
10 : : * 2. Redistributions in binary form must reproduce the above copyright
11 : : * notice, this list of conditions and the following disclaimer in the
12 : : * documentation and/or other materials provided with the distribution.
13 : : *
14 : : * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
15 : : * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 : : * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 : : * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
18 : : * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 : : * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 : : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 : : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 : : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 : : * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 : : */
25 : :
26 : : #include "pkghash.h"
27 : :
28 : : #include <stdint.h>
29 : : #include <stdlib.h>
30 : : #include <string.h>
31 : : #include <mum.h>
32 : : #include <xmalloc.h>
33 : :
34 : : struct pkghash {
35 : : pkghash_entry *entries;
36 : : size_t capacity;
37 : : size_t count;
38 : : size_t index;
39 : : };
40 : :
41 : : pkghash *
42 : 12683 : pkghash_new(void)
43 : : {
44 : 12683 : pkghash *table = xmalloc(sizeof(pkghash));
45 : 12683 : table->count = 0;
46 : 12683 : table->capacity = 128;
47 : :
48 : 12683 : table->entries = xcalloc(table->capacity, sizeof(pkghash_entry));
49 : 12683 : return (table);
50 : : }
51 : :
52 : : void
53 : 99463 : pkghash_destroy(pkghash *table)
54 : : {
55 [ + + ]: 99463 : if (table == NULL)
56 : 87600 : return;
57 : :
58 [ + + ]: 6807767 : for (size_t i = 0; i < table->capacity; i++) {
59 [ + + ]: 6795904 : if (table->entries[i].key != NULL)
60 : 5234424 : free(table->entries[i].key);
61 [ + + ]: 6795904 : if (table->entries[i].free_func != NULL)
62 : 5217662 : table->entries[i].free_func(table->entries[i].value);
63 : 6795904 : }
64 : 11863 : free(table->entries);
65 : 11863 : free(table);
66 : 99463 : }
67 : :
68 : : pkghash_entry *
69 : 10493761 : pkghash_get(pkghash *table, const char *key)
70 : : {
71 [ + + ]: 10493761 : if (table == NULL)
72 : 12497 : return (NULL);
73 : 10481264 : uint64_t hash = mum_hash(key, strlen(key), 0);
74 : 10481264 : size_t index = (size_t)(hash & (uint64_t)(table->capacity -1));
75 : :
76 [ + + ]: 372571289 : while (table->entries[index].key != NULL) {
77 [ + + ]: 362128399 : if (strcmp(key, table->entries[index].key) == 0)
78 : 38374 : return (&table->entries[index]);
79 : 362090025 : index++;
80 [ + + ]: 362090025 : if (index >= table->capacity)
81 : 401660 : index = 0;
82 : : }
83 : 10442890 : return (NULL);
84 : 10493761 : }
85 : :
86 : : void *
87 : 16296 : pkghash_get_value(pkghash *table, const char *key)
88 : : {
89 : : pkghash_entry *e;
90 : :
91 : 16296 : e = pkghash_get(table, key);
92 [ + + ]: 16296 : return (e != NULL ? e->value : NULL);
93 : :
94 : : }
95 : :
96 : : static bool
97 : 10506263 : pkghash_set_entry(pkghash_entry *entries, size_t capacity,
98 : : const char *key, void *value, size_t *pcount, void (*free_func)(void *)) {
99 : 10506263 : uint64_t hash = mum_hash(key, strlen(key), 0);
100 : 10506263 : size_t index = (size_t)(hash & (uint64_t)(capacity - 1));
101 : :
102 [ + + ]: 189976622 : while (entries[index].key != NULL) {
103 [ + - ]: 179470359 : if (strcmp(key, entries[index].key) == 0)
104 : 0 : return (false);
105 : 179470359 : index++;
106 [ + + ]: 179470359 : if (index >= capacity)
107 : 195510 : index = 0;
108 : : }
109 : :
110 [ + + ]: 10506263 : if (pcount != NULL) {
111 : 5235473 : key = xstrdup(key);
112 : 5235473 : (*pcount)++;
113 : 5235473 : }
114 : 10506263 : entries[index].key = (char *)key;
115 : 10506263 : entries[index].value = value;
116 : 10506263 : entries[index].free_func = free_func;
117 : 10506263 : return (true);
118 : 10506263 : }
119 : :
120 : : static bool
121 : 6650 : pkghash_expand(pkghash *table)
122 : : {
123 : 6650 : size_t new_capacity = table->capacity * 2;
124 [ - + ]: 6650 : if (new_capacity < table->capacity)
125 : 0 : return (false);
126 : 6650 : pkghash_entry *new_entries = xcalloc(new_capacity, sizeof(pkghash_entry));
127 : :
128 [ + + ]: 5284090 : for (size_t i = 0; i < table->capacity; i++) {
129 : 5277440 : pkghash_entry entry = table->entries[i];
130 [ + + ]: 5277440 : if (entry.key != NULL)
131 : 10541580 : pkghash_set_entry(new_entries, new_capacity, entry.key,
132 : 5270790 : entry.value, NULL, entry.free_func);
133 : 5277440 : }
134 : :
135 : 6650 : free(table->entries);
136 : 6650 : table->entries = new_entries;
137 : 6650 : table->capacity = new_capacity;
138 : 6650 : return (true);
139 : 6650 : }
140 : :
141 : : bool
142 : 5235473 : pkghash_add(pkghash *table, const char *key, void *value, void (*free_func)(void *))
143 : : {
144 [ + + + - ]: 5235473 : if (table->count >= table->capacity -1 && !pkghash_expand(table))
145 : 0 : return (NULL);
146 : :
147 : 10470946 : return (pkghash_set_entry(table->entries, table->capacity, key, value,
148 : 5235473 : &table->count, free_func));
149 : 5235473 : }
150 : :
151 : : size_t
152 : 7739 : pkghash_count(pkghash *table)
153 : : {
154 [ + + ]: 7739 : if (table == 0)
155 : 6477 : return (0);
156 : 1262 : return (table->count);
157 : 7739 : }
158 : :
159 : : pkghash_it
160 : 50999 : pkghash_iterator(pkghash *table)
161 : : {
162 : : pkghash_it it;
163 : 50999 : it._table = table;
164 : 50999 : it._index = 0;
165 : 50999 : return (it);
166 : : }
167 : :
168 : : bool
169 : 65732 : pkghash_next(pkghash_it *it)
170 : : {
171 : 65732 : pkghash *table = it->_table;
172 [ + + ]: 65732 : if (table == NULL)
173 : 40606 : return (false);
174 [ + + ]: 25126 : if (table->count == 0)
175 : 8 : return (false);
176 [ + + ]: 1336525 : while (it->_index < table->capacity) {
177 : 1326188 : size_t i = it->_index;
178 : 1326188 : it->_index++;
179 [ + + ]: 1326188 : if (table->entries[i].key != NULL) {
180 : 14781 : pkghash_entry entry = table->entries[i];
181 : 14781 : it->key = entry.key;
182 : 14781 : it->value = entry.value;
183 : 14781 : return (true);
184 : : }
185 : : }
186 : 10337 : return (false);
187 : 65732 : }
188 : :
189 : : void
190 : 0 : pkghash_loopinit(pkghash *h)
191 : : {
192 [ # # ]: 0 : if (h == NULL)
193 : 0 : return;
194 : 0 : h->index = 0;
195 : 0 : }
196 : :
197 : : pkghash_entry *
198 : 0 : pkghash_inext(pkghash *h)
199 : : {
200 [ # # ]: 0 : if (h == NULL)
201 : 0 : return (NULL);
202 [ # # ]: 0 : if (h->count == 0) {
203 : 0 : h->index = 0;
204 : 0 : return (NULL);
205 : : }
206 : :
207 [ # # ]: 0 : while (h->index < h->capacity) {
208 : 0 : size_t i = h->index;
209 : 0 : h->index++;
210 [ # # ]: 0 : if (h->entries[i].key != NULL)
211 : 0 : return (&h->entries[i]);
212 : : }
213 : : /* rewind just in case */
214 : 0 : h->index = 0;
215 : 0 : return (NULL);
216 : 0 : }
217 : :
218 : : bool
219 : 145 : pkghash_del(pkghash *h, const char *key)
220 : : {
221 : 145 : pkghash_entry *e = pkghash_get(h, key);
222 [ - + ]: 145 : if (e == NULL)
223 : 0 : return (false);
224 : 145 : free(e->key);
225 : 145 : e->key = NULL;
226 [ + - ]: 145 : if (e->free_func != NULL)
227 : 0 : e->free_func(e->value);
228 : 145 : h->count--;
229 : 145 : return (true);
230 : 145 : }
231 : :
232 : : void *
233 : 0 : pkghash_delete(pkghash *h, const char *key)
234 : : {
235 : 0 : pkghash_entry *e = pkghash_get(h, key);
236 [ # # ]: 0 : if (e == NULL)
237 : 0 : return (NULL);
238 : 0 : free(e->key);
239 : 0 : e->key = NULL;
240 : 0 : h->count--;
241 : 0 : return (e->value);
242 : 0 : }
|
