| 1 |
/* Copyright (C) 2004 Christopher Clark <[email protected]> */ |
| 2 |
|
| 3 |
#include "hashtable.h" |
| 4 |
#include <stdlib.h> |
| 5 |
#include <stdio.h> |
| 6 |
#include <string.h> |
| 7 |
#include <math.h> |
| 8 |
#include <stdint.h> |
| 9 |
#include <stdarg.h> |
| 10 |
#include "talloc.h" |
| 11 |
|
| 12 |
struct entry |
| 13 |
{ |
| 14 |
const void *k; |
| 15 |
void *v; |
| 16 |
unsigned int h; |
| 17 |
struct entry *next; |
| 18 |
}; |
| 19 |
|
| 20 |
struct hashtable { |
| 21 |
unsigned int tablelength; |
| 22 |
unsigned int flags; |
| 23 |
struct entry **table; |
| 24 |
unsigned int entrycount; |
| 25 |
unsigned int loadlimit; |
| 26 |
unsigned int primeindex; |
| 27 |
unsigned int (*hashfn) (const void *k); |
| 28 |
int (*eqfn) (const void *k1, const void *k2); |
| 29 |
}; |
| 30 |
|
| 31 |
/* |
| 32 |
* Credit for primes table: Aaron Krowne |
| 33 |
* https://planetmath.org/goodhashtableprimes |
| 34 |
*/ |
| 35 |
static const unsigned int primes[] = { |
| 36 |
11, 23, 53, 97, 193, 389, |
| 37 |
769, 1543, 3079, 6151, |
| 38 |
12289, 24593, 49157, 98317, |
| 39 |
196613, 393241, 786433, 1572869, |
| 40 |
3145739, 6291469, 12582917, 25165843, |
| 41 |
50331653, 100663319, 201326611, 402653189, |
| 42 |
805306457, 1610612741 |
| 43 |
}; |
| 44 |
|
| 45 |
#define PRIME_TABLE_LEN ARRAY_SIZE(primes) |
| 46 |
#define MAX_LOAD_PERCENT 65 |
| 47 |
|
| 48 |
static inline unsigned int indexFor(unsigned int tablelength, |
| 49 |
unsigned int hashvalue) |
| 50 |
{ |
| 51 |
return (hashvalue % tablelength); |
| 52 |
} |
| 53 |
|
| 54 |
static unsigned int loadlimit(unsigned int pindex) |
| 55 |
{ |
| 56 |
return ((uint64_t)primes[pindex] * MAX_LOAD_PERCENT) / 100; |
| 57 |
} |
| 58 |
|
| 59 |
struct hashtable *create_hashtable(const void *ctx, const char *name, |
| 60 |
unsigned int (*hashf) (const void *), |
| 61 |
int (*eqf) (const void *, const void *), |
| 62 |
unsigned int flags) |
| 63 |
{ |
| 64 |
struct hashtable *h; |
| 65 |
|
| 66 |
h = talloc_zero(ctx, struct hashtable); |
| 67 |
if (NULL == h) |
| 68 |
goto err0; |
| 69 |
talloc_set_name_const(h, name); |
| 70 |
h->table = talloc_zero_array(h, struct entry *, primes[0]); |
| 71 |
if (NULL == h->table) |
| 72 |
goto err1; |
| 73 |
|
| 74 |
h->primeindex = 0; |
| 75 |
h->tablelength = primes[h->primeindex]; |
| 76 |
h->flags = flags; |
| 77 |
h->entrycount = 0; |
| 78 |
h->hashfn = hashf; |
| 79 |
h->eqfn = eqf; |
| 80 |
h->loadlimit = loadlimit(h->primeindex); |
| 81 |
return h; |
| 82 |
|
| 83 |
err1: |
| 84 |
talloc_free(h); |
| 85 |
err0: |
| 86 |
return NULL; |
| 87 |
} |
| 88 |
|
| 89 |
static unsigned int hash(const struct hashtable *h, const void *k) |
| 90 |
{ |
| 91 |
/* Aim to protect against poor hash functions by adding logic here |
| 92 |
* - logic taken from java 1.4 hashtable source */ |
| 93 |
unsigned int i = h->hashfn(k); |
| 94 |
i += ~(i << 9); |
| 95 |
i ^= ((i >> 14) | (i << 18)); /* >>> */ |
| 96 |
i += (i << 4); |
| 97 |
i ^= ((i >> 10) | (i << 22)); /* >>> */ |
| 98 |
return i; |
| 99 |
} |
| 100 |
|
| 101 |
static int hashtable_expand(struct hashtable *h) |
| 102 |
{ |
| 103 |
/* Double the size of the table to accomodate more entries */ |
| 104 |
struct entry **newtable; |
| 105 |
struct entry *e; |
| 106 |
struct entry **pE; |
| 107 |
unsigned int newsize, i, index; |
| 108 |
/* Check we're not hitting max capacity */ |
| 109 |
if (h->primeindex == (PRIME_TABLE_LEN - 1)) |
| 110 |
return ENOSPC; |
| 111 |
newsize = primes[++(h->primeindex)]; |
| 112 |
|
| 113 |
newtable = talloc_realloc(h, h->table, struct entry *, newsize); |
| 114 |
if (!newtable) |
| 115 |
{ |
| 116 |
h->primeindex--; |
| 117 |
return ENOMEM; |
| 118 |
} |
| 119 |
|
| 120 |
h->table = newtable; |
| 121 |
memset(newtable + h->tablelength, 0, |
| 122 |
(newsize - h->tablelength) * sizeof(*newtable)); |
| 123 |
for (i = 0; i < h->tablelength; i++) { |
| 124 |
for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) { |
| 125 |
index = indexFor(newsize, e->h); |
| 126 |
if (index == i) |
| 127 |
{ |
| 128 |
pE = &(e->next); |
| 129 |
} |
| 130 |
else |
| 131 |
{ |
| 132 |
*pE = e->next; |
| 133 |
e->next = newtable[index]; |
| 134 |
newtable[index] = e; |
| 135 |
} |
| 136 |
} |
| 137 |
} |
| 138 |
|
| 139 |
h->tablelength = newsize; |
| 140 |
h->loadlimit = loadlimit(h->primeindex); |
| 141 |
return 0; |
| 142 |
} |
| 143 |
|
| 144 |
static struct entry *hashtable_search_entry(const struct hashtable *h, |
| 145 |
const void *k) |
| 146 |
{ |
| 147 |
struct entry *e; |
| 148 |
unsigned int hashvalue, index; |
| 149 |
|
| 150 |
hashvalue = hash(h, k); |
| 151 |
index = indexFor(h->tablelength, hashvalue); |
| 152 |
e = h->table[index]; |
| 153 |
|
| 154 |
for (e = h->table[index]; e; e = e->next) |
| 155 |
{ |
| 156 |
/* Check hash value to short circuit heavier comparison */ |
| 157 |
if ((hashvalue == e->h) && (h->eqfn(k, e->k))) |
| 158 |
return e; |
| 159 |
} |
| 160 |
|
| 161 |
return NULL; |
| 162 |
} |
| 163 |
|
| 164 |
int hashtable_add(struct hashtable *h, const void *k, void *v) |
| 165 |
{ |
| 166 |
unsigned int index; |
| 167 |
struct entry *e; |
| 168 |
|
| 169 |
if (hashtable_search_entry(h, k)) |
| 170 |
return EEXIST; |
| 171 |
|
| 172 |
if (++(h->entrycount) > h->loadlimit) |
| 173 |
{ |
| 174 |
/* Ignore the return value. If expand fails, we should |
| 175 |
* still try cramming just this value into the existing table |
| 176 |
* -- we may not have memory for a larger table, but one more |
| 177 |
* element may be ok. Next time we insert, we'll try expanding again.*/ |
| 178 |
hashtable_expand(h); |
| 179 |
} |
| 180 |
e = talloc_zero(h, struct entry); |
| 181 |
if (NULL == e) |
| 182 |
{ |
| 183 |
--h->entrycount; |
| 184 |
return ENOMEM; |
| 185 |
} |
| 186 |
e->h = hash(h,k); |
| 187 |
index = indexFor(h->tablelength,e->h); |
| 188 |
e->k = k; |
| 189 |
if (h->flags & HASHTABLE_FREE_KEY) |
| 190 |
talloc_steal(e, k); |
| 191 |
e->v = v; |
| 192 |
if (h->flags & HASHTABLE_FREE_VALUE) |
| 193 |
talloc_steal(e, v); |
| 194 |
e->next = h->table[index]; |
| 195 |
h->table[index] = e; |
| 196 |
return 0; |
| 197 |
} |
| 198 |
|
| 199 |
void *hashtable_search(const struct hashtable *h, const void *k) |
| 200 |
{ |
| 201 |
struct entry *e; |
| 202 |
|
| 203 |
e = hashtable_search_entry(h, k); |
| 204 |
|
| 205 |
return e ? e->v : NULL; |
| 206 |
} |
| 207 |
|
| 208 |
int hashtable_replace(struct hashtable *h, const void *k, void *v) |
| 209 |
{ |
| 210 |
struct entry *e; |
| 211 |
|
| 212 |
e = hashtable_search_entry(h, k); |
| 213 |
if (!e) |
| 214 |
return ENOENT; |
| 215 |
|
| 216 |
if (h->flags & HASHTABLE_FREE_VALUE) |
| 217 |
{ |
| 218 |
talloc_free(e->v); |
| 219 |
talloc_steal(e, v); |
| 220 |
} |
| 221 |
|
| 222 |
e->v = v; |
| 223 |
|
| 224 |
return 0; |
| 225 |
} |
| 226 |
|
| 227 |
void |
| 228 |
hashtable_remove(struct hashtable *h, const void *k) |
| 229 |
{ |
| 230 |
/* TODO: consider compacting the table when the load factor drops enough, |
| 231 |
* or provide a 'compact' method. */ |
| 232 |
|
| 233 |
struct entry *e; |
| 234 |
struct entry **pE; |
| 235 |
unsigned int hashvalue, index; |
| 236 |
|
| 237 |
hashvalue = hash(h,k); |
| 238 |
index = indexFor(h->tablelength,hash(h,k)); |
| 239 |
pE = &(h->table[index]); |
| 240 |
e = *pE; |
| 241 |
while (NULL != e) |
| 242 |
{ |
| 243 |
/* Check hash value to short circuit heavier comparison */ |
| 244 |
if ((hashvalue == e->h) && (h->eqfn(k, e->k))) |
| 245 |
{ |
| 246 |
*pE = e->next; |
| 247 |
h->entrycount--; |
| 248 |
talloc_free(e); |
| 249 |
return; |
| 250 |
} |
| 251 |
pE = &(e->next); |
| 252 |
e = e->next; |
| 253 |
} |
| 254 |
} |
| 255 |
|
| 256 |
int hashtable_iterate(struct hashtable *h, |
| 257 |
int (*func)(const void *k, void *v, void *arg), void *arg) |
| 258 |
{ |
| 259 |
int ret; |
| 260 |
unsigned int i; |
| 261 |
struct entry *e, *f; |
| 262 |
struct entry **table = h->table; |
| 263 |
|
| 264 |
for (i = 0; i < h->tablelength; i++) |
| 265 |
{ |
| 266 |
e = table[i]; |
| 267 |
while (e) |
| 268 |
{ |
| 269 |
f = e; |
| 270 |
e = e->next; |
| 271 |
ret = func(f->k, f->v, arg); |
| 272 |
if (ret) |
| 273 |
return ret; |
| 274 |
} |
| 275 |
} |
| 276 |
|
| 277 |
return 0; |
| 278 |
} |
| 279 |
|
| 280 |
void hashtable_destroy(struct hashtable *h) |
| 281 |
{ |
| 282 |
talloc_free(h); |
| 283 |
} |
| 284 |
|
| 285 |
/* |
| 286 |
* Copyright (c) 2002, Christopher Clark |
| 287 |
* All rights reserved. |
| 288 |
* |
| 289 |
* Redistribution and use in source and binary forms, with or without |
| 290 |
* modification, are permitted provided that the following conditions |
| 291 |
* are met: |
| 292 |
* |
| 293 |
* * Redistributions of source code must retain the above copyright |
| 294 |
* notice, this list of conditions and the following disclaimer. |
| 295 |
* |
| 296 |
* * Redistributions in binary form must reproduce the above copyright |
| 297 |
* notice, this list of conditions and the following disclaimer in the |
| 298 |
* documentation and/or other materials provided with the distribution. |
| 299 |
* |
| 300 |
* * Neither the name of the original author; nor the names of any contributors |
| 301 |
* may be used to endorse or promote products derived from this software |
| 302 |
* without specific prior written permission. |
| 303 |
* |
| 304 |
* |
| 305 |
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 306 |
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 307 |
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 308 |
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER |
| 309 |
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| 310 |
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| 311 |
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 312 |
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 313 |
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 314 |
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 315 |
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 316 |
*/ |