summaryrefslogtreecommitdiffstats
path: root/contrib/hiredis/dict.c
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/hiredis/dict.c')
-rw-r--r--contrib/hiredis/dict.c340
1 files changed, 340 insertions, 0 deletions
diff --git a/contrib/hiredis/dict.c b/contrib/hiredis/dict.c
new file mode 100644
index 0000000..0fbc1b4
--- /dev/null
+++ b/contrib/hiredis/dict.c
@@ -0,0 +1,340 @@
+/* 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. */
+ if (entry) {
+ 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;
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-16 22:00:59 +0000