libhttp/hashmap.c

   1 // hashmap.c -- Basic implementation of a hashmap abstract data type
   2 // Copyright (C) 2008-2009 Markus Gutschke <markus@shellinabox.com>
   3 //
   4 // This program is free software; you can redistribute it and/or modify
   5 // it under the terms of the GNU General Public License version 2 as
   6 // published by the Free Software Foundation.
   7 //
   8 // This program is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 // GNU General Public License for more details.
  12 //
  13 // You should have received a copy of the GNU General Public License along
  14 // with this program; if not, write to the Free Software Foundation, Inc.,
  15 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  16 //
  17 // In addition to these license terms, the author grants the following
  18 // additional rights:
  19 //
  20 // If you modify this program, or any covered work, by linking or
  21 // combining it with the OpenSSL project's OpenSSL library (or a
  22 // modified version of that library), containing parts covered by the
  23 // terms of the OpenSSL or SSLeay licenses, the author
  24 // grants you additional permission to convey the resulting work.
  25 // Corresponding Source for a non-source form of such a combination
  26 // shall include the source code for the parts of OpenSSL used as well
  27 // as that of the covered work.
  28 //
  29 // You may at your option choose to remove this additional permission from
  30 // the work, or from any part of it.
  31 //
  32 // It is possible to build this program in a way that it loads OpenSSL
  33 // libraries at run-time. If doing so, the following notices are required
  34 // by the OpenSSL and SSLeay licenses:
  35 //
  36 // This product includes software developed by the OpenSSL Project
  37 // for use in the OpenSSL Toolkit. (http://www.openssl.org/)
  38 //
  39 // This product includes cryptographic software written by Eric Young
  40 // (eay@cryptsoft.com)
  41 //
  42 //
  43 // The most up-to-date version of this program is always available from
  44 // http://shellinabox.com
  45
  46 #include "config.h"
  47
  48 #include <stdlib.h>
  49 #include <string.h>
  50
  51 #include "libhttp/hashmap.h"
  52 #include "logging/logging.h"
  53
  54 struct HashMap *newHashMap(void (*destructor)(void *arg, char *key,
  55                                               char *value),
  56                            void *arg) {
  57   struct HashMap *hashmap;
  58   check(hashmap = malloc(sizeof(struct HashMap)));
  59   initHashMap(hashmap, destructor, arg);
  60   return hashmap;
  61 }
  62
  63 void initHashMap(struct HashMap *hashmap,
  64                  void (*destructor)(void *arg, char *key, char *value),
  65                  void *arg) {
  66   hashmap->destructor  = destructor;
  67   hashmap->arg         = arg;
  68   hashmap->entries     = NULL;
  69   hashmap->mapSize     = 0;
  70   hashmap->numEntries  = 0;
  71 }
  72
  73 void destroyHashMap(struct HashMap *hashmap) {
  74   if (hashmap) {
  75     for (int i = 0; i < hashmap->mapSize; i++) {
  76       if (hashmap->entries[i]) {
  77         for (int j = 0; hashmap->entries[i][j].key; j++) {
  78           if (hashmap->destructor) {
  79             hashmap->destructor(hashmap->arg,
  80                                 (char *)hashmap->entries[i][j].key,
  81                                 (char *)hashmap->entries[i][j].value);
  82           }
  83         }
  84         free(hashmap->entries[i]);
  85       }
  86     }
  87     free(hashmap->entries);
  88   }
  89 }
  90
  91 void deleteHashMap(struct HashMap *hashmap) {
  92   destroyHashMap(hashmap);
  93   free(hashmap);
  94 }
  95
  96 static unsigned int stringHashFunc(const char *s) {
  97   unsigned int h = 0;
  98   while (*s) {
  99     h = 31*h + *(unsigned char *)s++;
 100   }
 101   return h;
 102 }
 103
 104 const void *addToHashMap(struct HashMap *hashmap, const char *key,
 105                          const char *value) {
 106   if (hashmap->numEntries + 1 > (hashmap->mapSize * 8)/10) {
 107     struct HashMap newMap;
 108     newMap.numEntries            = hashmap->numEntries;
 109     if (hashmap->mapSize == 0) {
 110       newMap.mapSize             = 32;
 111     } else if (hashmap->mapSize < 1024) {
 112       newMap.mapSize             = 2*hashmap->mapSize;
 113     } else {
 114       newMap.mapSize             = hashmap->mapSize + 1024;
 115     }
 116     check(newMap.entries         = calloc(sizeof(void *), newMap.mapSize));
 117     for (int i = 0; i < hashmap->mapSize; i++) {
 118       if (!hashmap->entries[i]) {
 119         continue;
 120       }
 121       for (int j = 0; hashmap->entries[i][j].key; j++) {
 122         addToHashMap(&newMap, hashmap->entries[i][j].key,
 123                      hashmap->entries[i][j].value);
 124       }
 125       free(hashmap->entries[i]);
 126     }
 127     free(hashmap->entries);
 128     hashmap->entries             = newMap.entries;
 129     hashmap->mapSize             = newMap.mapSize;
 130     hashmap->numEntries          = newMap.numEntries;
 131   }
 132   unsigned hash                  = stringHashFunc(key);
 133   int idx                        = hash % hashmap->mapSize;
 134   int i                          = 0;
 135   if (hashmap->entries[idx]) {
 136     for (i = 0; hashmap->entries[idx][i].key; i++) {
 137       if (!strcmp(hashmap->entries[idx][i].key, key)) {
 138         if (hashmap->destructor) {
 139           hashmap->destructor(hashmap->arg,
 140                               (char *)hashmap->entries[idx][i].key,
 141                               (char *)hashmap->entries[idx][i].value);
 142         }
 143         hashmap->entries[idx][i].key   = key;
 144         hashmap->entries[idx][i].value = value;
 145         return value;
 146       }
 147     }
 148   }
 149   check(hashmap->entries[idx]    = realloc(hashmap->entries[idx],
 150                                         (i+2)*sizeof(*hashmap->entries[idx])));
 151   hashmap->entries[idx][i].key   = key;
 152   hashmap->entries[idx][i].value = value;
 153   memset(&hashmap->entries[idx][i+1], 0, sizeof(*hashmap->entries[idx]));
 154   hashmap->numEntries++;
 155   return value;
 156 }
 157
 158 void deleteFromHashMap(struct HashMap *hashmap, const char *key) {
 159   if (hashmap->mapSize == 0) {
 160     return;
 161   }
 162   unsigned hash = stringHashFunc(key);
 163   int idx       = hash % hashmap->mapSize;
 164   if (!hashmap->entries[idx]) {
 165     return;
 166   }
 167   for (int i = 0; hashmap->entries[idx][i].key; i++) {
 168     if (!strcmp(hashmap->entries[idx][i].key, key)) {
 169       int j     = i + 1;
 170       while (hashmap->entries[idx][j].key) {
 171         j++;
 172       }
 173       if (hashmap->destructor) {
 174         hashmap->destructor(hashmap->arg,
 175                             (char *)hashmap->entries[idx][i].key,
 176                             (char *)hashmap->entries[idx][i].value);
 177       }
 178       if (i != j-1) {
 179         memcpy(&hashmap->entries[idx][i], &hashmap->entries[idx][j-1],
 180                sizeof(*hashmap->entries[idx]));
 181       }
 182       memset(&hashmap->entries[idx][j-1], 0, sizeof(*hashmap->entries[idx]));
 183       check(--hashmap->numEntries >= 0);
 184     }
 185   }
 186 }
 187
 188 char **getRefFromHashMap(const struct HashMap *hashmap, const char *key) {
 189   if (hashmap->mapSize == 0) {
 190     return NULL;
 191   }
 192   unsigned hash = stringHashFunc(key);
 193   int idx       = hash % hashmap->mapSize;
 194   if (!hashmap->entries[idx]) {
 195     return NULL;
 196   }
 197   for (int i = 0; hashmap->entries[idx][i].key; i++) {
 198     if (!strcmp(hashmap->entries[idx][i].key, key)) {
 199       return (char **)&hashmap->entries[idx][i].value;
 200     }
 201   }
 202   return NULL;
 203 }
 204
 205 const char *getFromHashMap(const struct HashMap *hashmap, const char *key) {
 206   char **ref = getRefFromHashMap(hashmap, key);
 207   return ref ? *ref : NULL;
 208 }
 209
 210 void iterateOverHashMap(struct HashMap *hashmap,
 211                         int (*fnc)(void *arg, const char *key, char **value),
 212                         void *arg) {
 213   for (int i = 0; i < hashmap->mapSize; i++) {
 214     if (hashmap->entries[i]) {
 215       int count = 0;
 216       while (hashmap->entries[i][count].key) {
 217         count++;
 218       }
 219       for (int j = 0; j < count; j++) {
 220         if (!fnc(arg, hashmap->entries[i][j].key,
 221                  (char **)&hashmap->entries[i][j].value)) {
 222           if (hashmap->destructor) {
 223             hashmap->destructor(hashmap->arg,
 224                                 (char *)hashmap->entries[i][j].key,
 225                                 (char *)hashmap->entries[i][j].value);
 226           }
 227           if (j != count-1) {
 228             memcpy(&hashmap->entries[i][j], &hashmap->entries[i][count-1],
 229                    sizeof(*hashmap->entries[i]));
 230           }
 231           memset(&hashmap->entries[i][count-1], 0,
 232                  sizeof(*hashmap->entries[i]));
 233           count--;
 234           j--;
 235         }
 236       }
 237     }
 238   }
 239 }
 240
 241 int getHashmapSize(const struct HashMap *hashmap) {
 242   return hashmap->numEntries;
 243 }