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