1 /****
2 DIAMOND protein aligner
3 Copyright (C) 2013-2018 Benjamin Buchfink <buchfink@gmail.com>
4 
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
9 
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 GNU General Public License for more details.
14 
15 You should have received a copy of the GNU General Public License
16 along with this program.  If not, see <http://www.gnu.org/licenses/>.
17 ****/
18 
19 #ifndef HASH_TABLE2_H_
20 #define HASH_TABLE2_H_
21 
22 #include <stdexcept>
23 #include <stdlib.h>
24 
25 template<typename _K, typename _V, typename _HashFunction>
26 struct HashTable : private _HashFunction
27 {
28 
29 	struct Entry : public _V
30 	{
31 		_K key;
blankHashTable::Entry32 		bool blank() const
33 		{
34 			return _V::operator unsigned() == 0;
35 		}
36 	};
37 
HashTableHashTable38 	HashTable(size_t size, const _HashFunction &hash) :
39 		_HashFunction(hash),
40 		table((Entry*)calloc(size, sizeof(Entry))),
41 		size_(size)
42 	{
43 	}
44 
~HashTableHashTable45 	~HashTable()
46 	{
47 		free(table);
48 	}
49 
50 	_V& operator[](_K key)
51 	{
52 		Entry *e = get_entry(key);
53 		if (e->blank())
54 			e->key = key;
55 		return *e;
56 	}
57 
findHashTable58 	_V* find(_K key)
59 	{
60 		return get_present_entry(key);
61 	}
62 
find_entryHashTable63 	Entry* find_entry(_K key)
64 	{
65 		return get_present_entry(key);
66 	}
67 
insertHashTable68 	Entry* insert(_K key)
69 	{
70 		return get_or_insert_entry(key);
71 	}
72 
sizeHashTable73 	size_t size() const
74 	{
75 		return size_;
76 	}
77 
countHashTable78 	size_t count() const
79 	{
80 		size_t n = 0;
81 		for (size_t i = 0; i < size_; ++i)
82 			if (!table[i].blank())
83 				++n;
84 		return n;
85 	}
86 
dataHashTable87 	Entry* data()
88 	{
89 		return table;
90 	}
91 
92 private:
93 
94 	Entry* get_entry(_K key, bool stat=false)
95 	{
96 		//Entry *p = &table[_H()(key) % size_];
97 		Entry *p = &table[_HashFunction::operator()(key)];
98 		bool wrapped = false;
99 		//if(stat) ++probe_n;
100 		while (p->key != key && !p->blank()) {
101 			//if(stat) ++probe_l;
102 			++p;
103 			if (p == &table[size_]) {
104 				if (wrapped)
105 					throw std::runtime_error("Hash table overflow.");
106 				p = &table[0];
107 				wrapped = true;
108 			}
109 		}
110 		return p;
111 	}
112 
113 	Entry* get_present_entry(_K key, bool stat = false)
114 	{
115 		Entry *p = &table[_HashFunction::operator()(key)];
116 		bool wrapped = false;
117 		//if(stat) ++probe_n;
118 		while(true) {
119 			//if(stat) ++probe_l;
120 			if (p->blank())
121 				return nullptr;
122 			if (p->key == key)
123 				return p;
124 			++p;
125 			if (p == &table[size_]) {
126 				if (wrapped)
127 					throw std::runtime_error("Hash table overflow.");
128 				p = &table[0];
129 				wrapped = true;
130 			}
131 		}
132 		return p;
133 	}
134 
135 	Entry* get_or_insert_entry(_K key, bool stat = false)
136 	{
137 		Entry *p = &table[_HashFunction::operator()(key)];
138 		bool wrapped = false;
139 		//if(stat) ++probe_n;
140 		while (true) {
141 			//if(stat) ++probe_l;
142 			if (p->key == key)
143 				return p;
144 			if (p->blank()) {
145 				p->key = key;
146 				return p;
147 			}
148 			++p;
149 			if (p == &table[size_]) {
150 				if (wrapped)
151 					throw std::runtime_error("Hash table overflow.");
152 				p = &table[0];
153 				wrapped = true;
154 			}
155 		}
156 		return p;
157 	}
158 
159 	Entry *table;
160 	size_t size_;
161 
162 };
163 
164 #endif