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 : : #ifndef STREQ
35 : : #define STREQ(s1, s2) (strcmp(s1, s2) == 0)
36 : : #endif
37 : :
38 : : struct pkghash {
39 : : pkghash_entry *entries;
40 : : size_t capacity;
41 : : size_t count;
42 : : size_t index;
43 : : };
44 : :
45 : : pkghash *
46 : 2077 : pkghash_new(void)
47 : : {
48 : 2077 : pkghash *table = xmalloc(sizeof(pkghash));
49 : 2077 : table->count = 0;
50 : 2077 : table->capacity = 128;
51 : :
52 : 2077 : table->entries = xcalloc(table->capacity, sizeof(pkghash_entry));
53 : 2077 : return (table);
54 : : }
55 : :
56 : : void
57 : 16903 : pkghash_destroy(pkghash *table)
58 : : {
59 [ + + ]: 16903 : if (table == NULL)
60 : 15000 : return;
61 : :
62 [ + + ]: 325231 : for (size_t i = 0; i < table->capacity; i++) {
63 [ + + ]: 323328 : if (table->entries[i].key != NULL)
64 : 31031 : free(table->entries[i].key);
65 [ + + ]: 323328 : if (table->entries[i].free_func != NULL)
66 : 1 : table->entries[i].free_func(table->entries[i].value);
67 : 323328 : }
68 : 1903 : free(table->entries);
69 : 1903 : free(table);
70 : 16903 : }
71 : :
72 : : pkghash_entry *
73 : 35096 : pkghash_get(pkghash *table, const char *key)
74 : : {
75 [ + + ]: 35096 : if (table == NULL)
76 : 2080 : return (NULL);
77 : 33016 : uint64_t hash = mum_hash(key, strlen(key), 0);
78 : 33016 : size_t index = (size_t)(hash & (uint64_t)(table->capacity -1));
79 : :
80 [ + + ]: 52044 : while (table->entries[index].key != NULL) {
81 [ + + ]: 21793 : if (STREQ(key, table->entries[index].key))
82 : 2765 : return (&table->entries[index]);
83 : 19028 : index++;
84 [ + - ]: 19028 : if (index >= table->capacity)
85 : 0 : index = 0;
86 : : }
87 : 30251 : return (NULL);
88 : 35096 : }
89 : :
90 : : void *
91 : 4501 : pkghash_get_value(pkghash *table, const char *key)
92 : : {
93 : : pkghash_entry *e;
94 : :
95 : 4501 : e = pkghash_get(table, key);
96 [ + + ]: 4501 : return (e != NULL ? e->value : NULL);
97 : :
98 : : }
99 : :
100 : : static bool
101 : 71146 : pkghash_set_entry(pkghash_entry *entries, size_t capacity,
102 : : const char *key, void *value, size_t *pcount, void (*free_func)(void *)) {
103 : 71146 : uint64_t hash = mum_hash(key, strlen(key), 0);
104 : 71146 : size_t index = (size_t)(hash & (uint64_t)(capacity - 1));
105 : :
106 [ + + ]: 95563 : while (entries[index].key != NULL) {
107 [ - + ]: 24417 : if (STREQ(key, entries[index].key))
108 : 0 : return (false);
109 : 24417 : index++;
110 [ + - ]: 24417 : if (index >= capacity)
111 : 0 : index = 0;
112 : : }
113 : :
114 [ + + ]: 71146 : if (pcount != NULL) {
115 : 31273 : key = xstrdup(key);
116 : 31273 : (*pcount)++;
117 : 31273 : }
118 : 71146 : entries[index].key = (char *)key;
119 : 71146 : entries[index].value = value;
120 : 71146 : entries[index].free_func = free_func;
121 : 71146 : return (true);
122 : 71146 : }
123 : :
124 : : static bool
125 : 267 : pkghash_expand(pkghash *table)
126 : : {
127 : 267 : size_t new_capacity = table->capacity * 2;
128 [ - + ]: 267 : if (new_capacity < table->capacity)
129 : 0 : return (false);
130 : 267 : pkghash_entry *new_entries = xcalloc(new_capacity, sizeof(pkghash_entry));
131 : :
132 [ + + ]: 80011 : for (size_t i = 0; i < table->capacity; i++) {
133 : 79744 : pkghash_entry entry = table->entries[i];
134 [ + + ]: 79744 : if (entry.key != NULL)
135 : 79744 : pkghash_set_entry(new_entries, new_capacity, entry.key,
136 : 39872 : entry.value, NULL, entry.free_func);
137 : 79744 : }
138 : :
139 : 267 : free(table->entries);
140 : 267 : table->entries = new_entries;
141 : 267 : table->capacity = new_capacity;
142 : 267 : return (true);
143 : 267 : }
144 : :
145 : : bool
146 : 31274 : pkghash_add(pkghash *table, const char *key, void *value, void (*free_func)(void *))
147 : : {
148 [ + + + - ]: 31274 : if (table->count * 2 >= table->capacity && !pkghash_expand(table))
149 : 0 : return (false);
150 : :
151 : 62548 : return (pkghash_set_entry(table->entries, table->capacity, key, value,
152 : 31274 : &table->count, free_func));
153 : 31274 : }
154 : :
155 : : size_t
156 : 938 : pkghash_count(pkghash *table)
157 : : {
158 [ + + ]: 938 : if (table == NULL)
159 : 596 : return (0);
160 : 342 : return (table->count);
161 : 938 : }
162 : :
163 : : pkghash_it
164 : 4534 : pkghash_iterator(pkghash *table)
165 : : {
166 : : pkghash_it it;
167 : 4534 : it._table = table;
168 : 4534 : it._index = 0;
169 : 4534 : return (it);
170 : : }
171 : :
172 : : bool
173 : 7721 : pkghash_next(pkghash_it *it)
174 : : {
175 : 7721 : pkghash *table = it->_table;
176 [ + + ]: 7721 : if (table == NULL)
177 : 2773 : return (false);
178 [ + + ]: 4948 : if (table->count == 0)
179 : 2 : return (false);
180 [ + + ]: 226390 : while (it->_index < table->capacity) {
181 : 224640 : size_t i = it->_index;
182 : 224640 : it->_index++;
183 [ + + ]: 224640 : if (table->entries[i].key != NULL) {
184 : 3196 : pkghash_entry entry = table->entries[i];
185 : 3196 : it->key = entry.key;
186 : 3196 : it->value = entry.value;
187 : 3196 : return (true);
188 : : }
189 : : }
190 : 1750 : return (false);
191 : 7721 : }
192 : :
193 : : bool
194 : 58 : pkghash_del(pkghash *h, const char *key)
195 : : {
196 : 58 : pkghash_entry *e = pkghash_get(h, key);
197 [ + + ]: 58 : if (e == NULL)
198 : 1 : return (false);
199 : 57 : free(e->key);
200 : 57 : e->key = NULL;
201 [ + + ]: 57 : if (e->free_func != NULL)
202 : 1 : e->free_func(e->value);
203 : 57 : h->count--;
204 : 57 : return (true);
205 : 58 : }
206 : :
207 : : void *
208 : 2 : pkghash_delete(pkghash *h, const char *key)
209 : : {
210 : 2 : pkghash_entry *e = pkghash_get(h, key);
211 [ + + ]: 2 : if (e == NULL)
212 : 1 : return (NULL);
213 : 1 : free(e->key);
214 : 1 : e->key = NULL;
215 : 1 : h->count--;
216 : 1 : return (e->value);
217 : 2 : }
|
