LCOV - code coverage report
Current view: top level - common/hashtable - hashtable.c (source / functions) Hit Total Coverage
Test: a simple test Lines: 0 104 0.0 %
Date: 2024-06-05 20:10:43 Functions: 0 8 0.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13