* @brief Hashtable. Standard chained bucket variety.
*/
-#ifndef __HASHTABLE_H__
-#define __HASHTABLE_H__
+#ifndef HASHTABLE_H__
+#define HASHTABLE_H__
#include <stdlib.h>
#include <stdio.h>
#include "common.h"
/**
- * @brief HashTable node
+ * @brief Hashtable node
*
* @tparam _Key Type name for the key
* @tparam _Val Type name for the values to be stored
*/
template<typename _Key, typename _Val>
-struct hashlistnode {
+struct Hashlistnode {
_Key key;
_Val val;
+ uint hashcode;
};
template<typename _Key, int _Shift, typename _KeyInt>
-inline unsigned int default_hash_function(_Key hash) {
+inline unsigned int defaultHashFunction(_Key hash) {
return (unsigned int)(((_KeyInt)hash) >> _Shift);
}
template<typename _Key>
-inline bool default_equals(_Key key1, _Key key2) {
+inline bool defaultEquals(_Key key1, _Key key2) {
return key1 == key2;
}
* manipulation and storage.
* @tparam _Shift Logical shift to apply to all keys. Default 0.
*/
-template<typename _Key, typename _Val, typename _KeyInt, int _Shift = 0, unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
-class HashTable {
+template<typename _Key, typename _Val, typename _KeyInt, int _Shift = 0, unsigned int (*hash_function) (_Key) = defaultHashFunction<_Key, _Shift, _KeyInt>, bool (*equals) (_Key, _Key) = defaultEquals<_Key> >
+class Hashtable {
public:
/**
* @brief Hash table constructor
* @param factor Sets the percentage full before the hashtable is
* resized. Default ratio 0.5.
*/
- HashTable(unsigned int initialcapacity = 1024, double factor = 0.5) {
+ Hashtable(unsigned int initialcapacity = 1024, double factor = 0.5) {
// Allocate space for the hash table
- table = (struct hashlistnode<_Key, _Val> *)ourcalloc(initialcapacity, sizeof(struct hashlistnode<_Key, _Val>));
+ table = (struct Hashlistnode<_Key, _Val> *)ourcalloc(initialcapacity, sizeof(struct Hashlistnode<_Key, _Val>));
zero = NULL;
loadfactor = factor;
capacity = initialcapacity;
}
/** @brief Hash table destructor */
- ~HashTable() {
+ ~Hashtable() {
ourfree(table);
if (zero)
ourfree(zero);
/** @brief Reset the table to its initial state. */
void reset() {
- memset(table, 0, capacity * sizeof(struct hashlistnode<_Key, _Val>));
+ memset(table, 0, capacity * sizeof(struct Hashlistnode<_Key, _Val>));
if (zero) {
ourfree(zero);
zero = NULL;
size = 0;
}
- /** Doesn't work with zero value */
- _Val getRandomValue() {
- while(true) {
- unsigned int index=random() & capacitymask;
- struct hashlistnode<_Key, _Val> *bin = &table[index];
+ /** Doesn't work with zero value */
+ _Val getRandomValue() {
+ while (true) {
+ unsigned int index = random() & capacitymask;
+ struct Hashlistnode<_Key, _Val> *bin = &table[index];
if (bin->key != NULL && bin->val != NULL) {
return bin->val;
}
}
}
- void resetanddelete() {
+ void resetAndDeleteKeys() {
for (unsigned int i = 0; i < capacity; i++) {
- struct hashlistnode<_Key, _Val> *bin = &table[i];
+ struct Hashlistnode<_Key, _Val> *bin = &table[i];
+ if (bin->key != NULL) {
+ delete bin->key;
+ bin->key = NULL;
+ if (bin->val != NULL) {
+ bin->val = NULL;
+ }
+ }
+ }
+ if (zero) {
+ ourfree(zero);
+ zero = NULL;
+ }
+ size = 0;
+ }
+
+ void resetAndDeleteVals() {
+ for (unsigned int i = 0; i < capacity; i++) {
+ struct Hashlistnode<_Key, _Val> *bin = &table[i];
if (bin->key != NULL) {
bin->key = NULL;
if (bin->val != NULL) {
size = 0;
}
- void resetandfree() {
+ void resetAndFreeVals() {
for (unsigned int i = 0; i < capacity; i++) {
- struct hashlistnode<_Key, _Val> *bin = &table[i];
+ struct Hashlistnode<_Key, _Val> *bin = &table[i];
if (bin->key != NULL) {
bin->key = NULL;
if (bin->val != NULL) {
* @param val The value to store in the table
*/
void put(_Key key, _Val val) {
- /* HashTable cannot handle 0 as a key */
+ /* Hashtable cannot handle 0 as a key */
if (!key) {
if (!zero) {
- zero = (struct hashlistnode<_Key, _Val> *)ourmalloc(sizeof(struct hashlistnode<_Key, _Val>));
+ zero = (struct Hashlistnode<_Key, _Val> *)ourmalloc(sizeof(struct Hashlistnode<_Key, _Val>));
size++;
}
zero->key = key;
if (size > threshold)
resize(capacity << 1);
- struct hashlistnode<_Key, _Val> *search;
+ struct Hashlistnode<_Key, _Val> *search;
- unsigned int index = hash_function(key);
+ unsigned int hashcode = hash_function(key);
+ unsigned int index = hashcode;
do {
index &= capacitymask;
search = &table[index];
//key is null, probably done
break;
}
- if (equals(search->key, key)) {
- search->val = val;
- return;
- }
+ if (search->hashcode == hashcode)
+ if (equals(search->key, key)) {
+ search->val = val;
+ return;
+ }
index++;
} while (true);
search->key = key;
search->val = val;
+ search->hashcode = hashcode;
size++;
}
* @return The value in the table, if the key is found; otherwise 0
*/
_Val get(_Key key) const {
- struct hashlistnode<_Key, _Val> *search;
+ struct Hashlistnode<_Key, _Val> *search;
- /* HashTable cannot handle 0 as a key */
+ /* Hashtable cannot handle 0 as a key */
if (!key) {
if (zero)
return zero->val;
return (_Val) 0;
}
- unsigned int oindex = hash_function(key) & capacitymask;
+ unsigned int hashcode = hash_function(key);
+ unsigned int oindex = hashcode & capacitymask;
unsigned int index = oindex;
do {
search = &table[index];
if (!search->val)
break;
} else
- if (equals(search->key, key))
- return search->val;
+ if (hashcode == search->hashcode)
+ if (equals(search->key, key))
+ return search->val;
index++;
index &= capacitymask;
if (index == oindex)
* @return The value in the table, if the key is found; otherwise 0
*/
_Val remove(_Key key) {
- struct hashlistnode<_Key, _Val> *search;
+ struct Hashlistnode<_Key, _Val> *search;
- /* HashTable cannot handle 0 as a key */
+ /* Hashtable cannot handle 0 as a key */
if (!key) {
if (!zero) {
return (_Val)0;
}
- unsigned int index = hash_function(key);
+ unsigned int hashcode = hash_function(key);
+ unsigned int index = hashcode;
do {
index &= capacitymask;
search = &table[index];
if (!search->val)
break;
} else
- if (equals(search->key, key)) {
- _Val v = search->val;
- //empty out this bin
- search->val = (_Val) 1;
- search->key = 0;
- size--;
- return v;
- }
+ if (hashcode == search->hashcode)
+ if (equals(search->key, key)) {
+ _Val v = search->val;
+ //empty out this bin
+ search->val = (_Val) 1;
+ search->key = 0;
+ size--;
+ return v;
+ }
index++;
} while (true);
return (_Val)0;
* @return True, if the key is found; false otherwise
*/
bool contains(_Key key) const {
- struct hashlistnode<_Key, _Val> *search;
+ struct Hashlistnode<_Key, _Val> *search;
- /* HashTable cannot handle 0 as a key */
+ /* Hashtable cannot handle 0 as a key */
if (!key) {
return zero != NULL;
}
unsigned int index = hash_function(key);
+ unsigned int hashcode = index;
do {
index &= capacitymask;
search = &table[index];
if (!search->val)
break;
} else
- if (equals(search->key, key))
- return true;
+ if (hashcode == search->hashcode)
+ if (equals(search->key, key))
+ return true;
index++;
} while (true);
return false;
* @param newsize The new size of the table
*/
void resize(unsigned int newsize) {
- struct hashlistnode<_Key, _Val> *oldtable = table;
- struct hashlistnode<_Key, _Val> *newtable;
+ struct Hashlistnode<_Key, _Val> *oldtable = table;
+ struct Hashlistnode<_Key, _Val> *newtable;
unsigned int oldcapacity = capacity;
- if ((newtable = (struct hashlistnode<_Key, _Val> *)ourcalloc(newsize, sizeof(struct hashlistnode<_Key, _Val>))) == NULL) {
+ if ((newtable = (struct Hashlistnode<_Key, _Val> *)ourcalloc(newsize, sizeof(struct Hashlistnode<_Key, _Val>))) == NULL) {
model_print("calloc error %s %d\n", __FILE__, __LINE__);
exit(EXIT_FAILURE);
}
threshold = (unsigned int)(newsize * loadfactor);
- struct hashlistnode<_Key, _Val> *bin = &oldtable[0];
- struct hashlistnode<_Key, _Val> *lastbin = &oldtable[oldcapacity];
+ struct Hashlistnode<_Key, _Val> *bin = &oldtable[0];
+ struct Hashlistnode<_Key, _Val> *lastbin = &oldtable[oldcapacity];
for (; bin < lastbin; bin++) {
_Key key = bin->key;
- struct hashlistnode<_Key, _Val> *search;
+ struct Hashlistnode<_Key, _Val> *search;
if (!key)
continue;
- unsigned int index = hash_function(key);
+ unsigned int hashcode = bin->hashcode;
+ unsigned int index = hashcode;
do {
index &= capacitymask;
search = &table[index];
index++;
} while (search->key);
+ search->hashcode = hashcode;
search->key = key;
search->val = bin->val;
}
}
double getLoadFactor() {return loadfactor;}
unsigned int getCapacity() {return capacity;}
- struct hashlistnode<_Key, _Val> *table;
- struct hashlistnode<_Key, _Val> *zero;
+ struct Hashlistnode<_Key, _Val> *table;
+ struct Hashlistnode<_Key, _Val> *zero;
unsigned int capacity;
unsigned int size;
private:
projects / satune.git / blobdiff