2 * uhtbl - Generic coalesced hash table implementation
3 * Copyright (C) 2010 Steven Barth <steven@midlink.org>
4 * Copyright (C) 2010 John Crispin <blogic@openwrt.org>
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
27 /* Forward static helpers */
28 UHTBL_INLINE uhtbl_size_t _uhtbl_address(uhtbl_t *tbl, uhtbl_bucket_t *bucket);
29 UHTBL_INLINE uhtbl_bucket_t* _uhtbl_bucket(uhtbl_t *tbl, uhtbl_size_t address);
30 static uhtbl_bucket_t* _uhtbl_allocate(uhtbl_t *tbl);
31 static uhtbl_bucket_t* _uhtbl_find(uhtbl_t *tbl, const void *key,
32 long len, uhtbl_bucket_t **previous, uhtbl_size_t *mainaddress);
36 UHTBL_API int uhtbl_init(uhtbl_t *tbl, uint32_t bucketsize,
37 uhtbl_size_t sizehint, uhtbl_hash_t *fct_hash, uhtbl_gc_t *fct_gc) {
38 sizehint = (sizehint) ? sizehint : UHTBL_MINIMUMSIZE;
39 tbl->bucketsize = bucketsize;
40 tbl->fct_hash = fct_hash;
42 if (!tbl->fct_hash || tbl->bucketsize < sizeof(uhtbl_bucket_t)) {
49 return uhtbl_resize(tbl, sizehint);
52 UHTBL_API void uhtbl_clear(uhtbl_t *tbl) {
53 for (uhtbl_size_t i = 0; i < tbl->size; i++) {
54 uhtbl_bucket_t *bucket = _uhtbl_bucket(tbl, i);
55 if (tbl->fct_gc && bucket->head.flags & UHTBL_FLAG_OCCUPIED) {
58 bucket->head.flags = 0;
61 tbl->nextfree = tbl->size - 1;
64 UHTBL_API void* uhtbl_get (uhtbl_t *tbl, const void *key, long len) {
65 return _uhtbl_find(tbl, key, len, NULL, NULL);
68 UHTBL_API void* uhtbl_set (uhtbl_t *tbl, void *key, long len) {
70 uint16_t keysize = len, flags;
71 if (!key) { /* Check whether key is treated as a pointer */
73 keysize = sizeof(len);
77 uhtbl_size_t mainaddr;
78 uhtbl_bucket_t *resolve, *match, *prev = NULL;
79 uhtbl_bucket_t *lookup = _uhtbl_find(tbl, key, keysize, &prev, &mainaddr);
83 flags = match->head.flags;
84 if (flags & UHTBL_FLAG_OCCUPIED) { /* We are replacing an entry */
92 flags = match->head.flags;
93 if ((flags & UHTBL_FLAG_STRANGER)
94 && _uhtbl_address(tbl, match) == mainaddr) {
95 /* Mainposition occupied by key with different hash -> move it away */
97 /* Find old prev and update its next pointer */
98 if ((flags & UHTBL_FLAG_LOCALKEY)) {
100 match->head.key.handle, &prev, NULL);
102 _uhtbl_find(tbl, match->head.key.ptr,
103 match->head.keysize, &prev, NULL);
106 if (!(resolve = _uhtbl_allocate(tbl))) {
107 if (!uhtbl_resize(tbl, tbl->payload * UHTBL_GROWFACTOR)) {
108 return uhtbl_set(tbl, (localkey) ? NULL : key, len);
113 memcpy(resolve, match, tbl->bucketsize); /* Copy bucket data */
114 prev->head.next = _uhtbl_address(tbl, resolve);
116 } else if ((flags & UHTBL_FLAG_OCCUPIED) &&
117 (match->head.keysize != keysize || memcmp((flags & UHTBL_FLAG_LOCALKEY)
118 ? &match->head.key.handle : match->head.key.ptr, key, keysize))) {
119 /* Mainposition has different key (but same hash) */
120 if (!(resolve = _uhtbl_allocate(tbl))) {
121 if (!uhtbl_resize(tbl, tbl->payload * UHTBL_GROWFACTOR)) {
122 return uhtbl_set(tbl, (localkey) ? NULL : key, len);
130 flags = UHTBL_FLAG_STRANGER; /* We will not be in main position */
131 prev->head.flags |= UHTBL_FLAG_WITHNEXT; /* Main now has next */
132 prev->head.next = _uhtbl_address(tbl, match); /* main->next = us */
137 match->head.key.handle = len;
138 flags |= UHTBL_FLAG_LOCALKEY;
140 match->head.key.ptr = key;
141 flags &= ~UHTBL_FLAG_LOCALKEY;
143 match->head.keysize = keysize;
144 flags |= UHTBL_FLAG_OCCUPIED;
145 match->head.flags = flags;
151 UHTBL_API void* uhtbl_next(uhtbl_t *tbl, uhtbl_size_t *iter) {
152 for (; *iter < tbl->size; (*iter)++) {
153 if (_uhtbl_bucket(tbl, *iter)->head.flags & UHTBL_FLAG_OCCUPIED) {
154 return _uhtbl_bucket(tbl, (*iter)++);
160 UHTBL_API int uhtbl_remove(uhtbl_t *tbl, uhtbl_head_t *head) {
163 uhtbl_key(head, &key, &len);
164 return uhtbl_unset(tbl, key, len);
167 UHTBL_API int uhtbl_unset(uhtbl_t *tbl, const void *key, long len) {
168 uhtbl_bucket_t *prev = NULL;
169 uhtbl_bucket_t *bucket = _uhtbl_find(tbl, key, len, &prev, NULL);
178 bucket->head.flags &= ~UHTBL_FLAG_OCCUPIED;
181 /* If not in main position, get us out of the next-list */
182 if (bucket->head.flags & UHTBL_FLAG_STRANGER) {
183 if (bucket->head.flags & UHTBL_FLAG_WITHNEXT) {/* We had next buckets */
184 prev->head.next = bucket->head.next; /* Give them to out prev */
186 prev->head.flags &= ~UHTBL_FLAG_WITHNEXT;/* We were the only next */
188 bucket->head.flags = 0;
191 uhtbl_size_t address = _uhtbl_address(tbl, bucket);
192 if (address > tbl->nextfree) {
193 tbl->nextfree = address;
199 UHTBL_API int uhtbl_resize(uhtbl_t *tbl, uhtbl_size_t payload) {
200 uhtbl_size_t size = payload / UHTBL_PAYLOADFACTOR;
201 if (size < payload || size < tbl->used) {
204 if (payload == tbl->payload) {
208 void *buckets = calloc(size, tbl->bucketsize);
213 uhtbl_t oldtbl; /* Save essentials of table for rehashing */
214 oldtbl.buckets = tbl->buckets;
215 oldtbl.bucketsize = tbl->bucketsize;
216 oldtbl.size = tbl->size;
217 oldtbl.used = tbl->used;
219 tbl->buckets = buckets;
220 tbl->payload = payload;
223 tbl->nextfree = size - 1;
225 if (oldtbl.used) { /* Rehash if table had entries before */
226 uhtbl_size_t iter = 0;
227 uhtbl_bucket_t *old, *new;
228 while ((old = uhtbl_next(&oldtbl, &iter))) {
229 new = uhtbl_set(tbl, (old->head.flags & UHTBL_FLAG_LOCALKEY)
230 ? NULL : old->head.key.ptr,
231 (old->head.flags & UHTBL_FLAG_LOCALKEY)
232 ? old->head.key.handle : old->head.keysize);
233 new->head.user = old->head.user;
234 memcpy(((char*)new) + sizeof(uhtbl_head_t),
235 ((char*)old) + sizeof(uhtbl_head_t),
236 tbl->bucketsize - sizeof(uhtbl_head_t));
240 free(oldtbl.buckets);
244 UHTBL_API void uhtbl_finalize(uhtbl_t *tbl) {
250 UHTBL_API void uhtbl_key(uhtbl_head_t *head, void **key, long *len) {
252 *key = (head->flags & UHTBL_FLAG_LOCALKEY)
253 ? NULL : head->key.ptr;
256 *len = (head->flags & UHTBL_FLAG_LOCALKEY)
257 ? head->key.handle : head->keysize;
261 UHTBL_API void uhtbl_gc_key(void *bucket) {
263 uhtbl_key(bucket, &key, NULL);
268 /* Static auxiliary */
270 UHTBL_INLINE uhtbl_size_t _uhtbl_address(uhtbl_t *tbl, uhtbl_bucket_t *bucket) {
271 return ((uint8_t*)bucket - (uint8_t*)tbl->buckets) / tbl->bucketsize;
274 UHTBL_INLINE uhtbl_bucket_t* _uhtbl_bucket(uhtbl_t *tbl, uhtbl_size_t address) {
275 return (uhtbl_bucket_t*)
276 ((uint8_t*)tbl->buckets + (address * tbl->bucketsize));
279 static uhtbl_bucket_t* _uhtbl_allocate(uhtbl_t *tbl) {
280 uhtbl_size_t address = tbl->nextfree;
282 uhtbl_bucket_t *bucket = _uhtbl_bucket(tbl, address);
283 if (!(bucket->head.flags & UHTBL_FLAG_OCCUPIED)) {
284 if (bucket->head.flags & UHTBL_FLAG_WITHNEXT) {
285 /* Empty bucket still has a successor -> swap it with its */
286 /* successor and return the old successor-bucket as free */
287 uhtbl_bucket_t *old = bucket;
288 bucket = _uhtbl_bucket(tbl, old->head.next);
289 memcpy(old, bucket, tbl->bucketsize);
290 old->head.flags &= ~UHTBL_FLAG_STRANGER; /* sucessor now main */
292 /* WARN: If set will ever fail in the future we'd take care here */
293 tbl->nextfree = (address) ? address - 1 : 0;
300 static uhtbl_bucket_t* _uhtbl_find(uhtbl_t *tbl, const void *key,
301 long len, uhtbl_bucket_t **previous, uhtbl_size_t *mainaddress) {
302 uint16_t keysize = len;
305 keysize = sizeof(len);
307 uhtbl_size_t address = tbl->fct_hash(key, keysize) % tbl->payload;
308 uhtbl_bucket_t *buck = _uhtbl_bucket(tbl, address);
310 *mainaddress = address;
311 if (!(buck->head.flags & UHTBL_FLAG_OCCUPIED)) {
315 if (buck->head.flags & UHTBL_FLAG_STRANGER) {
321 for (;; buck = _uhtbl_bucket(tbl, address)) {
322 if (buck->head.flags & UHTBL_FLAG_OCCUPIED
323 && buck->head.keysize == keysize
324 && !memcmp((buck->head.flags & UHTBL_FLAG_LOCALKEY)
325 ? &buck->head.key.handle : buck->head.key.ptr, key, keysize)) {
328 if (!(buck->head.flags & UHTBL_FLAG_WITHNEXT)) {
335 address = buck->head.next;