#include "fmacros.h"

#include <stdio.h>

#include <stdlib.h>

#include <stdint.h>

#include <string.h>

#include <stdarg.h>

#include <limits.h>

#include <sys/time.h>

#include "dict.h"

#include "zmalloc.h"

#ifndef DICT_BENCHMARK_MAIN

#include "redisassert.h"

#else

#include <assert.h>

#endif

static int dict_can_resize = 1;

static unsigned int dict_force_resize_ratio = 5;

static int _dictExpandIfNeeded(dict *ht);

static unsigned long _dictNextPower(unsigned long size);

static long _dictKeyIndex(dict *ht, const void *key, uint64_t hash, dictEntry **existing);

static int _dictInit(dict *ht, dictType *type, void *privDataPtr);

static uint8_t dict_hash_function_seed[16];

void dictSetHashFunctionSeed(uint8_t *seed) {

memcpy(dict_hash_function_seed,seed,sizeof(dict_hash_function_seed));

}

uint8_t *dictGetHashFunctionSeed(void) {

return dict_hash_function_seed;

}

extern "C" uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k);

extern "C" uint64_t siphash_nocase(const uint8_t *in, const size_t inlen, const uint8_t *k);

uint64_t dictGenHashFunction(const void *key, int len) {

return siphash((const uint8_t*)key,len,dict_hash_function_seed);

}

uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len) {

return siphash_nocase(buf,len,dict_hash_function_seed);

}

static void _dictReset(dictht *ht)

}

dict *dictCreate(dictType *type,

void *privDataPtr)

{

dict *d = (dict*)zmalloc(sizeof(*d), MALLOC_SHARED);

_dictInit(d,type,privDataPtr);

return d;

}

int _dictInit(dict *d, dictType *type,

}

int dictResize(dict *d)

}

int dictExpand(dict *d, unsigned long size)

}

int dictRehash(dict *d, int n) {

}

dictAsyncRehashCtl *dictRehashAsyncStart(dict *d, int buckets) {

if (!dictIsRehashing(d)) return 0;

d->asyncdata = new dictAsyncRehashCtl(d, d->asyncdata);

int empty_visits = buckets * 10;

while (d->asyncdata->queue.size() < (size_t)buckets && d->rehashidx < d->ht[0].size) {

dictEntry *de;

/* Note that rehashidx can't overflow as we are sure there are more

while(d->ht[0].table[d->rehashidx] == NULL) {

d->rehashidx++;

if (--empty_visits == 0) goto LDone;

if (d->rehashidx >= d->ht[0].size) goto LDone;

}

de = d->ht[0].table[d->rehashidx];

// We have to queue every node in the bucket, even if we go over our target size

while (de != nullptr) {

d->asyncdata->queue.emplace_back(de);

de = de->next;

}

d->rehashidx++;

}

LDone:

if (d->asyncdata->queue.empty()) {

// We didn't find any work to do (can happen if there is a large gap in the hash table)

auto asyncT = d->asyncdata;

d->asyncdata = d->asyncdata->next;

delete asyncT;

return nullptr;

}

return d->asyncdata;

}

void dictRehashAsync(dictAsyncRehashCtl *ctl) {

}

bool dictRehashSomeAsync(dictAsyncRehashCtl *ctl, size_t hashes) {

}

void dictCompleteRehashAsync(dictAsyncRehashCtl *ctl, bool fFree) {

}

long long timeInMilliseconds(void) {

}

int dictRehashMilliseconds(dict *d, int ms) {

}

static void _dictRehashStep(dict *d) {

if (d->iterators == 0) dictRehash(d,1);

}

int dictAdd(dict *d, void *key, void *val)

}

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)

{

long index;

dictEntry *entry;

dictht *ht;

if (dictIsRehashing(d)) _dictRehashStep(d);

/* Get the index of the new element, or -1 if

if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)

return NULL;

/* Allocate the memory and store the new entry.

ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];

entry = (dictEntry*)zmalloc(sizeof(*entry), MALLOC_SHARED);

entry->next = ht->table[index];

ht->table[index] = entry;

ht->used++;

/* Set the hash entry fields. */

dictSetKey(d, entry, key);

return entry;

}

int dictReplace(dict *d, void *key, void *val)

}

dictEntry *dictAddOrFind(dict *d, void *key) {

dictEntry *entry, *existing;

entry = dictAddRaw(d,key,&existing);

return entry ? entry : existing;

}

static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {

uint64_t h, idx;

dictEntry *he, *prevHe;

int table;

if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;

if (dictIsRehashing(d)) _dictRehashStep(d);

h = dictHashKey(d, key);

for (table = 0; table <= 1; table++) {

idx = h & d->ht[table].sizemask;

he = d->ht[table].table[idx];

prevHe = NULL;

while(he) {

if (key==he->key || dictCompareKeys(d, key, he->key)) {

/* Unlink the element from the list */

if (prevHe)

prevHe->next = he->next;

else

d->ht[table].table[idx] = he->next;

if (!nofree) {

if (table == 0 && d->asyncdata != nullptr && idx < d->rehashidx) {

he->next = d->asyncdata->deGCList;

d->asyncdata->deGCList = he->next;

} else {

dictFreeKey(d, he);

dictFreeVal(d, he);

zfree(he);

}

}

d->ht[table].used--;

return he;

}

prevHe = he;

he = he->next;

}

if (!dictIsRehashing(d)) break;

}

return NULL; /* not found */

}

int dictDelete(dict *ht, const void *key) {

return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;

}

dictEntry *dictUnlink(dict *ht, const void *key) {

return dictGenericDelete(ht,key,1);

}

void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {

}

int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {

}

void dictRelease(dict *d)

}

dictEntry *dictFind(dict *d, const void *key)

{

dictEntry *he;

uint64_t h, idx, table;

if (dictSize(d) == 0) return NULL; /* dict is empty */

if (dictIsRehashing(d)) _dictRehashStep(d);

h = dictHashKey(d, key);

for (table = 0; table <= 1; table++) {

idx = h & d->ht[table].sizemask;

he = d->ht[table].table[idx];

while(he) {

if (key==he->key || dictCompareKeys(d, key, he->key))

return he;

he = he->next;

}

if (!dictIsRehashing(d)) return NULL;

}

return NULL;

}

void *dictFetchValue(dict *d, const void *key) {

dictEntry *he;

he = dictFind(d,key);

return he ? dictGetVal(he) : NULL;

}

long long dictFingerprint(dict *d) {

}

dictIterator *dictGetIterator(dict *d)

{

dictIterator *iter = (dictIterator*)zmalloc(sizeof(*iter), MALLOC_LOCAL);

iter->d = d;

iter->table = 0;

iter->index = -1;

iter->safe = 0;

iter->entry = NULL;

iter->nextEntry = NULL;

return iter;

}

dictIterator *dictGetSafeIterator(dict *d) {

dictIterator *i = dictGetIterator(d);

i->safe = 1;

return i;

}

dictEntry *dictNext(dictIterator *iter)

{

while (1) {

if (iter->entry == NULL) {

dictht *ht = &iter->d->ht[iter->table];

if (iter->index == -1 && iter->table == 0) {

if (iter->safe)

iter->d->iterators++;

else

iter->fingerprint = dictFingerprint(iter->d);

}

iter->index++;

if (iter->index >= (long) ht->size) {

if (dictIsRehashing(iter->d) && iter->table == 0) {

iter->table++;

iter->index = 0;

ht = &iter->d->ht[1];

} else {

break;

}

}

iter->entry = ht->table[iter->index];

} else {

iter->entry = iter->nextEntry;

}

if (iter->entry) {

/* We need to save the 'next' here, the iterator user

iter->nextEntry = iter->entry->next;

return iter->entry;

}

}

return NULL;

}

void dictReleaseIterator(dictIterator *iter)

}

dictEntry *dictGetRandomKey(dict *d)

{

dictEntry *he, *orighe;

unsigned long h;

int listlen, listele;

if (dictSize(d) == 0) return NULL;

if (dictIsRehashing(d)) _dictRehashStep(d);

if (dictIsRehashing(d)) {

do {

/* We are sure there are no elements in indexes from 0

h = d->rehashidx + (random() % (d->ht[0].size +

d->ht[1].size -

d->rehashidx));

he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :

d->ht[0].table[h];

} while(he == NULL);

} else {

do {

h = random() & d->ht[0].sizemask;

he = d->ht[0].table[h];

} while(he == NULL);

}

/* Now we found a non empty bucket, but it is a linked

listlen = 0;

orighe = he;

while(he) {

he = he->next;

listlen++;

}

listele = random() % listlen;

he = orighe;

while(listele--) he = he->next;

return he;

}

unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) {

}

#define GETFAIR_NUM_ENTRIES 15

dictEntry *dictGetFairRandomKey(dict *d) {

dictEntry *entries[GETFAIR_NUM_ENTRIES];

unsigned int count = dictGetSomeKeys(d,entries,GETFAIR_NUM_ENTRIES);

/* Note that dictGetSomeKeys() may return zero elements in an unlucky

if (count == 0) return dictGetRandomKey(d);

unsigned int idx = rand() % count;

return entries[idx];

}

static unsigned long rev(unsigned long v) {

}