/**
* WinPR: Windows Portable Runtime
* System.Collections.Hashtable
*
* Copyright 2014 Marc-Andre Moreau <marcandre.moreau@gmail.com>
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include <winpr/crt.h>
#include <winpr/collections.h>
/**
* This implementation is based on the public domain
* hash table implementation made by Keith Pomakis:
*
* http://www.pomakis.com/hashtable/hashtable.c
* http://www.pomakis.com/hashtable/hashtable.h
*/
BOOL HashTable_PointerCompare(void* pointer1, void* pointer2)
{
return (pointer1 == pointer2);
}
UINT32 HashTable_PointerHash(void* pointer)
{
return ((UINT32)(UINT_PTR)pointer) >> 4;
}
BOOL HashTable_StringCompare(void* string1, void* string2)
{
if (!string1 || !string2)
return (string1 == string2);
return (strcmp((char*)string1, (char*)string2) == 0);
}
UINT32 HashTable_StringHash(void* key)
{
UINT32 c;
UINT32 hash = 5381;
BYTE* str = (BYTE*)key;
/* djb2 algorithm */
while ((c = *str++) != '\0')
hash = (hash * 33) + c;
return hash;
}
void* HashTable_StringClone(void* str)
{
return _strdup((char*)str);
}
void HashTable_StringFree(void* str)
{
free(str);
}
static int HashTable_IsProbablePrime(int oddNumber)
{
int i;
for (i = 3; i < 51; i += 2)
{
if (oddNumber == i)
return 1;
else if (oddNumber % i == 0)
return 0;
}
return 1; /* maybe */
}
static long HashTable_CalculateIdealNumOfBuckets(wHashTable* table)
{
int idealNumOfBuckets = table->numOfElements / ((int)table->idealRatio);
if (idealNumOfBuckets < 5)
idealNumOfBuckets = 5;
else
idealNumOfBuckets |= 0x01;
while (!HashTable_IsProbablePrime(idealNumOfBuckets))
idealNumOfBuckets += 2;
return idealNumOfBuckets;
}
static void HashTable_Rehash(wHashTable* table, int numOfBuckets)
{
int index;
UINT32 hashValue;
wKeyValuePair* pair;
wKeyValuePair* nextPair;
wKeyValuePair** newBucketArray;
if (numOfBuckets == 0)
numOfBuckets = HashTable_CalculateIdealNumOfBuckets(table);
if (numOfBuckets == table->numOfBuckets)
return; /* already the right size! */
newBucketArray = (wKeyValuePair**)calloc(numOfBuckets, sizeof(wKeyValuePair*));
if (!newBucketArray)
{
/*
* Couldn't allocate memory for the new array.
* This isn't a fatal error; we just can't perform the rehash.
*/
return;
}
for (index = 0; index < table->numOfBuckets; index++)
{
pair = table->bucketArray[index];
while (pair)
{
nextPair = pair->next;
hashValue = table->hash(pair->key) % numOfBuckets;
pair->next = newBucketArray[hashValue];
newBucketArray[hashValue] = pair;
pair = nextPair;
}
}
free(table->bucketArray);
table->bucketArray = newBucketArray;
table->numOfBuckets = numOfBuckets;
}
wKeyValuePair* HashTable_Get(wHashTable* table, void* key)
{
UINT32 hashValue;
wKeyValuePair* pair;
hashValue = table->hash(key) % table->numOfBuckets;
pair = table->bucketArray[hashValue];
while (pair && !table->keyCompare(key, pair->key))
pair = pair->next;
return pair;
}
/**
* C equivalent of the C# Hashtable Class:
* http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx
*/
/**
* Properties
*/
/**
* Gets the number of key/value pairs contained in the HashTable.
*/
int HashTable_Count(wHashTable* table)
{
return table->numOfElements;
}
/**
* Methods
*/
/**
* Adds an element with the specified key and value into the HashTable.
*/
int HashTable_Add(wHashTable* table, void* key, void* value)
{
int status = 0;
UINT32 hashValue;
wKeyValuePair* pair;
wKeyValuePair* newPair;
if (!key || !value)
return -1;
if (table->keyClone)
{
key = table->keyClone(key);
if (!key)
return -1;
}
if (table->valueClone)
{
value = table->valueClone(value);
if (!value)
return -1;
}
if (table->synchronized)
EnterCriticalSection(&table->lock);
hashValue = table->hash(key) % table->numOfBuckets;
pair = table->bucketArray[hashValue];
while (pair && !table->keyCompare(key, pair->key))
pair = pair->next;
if (pair)
{
if (pair->key != key)
{
if (table->keyFree)
table->keyFree(pair->key);
pair->key = key;
}
if (pair->value != value)
{
if (table->valueFree)
table->valueFree(pair->value);
pair->value = value;
}
}
else
{
newPair = (wKeyValuePair*)malloc(sizeof(wKeyValuePair));
if (!newPair)
{
status = -1;
}
else
{
newPair->key = key;
newPair->value = value;
newPair->next = table->bucketArray[hashValue];
table->bucketArray[hashValue] = newPair;
table->numOfElements++;
if (table->upperRehashThreshold > table->idealRatio)
{
float elementToBucketRatio =
(float)table->numOfElements / (float)table->numOfBuckets;
if (elementToBucketRatio > table->upperRehashThreshold)
HashTable_Rehash(table, 0);
}
}
}
if (table->synchronized)
LeaveCriticalSection(&table->lock);
return status;
}
/**
* Removes the element with the specified key from the HashTable.
*/
BOOL HashTable_Remove(wHashTable* table, void* key)
{
UINT32 hashValue;
BOOL status = TRUE;
wKeyValuePair* pair = NULL;
wKeyValuePair* previousPair = NULL;
if (table->synchronized)
EnterCriticalSection(&table->lock);
hashValue = table->hash(key) % table->numOfBuckets;
pair = table->bucketArray[hashValue];
while (pair && !table->keyCompare(key, pair->key))
{
previousPair = pair;
pair = pair->next;
}
if (!pair)
{
status = FALSE;
}
else
{
if (table->keyFree)
table->keyFree(pair->key);
if (table->valueFree)
table->valueFree(pair->value);
if (previousPair)
previousPair->next = pair->next;
else
table->bucketArray[hashValue] = pair->next;
free(pair);
table->numOfElements--;
if (table->lowerRehashThreshold > 0.0)
{
float elementToBucketRatio = (float)table->numOfElements / (float)table->numOfBuckets;
if (elementToBucketRatio < table->lowerRehashThreshold)
HashTable_Rehash(table, 0);
}
}
if (table->synchronized)
LeaveCriticalSection(&table->lock);
return status;
}
/**
* Get an item value using key
*/
void* HashTable_GetItemValue(wHashTable* table, void* key)
{
void* value = NULL;
wKeyValuePair* pair;
if (table->synchronized)
EnterCriticalSection(&table->lock);
pair = HashTable_Get(table, key);
if (pair)
value = pair->value;
if (table->synchronized)
LeaveCriticalSection(&table->lock);
return value;
}
/**
* Set an item value using key
*/
BOOL HashTable_SetItemValue(wHashTable* table, void* key, void* value)
{
BOOL status = TRUE;
wKeyValuePair* pair;
if (table->valueClone && value)
{
value = table->valueClone(value);
if (!value)
return FALSE;
}
if (table->synchronized)
EnterCriticalSection(&table->lock);
pair = HashTable_Get(table, key);
if (!pair)
status = FALSE;
else
{
if (table->valueClone && table->valueFree)
table->valueFree(pair->value);
pair->value = value;
}
if (table->synchronized)
LeaveCriticalSection(&table->lock);
return status;
}
/**
* Removes all elements from the HashTable.
*/
void HashTable_Clear(wHashTable* table)
{
int index;
wKeyValuePair* pair;
wKeyValuePair* nextPair;
if (table->synchronized)
EnterCriticalSection(&table->lock);
for (index = 0; index < table->numOfBuckets; index++)
{
pair = table->bucketArray[index];
while (pair)
{
nextPair = pair->next;
if (table->keyFree)
table->keyFree(pair->key);
if (table->valueFree)
table->valueFree(pair->value);
free(pair);
pair = nextPair;
}
table->bucketArray[index] = NULL;
}
table->numOfElements = 0;
HashTable_Rehash(table, 5);
if (table->synchronized)
LeaveCriticalSection(&table->lock);
}
/**
* Gets the list of keys as an array
*/
int HashTable_GetKeys(wHashTable* table, ULONG_PTR** ppKeys)
{
int iKey;
int count;
int index;
ULONG_PTR* pKeys;
wKeyValuePair* pair;
wKeyValuePair* nextPair;
if (table->synchronized)
EnterCriticalSection(&table->lock);
iKey = 0;
count = table->numOfElements;
*ppKeys = NULL;
if (count < 1)
{
if (table->synchronized)
LeaveCriticalSection(&table->lock);
return 0;
}
pKeys = (ULONG_PTR*)calloc(count, sizeof(ULONG_PTR));
if (!pKeys)
{
if (table->synchronized)
LeaveCriticalSection(&table->lock);
return -1;
}
for (index = 0; index < table->numOfBuckets; index++)
{
pair = table->bucketArray[index];
while (pair)
{
nextPair = pair->next;
pKeys[iKey++] = (ULONG_PTR)pair->key;
pair = nextPair;
}
}
if (table->synchronized)
LeaveCriticalSection(&table->lock);
*ppKeys = pKeys;
return count;
}
/**
* Determines whether the HashTable contains a specific key.
*/
BOOL HashTable_Contains(wHashTable* table, void* key)
{
BOOL status;
if (table->synchronized)
EnterCriticalSection(&table->lock);
status = (HashTable_Get(table, key) != NULL) ? TRUE : FALSE;
if (table->synchronized)
LeaveCriticalSection(&table->lock);
return status;
}
/**
* Determines whether the HashTable contains a specific key.
*/
BOOL HashTable_ContainsKey(wHashTable* table, void* key)
{
BOOL status;
if (table->synchronized)
EnterCriticalSection(&table->lock);
status = (HashTable_Get(table, key) != NULL) ? TRUE : FALSE;
if (table->synchronized)
LeaveCriticalSection(&table->lock);
return status;
}
/**
* Determines whether the HashTable contains a specific value.
*/
BOOL HashTable_ContainsValue(wHashTable* table, void* value)
{
int index;
BOOL status = FALSE;
wKeyValuePair* pair;
if (table->synchronized)
EnterCriticalSection(&table->lock);
for (index = 0; index < table->numOfBuckets; index++)
{
pair = table->bucketArray[index];
while (pair)
{
if (table->valueCompare(value, pair->value))
{
status = TRUE;
break;
}
pair = pair->next;
}
if (status)
break;
}
if (table->synchronized)
LeaveCriticalSection(&table->lock);
return status;
}
/**
* Construction, Destruction
*/
wHashTable* HashTable_New(BOOL synchronized)
{
wHashTable* table;
table = (wHashTable*)calloc(1, sizeof(wHashTable));
if (table)
{
table->synchronized = synchronized;
InitializeCriticalSectionAndSpinCount(&(table->lock), 4000);
table->numOfBuckets = 64;
table->numOfElements = 0;
table->bucketArray = (wKeyValuePair**)calloc(table->numOfBuckets, sizeof(wKeyValuePair*));
if (!table->bucketArray)
{
free(table);
return NULL;
}
table->idealRatio = 3.0;
table->lowerRehashThreshold = 0.0;
table->upperRehashThreshold = 15.0;
table->hash = HashTable_PointerHash;
table->keyCompare = HashTable_PointerCompare;
table->valueCompare = HashTable_PointerCompare;
table->keyClone = NULL;
table->valueClone = NULL;
table->keyFree = NULL;
table->valueFree = NULL;
}
return table;
}
void HashTable_Free(wHashTable* table)
{
int index;
wKeyValuePair* pair;
wKeyValuePair* nextPair;
if (table)
{
for (index = 0; index < table->numOfBuckets; index++)
{
pair = table->bucketArray[index];
while (pair)
{
nextPair = pair->next;
if (table->keyFree)
table->keyFree(pair->key);
if (table->valueFree)
table->valueFree(pair->value);
free(pair);
pair = nextPair;
}
}
DeleteCriticalSection(&(table->lock));
free(table->bucketArray);
free(table);
}
}