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