akaros/kern/src/hashtable.c
<<
>>
Prefs
   1/* Copyright (C) 2002, 2004 Christopher Clark  <firstname.lastname@cl.cam.ac.uk>
   2 *
   3 * Modified 2009 by Barret Rhoden <brho@cs.berkeley.edu>
   4 * Changes include:
   5 *   - No longer frees keys or values.  It's up to the client to do that.
   6 *   - Uses the slab allocator for hash entry allocation.
   7 *   - Merges the iterator code with the main hash table code, mostly to avoid
   8 *   externing the hentry cache. */
   9
  10#include <arch/types.h>
  11#include <assert.h>
  12#include <hash.h>
  13#include <hashtable.h>
  14#include <kmalloc.h>
  15#include <ros/common.h>
  16#include <slab.h>
  17#include <stdio.h>
  18#include <string.h>
  19
  20/*
  21Credit for primes table: Aaron Krowne
  22 http://br.endernet.org/~akrowne/
  23 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
  24*/
  25static const unsigned int primes[] = {
  26    53,        97,        193,       389,       769,       1543,     3079,
  27    6151,      12289,     24593,     49157,     98317,     196613,   393241,
  28    786433,    1572869,   3145739,   6291469,   12582917,  25165843, 50331653,
  29    100663319, 201326611, 402653189, 805306457, 1610612741};
  30const unsigned int prime_table_length = sizeof(primes) / sizeof(primes[0]);
  31#define APPLY_MAX_LOAD_FACTOR(size) ((size * 13) / 20)
  32// const float max_load_factor = 0.65;
  33
  34struct kmem_cache *hentry_cache;
  35
  36/* Call this once on bootup, after initializing the slab allocator.  */
  37void hashtable_init(void)
  38{
  39        hentry_cache = kmem_cache_create("hash_entry",
  40                                         sizeof(struct hash_entry),
  41                                         __alignof__(struct hash_entry), 0,
  42                                         NULL, 0, 0, NULL);
  43}
  44
  45/* Common hash/equals functions.  Don't call these directly. */
  46size_t __generic_hash(void *k)
  47{
  48        return hash_long((unsigned long)k, BITS_PER_LONG);
  49}
  50
  51ssize_t __generic_eq(void *k1, void *k2)
  52{
  53        return k1 == k2;
  54}
  55
  56/*****************************************************************************/
  57hashtable_t *create_hashtable(size_t minsize, size_t (*hashf)(void *),
  58                              ssize_t (*eqf)(void *, void *))
  59{
  60        hashtable_t *h;
  61        size_t pindex, size = primes[0];
  62
  63        /* Check requested hashtable isn't too large */
  64        if (minsize > (1u << 30))
  65                return NULL;
  66        /* Enforce size as prime */
  67        for (pindex = 0; pindex < prime_table_length; pindex++) {
  68                if (primes[pindex] > minsize) {
  69                        size = primes[pindex];
  70                        break;
  71                }
  72        }
  73        h = (hashtable_t *)kmalloc(sizeof(hashtable_t), 0);
  74        if (NULL == h)
  75                return NULL; /*oom*/
  76        h->table = (hash_entry_t **)kmalloc(sizeof(hash_entry_t *) * size, 0);
  77        if (NULL == h->table) {
  78                kfree(h);
  79                return NULL;
  80        } /*oom*/
  81        memset(h->table, 0, size * sizeof(hash_entry_t *));
  82        h->tablelength = size;
  83        h->primeindex = pindex;
  84        h->entrycount = 0;
  85        h->hashfn = hashf;
  86        h->eqfn = eqf;
  87        h->loadlimit = APPLY_MAX_LOAD_FACTOR(size);
  88        return h;
  89}
  90
  91/*****************************************************************************/
  92static size_t hash(hashtable_t *h, void *k)
  93{
  94        /* Aim to protect against poor hash functions by adding logic here
  95         * - logic taken from java 1.4 hashtable source */
  96        size_t i = h->hashfn(k);
  97
  98        i += ~(i << 9);
  99        i ^= ((i >> 14) | (i << 18)); /* >>> */
 100        i += (i << 4);
 101        i ^= ((i >> 10) | (i << 22)); /* >>> */
 102        return i;
 103}
 104
 105/*****************************************************************************/
 106static ssize_t hashtable_expand(hashtable_t *h)
 107{
 108        /* Double the size of the table to accomodate more entries */
 109        hash_entry_t **newtable;
 110        hash_entry_t *e;
 111        hash_entry_t **pE;
 112        size_t newsize, i, index;
 113
 114        /* Check we're not hitting max capacity */
 115        if (h->primeindex == (prime_table_length - 1))
 116                return 0;
 117        newsize = primes[++(h->primeindex)];
 118
 119        newtable =
 120            (hash_entry_t **)kmalloc(sizeof(hash_entry_t *) * newsize, 0);
 121        if (NULL != newtable) {
 122                memset(newtable, 0, newsize * sizeof(hash_entry_t *));
 123                /* This algorithm is not 'stable'. ie. it reverses the list
 124                 * when it transfers entries between the tables */
 125                for (i = 0; i < h->tablelength; i++) {
 126                        while (NULL != (e = h->table[i])) {
 127                                h->table[i] = e->next;
 128                                index = indexFor(newsize, e->h);
 129                                e->next = newtable[index];
 130                                newtable[index] = e;
 131                        }
 132                }
 133                kfree(h->table);
 134                h->table = newtable;
 135        }
 136        /* Plan B: realloc instead */
 137        else {
 138                newtable = (hash_entry_t **)krealloc(
 139                    h->table, newsize * sizeof(hash_entry_t *), 0);
 140                if (NULL == newtable) {
 141                        (h->primeindex)--;
 142                        return 0;
 143                }
 144                h->table = newtable;
 145                memset(newtable[h->tablelength], 0, newsize - h->tablelength);
 146                for (i = 0; i < h->tablelength; i++) {
 147                        for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
 148                                index = indexFor(newsize, e->h);
 149                                if (index == i) {
 150                                        pE = &(e->next);
 151                                } else {
 152                                        *pE = e->next;
 153                                        e->next = newtable[index];
 154                                        newtable[index] = e;
 155                                }
 156                        }
 157                }
 158        }
 159        h->tablelength = newsize;
 160        h->loadlimit = APPLY_MAX_LOAD_FACTOR(newsize);
 161        return -1;
 162}
 163
 164/*****************************************************************************/
 165size_t hashtable_count(hashtable_t *h)
 166{
 167        return h->entrycount;
 168}
 169
 170/*****************************************************************************/
 171ssize_t hashtable_insert(hashtable_t *h, void *k, void *v)
 172{
 173        /* This method allows duplicate keys - but they shouldn't be used */
 174        size_t index;
 175        hash_entry_t *e;
 176
 177        if (++(h->entrycount) > h->loadlimit) {
 178                /* Ignore the return value. If expand fails, we should
 179                 * still try cramming just this value into the existing table
 180                 * -- we may not have memory for a larger table, but one more
 181                 * element may be ok. Next time we insert, we'll try expanding
 182                 * again.*/
 183                hashtable_expand(h);
 184        }
 185        e = (hash_entry_t *)kmem_cache_alloc(hentry_cache, 0);
 186        if (NULL == e) {
 187                --(h->entrycount);
 188                return 0;
 189        } /*oom*/
 190        e->h = hash(h, k);
 191        index = indexFor(h->tablelength, e->h);
 192        e->k = k;
 193        e->v = v;
 194        e->next = h->table[index];
 195        h->table[index] = e;
 196        return -1;
 197}
 198
 199/*****************************************************************************/
 200/* returns value associated with key */
 201void *hashtable_search(hashtable_t *h, void *k)
 202{
 203        hash_entry_t *e;
 204        size_t hashvalue, index;
 205
 206        hashvalue = hash(h, k);
 207        index = indexFor(h->tablelength, hashvalue);
 208        e = h->table[index];
 209        while (NULL != e) {
 210                /* Check hash value to short circuit heavier comparison */
 211                if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 212                        return e->v;
 213                e = e->next;
 214        }
 215        return NULL;
 216}
 217
 218/*****************************************************************************/
 219/* returns value associated with key */
 220void *hashtable_remove(hashtable_t *h, void *k)
 221{
 222        /* TODO: consider compacting the table when the load factor drops
 223         * enough, or provide a 'compact' method. */
 224
 225        hash_entry_t *e;
 226        hash_entry_t **pE;
 227        void *v;
 228        size_t hashvalue, index;
 229
 230        hashvalue = hash(h, k);
 231        index = indexFor(h->tablelength, hash(h, k));
 232        pE = &(h->table[index]);
 233        e = *pE;
 234        while (NULL != e) {
 235                /* Check hash value to short circuit heavier comparison */
 236                if ((hashvalue == e->h) && (h->eqfn(k, e->k))) {
 237                        *pE = e->next;
 238                        h->entrycount--;
 239                        v = e->v;
 240                        kmem_cache_free(hentry_cache, e);
 241                        return v;
 242                }
 243                pE = &(e->next);
 244                e = e->next;
 245        }
 246        return NULL;
 247}
 248
 249/*****************************************************************************/
 250/* destroy */
 251void hashtable_destroy(hashtable_t *h)
 252{
 253        if (hashtable_count(h))
 254                warn("Destroying a non-empty hashtable, clean up after "
 255                     "yourself!\n");
 256
 257        size_t i;
 258        hash_entry_t *e, *f;
 259        hash_entry_t **table = h->table;
 260
 261        for (i = 0; i < h->tablelength; i++) {
 262                e = table[i];
 263                while (NULL != e) {
 264                        f = e;
 265                        e = e->next;
 266                        kmem_cache_free(hentry_cache, f);
 267                }
 268        }
 269        kfree(h->table);
 270        kfree(h);
 271}
 272
 273/*****************************************************************************/
 274/* hashtable_iterator    - iterator constructor, be sure to kfree this when
 275 * you're done.
 276 *
 277 * If the htable isn't empty, e and index will refer to the first entry. */
 278
 279hashtable_itr_t *hashtable_iterator(hashtable_t *h)
 280{
 281        size_t i, tablelength;
 282        hashtable_itr_t *itr =
 283            (hashtable_itr_t *)kmalloc(sizeof(hashtable_itr_t), 0);
 284
 285        if (NULL == itr)
 286                return NULL;
 287        itr->h = h;
 288        itr->e = NULL;
 289        itr->parent = NULL;
 290        tablelength = h->tablelength;
 291        itr->index = tablelength;
 292        if (0 == h->entrycount)
 293                return itr;
 294
 295        for (i = 0; i < tablelength; i++) {
 296                if (NULL != h->table[i]) {
 297                        itr->e = h->table[i];
 298                        itr->index = i;
 299                        break;
 300                }
 301        }
 302        return itr;
 303}
 304
 305/*****************************************************************************/
 306/* key      - return the key of the (key,value) pair at the current position */
 307/* value    - return the value of the (key,value) pair at the current position
 308 */
 309
 310void *hashtable_iterator_key(hashtable_itr_t *i)
 311{
 312        return i->e->k;
 313}
 314
 315void *hashtable_iterator_value(hashtable_itr_t *i)
 316{
 317        return i->e->v;
 318}
 319
 320/*****************************************************************************/
 321/* advance - advance the iterator to the next element
 322 *           returns zero if advanced to end of table */
 323
 324ssize_t hashtable_iterator_advance(hashtable_itr_t *itr)
 325{
 326        size_t j, tablelength;
 327        hash_entry_t **table;
 328        hash_entry_t *next;
 329
 330        if (NULL == itr->e)
 331                return 0; /* stupidity check */
 332
 333        next = itr->e->next;
 334        if (NULL != next) {
 335                itr->parent = itr->e;
 336                itr->e = next;
 337                return -1;
 338        }
 339        tablelength = itr->h->tablelength;
 340        itr->parent = NULL;
 341        if (tablelength <= (j = ++(itr->index))) {
 342                itr->e = NULL;
 343                return 0;
 344        }
 345        table = itr->h->table;
 346        while (NULL == (next = table[j])) {
 347                if (++j >= tablelength) {
 348                        itr->index = tablelength;
 349                        itr->e = NULL;
 350                        return 0;
 351                }
 352        }
 353        itr->index = j;
 354        itr->e = next;
 355        return -1;
 356}
 357
 358/*****************************************************************************/
 359/* remove - remove the entry at the current iterator position
 360 *          and advance the iterator, if there is a successive
 361 *          element.
 362 *          If you want the value, read it before you remove:
 363 *          beware memory leaks if you don't.
 364 *          Returns zero if end of iteration. */
 365
 366ssize_t hashtable_iterator_remove(hashtable_itr_t *itr)
 367{
 368        hash_entry_t *remember_e, *remember_parent;
 369        ssize_t ret;
 370
 371        /* Do the removal */
 372        if (NULL == (itr->parent)) {
 373                /* element is head of a chain */
 374                itr->h->table[itr->index] = itr->e->next;
 375        } else {
 376                /* element is mid-chain */
 377                itr->parent->next = itr->e->next;
 378        }
 379        /* itr->e is now outside the hashtable */
 380        remember_e = itr->e;
 381        itr->h->entrycount--;
 382
 383        /* Advance the iterator, correcting the parent */
 384        remember_parent = itr->parent;
 385        ret = hashtable_iterator_advance(itr);
 386        if (itr->parent == remember_e) {
 387                itr->parent = remember_parent;
 388        }
 389        kmem_cache_free(hentry_cache, remember_e);
 390        return ret;
 391}
 392
 393/*****************************************************************************/
 394/* returns zero if not found */
 395ssize_t hashtable_iterator_search(hashtable_itr_t *itr, hashtable_t *h, void *k)
 396{
 397        hash_entry_t *e, *parent;
 398        size_t hashvalue, index;
 399
 400        hashvalue = hash(h, k);
 401        index = indexFor(h->tablelength, hashvalue);
 402
 403        e = h->table[index];
 404        parent = NULL;
 405        while (NULL != e) {
 406                /* Check hash value to short circuit heavier comparison */
 407                if ((hashvalue == e->h) && (h->eqfn(k, e->k))) {
 408                        itr->index = index;
 409                        itr->e = e;
 410                        itr->parent = parent;
 411                        itr->h = h;
 412                        return -1;
 413                }
 414                parent = e;
 415                e = e->next;
 416        }
 417        return 0;
 418}
 419
 420/* Runs func on each member of the hash table */
 421void hash_for_each(struct hashtable *hash, void func(void *, void *),
 422                   void *opaque)
 423{
 424        if (hashtable_count(hash)) {
 425                struct hashtable_itr *iter = hashtable_iterator(hash);
 426                do {
 427                        void *item = hashtable_iterator_value(iter);
 428                        func(item, opaque);
 429                } while (hashtable_iterator_advance(iter));
 430                kfree(iter);
 431        }
 432}
 433
 434/* Runs func on each member of the hash table, removing the item after
 435 * processing it.  Make sure func frees the item, o/w you'll leak. */
 436void hash_for_each_remove(struct hashtable *hash, void func(void *, void *),
 437                          void *opaque)
 438{
 439        if (hashtable_count(hash)) {
 440                struct hashtable_itr *iter = hashtable_iterator(hash);
 441                do {
 442                        void *item = hashtable_iterator_value(iter);
 443                        func(item, opaque);
 444                } while (hashtable_iterator_remove(iter));
 445                kfree(iter);
 446        }
 447}
 448
 449/*
 450 * Copyright (c) 2002, 2004, Christopher Clark
 451 * All rights reserved.
 452 *
 453 * Redistribution and use in source and binary forms, with or without
 454 * modification, are permitted provided that the following conditions
 455 * are met:
 456 *
 457 * * Redistributions of source code must retain the above copyright
 458 * notice, this list of conditions and the following disclaimer.
 459 *
 460 * * Redistributions in binary form must reproduce the above copyright
 461 * notice, this list of conditions and the following disclaimer in the
 462 * documentation and/or other materials provided with the distribution.
 463 *
 464 * * Neither the name of the original author; nor the names of any contributors
 465 * may be used to endorse or promote products derived from this software
 466 * without specific prior written permission.
 467 *
 468 *
 469 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 470 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 471 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 472 * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 473 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 474 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 475 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 476 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 477 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 478 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 479 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 480 */
 481