* tables of power of two in size are used, collisions are handled by
* chaining. See the source code for more information... :)
*
- * Copyright (c) 2006-20
09, Salvatore Sanfilippo <antirez at gmail dot com>
+ * Copyright (c) 2006-20
10, Salvatore Sanfilippo <antirez at gmail dot com>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* POSSIBILITY OF SUCH DAMAGE.
*/
+#include "fmacros.h"
+
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <assert.h>
+#include <limits.h>
#include "dict.h"
#include "zmalloc.h"
+/* Using dictEnableResize() / dictDisableResize() we make possible to
+ * enable/disable resizing of the hash table as needed. This is very important
+ * for Redis, as we use copy-on-write and don't want to move too much memory
+ * around when there is a child performing saving operations. */
+static int dict_can_resize = 1;
+
/* ---------------------------- Utility funcitons --------------------------- */
static void _dictPanic(const char *fmt, ...)
/* ------------------------- Heap Management Wrappers------------------------ */
-static void *_dictAlloc(int size)
+static void *_dictAlloc(size_t size)
{
void *p = zmalloc(size);
if (p == NULL)
/* -------------------------- private prototypes ---------------------------- */
static int _dictExpandIfNeeded(dict *ht);
-static unsigned int _dictNextPower(unsigned int size);
+static unsigned long _dictNextPower(unsigned long size);
static int _dictKeyIndex(dict *ht, const void *key);
static int _dictInit(dict *ht, dictType *type, void *privDataPtr);
{
int minimal = ht->used;
+ if (!dict_can_resize) return DICT_ERR;
if (minimal < DICT_HT_INITIAL_SIZE)
minimal = DICT_HT_INITIAL_SIZE;
return dictExpand(ht, minimal);
}
/* Expand or create the hashtable */
-int dictExpand(dict *ht, unsigned int size)
+int dictExpand(dict *ht, unsigned long size)
{
dict n; /* the new hashtable */
- unsigned int realsize = _dictNextPower(size), i;
+ unsigned long realsize = _dictNextPower(size), i;
/* the size is invalid if it is smaller than the number of
* elements already inside the hashtable */
return DICT_OK;
}
-/* Add an element, discarding the old if the key already exists */
+/* 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. */
int dictReplace(dict *ht, void *key, void *val)
{
- dictEntry *entry;
+ dictEntry *entry, auxentry;
/* Try to add the element. If the key
* does not exists dictAdd will suceed. */
if (dictAdd(ht, key, val) == DICT_OK)
- return DICT_OK;
+ return 1;
/* It already exists, get the entry */
entry = dictFind(ht, key);
/* Free the old value and set the new one */
- dictFreeEntryVal(ht, entry);
+ /* 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);
- return DICT_OK;
+ dictFreeEntryVal(ht, &auxentry);
+ return 0;
}
/* Search and remove an element */
/* Destroy an entire hash table */
int _dictClear(dict *ht)
{
- unsigned int i;
+ unsigned long i;
/* Free all the elements */
for (i = 0; i < ht->size && ht->used > 0; i++) {
unsigned int h;
int listlen, listele;
- if (ht->size == 0) return NULL;
+ if (ht->used == 0) return NULL;
do {
h = random() & ht->sizemask;
he = ht->table[h];
* 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);
+ if (ht->used >= ht->size && dict_can_resize)
+ return dictExpand(ht, ((ht->size > ht->used) ? ht->size : ht->used)*2);
return DICT_OK;
}
/* Our hash table capability is a power of two */
-static unsigned int _dictNextPower(unsigned int size)
+static unsigned long _dictNextPower(unsigned long size)
{
- unsigned int i = DICT_HT_INITIAL_SIZE;
+ unsigned long i = DICT_HT_INITIAL_SIZE;
- if (size >= 2147483648U)
- return 2147483648U;
+ if (size >= LONG_MAX) return LONG_MAX;
while(1) {
if (i >= size)
return i;
#define DICT_STATS_VECTLEN 50
void dictPrintStats(dict *ht) {
- unsigned int i, slots = 0, chainlen, maxchainlen = 0;
- unsigned int totchainlen = 0;
- unsigned int clvector[DICT_STATS_VECTLEN];
+ unsigned long i, slots = 0, chainlen, maxchainlen = 0;
+ unsigned long totchainlen = 0;
+ unsigned long clvector[DICT_STATS_VECTLEN];
if (ht->used == 0) {
printf("No stats available for empty dictionaries\n");
totchainlen += chainlen;
}
printf("Hash table stats:\n");
- printf(" table size: %d\n", ht->size);
- printf(" number of elements: %d\n", ht->used);
- printf(" different slots: %d\n", slots);
- printf(" max chain length: %d\n", maxchainlen);
+ printf(" table size: %ld\n", ht->size);
+ printf(" number of elements: %ld\n", ht->used);
+ printf(" different slots: %ld\n", slots);
+ printf(" max chain length: %ld\n", maxchainlen);
printf(" avg chain length (counted): %.02f\n", (float)totchainlen/slots);
printf(" avg chain length (computed): %.02f\n", (float)ht->used/slots);
printf(" Chain length distribution:\n");
for (i = 0; i < DICT_STATS_VECTLEN-1; i++) {
if (clvector[i] == 0) continue;
- printf(" %s%d: %d (%.02f%%)\n",(i == DICT_STATS_VECTLEN-1)?">= ":"", i, clvector[i], ((float)clvector[i]/ht->size)*100);
+ printf(" %s%ld: %ld (%.02f%%)\n",(i == DICT_STATS_VECTLEN-1)?">= ":"", i, clvector[i], ((float)clvector[i]/ht->size)*100);
}
}
+void dictEnableResize(void) {
+ dict_can_resize = 1;
+}
+
+void dictDisableResize(void) {
+ dict_can_resize = 0;
+}
+
/* ----------------------- StringCopy Hash Table Type ------------------------*/
static unsigned int _dictStringCopyHTHashFunction(const void *key)
projects / redis.git / blobdiff