git.itanic.dy.fi Git - maemo-mapper/blob - src/hashtable.c

   1
   2
   3 /*
   4  *
   5  * This file is part of Maemo Mapper.
   6  *
   7  * Maemo Mapper is free software: you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation, either version 3 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * Maemo Mapper is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Maemo Mapper.  If not, see <http://www.gnu.org/licenses/>.
  19  *
  20  *
  21  * Parts of this code have been ported from Xastir by Rob Williams (10 Aug 2008):
  22  *
  23  *  * XASTIR, Amateur Station Tracking and Information Reporting
  24  * Copyright (C) 1999,2000  Frank Giannandrea
  25  * Copyright (C) 2000-2007  The Xastir Group
  26  * Copyright (C) 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
  27  */
  28
  29 #ifdef HAVE_CONFIG_H
  30 #    include "config.h"
  31 #endif
  32
  33 #ifdef INCLUDE_APRS
  34
  35 #include <stdlib.h>
  36 #include <stdio.h>
  37 #include <string.h>
  38 #include <math.h>
  39
  40 #include "hashtable.h"
  41 #include "hashtable_private.h"
  42
  43 /*
  44 Credit for primes table: Aaron Krowne
  45  http://br.endernet.org/~akrowne/
  46  http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
  47 */
  48 static const unsigned int primes[] = {
  49 53, 97, 193, 389,
  50 769, 1543, 3079, 6151,
  51 12289, 24593, 49157, 98317,
  52 196613, 393241, 786433, 1572869,
  53 3145739, 6291469, 12582917, 25165843,
  54 50331653, 100663319, 201326611, 402653189,
  55 805306457, 1610612741
  56 };
  57 const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
  58 const float max_load_factor = 0.65;
  59
  60 /*****************************************************************************/
  61 struct hashtable *
  62 create_hashtable(unsigned int minsize,
  63                  unsigned int (*hashf) (void*),
  64                  int (*eqf) (void*,void*))
  65 {
  66     struct hashtable *h;
  67     unsigned int pindex, size = primes[0];
  68     /* Check requested hashtable isn't too large */
  69     if (minsize > (1u << 30)) return NULL;
  70     /* Enforce size as prime */
  71     for (pindex=0; pindex < prime_table_length; pindex++) {
  72         if (primes[pindex] > minsize) { size = primes[pindex]; break; }
  73     }
  74     h = (struct hashtable *)malloc(sizeof(struct hashtable));
  75     if (NULL == h) return NULL; /*oom*/
  76     h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
  77     if (NULL == h->table) { free(h); return NULL; } /*oom*/
  78     memset(h->table, 0, size * sizeof(struct entry *));
  79     h->tablelength  = size;
  80     h->primeindex   = pindex;
  81     h->entrycount   = 0;
  82     h->hashfn       = hashf;
  83     h->eqfn         = eqf;
  84     h->loadlimit    = (unsigned int) ceil(size * max_load_factor);
  85     return h;
  86 }
  87
  88 /*****************************************************************************/
  89 unsigned int
  90 hash(struct hashtable *h, void *k)
  91 {
  92     /* Aim to protect against poor hash functions by adding logic here
  93      * - logic taken from java 1.4 hashtable source */
  94     unsigned int i = h->hashfn(k);
  95     i += ~(i << 9);
  96     i ^=  ((i >> 14) | (i << 18)); /* >>> */
  97     i +=  (i << 4);
  98     i ^=  ((i >> 10) | (i << 22)); /* >>> */
  99     return i;
 100 }
 101
 102 /*****************************************************************************/
 103 static int
 104 hashtable_expand(struct hashtable *h)
 105 {
 106     /* Double the size of the table to accomodate more entries */
 107     struct entry **newtable;
 108     struct entry *e;
 109     struct entry **pE;
 110     unsigned int newsize, i, index;
 111     /* Check we're not hitting max capacity */
 112     if (h->primeindex == (prime_table_length - 1)) return 0;
 113     newsize = primes[++(h->primeindex)];
 114
 115     newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
 116     if (NULL != newtable)
 117     {
 118         memset(newtable, 0, newsize * sizeof(struct entry *));
 119         /* This algorithm is not 'stable'. ie. it reverses the list
 120          * when it transfers entries between the tables */
 121         for (i = 0; i < h->tablelength; i++) {
 122             while (NULL != (e = h->table[i])) {
 123                 h->table[i] = e->next;
 124                 index = indexFor(newsize,e->h);
 125                 e->next = newtable[index];
 126                 newtable[index] = e;
 127             }
 128         }
 129         free(h->table);
 130         h->table = newtable;
 131     }
 132     /* Plan B: realloc instead */
 133     else
 134     {
 135         newtable = (struct entry **)
 136                    realloc(h->table, newsize * sizeof(struct entry *));
 137         if (NULL == newtable) { (h->primeindex)--; return 0; }
 138         h->table = newtable;
 139         memset(newtable[h->tablelength], 0, newsize - h->tablelength);
 140         for (i = 0; i < h->tablelength; i++) {
 141             for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
 142                 index = indexFor(newsize,e->h);
 143                 if (index == i)
 144                 {
 145                     pE = &(e->next);
 146                 }
 147                 else
 148                 {
 149                     *pE = e->next;
 150                     e->next = newtable[index];
 151                     newtable[index] = e;
 152                 }
 153             }
 154         }
 155     }
 156     h->tablelength = newsize;
 157     h->loadlimit   = (unsigned int) ceil(newsize * max_load_factor);
 158     return -1;
 159 }
 160
 161 /*****************************************************************************/
 162 unsigned int
 163 hashtable_count(struct hashtable *h)
 164 {
 165     return h->entrycount;
 166 }
 167
 168 /*****************************************************************************/
 169 int
 170 hashtable_insert(struct hashtable *h, void *k, void *v)
 171 {
 172     /* This method allows duplicate keys - but they shouldn't be used */
 173     unsigned int index;
 174     struct entry *e;
 175     if (++(h->entrycount) > h->loadlimit)
 176     {
 177         /* Ignore the return value. If expand fails, we should
 178          * still try cramming just this value into the existing table
 179          * -- we may not have memory for a larger table, but one more
 180          * element may be ok. Next time we insert, we'll try expanding again.*/
 181         hashtable_expand(h);
 182     }
 183     e = (struct entry *)malloc(sizeof(struct entry));
 184     if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
 185     e->h = hash(h,k);
 186     index = indexFor(h->tablelength,e->h);
 187     e->k = k;
 188     e->v = v;
 189     e->next = h->table[index];
 190     h->table[index] = e;
 191     return -1;
 192 }
 193
 194 /*****************************************************************************/
 195 void * /* returns value associated with key */
 196 hashtable_search(struct hashtable *h, void *k)
 197 {
 198     struct entry *e;
 199     unsigned int hashvalue, index;
 200     hashvalue = hash(h,k);
 201     index = indexFor(h->tablelength,hashvalue);
 202     e = h->table[index];
 203     while (NULL != e)
 204     {
 205         /* Check hash value to short circuit heavier comparison */
 206         if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
 207         e = e->next;
 208     }
 209     return NULL;
 210 }
 211
 212 /*****************************************************************************/
 213 void * /* returns value associated with key */
 214 hashtable_remove(struct hashtable *h, void *k)
 215 {
 216     /* TODO: consider compacting the table when the load factor drops enough,
 217      *       or provide a 'compact' method. */
 218
 219     struct entry *e;
 220     struct entry **pE;
 221     void *v;
 222     unsigned int hashvalue, index;
 223
 224     hashvalue = hash(h,k);
 225     index = indexFor(h->tablelength,hash(h,k));
 226     pE = &(h->table[index]);
 227     e = *pE;
 228     while (NULL != e)
 229     {
 230         /* Check hash value to short circuit heavier comparison */
 231         if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 232         {
 233             *pE = e->next;
 234             h->entrycount--;
 235             v = e->v;
 236             freekey(e->k);
 237             free(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(struct hashtable *h, int free_values)
 250 {
 251     unsigned int i;
 252     struct entry *e, *f;
 253     struct entry **table = h->table;
 254     if (free_values)
 255     {
 256         for (i = 0; i < h->tablelength; i++)
 257         {
 258             e = table[i];
 259             while (NULL != e)
 260             { f = e; e = e->next; freekey(f->k); free(f->v); free(f); }
 261         }
 262     }
 263     else
 264     {
 265         for (i = 0; i < h->tablelength; i++)
 266         {
 267             e = table[i];
 268             while (NULL != e)
 269             { f = e; e = e->next; freekey(f->k); free(f); }
 270         }
 271     }
 272     free(h->table);
 273     free(h);
 274 }
 275
 276 #endif // INCLUDE_APRS
 277
 278 /*
 279  * Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
 280  *
 281  * Permission is hereby granted, free of charge, to any person obtaining a copy
 282  * of this software and associated documentation files (the "Software"), to
 283  * deal in the Software without restriction, including without limitation the
 284  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 285  * sell copies of the Software, and to permit persons to whom the Software is
 286  * furnished to do so, subject to the following conditions:
 287  *
 288  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 289  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 290  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 291  * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 292  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 293  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 294  * */
 295
 296