You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
343 lines
10 KiB
343 lines
10 KiB
/* Hash table implementation. |
|
* |
|
* This file implements in memory hash tables with insert/del/replace/find/ |
|
* get-random-element operations. Hash tables will auto resize if needed |
|
* tables of power of two in size are used, collisions are handled by |
|
* chaining. See the source code for more information... :) |
|
* |
|
* Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com> |
|
* All rights reserved. |
|
* |
|
* Redistribution and use in source and binary forms, with or without |
|
* modification, are permitted provided that the following conditions are met: |
|
* |
|
* * Redistributions of source code must retain the above copyright notice, |
|
* this list of conditions and the following disclaimer. |
|
* * Redistributions in binary form must reproduce the above copyright |
|
* notice, this list of conditions and the following disclaimer in the |
|
* documentation and/or other materials provided with the distribution. |
|
* * Neither the name of Redis nor the names of its contributors may be used |
|
* to endorse or promote products derived from this software without |
|
* specific prior written permission. |
|
* |
|
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
|
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
|
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
|
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
|
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
|
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
|
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
|
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
|
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
|
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
|
* POSSIBILITY OF SUCH DAMAGE. |
|
*/ |
|
|
|
#include "fmacros.h" |
|
#include "alloc.h" |
|
#include <stdlib.h> |
|
#include <assert.h> |
|
#include <limits.h> |
|
#include "dict.h" |
|
|
|
/* -------------------------- private prototypes ---------------------------- */ |
|
|
|
static int _dictExpandIfNeeded(dict *ht); |
|
static unsigned long _dictNextPower(unsigned long size); |
|
static int _dictKeyIndex(dict *ht, const void *key); |
|
static int _dictInit(dict *ht, dictType *type, void *privDataPtr); |
|
|
|
/* -------------------------- hash functions -------------------------------- */ |
|
|
|
/* Generic hash function (a popular one from Bernstein). |
|
* I tested a few and this was the best. */ |
|
static unsigned int dictGenHashFunction(const unsigned char *buf, int len) { |
|
unsigned int hash = 5381; |
|
|
|
while (len--) |
|
hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */ |
|
return hash; |
|
} |
|
|
|
/* ----------------------------- API implementation ------------------------- */ |
|
|
|
/* Reset an hashtable already initialized with ht_init(). |
|
* NOTE: This function should only called by ht_destroy(). */ |
|
static void _dictReset(dict *ht) { |
|
ht->table = NULL; |
|
ht->size = 0; |
|
ht->sizemask = 0; |
|
ht->used = 0; |
|
} |
|
|
|
/* Create a new hash table */ |
|
static dict *dictCreate(dictType *type, void *privDataPtr) { |
|
dict *ht = hi_malloc(sizeof(*ht)); |
|
if (ht == NULL) |
|
return NULL; |
|
|
|
_dictInit(ht,type,privDataPtr); |
|
return ht; |
|
} |
|
|
|
/* Initialize the hash table */ |
|
static int _dictInit(dict *ht, dictType *type, void *privDataPtr) { |
|
_dictReset(ht); |
|
ht->type = type; |
|
ht->privdata = privDataPtr; |
|
return DICT_OK; |
|
} |
|
|
|
/* Expand or create the hashtable */ |
|
static int dictExpand(dict *ht, unsigned long size) { |
|
dict n; /* the new hashtable */ |
|
unsigned long realsize = _dictNextPower(size), i; |
|
|
|
/* the size is invalid if it is smaller than the number of |
|
* elements already inside the hashtable */ |
|
if (ht->used > size) |
|
return DICT_ERR; |
|
|
|
_dictInit(&n, ht->type, ht->privdata); |
|
n.size = realsize; |
|
n.sizemask = realsize-1; |
|
n.table = hi_calloc(realsize,sizeof(dictEntry*)); |
|
if (n.table == NULL) |
|
return DICT_ERR; |
|
|
|
/* Copy all the elements from the old to the new table: |
|
* note that if the old hash table is empty ht->size is zero, |
|
* so dictExpand just creates an hash table. */ |
|
n.used = ht->used; |
|
for (i = 0; i < ht->size && ht->used > 0; i++) { |
|
dictEntry *he, *nextHe; |
|
|
|
if (ht->table[i] == NULL) continue; |
|
|
|
/* For each hash entry on this slot... */ |
|
he = ht->table[i]; |
|
while(he) { |
|
unsigned int h; |
|
|
|
nextHe = he->next; |
|
/* Get the new element index */ |
|
h = dictHashKey(ht, he->key) & n.sizemask; |
|
he->next = n.table[h]; |
|
n.table[h] = he; |
|
ht->used--; |
|
/* Pass to the next element */ |
|
he = nextHe; |
|
} |
|
} |
|
assert(ht->used == 0); |
|
hi_free(ht->table); |
|
|
|
/* Remap the new hashtable in the old */ |
|
*ht = n; |
|
return DICT_OK; |
|
} |
|
|
|
/* Add an element to the target hash table */ |
|
static int dictAdd(dict *ht, void *key, void *val) { |
|
int index; |
|
dictEntry *entry; |
|
|
|
/* Get the index of the new element, or -1 if |
|
* the element already exists. */ |
|
if ((index = _dictKeyIndex(ht, key)) == -1) |
|
return DICT_ERR; |
|
|
|
/* Allocates the memory and stores key */ |
|
entry = hi_malloc(sizeof(*entry)); |
|
if (entry == NULL) |
|
return DICT_ERR; |
|
|
|
entry->next = ht->table[index]; |
|
ht->table[index] = entry; |
|
|
|
/* Set the hash entry fields. */ |
|
dictSetHashKey(ht, entry, key); |
|
dictSetHashVal(ht, entry, val); |
|
ht->used++; |
|
return DICT_OK; |
|
} |
|
|
|
/* Add an element, discarding the old if the key already exists. |
|
* Return 1 if the key was added from scratch, 0 if there was already an |
|
* element with such key and dictReplace() just performed a value update |
|
* operation. */ |
|
static int dictReplace(dict *ht, void *key, void *val) { |
|
dictEntry *entry, auxentry; |
|
|
|
/* Try to add the element. If the key |
|
* does not exists dictAdd will succeed. */ |
|
if (dictAdd(ht, key, val) == DICT_OK) |
|
return 1; |
|
/* It already exists, get the entry */ |
|
entry = dictFind(ht, key); |
|
if (entry == NULL) |
|
return 0; |
|
|
|
/* Free the old value and set the new one */ |
|
/* Set the new value and free the old one. Note that it is important |
|
* to do that in this order, as the value may just be exactly the same |
|
* as the previous one. In this context, think to reference counting, |
|
* you want to increment (set), and then decrement (free), and not the |
|
* reverse. */ |
|
auxentry = *entry; |
|
dictSetHashVal(ht, entry, val); |
|
dictFreeEntryVal(ht, &auxentry); |
|
return 0; |
|
} |
|
|
|
/* Search and remove an element */ |
|
static int dictDelete(dict *ht, const void *key) { |
|
unsigned int h; |
|
dictEntry *de, *prevde; |
|
|
|
if (ht->size == 0) |
|
return DICT_ERR; |
|
h = dictHashKey(ht, key) & ht->sizemask; |
|
de = ht->table[h]; |
|
|
|
prevde = NULL; |
|
while(de) { |
|
if (dictCompareHashKeys(ht,key,de->key)) { |
|
/* Unlink the element from the list */ |
|
if (prevde) |
|
prevde->next = de->next; |
|
else |
|
ht->table[h] = de->next; |
|
|
|
dictFreeEntryKey(ht,de); |
|
dictFreeEntryVal(ht,de); |
|
hi_free(de); |
|
ht->used--; |
|
return DICT_OK; |
|
} |
|
prevde = de; |
|
de = de->next; |
|
} |
|
return DICT_ERR; /* not found */ |
|
} |
|
|
|
/* Destroy an entire hash table */ |
|
static int _dictClear(dict *ht) { |
|
unsigned long i; |
|
|
|
/* Free all the elements */ |
|
for (i = 0; i < ht->size && ht->used > 0; i++) { |
|
dictEntry *he, *nextHe; |
|
|
|
if ((he = ht->table[i]) == NULL) continue; |
|
while(he) { |
|
nextHe = he->next; |
|
dictFreeEntryKey(ht, he); |
|
dictFreeEntryVal(ht, he); |
|
hi_free(he); |
|
ht->used--; |
|
he = nextHe; |
|
} |
|
} |
|
/* Free the table and the allocated cache structure */ |
|
hi_free(ht->table); |
|
/* Re-initialize the table */ |
|
_dictReset(ht); |
|
return DICT_OK; /* never fails */ |
|
} |
|
|
|
/* Clear & Release the hash table */ |
|
static void dictRelease(dict *ht) { |
|
_dictClear(ht); |
|
hi_free(ht); |
|
} |
|
|
|
static dictEntry *dictFind(dict *ht, const void *key) { |
|
dictEntry *he; |
|
unsigned int h; |
|
|
|
if (ht->size == 0) return NULL; |
|
h = dictHashKey(ht, key) & ht->sizemask; |
|
he = ht->table[h]; |
|
while(he) { |
|
if (dictCompareHashKeys(ht, key, he->key)) |
|
return he; |
|
he = he->next; |
|
} |
|
return NULL; |
|
} |
|
|
|
static void dictInitIterator(dictIterator *iter, dict *ht) { |
|
iter->ht = ht; |
|
iter->index = -1; |
|
iter->entry = NULL; |
|
iter->nextEntry = NULL; |
|
} |
|
|
|
static dictEntry *dictNext(dictIterator *iter) { |
|
while (1) { |
|
if (iter->entry == NULL) { |
|
iter->index++; |
|
if (iter->index >= |
|
(signed)iter->ht->size) break; |
|
iter->entry = iter->ht->table[iter->index]; |
|
} else { |
|
iter->entry = iter->nextEntry; |
|
} |
|
if (iter->entry) { |
|
/* We need to save the 'next' here, the iterator user |
|
* may delete the entry we are returning. */ |
|
iter->nextEntry = iter->entry->next; |
|
return iter->entry; |
|
} |
|
} |
|
return NULL; |
|
} |
|
|
|
/* ------------------------- private functions ------------------------------ */ |
|
|
|
/* Expand the hash table if needed */ |
|
static int _dictExpandIfNeeded(dict *ht) { |
|
/* If the hash table is empty expand it to the initial size, |
|
* if the table is "full" double its size. */ |
|
if (ht->size == 0) |
|
return dictExpand(ht, DICT_HT_INITIAL_SIZE); |
|
if (ht->used == ht->size) |
|
return dictExpand(ht, ht->size*2); |
|
return DICT_OK; |
|
} |
|
|
|
/* Our hash table capability is a power of two */ |
|
static unsigned long _dictNextPower(unsigned long size) { |
|
unsigned long i = DICT_HT_INITIAL_SIZE; |
|
|
|
if (size >= LONG_MAX) return LONG_MAX; |
|
while(1) { |
|
if (i >= size) |
|
return i; |
|
i *= 2; |
|
} |
|
} |
|
|
|
/* Returns the index of a free slot that can be populated with |
|
* an hash entry for the given 'key'. |
|
* If the key already exists, -1 is returned. */ |
|
static int _dictKeyIndex(dict *ht, const void *key) { |
|
unsigned int h; |
|
dictEntry *he; |
|
|
|
/* Expand the hashtable if needed */ |
|
if (_dictExpandIfNeeded(ht) == DICT_ERR) |
|
return -1; |
|
/* Compute the key hash value */ |
|
h = dictHashKey(ht, key) & ht->sizemask; |
|
/* Search if this slot does not already contain the given key */ |
|
he = ht->table[h]; |
|
while(he) { |
|
if (dictCompareHashKeys(ht, key, he->key)) |
|
return -1; |
|
he = he->next; |
|
} |
|
return h; |
|
} |
|
|
|
|