|
Packit |
857059 |
/* BEGIN_ICS_COPYRIGHT5 ****************************************
|
|
Packit |
857059 |
|
|
Packit |
857059 |
Copyright (c) 2015-2017, Intel Corporation
|
|
Packit |
857059 |
|
|
Packit |
857059 |
Redistribution and use in source and binary forms, with or without
|
|
Packit |
857059 |
modification, are permitted provided that the following conditions are met:
|
|
Packit |
857059 |
|
|
Packit |
857059 |
* Redistributions of source code must retain the above copyright notice,
|
|
Packit |
857059 |
this list of conditions and the following disclaimer.
|
|
Packit |
857059 |
* Redistributions in binary form must reproduce the above copyright
|
|
Packit |
857059 |
notice, this list of conditions and the following disclaimer in the
|
|
Packit |
857059 |
documentation and/or other materials provided with the distribution.
|
|
Packit |
857059 |
* Neither the name of Intel Corporation nor the names of its contributors
|
|
Packit |
857059 |
may be used to endorse or promote products derived from this software
|
|
Packit |
857059 |
without specific prior written permission.
|
|
Packit |
857059 |
|
|
Packit |
857059 |
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
|
|
Packit |
857059 |
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
|
Packit |
857059 |
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
|
|
Packit |
857059 |
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
|
|
Packit |
857059 |
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
|
|
Packit |
857059 |
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
|
|
Packit |
857059 |
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
|
|
Packit |
857059 |
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
|
|
Packit |
857059 |
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
|
|
Packit |
857059 |
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
Packit |
857059 |
|
|
Packit |
857059 |
* ** END_ICS_COPYRIGHT5 ****************************************/
|
|
Packit |
857059 |
|
|
Packit |
857059 |
#define INLINE
|
|
Packit |
857059 |
#include "cs_hashtable.h"
|
|
Packit |
857059 |
#include <stdlib.h>
|
|
Packit |
857059 |
#include <stdio.h>
|
|
Packit |
857059 |
#include <string.h>
|
|
Packit |
857059 |
#include <math.h>
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* prime table
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
static const uint32_t primes[] = {
|
|
Packit |
857059 |
53, 97, 193, 389,
|
|
Packit |
857059 |
769, 1543, 3079, 6151,
|
|
Packit |
857059 |
12289, 24593, 49157, 98317,
|
|
Packit |
857059 |
196613, 393241, 786433, 1572869,
|
|
Packit |
857059 |
3145739, 6291469, 12582917, 25165843,
|
|
Packit |
857059 |
50331653, 100663319, 201326611, 402653189,
|
|
Packit |
857059 |
805306457, 1610612741
|
|
Packit |
857059 |
};
|
|
Packit |
857059 |
const uint32_t prime_table_length = sizeof(primes)/sizeof(primes[0]);
|
|
Packit |
857059 |
#define MAX_LOAD_FACTOR_NUMERATOR 8
|
|
Packit |
857059 |
#define MAX_LOAD_FACTOR_DENOMINATOR 10
|
|
Packit |
857059 |
static int32_t cs_hashtable_expand(struct cs_hashtable *h);
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* cs_create_hashtable
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
struct cs_hashtable *
|
|
Packit |
857059 |
cs_create_hashtable(const char *name,
|
|
Packit |
857059 |
uint32_t minsize,
|
|
Packit |
857059 |
uint64_t (*hashf) (void*),
|
|
Packit |
857059 |
int32_t (*eqf) (void*,void*),
|
|
Packit |
857059 |
CS_Hash_KeyType_t keytype)
|
|
Packit |
857059 |
{
|
|
Packit |
857059 |
struct cs_hashtable *h;
|
|
Packit |
857059 |
uint32_t pindex;
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/* Check requested hashtable isn't too large */
|
|
Packit |
857059 |
if (minsize > (1u << 30)) return NULL;
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/* Enforce size as prime */
|
|
Packit |
857059 |
for (pindex=0; pindex < prime_table_length; pindex++) {
|
|
Packit |
857059 |
if (primes[pindex] > minsize) break;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|
|
Packit |
857059 |
h = (struct cs_hashtable *)malloc(sizeof(struct cs_hashtable));
|
|
Packit |
857059 |
if (NULL == h) return NULL;
|
|
Packit |
857059 |
|
|
Packit |
857059 |
memset(h, 0, sizeof(*h));
|
|
Packit |
857059 |
h->name = name;
|
|
Packit |
857059 |
h->primeindex = pindex - 1;
|
|
Packit |
857059 |
h->hashfn = hashf;
|
|
Packit |
857059 |
h->eqfn = eqf;
|
|
Packit |
857059 |
h->keyType = keytype;
|
|
Packit |
857059 |
if (cs_hashtable_expand(h) == 0) {
|
|
Packit |
857059 |
free(h);
|
|
Packit |
857059 |
return NULL;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
return h;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* hash
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
static uint64_t
|
|
Packit |
857059 |
_hash(struct cs_hashtable *h, void *k)
|
|
Packit |
857059 |
{
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* Aim to protect against poor hash functions by adding logic here
|
|
Packit |
857059 |
* - logic taken from java 1.4 hashtable source
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
uint64_t i = h->hashfn(k);
|
|
Packit |
857059 |
i += ~(i << 9);
|
|
Packit |
857059 |
i ^= ((i >> 14) | (i << 18)); /* >>> */
|
|
Packit |
857059 |
i += (i << 4);
|
|
Packit |
857059 |
i ^= ((i >> 10) | (i << 22)); /* >>> */
|
|
Packit |
857059 |
return i;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* cs_hashtable_expand
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
static int32_t
|
|
Packit |
857059 |
cs_hashtable_expand(struct cs_hashtable *h)
|
|
Packit |
857059 |
{
|
|
Packit |
857059 |
/* Double the size of the table to accomodate more entries */
|
|
Packit |
857059 |
struct hash_entry **newtable;
|
|
Packit |
857059 |
struct hash_entry *e;
|
|
Packit |
857059 |
uint32_t newsize;
|
|
Packit |
857059 |
uint32_t index;
|
|
Packit |
857059 |
/* Check we're not hitting max capacity */
|
|
Packit |
857059 |
if (h->primeindex == (prime_table_length - 1))
|
|
Packit |
857059 |
return 0;
|
|
Packit |
857059 |
newsize = primes[++(h->primeindex)];
|
|
Packit |
857059 |
// sysPrintf("%s h=%p(%s) primeindex=%lu newsize=%lu\n", __FUNCTION__, h, h->name, h->primeindex, newsize);
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/* malloc table */
|
|
Packit |
857059 |
newtable = (struct hash_entry **)malloc(newsize * sizeof(struct hash_entry *));
|
|
Packit |
857059 |
if (NULL == newtable) {
|
|
Packit |
857059 |
(h->primeindex)--;
|
|
Packit |
857059 |
return 0;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
memset(newtable, 0, newsize * sizeof(struct hash_entry *));
|
|
Packit |
857059 |
for (e = h->listHead; e != NULL; e = e->listNext) {
|
|
Packit |
857059 |
index = indexFor(newsize, e->h);
|
|
Packit |
857059 |
e->hashNext = newtable[index];
|
|
Packit |
857059 |
newtable[index] = e;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
if (h->table)
|
|
Packit |
857059 |
free(h->table);
|
|
Packit |
857059 |
h->table = newtable;
|
|
Packit |
857059 |
h->tablelength = newsize;
|
|
Packit |
857059 |
h->loadlimit = ((uint64_t)newsize * MAX_LOAD_FACTOR_NUMERATOR) / MAX_LOAD_FACTOR_DENOMINATOR;
|
|
Packit |
857059 |
return -1;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* cs_hashtable_insert
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
int32_t
|
|
Packit |
857059 |
cs_hashtable_insert(struct cs_hashtable *h, void *k, void *v)
|
|
Packit |
857059 |
{
|
|
Packit |
857059 |
/* This method allows duplicate keys - but they shouldn't be used */
|
|
Packit |
857059 |
uint32_t index;
|
|
Packit |
857059 |
struct hash_entry *e;
|
|
Packit |
857059 |
// sysPrintf("%s h=%p(%s) k=%p v=%p ra=%p\n", __FUNCTION__, h, h->name, k, v, __builtin_return_address(0));
|
|
Packit |
857059 |
if (++h->entrycount > h->loadlimit) {
|
|
Packit |
857059 |
/* Ignore the return value. If expand fails, we should
|
|
Packit |
857059 |
* still try cramming just this value into the existing table
|
|
Packit |
857059 |
* -- we may not have memory for a larger table, but one more
|
|
Packit |
857059 |
* element may be ok. Next time we insert, we'll try expanding again.*/
|
|
Packit |
857059 |
cs_hashtable_expand(h);
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
/* retrieve a free hash_entry or allocate a new one */
|
|
Packit |
857059 |
if ((e = h->freeHead) == NULL) {
|
|
Packit |
857059 |
e = (struct hash_entry *)malloc(sizeof(struct hash_entry));
|
|
Packit |
857059 |
if (NULL == e) { /* out of memory */
|
|
Packit |
857059 |
--h->entrycount;
|
|
Packit |
857059 |
return 0;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
} else
|
|
Packit |
857059 |
h->freeHead = e->listNext;
|
|
Packit |
857059 |
|
|
Packit |
857059 |
e->h = _hash(h,k);
|
|
Packit |
857059 |
//IB_LOG_INFINI_INFOLX("key is", e->h);
|
|
Packit |
857059 |
index = indexFor(h->tablelength,e->h);
|
|
Packit |
857059 |
e->k = k;
|
|
Packit |
857059 |
e->v = v;
|
|
Packit |
857059 |
e->hashNext = h->table[index];
|
|
Packit |
857059 |
h->table[index] = e;
|
|
Packit |
857059 |
e->listNext = NULL;
|
|
Packit |
857059 |
if (h->listHead == NULL) {
|
|
Packit |
857059 |
h->listHead = h->listTail = e;
|
|
Packit |
857059 |
e->listPrev = NULL;
|
|
Packit |
857059 |
} else {
|
|
Packit |
857059 |
e->listPrev = h->listTail;
|
|
Packit |
857059 |
h->listTail = h->listTail->listNext = e;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
return -1;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* cs_hashtable_search
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
void *cs_hashtable_search(struct cs_hashtable *h, void *k)
|
|
Packit |
857059 |
{
|
|
Packit |
857059 |
struct hash_entry *e;
|
|
Packit |
857059 |
uint64_t hashvalue = _hash(h,k);
|
|
Packit |
857059 |
|
|
Packit |
857059 |
for(e = h->table[indexFor(h->tablelength,hashvalue)]; e != NULL; e = e->hashNext) {
|
|
Packit |
857059 |
/* Check hash value to short circuit heavier comparison */
|
|
Packit |
857059 |
if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
|
|
Packit |
857059 |
return e->v;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
return NULL;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|
|
Packit |
857059 |
void cs_hashentry_delete(struct cs_hashtable *h, struct hash_entry *e) {
|
|
Packit |
857059 |
h->entrycount--;
|
|
Packit |
857059 |
if (e == h->listHead)
|
|
Packit |
857059 |
h->listHead = e->listNext;
|
|
Packit |
857059 |
if (e == h->listTail)
|
|
Packit |
857059 |
h->listTail = e->listPrev;
|
|
Packit |
857059 |
if (e->listPrev != NULL)
|
|
Packit |
857059 |
e->listPrev->listNext = e->listNext;
|
|
Packit |
857059 |
if (e->listNext != NULL)
|
|
Packit |
857059 |
e->listNext->listPrev = e->listPrev;
|
|
Packit |
857059 |
if (h->keyType == CS_HASH_KEY_ALLOCATED) freekey(e->k);
|
|
Packit |
857059 |
e->listNext = h->freeHead;
|
|
Packit |
857059 |
h->freeHead = e;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* cs_hashtable_remove
|
|
Packit |
857059 |
* returns value associated with key
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
void *cs_hashtable_remove(struct cs_hashtable *h, void *k) {
|
|
Packit |
857059 |
/* TODO: consider compacting the table when the load factor drops enough,
|
|
Packit |
857059 |
* or provide a 'compact' method. */
|
|
Packit |
857059 |
|
|
Packit |
857059 |
struct hash_entry *e;
|
|
Packit |
857059 |
struct hash_entry **pE;
|
|
Packit |
857059 |
void *v;
|
|
Packit |
857059 |
uint64_t hashvalue = _hash(h,k);
|
|
Packit |
857059 |
|
|
Packit |
857059 |
pE = &(h->table[indexFor(h->tablelength,hashvalue)]);
|
|
Packit |
857059 |
for(e = *pE; e != NULL; e = e->hashNext) {
|
|
Packit |
857059 |
/* Check hash value to short circuit heavier comparison */
|
|
Packit |
857059 |
if ((hashvalue == e->h) && (h->eqfn(k, e->k))) {
|
|
Packit |
857059 |
*pE = e->hashNext;
|
|
Packit |
857059 |
v = e->v;
|
|
Packit |
857059 |
cs_hashentry_delete(h, e);
|
|
Packit |
857059 |
return v;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
pE = &(e->hashNext);
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
return NULL;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* cs_hashtable_destroy
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
void cs_hashtable_destroy(struct cs_hashtable *h, int32_t free_values)
|
|
Packit |
857059 |
{
|
|
Packit |
857059 |
struct hash_entry *e;
|
|
Packit |
857059 |
struct hash_entry *listNext;
|
|
Packit |
857059 |
|
|
Packit |
857059 |
for(e = h->freeHead; e != NULL; e = listNext) {
|
|
Packit |
857059 |
listNext = e->listNext;
|
|
Packit |
857059 |
free(e);
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|
|
Packit |
857059 |
for(e = h->listHead; e != NULL; e = listNext) {
|
|
Packit |
857059 |
listNext = e->listNext;
|
|
Packit |
857059 |
if (h->keyType == CS_HASH_KEY_ALLOCATED) freekey(e->k);
|
|
Packit |
857059 |
if (free_values)
|
|
Packit |
857059 |
free(e->v);
|
|
Packit |
857059 |
free(e);
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
free(h->table);
|
|
Packit |
857059 |
free(h);
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* cs_hashtable_change
|
|
Packit |
857059 |
*
|
|
Packit |
857059 |
* function to change the value associated with a key, where there already
|
|
Packit |
857059 |
* exists a value bound to the key in the hashtable.
|
|
Packit |
857059 |
* Source due to Holger Schemel.
|
|
Packit |
857059 |
*
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
int32_t
|
|
Packit |
857059 |
cs_hashtable_change(struct cs_hashtable *h, void *k, void *v)
|
|
Packit |
857059 |
{
|
|
Packit |
857059 |
struct hash_entry *e;
|
|
Packit |
857059 |
uint64_t hashvalue = _hash(h,k);
|
|
Packit |
857059 |
|
|
Packit |
857059 |
for(e = h->table[indexFor(h->tablelength,hashvalue)]; e != NULL; e = e->hashNext) {
|
|
Packit |
857059 |
/* Check hash value to short circuit heavier comparison */
|
|
Packit |
857059 |
if ((hashvalue == e->h) && (h->eqfn(k, e->k))) {
|
|
Packit |
857059 |
free(e->v);
|
|
Packit |
857059 |
e->v = v;
|
|
Packit |
857059 |
return -1;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
return 0;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* remove - remove the entry at the current iterator position
|
|
Packit |
857059 |
* and advance the iterator, if there is a successive
|
|
Packit |
857059 |
* element.
|
|
Packit |
857059 |
* If you want the value, read it before you remove:
|
|
Packit |
857059 |
* beware memory leaks if you don't.
|
|
Packit |
857059 |
* Returns zero if end of iteration.
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
int32_t
|
|
Packit |
857059 |
cs_hashtable_iterator_remove(struct cs_hashtable_itr *itr) {
|
|
Packit |
857059 |
struct cs_hashtable *h = itr->h;
|
|
Packit |
857059 |
struct hash_entry *removeEntry = itr->e;
|
|
Packit |
857059 |
struct hash_entry *e;
|
|
Packit |
857059 |
struct hash_entry **pE;
|
|
Packit |
857059 |
int32_t ret;
|
|
Packit |
857059 |
|
|
Packit |
857059 |
ret = cs_hashtable_iterator_advance(itr);
|
|
Packit |
857059 |
|
|
Packit |
857059 |
pE = &(h->table[indexFor(h->tablelength,_hash(h,removeEntry->k))]);
|
|
Packit |
857059 |
for(e = *pE; e != NULL; e = e->hashNext) {
|
|
Packit |
857059 |
if (e == removeEntry) {
|
|
Packit |
857059 |
*pE = e->hashNext;
|
|
Packit |
857059 |
cs_hashentry_delete(h, e);
|
|
Packit |
857059 |
break;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
pE = &(e->hashNext);
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
return ret;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|
|
Packit |
857059 |
/*
|
|
Packit |
857059 |
* cs_hashtable_iterator_search
|
|
Packit |
857059 |
* returns zero if not found
|
|
Packit |
857059 |
*/
|
|
Packit |
857059 |
int32_t
|
|
Packit |
857059 |
cs_hashtable_iterator_search(struct cs_hashtable_itr *itr,
|
|
Packit |
857059 |
struct cs_hashtable *h, void *k) {
|
|
Packit |
857059 |
struct hash_entry *e;
|
|
Packit |
857059 |
uint64_t hashvalue = _hash(h,k);
|
|
Packit |
857059 |
|
|
Packit |
857059 |
for(e = h->table[indexFor(h->tablelength,hashvalue)]; e != NULL; e = e->hashNext) {
|
|
Packit |
857059 |
/* Check hash value to short circuit heavier comparison */
|
|
Packit |
857059 |
if ((hashvalue == e->h) && (h->eqfn(k, e->k))) {
|
|
Packit |
857059 |
itr->e = e;
|
|
Packit |
857059 |
itr->h = h;
|
|
Packit |
857059 |
return -1;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
return 0;
|
|
Packit |
857059 |
}
|
|
Packit |
857059 |
|