kern/src/hashtable.c

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