1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/common/hashtable.h	Thu Oct 23 01:46:07 2014 +0300
     1.3 @@ -0,0 +1,103 @@
     1.4 +#ifndef HASHTABLE_H_
     1.5 +#define HASHTABLE_H_
     1.6 +
     1.7 +#include <list>
     1.8 +#include <vector>
     1.9 +
    1.10 +template <class KeyT, class ValT> 
    1.11 +struct Pair {
    1.12 +	KeyT key; 
    1.13 +	ValT val;
    1.14 +};
    1.15 +
    1.16 +template <class KeyType, class ValType>
    1.17 +class HashTable {
    1.18 +private:
    1.19 +
    1.20 +	size_t size;
    1.21 +	std::vector<std::list<Pair<KeyType, ValType> > > table;
    1.22 +	//std::list<Pair<KeyType, ValType> > table[100];
    1.23 +
    1.24 +	unsigned int (*HashFunc)(const KeyType &key, unsigned long size);
    1.25 +	unsigned int Hash(const KeyType &key) {return (unsigned int)HashFunc(key, (unsigned long)size);}
    1.26 +
    1.27 +public:
    1.28 +
    1.29 +	HashTable(unsigned long size = 101);
    1.30 +	~HashTable();
    1.31 +
    1.32 +	void SetHashFunction(unsigned int (*HashFunc)(const KeyType&, unsigned long));
    1.33 +
    1.34 +	void Insert(KeyType key, ValType value);
    1.35 +	void Remove(KeyType key);
    1.36 +
    1.37 +	Pair<KeyType, ValType> *Find(KeyType key);
    1.38 +};
    1.39 +
    1.40 +//// std hash function
    1.41 +//template <class KeyType>
    1.42 +//unsigned int _HashFunction(const KeyType &key, unsigned long size) {
    1.43 +//	return (size_t)key % size;
    1.44 +//}
    1.45 +
    1.46 +// hash table member functions
    1.47 +template <class KeyType, class ValType>
    1.48 +HashTable<KeyType, ValType>::HashTable(unsigned long size) {
    1.49 +	this->size = size;
    1.50 +	//HashFunc = _HashFunction;
    1.51 +	table.resize(size);
    1.52 +}
    1.53 +
    1.54 +template <class KeyType, class ValType>
    1.55 +HashTable<KeyType, ValType>::~HashTable() {
    1.56 +	for(unsigned long i=0; i<size; i++) {
    1.57 +		table[i].erase(table[i].begin(), table[i].end());
    1.58 +	}
    1.59 +}
    1.60 +
    1.61 +template <class KeyType, class ValType>
    1.62 +void HashTable<KeyType, ValType>::SetHashFunction(unsigned int (*HashFunc)(const KeyType&, unsigned long)) {
    1.63 +	this->HashFunc = HashFunc;
    1.64 +}
    1.65 +
    1.66 +template <class KeyType, class ValType>
    1.67 +void HashTable<KeyType, ValType>::Insert(KeyType key, ValType value) {
    1.68 +	Pair<KeyType, ValType> newpair;
    1.69 +	newpair.key = key;
    1.70 +	newpair.val = value;
    1.71 +
    1.72 +	table[Hash(key)].push_back(newpair);
    1.73 +}
    1.74 +
    1.75 +template <class KeyType, class ValType>
    1.76 +void HashTable<KeyType, ValType>::Remove(KeyType key) {
    1.77 +
    1.78 +	unsigned int pos = Hash(key);
    1.79 +
    1.80 +	std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();
    1.81 +	while(iter != table[pos].end()) {
    1.82 +		if(iter->key == key) {
    1.83 +			table[pos].erase(iter);
    1.84 +			return;
    1.85 +		}
    1.86 +		iter++;
    1.87 +	}
    1.88 +}
    1.89 +
    1.90 +template <class KeyType, class ValType>
    1.91 +Pair<KeyType, ValType> *HashTable<KeyType, ValType>::Find(KeyType key) {
    1.92 +
    1.93 +	unsigned int pos = Hash(key);
    1.94 +
    1.95 +	std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();
    1.96 +	while(iter != table[pos].end()) {
    1.97 +		if(iter->key == key) {
    1.98 +			return &(*iter);
    1.99 +		}
   1.100 +		iter++;
   1.101 +	}
   1.102 +
   1.103 +	return 0;
   1.104 +}
   1.105 +
   1.106 +#endif	// HASHTABLE_H_
   1.107 \ No newline at end of file