summaryrefslogtreecommitdiff
path: root/deps/hiredis/dict.c
diff options
context:
space:
mode:
Diffstat (limited to 'deps/hiredis/dict.c')
-rw-r--r--deps/hiredis/dict.c338
1 files changed, 0 insertions, 338 deletions
diff --git a/deps/hiredis/dict.c b/deps/hiredis/dict.c
deleted file mode 100644
index e17a62546..000000000
--- a/deps/hiredis/dict.c
+++ /dev/null
@@ -1,338 +0,0 @@
-/* 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 <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 = malloc(sizeof(*ht));
- _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 = calloc(realsize,sizeof(dictEntry*));
-
- /* 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);
- 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 = malloc(sizeof(*entry));
- 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);
- /* 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);
- 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);
- free(he);
- ht->used--;
- he = nextHe;
- }
- }
- /* Free the table and the allocated cache structure */
- 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);
- 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 dictIterator *dictGetIterator(dict *ht) {
- dictIterator *iter = malloc(sizeof(*iter));
-
- iter->ht = ht;
- iter->index = -1;
- iter->entry = NULL;
- iter->nextEntry = NULL;
- return iter;
-}
-
-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;
-}
-
-static void dictReleaseIterator(dictIterator *iter) {
- free(iter);
-}
-
-/* ------------------------- 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" dobule 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;
-}
-