absence_thelab

annotate src/common/hashtable.h @ 0:1cffe3409164

find changesets by author, revision, files, or words in the commit message
initial commit
author John Tsiombikas <nuclear@member.fsf.org>
date Thu, 23 Oct 2014 01:46:07 +0300
parents
children
rev   line source
nuclear@0 1 #ifndef HASHTABLE_H_
nuclear@0 2 #define HASHTABLE_H_
nuclear@0 3
nuclear@0 4 #include <list>
nuclear@0 5 #include <vector>
nuclear@0 6
nuclear@0 7 template <class KeyT, class ValT>
nuclear@0 8 struct Pair {
nuclear@0 9 KeyT key;
nuclear@0 10 ValT val;
nuclear@0 11 };
nuclear@0 12
nuclear@0 13 template <class KeyType, class ValType>
nuclear@0 14 class HashTable {
nuclear@0 15 private:
nuclear@0 16
nuclear@0 17 size_t size;
nuclear@0 18 std::vector<std::list<Pair<KeyType, ValType> > > table;
nuclear@0 19 //std::list<Pair<KeyType, ValType> > table[100];
nuclear@0 20
nuclear@0 21 unsigned int (*HashFunc)(const KeyType &key, unsigned long size);
nuclear@0 22 unsigned int Hash(const KeyType &key) {return (unsigned int)HashFunc(key, (unsigned long)size);}
nuclear@0 23
nuclear@0 24 public:
nuclear@0 25
nuclear@0 26 HashTable(unsigned long size = 101);
nuclear@0 27 ~HashTable();
nuclear@0 28
nuclear@0 29 void SetHashFunction(unsigned int (*HashFunc)(const KeyType&, unsigned long));
nuclear@0 30
nuclear@0 31 void Insert(KeyType key, ValType value);
nuclear@0 32 void Remove(KeyType key);
nuclear@0 33
nuclear@0 34 Pair<KeyType, ValType> *Find(KeyType key);
nuclear@0 35 };
nuclear@0 36
nuclear@0 37 //// std hash function
nuclear@0 38 //template <class KeyType>
nuclear@0 39 //unsigned int _HashFunction(const KeyType &key, unsigned long size) {
nuclear@0 40 // return (size_t)key % size;
nuclear@0 41 //}
nuclear@0 42
nuclear@0 43 // hash table member functions
nuclear@0 44 template <class KeyType, class ValType>
nuclear@0 45 HashTable<KeyType, ValType>::HashTable(unsigned long size) {
nuclear@0 46 this->size = size;
nuclear@0 47 //HashFunc = _HashFunction;
nuclear@0 48 table.resize(size);
nuclear@0 49 }
nuclear@0 50
nuclear@0 51 template <class KeyType, class ValType>
nuclear@0 52 HashTable<KeyType, ValType>::~HashTable() {
nuclear@0 53 for(unsigned long i=0; i<size; i++) {
nuclear@0 54 table[i].erase(table[i].begin(), table[i].end());
nuclear@0 55 }
nuclear@0 56 }
nuclear@0 57
nuclear@0 58 template <class KeyType, class ValType>
nuclear@0 59 void HashTable<KeyType, ValType>::SetHashFunction(unsigned int (*HashFunc)(const KeyType&, unsigned long)) {
nuclear@0 60 this->HashFunc = HashFunc;
nuclear@0 61 }
nuclear@0 62
nuclear@0 63 template <class KeyType, class ValType>
nuclear@0 64 void HashTable<KeyType, ValType>::Insert(KeyType key, ValType value) {
nuclear@0 65 Pair<KeyType, ValType> newpair;
nuclear@0 66 newpair.key = key;
nuclear@0 67 newpair.val = value;
nuclear@0 68
nuclear@0 69 table[Hash(key)].push_back(newpair);
nuclear@0 70 }
nuclear@0 71
nuclear@0 72 template <class KeyType, class ValType>
nuclear@0 73 void HashTable<KeyType, ValType>::Remove(KeyType key) {
nuclear@0 74
nuclear@0 75 unsigned int pos = Hash(key);
nuclear@0 76
nuclear@0 77 std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();
nuclear@0 78 while(iter != table[pos].end()) {
nuclear@0 79 if(iter->key == key) {
nuclear@0 80 table[pos].erase(iter);
nuclear@0 81 return;
nuclear@0 82 }
nuclear@0 83 iter++;
nuclear@0 84 }
nuclear@0 85 }
nuclear@0 86
nuclear@0 87 template <class KeyType, class ValType>
nuclear@0 88 Pair<KeyType, ValType> *HashTable<KeyType, ValType>::Find(KeyType key) {
nuclear@0 89
nuclear@0 90 unsigned int pos = Hash(key);
nuclear@0 91
nuclear@0 92 std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();
nuclear@0 93 while(iter != table[pos].end()) {
nuclear@0 94 if(iter->key == key) {
nuclear@0 95 return &(*iter);
nuclear@0 96 }
nuclear@0 97 iter++;
nuclear@0 98 }
nuclear@0 99
nuclear@0 100 return 0;
nuclear@0 101 }
nuclear@0 102
nuclear@0 103 #endif // HASHTABLE_H_