uhtbl.c

   1 /**
   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>
   5  *
   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.
  10  *
  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.
  15  *
  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.
  19  *
  20  */
  21
  22 #include <stdint.h>
  23 #include <string.h>
  24 #include <stdlib.h>
  25 #include "uhtbl.h"
  26
  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);
  33
  34
  35
  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;
  41         tbl->fct_gc = fct_gc;
  42         if (!tbl->fct_hash || tbl->bucketsize < sizeof(uhtbl_bucket_t)) {
  43                 return UHTBL_EINVAL;
  44         }
  45         tbl->payload = 0;
  46         tbl->buckets = NULL;
  47         tbl->used = 0;
  48
  49         return uhtbl_resize(tbl, sizehint);
  50 }
  51
  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) {
  56                         tbl->fct_gc(bucket);
  57                 }
  58                 bucket->head.flags = 0;
  59         }
  60         tbl->used = 0;
  61         tbl->nextfree = tbl->size - 1;
  62 }
  63
  64 UHTBL_API void* uhtbl_get (uhtbl_t *tbl, const void *key, long len) {
  65         return _uhtbl_find(tbl, key, len, NULL, NULL);
  66 }
  67
  68 UHTBL_API void* uhtbl_set (uhtbl_t *tbl, void *key, long len) {
  69         int localkey = 0;
  70         uint16_t keysize = len, flags;
  71         if (!key) {             /* Check whether key is treated as a pointer */
  72                 key = &len;
  73                 keysize = sizeof(len);
  74                 localkey = 1;
  75         }
  76
  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);
  80
  81         if (lookup) {
  82                 match = lookup;
  83                 flags = match->head.flags;
  84                 if (flags & UHTBL_FLAG_OCCUPIED) {      /* We are replacing an entry */
  85                         if (tbl->fct_gc) {
  86                                 tbl->fct_gc(match);
  87                         }
  88                         tbl->used--;
  89                 }
  90         } else {
  91                 match = prev;
  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 */
  96
  97                         /* Find old prev and update its next pointer */
  98                         if ((flags & UHTBL_FLAG_LOCALKEY)) {
  99                                 _uhtbl_find(tbl, 0,
 100                                  match->head.key.handle, &prev, NULL);
 101                         } else {
 102                                 _uhtbl_find(tbl, match->head.key.ptr,
 103                                                          match->head.keysize, &prev, NULL);
 104                         }
 105
 106                         if (!(resolve = _uhtbl_allocate(tbl))) {
 107                                 if (!uhtbl_resize(tbl, tbl->payload * UHTBL_GROWFACTOR)) {
 108                                         return uhtbl_set(tbl, (localkey) ? NULL : key, len);
 109                                 } else {
 110                                         return NULL;
 111                                 }
 112                         }
 113                         memcpy(resolve, match, tbl->bucketsize);        /* Copy bucket data */
 114                         prev->head.next = _uhtbl_address(tbl, resolve);
 115                         flags = 0;
 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);
 123                                 } else {
 124                                         return NULL;
 125                                 }
 126                         }
 127
 128                         prev = match;
 129                         match = resolve;
 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 */
 133                 }
 134         }
 135
 136         if (localkey) {
 137                 match->head.key.handle = len;
 138                 flags |= UHTBL_FLAG_LOCALKEY;
 139         } else {
 140                 match->head.key.ptr = key;
 141                 flags &= ~UHTBL_FLAG_LOCALKEY;
 142         }
 143         match->head.keysize = keysize;
 144         flags |= UHTBL_FLAG_OCCUPIED;
 145         match->head.flags = flags;
 146
 147         tbl->used++;
 148         return match;
 149 }
 150
 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)++);
 155                 }
 156         }
 157         return NULL;
 158 }
 159
 160 UHTBL_API int uhtbl_remove(uhtbl_t *tbl, uhtbl_head_t *head) {
 161         void *key;
 162         long len;
 163         uhtbl_key(head, &key, &len);
 164         return uhtbl_unset(tbl, key, len);
 165 }
 166
 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);
 170         if (!bucket) {
 171                 return UHTBL_ENOENT;
 172         }
 173
 174         if (tbl->fct_gc) {
 175                 tbl->fct_gc(bucket);
 176         }
 177
 178         bucket->head.flags &= ~UHTBL_FLAG_OCCUPIED;
 179         tbl->used--;
 180
 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 */
 185                 } else {
 186                         prev->head.flags &= ~UHTBL_FLAG_WITHNEXT;/* We were the only next */
 187                 }
 188                 bucket->head.flags = 0;
 189         }
 190
 191         uhtbl_size_t address = _uhtbl_address(tbl, bucket);
 192         if (address > tbl->nextfree) {
 193                 tbl->nextfree = address;
 194         }
 195
 196         return UHTBL_OK;
 197 }
 198
 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) {
 202                 return UHTBL_EINVAL;
 203         }
 204         if (payload == tbl->payload) {
 205                 return UHTBL_OK;
 206         }
 207
 208         void *buckets = calloc(size, tbl->bucketsize);
 209         if (!buckets) {
 210                 return UHTBL_ENOMEM;
 211         }
 212
 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;
 218
 219         tbl->buckets = buckets;
 220         tbl->payload = payload;
 221         tbl->size = size;
 222         tbl->used = 0;
 223         tbl->nextfree = size - 1;
 224
 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));
 237                 }
 238         }
 239
 240         free(oldtbl.buckets);
 241         return UHTBL_OK;
 242 }
 243
 244 UHTBL_API void uhtbl_finalize(uhtbl_t *tbl) {
 245         uhtbl_clear(tbl);
 246         free(tbl->buckets);
 247         tbl->buckets = NULL;
 248 }
 249
 250 UHTBL_API void uhtbl_key(uhtbl_head_t *head, void **key, long *len) {
 251         if (key) {
 252                 *key = (head->flags & UHTBL_FLAG_LOCALKEY)
 253                                 ? NULL : head->key.ptr;
 254         }
 255         if (len) {
 256                 *len = (head->flags & UHTBL_FLAG_LOCALKEY)
 257                                 ? head->key.handle : head->keysize;
 258         }
 259 }
 260
 261 UHTBL_API void uhtbl_gc_key(void *bucket) {
 262         void *key;
 263         uhtbl_key(bucket, &key, NULL);
 264         free(key);
 265 }
 266
 267
 268 /* Static auxiliary */
 269
 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;
 272 }
 273
 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));
 277 }
 278
 279 static uhtbl_bucket_t* _uhtbl_allocate(uhtbl_t *tbl) {
 280         uhtbl_size_t address = tbl->nextfree;
 281         do {
 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 */
 291                         }
 292                         /* WARN: If set will ever fail in the future we'd take care here */
 293                         tbl->nextfree = (address) ? address - 1 : 0;
 294                         return bucket;
 295                 }
 296         } while(address--);
 297         return NULL;
 298 }
 299
 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;
 303         if (!key) {
 304                 key = &len;
 305                 keysize = sizeof(len);
 306         }
 307         uhtbl_size_t address = tbl->fct_hash(key, keysize) % tbl->payload;
 308         uhtbl_bucket_t *buck = _uhtbl_bucket(tbl, address);
 309         if (mainaddress) {
 310                 *mainaddress = address;
 311                 if (!(buck->head.flags & UHTBL_FLAG_OCCUPIED)) {
 312                         return buck;
 313                 }
 314         }
 315         if (buck->head.flags & UHTBL_FLAG_STRANGER) {
 316                 if (previous) {
 317                         *previous = buck;
 318                 }
 319                 return NULL;
 320         }
 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)) {
 326                         return buck;
 327                 }
 328                 if (!(buck->head.flags & UHTBL_FLAG_WITHNEXT)) {
 329                         if (previous) {
 330                                 *previous = buck;
 331                         }
 332                         return NULL;
 333                 }
 334
 335                 address = buck->head.next;
 336                 if (previous) {
 337                         *previous = buck;
 338                 }
 339         }
 340 }