deps/hiredis/dict.c

   1 /* Hash table implementation.
   2  *
   3  * This file implements in memory hash tables with insert/del/replace/find/
   4  * get-random-element operations. Hash tables will auto resize if needed
   5  * tables of power of two in size are used, collisions are handled by
   6  * chaining. See the source code for more information... :)
   7  *
   8  * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>
   9  * All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions are met:
  13  *
  14  *   * Redistributions of source code must retain the above copyright notice,
  15  *     this list of conditions and the following disclaimer.
  16  *   * Redistributions in binary form must reproduce the above copyright
  17  *     notice, this list of conditions and the following disclaimer in the
  18  *     documentation and/or other materials provided with the distribution.
  19  *   * Neither the name of Redis nor the names of its contributors may be used
  20  *     to endorse or promote products derived from this software without
  21  *     specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  24  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  27  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  28  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  29  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  30  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  31  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  32  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33  * POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 #include "fmacros.h"
  37 #include <stdlib.h>
  38 #include <assert.h>
  39 #include <limits.h>
  40 #include "dict.h"
  41
  42 /* -------------------------- private prototypes ---------------------------- */
  43
  44 static int _dictExpandIfNeeded(dict *ht);
  45 static unsigned long _dictNextPower(unsigned long size);
  46 static int _dictKeyIndex(dict *ht, const void *key);
  47 static int _dictInit(dict *ht, dictType *type, void *privDataPtr);
  48
  49 /* -------------------------- hash functions -------------------------------- */
  50
  51 /* Generic hash function (a popular one from Bernstein).
  52  * I tested a few and this was the best. */
  53 static unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
  54     unsigned int hash = 5381;
  55
  56     while (len--)
  57         hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */
  58     return hash;
  59 }
  60
  61 /* ----------------------------- API implementation ------------------------- */
  62
  63 /* Reset an hashtable already initialized with ht_init().
  64  * NOTE: This function should only called by ht_destroy(). */
  65 static void _dictReset(dict *ht) {
  66     ht->table = NULL;
  67     ht->size = 0;
  68     ht->sizemask = 0;
  69     ht->used = 0;
  70 }
  71
  72 /* Create a new hash table */
  73 static dict *dictCreate(dictType *type, void *privDataPtr) {
  74     dict *ht = malloc(sizeof(*ht));
  75     _dictInit(ht,type,privDataPtr);
  76     return ht;
  77 }
  78
  79 /* Initialize the hash table */
  80 static int _dictInit(dict *ht, dictType *type, void *privDataPtr) {
  81     _dictReset(ht);
  82     ht->type = type;
  83     ht->privdata = privDataPtr;
  84     return DICT_OK;
  85 }
  86
  87 /* Expand or create the hashtable */
  88 static int dictExpand(dict *ht, unsigned long size) {
  89     dict n; /* the new hashtable */
  90     unsigned long realsize = _dictNextPower(size), i;
  91
  92     /* the size is invalid if it is smaller than the number of
  93      * elements already inside the hashtable */
  94     if (ht->used > size)
  95         return DICT_ERR;
  96
  97     _dictInit(&n, ht->type, ht->privdata);
  98     n.size = realsize;
  99     n.sizemask = realsize-1;
 100     n.table = calloc(realsize,sizeof(dictEntry*));
 101
 102     /* Copy all the elements from the old to the new table:
 103      * note that if the old hash table is empty ht->size is zero,
 104      * so dictExpand just creates an hash table. */
 105     n.used = ht->used;
 106     for (i = 0; i < ht->size && ht->used > 0; i++) {
 107         dictEntry *he, *nextHe;
 108
 109         if (ht->table[i] == NULL) continue;
 110
 111         /* For each hash entry on this slot... */
 112         he = ht->table[i];
 113         while(he) {
 114             unsigned int h;
 115
 116             nextHe = he->next;
 117             /* Get the new element index */
 118             h = dictHashKey(ht, he->key) & n.sizemask;
 119             he->next = n.table[h];
 120             n.table[h] = he;
 121             ht->used--;
 122             /* Pass to the next element */
 123             he = nextHe;
 124         }
 125     }
 126     assert(ht->used == 0);
 127     free(ht->table);
 128
 129     /* Remap the new hashtable in the old */
 130     *ht = n;
 131     return DICT_OK;
 132 }
 133
 134 /* Add an element to the target hash table */
 135 static int dictAdd(dict *ht, void *key, void *val) {
 136     int index;
 137     dictEntry *entry;
 138
 139     /* Get the index of the new element, or -1 if
 140      * the element already exists. */
 141     if ((index = _dictKeyIndex(ht, key)) == -1)
 142         return DICT_ERR;
 143
 144     /* Allocates the memory and stores key */
 145     entry = malloc(sizeof(*entry));
 146     entry->next = ht->table[index];
 147     ht->table[index] = entry;
 148
 149     /* Set the hash entry fields. */
 150     dictSetHashKey(ht, entry, key);
 151     dictSetHashVal(ht, entry, val);
 152     ht->used++;
 153     return DICT_OK;
 154 }
 155
 156 /* Add an element, discarding the old if the key already exists.
 157  * Return 1 if the key was added from scratch, 0 if there was already an
 158  * element with such key and dictReplace() just performed a value update
 159  * operation. */
 160 static int dictReplace(dict *ht, void *key, void *val) {
 161     dictEntry *entry, auxentry;
 162
 163     /* Try to add the element. If the key
 164      * does not exists dictAdd will suceed. */
 165     if (dictAdd(ht, key, val) == DICT_OK)
 166         return 1;
 167     /* It already exists, get the entry */
 168     entry = dictFind(ht, key);
 169     /* Free the old value and set the new one */
 170     /* Set the new value and free the old one. Note that it is important
 171      * to do that in this order, as the value may just be exactly the same
 172      * as the previous one. In this context, think to reference counting,
 173      * you want to increment (set), and then decrement (free), and not the
 174      * reverse. */
 175     auxentry = *entry;
 176     dictSetHashVal(ht, entry, val);
 177     dictFreeEntryVal(ht, &auxentry);
 178     return 0;
 179 }
 180
 181 /* Search and remove an element */
 182 static int dictDelete(dict *ht, const void *key) {
 183     unsigned int h;
 184     dictEntry *de, *prevde;
 185
 186     if (ht->size == 0)
 187         return DICT_ERR;
 188     h = dictHashKey(ht, key) & ht->sizemask;
 189     de = ht->table[h];
 190
 191     prevde = NULL;
 192     while(de) {
 193         if (dictCompareHashKeys(ht,key,de->key)) {
 194             /* Unlink the element from the list */
 195             if (prevde)
 196                 prevde->next = de->next;
 197             else
 198                 ht->table[h] = de->next;
 199
 200             dictFreeEntryKey(ht,de);
 201             dictFreeEntryVal(ht,de);
 202             free(de);
 203             ht->used--;
 204             return DICT_OK;
 205         }
 206         prevde = de;
 207         de = de->next;
 208     }
 209     return DICT_ERR; /* not found */
 210 }
 211
 212 /* Destroy an entire hash table */
 213 static int _dictClear(dict *ht) {
 214     unsigned long i;
 215
 216     /* Free all the elements */
 217     for (i = 0; i < ht->size && ht->used > 0; i++) {
 218         dictEntry *he, *nextHe;
 219
 220         if ((he = ht->table[i]) == NULL) continue;
 221         while(he) {
 222             nextHe = he->next;
 223             dictFreeEntryKey(ht, he);
 224             dictFreeEntryVal(ht, he);
 225             free(he);
 226             ht->used--;
 227             he = nextHe;
 228         }
 229     }
 230     /* Free the table and the allocated cache structure */
 231     free(ht->table);
 232     /* Re-initialize the table */
 233     _dictReset(ht);
 234     return DICT_OK; /* never fails */
 235 }
 236
 237 /* Clear & Release the hash table */
 238 static void dictRelease(dict *ht) {
 239     _dictClear(ht);
 240     free(ht);
 241 }
 242
 243 static dictEntry *dictFind(dict *ht, const void *key) {
 244     dictEntry *he;
 245     unsigned int h;
 246
 247     if (ht->size == 0) return NULL;
 248     h = dictHashKey(ht, key) & ht->sizemask;
 249     he = ht->table[h];
 250     while(he) {
 251         if (dictCompareHashKeys(ht, key, he->key))
 252             return he;
 253         he = he->next;
 254     }
 255     return NULL;
 256 }
 257
 258 static dictIterator *dictGetIterator(dict *ht) {
 259     dictIterator *iter = malloc(sizeof(*iter));
 260
 261     iter->ht = ht;
 262     iter->index = -1;
 263     iter->entry = NULL;
 264     iter->nextEntry = NULL;
 265     return iter;
 266 }
 267
 268 static dictEntry *dictNext(dictIterator *iter) {
 269     while (1) {
 270         if (iter->entry == NULL) {
 271             iter->index++;
 272             if (iter->index >=
 273                     (signed)iter->ht->size) break;
 274             iter->entry = iter->ht->table[iter->index];
 275         } else {
 276             iter->entry = iter->nextEntry;
 277         }
 278         if (iter->entry) {
 279             /* We need to save the 'next' here, the iterator user
 280              * may delete the entry we are returning. */
 281             iter->nextEntry = iter->entry->next;
 282             return iter->entry;
 283         }
 284     }
 285     return NULL;
 286 }
 287
 288 static void dictReleaseIterator(dictIterator *iter) {
 289     free(iter);
 290 }
 291
 292 /* ------------------------- private functions ------------------------------ */
 293
 294 /* Expand the hash table if needed */
 295 static int _dictExpandIfNeeded(dict *ht) {
 296     /* If the hash table is empty expand it to the intial size,
 297      * if the table is "full" dobule its size. */
 298     if (ht->size == 0)
 299         return dictExpand(ht, DICT_HT_INITIAL_SIZE);
 300     if (ht->used == ht->size)
 301         return dictExpand(ht, ht->size*2);
 302     return DICT_OK;
 303 }
 304
 305 /* Our hash table capability is a power of two */
 306 static unsigned long _dictNextPower(unsigned long size) {
 307     unsigned long i = DICT_HT_INITIAL_SIZE;
 308
 309     if (size >= LONG_MAX) return LONG_MAX;
 310     while(1) {
 311         if (i >= size)
 312             return i;
 313         i *= 2;
 314     }
 315 }
 316
 317 /* Returns the index of a free slot that can be populated with
 318  * an hash entry for the given 'key'.
 319  * If the key already exists, -1 is returned. */
 320 static int _dictKeyIndex(dict *ht, const void *key) {
 321     unsigned int h;
 322     dictEntry *he;
 323
 324     /* Expand the hashtable if needed */
 325     if (_dictExpandIfNeeded(ht) == DICT_ERR)
 326         return -1;
 327     /* Compute the key hash value */
 328     h = dictHashKey(ht, key) & ht->sizemask;
 329     /* Search if this slot does not already contain the given key */
 330     he = ht->table[h];
 331     while(he) {
 332         if (dictCompareHashKeys(ht, key, he->key))
 333             return -1;
 334         he = he->next;
 335     }
 336     return h;
 337 }
 338