53 return ((a << 5) + a) ^ b;
62 return ((a << 5) + a) + b;
70 }
else if (
sizeof(a) == 8) {
75 throw std::runtime_error(
"mkhash_xorshift() only implemented for 32 bit and 64 bit ints");
89 static inline bool cmp(
const T &a,
const T &b) {
99 static inline bool cmp(T a, T b) {
128 static inline bool cmp(
const std::string &a,
const std::string &b) {
139 template<
typename P,
typename Q>
struct hash_ops<
std::pair<P, Q>> {
140 static inline bool cmp(std::pair<P, Q> a, std::pair<P, Q> b) {
149 static inline bool cmp(std::tuple<T...> a, std::tuple<T...> b) {
152 template<
size_t I = 0>
153 static inline typename std::enable_if<I ==
sizeof...(T),
hm_uint>::type
hash(std::tuple<T...>) {
156 template<
size_t I = 0>
157 static inline typename std::enable_if<I !=
sizeof...(T),
hm_uint>::type
hash(std::tuple<T...> a) {
158 typedef hash_ops<
typename std::tuple_element<I, std::tuple<T...>>::type> element_ops_t;
159 return mkhash(hash<I+1>(a), element_ops_t::hash(std::get<I>(a)));
164 static inline bool cmp(std::vector<T> a, std::vector<T> b) {
176 static inline bool cmp(
const char *a,
const char *b) {
177 for (
int i = 0; a[i] || b[i]; i++)
185 hash =
mkhash(hash, *(a++));
191 static inline bool cmp(
const void *a,
const void *b) {
195 return (
unsigned long)a;
200 static inline bool cmp(
const void *a,
const void *b) {
205 return a ? a->hash() : 0;
216 static std::vector<hm_int> zero_and_some_primes = {
217 0, 23, 29, 37, 47, 59, 79, 101, 127, 163, 211, 269, 337, 431, 541, 677,
218 853, 1069, 1361, 1709, 2137, 2677, 3347, 4201, 5261, 6577, 8231, 10289,
219 12889, 16127, 20161, 25219, 31531, 39419, 49277, 61603, 77017, 96281,
220 120371, 150473, 188107, 235159, 293957, 367453, 459317, 574157, 717697,
221 897133, 1121423, 1401791, 1752239, 2190299, 2737937, 3422429, 4278037,
222 5347553, 6684443, 8355563, 10444457, 13055587, 16319519, 20399411,
223 25499291, 31874149, 39842687, 49803361, 62254207, 77817767, 97272239,
224 121590311, 151987889, 189984863, 237481091, 296851369, 371064217
227 for (
auto p : zero_and_some_primes)
228 if (p >= min_size)
return p;
231 throw std::length_error(
"hash table exceeded maximum size. use a ILP64 abi for larger tables.");
233 for (
auto p : zero_and_some_primes)
234 if (100129 * p > min_size)
return 100129 * p;
236 throw std::length_error(
"hash table exceeded maximum size.");
239 template<
typename K,
typename T,
typename OPS = hash_ops<K>>
class unordered_map;
240 template<
typename K, hm_
int offset = 0,
typename OPS = hash_ops<K>>
class idict;
242 template<
typename K,
typename OPS = hash_ops<K>>
class mfp;
251 template<
typename K,
typename T,
typename OPS>
257 std::pair<K, T> udata;
261 entry_t(
const std::pair<K, T> & idata,
hm_int inext) : udata(idata), next(inext) { }
262 entry_t(std::pair<K, T> && idata,
hm_int inext) : udata(
std::move(idata)), next(inext) { }
266 std::vector<hm_int> hashtable;
268 std::vector<entry_t> entries;
273 static inline void do_assert(
bool) { }
275 static inline void do_assert(
bool cond) {
276 if (!cond)
throw std::runtime_error(
"unordered_map<> assert failed.");
290 hm_int do_hash(
const K &key)
const 293 if (!hashtable.empty())
294 hash = ops.hash(key) % (
hm_uint)(hashtable.size());
307 do_assert(-1 <= entries[i].next && entries[i].next <
hm_int(entries.size()));
308 hm_int hash = do_hash(entries[i].udata.first);
309 entries[i].next = hashtable[
hash];
324 do_assert(index <
hm_int(entries.size()));
325 if (hashtable.empty() || index < 0)
329 do_assert(0 <= k && k <
hm_int(entries.size()));
332 hashtable[
hash] = entries[index].next;
334 while (entries[k].next != index) {
336 do_assert(0 <= k && k <
hm_int(entries.size()));
338 entries[k].next = entries[index].next;
341 hm_int back_idx = entries.size()-1;
343 if (index != back_idx)
345 hm_int back_hash = do_hash(entries[back_idx].udata.first);
347 k = hashtable[back_hash];
348 do_assert(0 <= k && k <
hm_int(entries.size()));
351 hashtable[back_hash] = index;
353 while (entries[k].next != back_idx) {
355 do_assert(0 <= k && k <
hm_int(entries.size()));
357 entries[k].next = index;
360 entries[index] = std::move(entries[back_idx]);
381 if (hashtable.empty())
384 if (entries.size() * hashtable_size_trigger > hashtable.size()) {
391 while (index >= 0 && !ops.cmp(entries[index].udata.first, key)) {
392 index = entries[index].next;
393 do_assert(-1 <= index && index <
hm_int(entries.size()));
412 if (hashtable.empty()) {
413 entries.push_back(entry_t(std::pair<K, T>(key, T()), -1));
417 entries.push_back(entry_t(std::pair<K, T>(key, T()), hashtable[hash]));
418 hashtable[
hash] = entries.size() - 1;
420 return entries.size() - 1;
434 hm_int do_insert(
const std::pair<K, T> &value,
hm_int &hash)
436 if (hashtable.empty()) {
437 entries.push_back(entry_t(value, -1));
439 hash = do_hash(value.first);
441 entries.push_back(entry_t(value, hashtable[hash]));
442 hashtable[
hash] = entries.size() - 1;
444 return entries.size() - 1;
452 class const_iterator :
public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
468 const std::pair<K, T> &
operator*()
const {
return ptr->entries[index].udata; }
469 const std::pair<K, T> *
operator->()
const {
return &ptr->entries[index].udata; }
473 class iterator :
public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
489 std::pair<K, T> &
operator*() {
return ptr->entries[index].udata; }
490 std::pair<K, T> *
operator->() {
return &ptr->entries[index].udata; }
491 const std::pair<K, T> &
operator*()
const {
return ptr->entries[index].udata; }
492 const std::pair<K, T> *
operator->()
const {
return &ptr->entries[index].udata; }
503 entries = other.entries;
514 entries = other.entries;
527 for (
auto &it : list)
532 template<
class InputIterator>
538 template<
class InputIterator>
539 void insert(InputIterator first, InputIterator last)
541 for (; first != last; ++first)
545 std::pair<iterator, bool>
insert(
const K &key)
547 hm_int hash = do_hash(key);
548 hm_int i = do_lookup(key, hash);
550 return std::pair<iterator, bool>(iterator(
this, i),
false);
551 i = do_insert(key, hash);
552 return std::pair<iterator, bool>(iterator(
this, i),
true);
555 std::pair<iterator, bool>
insert(
const std::pair<K, T> &value)
557 hm_int hash = do_hash(value.first);
558 hm_int i = do_lookup(value.first, hash);
560 return std::pair<iterator, bool>(iterator(
this, i),
false);
561 i = do_insert(value, hash);
562 return std::pair<iterator, bool>(iterator(
this, i),
true);
567 hm_int hash = do_hash(key);
568 hm_int index = do_lookup(key, hash);
569 return do_erase(index, hash);
574 hm_int hash = do_hash(it->first);
575 do_erase(it.index, hash);
581 hm_int hash = do_hash(key);
582 hm_int i = do_lookup(key, hash);
583 return i < 0 ? 0 : 1;
588 hm_int hash = do_hash(key);
589 hm_int i = do_lookup(key, hash);
590 return i < 0 || i > it.index ? 0 : 1;
595 hm_int hash = do_hash(key);
596 hm_int i = do_lookup(key, hash);
599 return iterator(
this, i);
603 const_iterator
find(
const K &key)
const 605 hm_int hash = do_hash(key);
606 hm_int i = do_lookup(key, hash);
609 return const_iterator(
this, i);
615 hm_int hash = do_hash(key);
616 hm_int i = do_lookup(key, hash);
618 throw std::out_of_range(
"unordered_map::at()");
619 return entries[i].udata.second;
623 const T&
at(
const K &key)
const 625 hm_int hash = do_hash(key);
626 hm_int i = do_lookup(key, hash);
628 throw std::out_of_range(
"unordered_map::at()");
629 return entries[i].udata.second;
633 T
at(
const K &key,
const T &defval)
const 635 hm_int hash = do_hash(key);
636 hm_int i = do_lookup(key, hash);
639 return entries[i].udata.second;
645 hm_int hash = do_hash(key);
646 hm_int i = do_lookup(key, hash);
648 i = do_insert(std::pair<K, T>(key, T()), hash);
649 return entries[i].udata.second;
658 template<
typename Compare = std::less<K>>
659 void sort(Compare comp = Compare())
661 std::sort(entries.begin(), entries.end(), [comp](
const entry_t &a,
const entry_t &b){
return comp(b.udata.first, a.udata.first); });
667 hashtable.swap(other.hashtable);
668 entries.swap(other.entries);
672 if (size() != other.
size())
674 for (
auto &it : entries) {
675 auto oit = other.
find(it.udata.first);
676 if (oit == other.
end() || !(oit->second == it.udata.second))
683 return !operator==(other);
686 void reserve(
size_t n) { entries.reserve(n); }
687 size_t size()
const {
return entries.size(); }
688 bool empty()
const {
return entries.empty(); }
689 void clear() { hashtable.clear(); entries.clear(); }
691 iterator
begin() {
return iterator(
this,
hm_int(entries.size())-1); }
692 iterator
end() {
return iterator(
nullptr, -1); }
694 const_iterator
begin()
const {
return const_iterator(
this,
hm_int(entries.size())-1); }
695 const_iterator
end()
const {
return const_iterator(
nullptr, -1); }
704 template<
typename K,
typename OPS>
707 template<
typename, hm_
int,
typename>
friend class idict;
728 static inline void do_assert(
bool) { }
731 if (!cond)
throw std::runtime_error(
"unordered_set<> assert failed.");
747 if (!hashtable.empty())
748 hash = ops.hash(key) % (
hm_uint)(hashtable.size());
761 do_assert(-1 <= entries[i].next && entries[i].next <
hm_int(entries.size()));
762 hm_int hash = do_hash(entries[i].udata);
763 entries[i].next = hashtable[
hash];
778 do_assert(index <
hm_int(entries.size()));
779 if (hashtable.empty() || index < 0)
784 hashtable[
hash] = entries[index].next;
786 while (entries[k].next != index) {
788 do_assert(0 <= k && k <
hm_int(entries.size()));
790 entries[k].next = entries[index].next;
793 hm_int back_idx = entries.size()-1;
795 if (index != back_idx)
797 hm_int back_hash = do_hash(entries[back_idx].udata);
799 k = hashtable[back_hash];
801 hashtable[back_hash] = index;
803 while (entries[k].next != back_idx) {
805 do_assert(0 <= k && k <
hm_int(entries.size()));
807 entries[k].next = index;
810 entries[index] = std::move(entries[back_idx]);
831 if (hashtable.empty())
834 if (entries.size() * hashtable_size_trigger > hashtable.size()) {
841 while (index >= 0 && !ops.cmp(entries[index].udata, key)) {
842 index = entries[index].next;
843 do_assert(-1 <= index && index <
hm_int(entries.size()));
862 if (hashtable.empty()) {
863 entries.push_back(entry_t(value, -1));
865 hash = do_hash(value);
868 entries.push_back(entry_t(value, hashtable[hash]));
869 hashtable[
hash] = entries.size() - 1;
871 return entries.size() - 1;
896 class iterator :
public std::iterator<std::forward_iterator_tag, K>
951 for (
auto &it : list)
955 template<
class InputIterator>
961 template<
class InputIterator>
962 void insert(InputIterator first, InputIterator last)
964 for (; first != last; ++first)
968 std::pair<iterator, bool>
insert(
const K &value)
970 hm_int hash = do_hash(value);
971 hm_int i = do_lookup(value, hash);
973 return std::pair<iterator, bool>(iterator(
this, i),
false);
974 i = do_insert(value, hash);
975 return std::pair<iterator, bool>(iterator(
this, i),
true);
980 hm_int hash = do_hash(key);
981 hm_int index = do_lookup(key, hash);
982 return do_erase(index, hash);
987 hm_int hash = do_hash(*it);
988 do_erase(it.index, hash);
994 hm_int hash = do_hash(key);
995 hm_int i = do_lookup(key, hash);
996 return i < 0 ? 0 : 1;
1001 hm_int hash = do_hash(key);
1002 hm_int i = do_lookup(key, hash);
1003 return i < 0 || i > it.index ? 0 : 1;
1008 hm_int hash = do_hash(key);
1009 hm_int i = do_lookup(key, hash);
1012 return iterator(
this, i);
1015 const_iterator
find(
const K &key)
const 1017 hm_int hash = do_hash(key);
1018 hm_int i = do_lookup(key, hash);
1021 return const_iterator(
this, i);
1026 hm_int hash = do_hash(key);
1027 hm_int i = do_lookup(key, hash);
1031 template<
typename Compare = std::less<K>>
1032 void sort(Compare comp = Compare())
1034 std::sort(entries.begin(), entries.end(), [comp](
const entry_t &a,
const entry_t &b){
return comp(b.udata, a.udata); });
1040 iterator it = begin();
1053 if (size() != other.
size())
1055 for (
auto &it : entries)
1056 if (!other.
count(it.udata))
1062 return !operator==(other);
1066 size_t size()
const {
return entries.size(); }
1067 bool empty()
const {
return entries.empty(); }
1068 void clear() { hashtable.clear(); entries.clear(); }
1071 iterator
end() {
return iterator(
nullptr, -1); }
1073 const_iterator
begin()
const {
return const_iterator(
this,
hm_int(entries.size())-1); }
1074 const_iterator
end()
const {
return const_iterator(
nullptr, -1); }
1077 template<
typename K, hm_
int offset,
typename OPS>
1087 hm_int hash = database.do_hash(key);
1088 hm_int i = database.do_lookup(key, hash);
1090 i = database.do_insert(key, hash);
1096 hm_int hash = database.do_hash(key);
1097 hm_int i = database.do_lookup(key, hash);
1099 throw std::out_of_range(
"idict::at()");
1105 hm_int hash = database.do_hash(key);
1106 hm_int i = database.do_lookup(key, hash);
1114 hm_int hash = database.do_hash(key);
1115 hm_int i = database.do_lookup(key, hash);
1116 return i < 0 ? 0 : 1;
1123 throw std::out_of_range(
"idict::expect()");
1128 return database.entries.at(index - offset).udata;
1133 database.swap(other.database);
1137 size_t size()
const {
return database.size(); }
1138 bool empty()
const {
return database.empty(); }
1141 const_iterator
begin()
const {
return database.begin(); }
1142 const_iterator
end()
const {
return database.end(); }
1145 template<
typename K,
typename OPS>
1149 mutable std::vector<hm_int> parents;
1156 hm_int i = database(key);
1157 parents.resize(database.
size(), -1);
1163 return database[index];
1170 while (parents[p] != -1)
1174 hm_int next_k = parents[k];
1196 hm_int next_k = parents[k];
1206 return ifind((*
this)(a));
1214 return (*
this)[ifind(i)];
1219 imerge((*
this)(a), (*
this)(b));
1231 database.
swap(other.database);
1232 parents.swap(other.parents);
1241 const_iterator
end()
const {
return database.
end(); }
const K * operator->() const
hm_int do_hash(const K &key) const
Generate a hash from a key.
std::pair< iterator, bool > insert(const K &key)
User insert as key lookup.
unordered_set(const std::initializer_list< K > &list)
hm_uint mkhash(hm_uint a, hm_uint b)
Custom unordered_set implementation.
const_iterator find(const K &key) const
const hm_int hashtable_size_factor
unordered_set(const unordered_set &other)
Construct from another set.
const std::pair< K, T > * operator->() const
bool operator==(const const_iterator &other) const
void insert(InputIterator first, InputIterator last)
Insert Iterator range.
static bool cmp(const T &a, const T &b)
unsigned long int hm_uint
static hm_uint hash(std::vector< T > a)
const K & operator[](hm_int index) const
unordered_map & operator=(unordered_map &&other)
unordered_map & operator=(const unordered_map &other)
static bool cmp(const void *a, const void *b)
iterator(unordered_set *iptr, hm_int iindex)
unordered_set & operator=(const unordered_set &other)
std::vector< hm_int > hashtable
the hashtable
const_iterator(const unordered_set *iptr, hm_int iindex)
bool operator!=(const const_iterator &other) const
void expect(const K &key, hm_int i)
hm_uint mkhash_add(hm_uint a, hm_uint b)
OPS ops
the hash generator
bool operator==(const unordered_set &other) const
unordered_map()
Empty constructor.
const_iterator(const unordered_map *iptr, hm_int iindex)
const_iterator operator--(int)
const_iterator & operator++()
const std::pair< K, T > * operator->() const
hm_int count(const K &key) const
bool operator!=(const iterator &other) const
unordered_set & operator=(unordered_set &&other)
const_iterator end() const
void swap(unordered_map &other)
std::pair< K, T > * operator->()
static hm_uint hash(int64_t a)
static bool cmp(const void *a, const void *b)
bool operator<(const const_iterator &other) const
bool operator==(const iterator &other) const
void imerge(hm_int i, hm_int j)
hm_int do_erase(hm_int index, hm_int hash)
Remove an entry.
bool operator==(const const_iterator &other) const
bool operator!=(const unordered_map &other) const
void merge(const K &a, const K &b)
const hm_int hashtable_size_trigger
const T & at(const K &key) const
Const data access by key.
T & at(const K &key)
Data access by key.
const_iterator begin() const
std::pair< iterator, bool > insert(const K &value)
void do_rehash()
Resize the hashtable and compute new hashes.
static hm_uint hash(const std::string &a)
const_iterator begin() const
const K & find(const K &a) const
bool operator[](const K &key)
hm_int lookup(const K &a) const
hm_int count(const K &key) const
const_iterator & operator++()
const K & operator*() const
hm_int at(const K &key, hm_int defval) const
hm_uint mkhash_xorshift(hm_uint a)
const std::pair< K, T > & operator*() const
void sort(Compare comp=Compare())
Sort data entries.
iterator(unordered_map *iptr, hm_int iindex)
static bool cmp(const char *a, const char *b)
const_iterator end() const
static bool cmp(std::pair< P, Q > a, std::pair< P, Q > b)
iterator erase(iterator it)
Erase by iterator.
hm_int hashtable_size(hm_int min_size)
static bool cmp(std::tuple< T... > a, std::tuple< T... > b)
unordered_set()
Empty constructor.
const K * operator->() const
const_iterator find(const K &key) const
Search for key. Return const_iterator.
static hm_uint hash(const T *a)
const_iterator operator++(int)
unordered_set(unordered_set &&other)
Construct from another set.
bool operator!=(const unordered_set &other) const
std::vector< entry_t > entries
the stored entries
const_iterator end() const
void insert(InputIterator first, InputIterator last)
static bool cmp(T a, T b)
hm_int do_lookup(const K &key, hm_int &hash) const
Return hash and index for a key.
const unordered_map * ptr
hm_int erase(const K &key)
Erase by key.
hm_int at(const K &key) const
bool operator==(const iterator &other) const
const std::pair< K, T > & operator*() const
const K & operator[](hm_int index) const
static std::enable_if< I !=sizeof...(T), hm_uint >::type hash(std::tuple< T... > a)
static std::enable_if< I==sizeof...(T), hm_uint >::type hash(std::tuple< T... >)
static bool cmp(std::vector< T > a, std::vector< T > b)
const_iterator begin() const
unordered_set< K, OPS >::const_iterator const_iterator
const_iterator operator++(int)
hm_int count(const K &key, const_iterator it) const
const K & operator*() const
bool operator<(const iterator &other) const
static bool cmp(const std::string &a, const std::string &b)
hm_int count(const K &key) const
Check if key exists.
hm_int operator()(const K &key)
hm_int count(const K &key, const_iterator it) const
Check if key exists and matches iterator.
void swap(unordered_set &other)
hm_int do_insert(const K &value, hm_int &hash)
Insert a pair consisting of a key and a default (empty) value.
bool operator!=(const const_iterator &other) const
iterator erase(iterator it)
std::pair< iterator, bool > insert(const std::pair< K, T > &value)
Insert key-value pair.
const hm_uint mkhash_init
hm_int operator()(const K &key) const
static hm_uint hash(const char *a)
static hm_uint hash(const void *a)
entry_t(const K &idata, hm_int inext)
static hm_uint hash(const T &a)
unordered_map(const unordered_map &other)
Construct from another map.
T at(const K &key, const T &defval) const
Return data if existent or default value.
bool operator==(const unordered_map &other) const
unordered_map(InputIterator first, InputIterator last)
Construct from Iterator range.
const_iterator & operator--()
unordered_set(InputIterator first, InputIterator last)
idict< K, 0, OPS >::const_iterator const_iterator
hm_int ifind(hm_int i) const
static hm_uint hash(std::pair< P, Q > a)
T & operator[](const K &key)
Data access or empty insert.
iterator find(const K &key)
Search for key. Return iterator.
iterator find(const K &key)
unordered_map(const std::initializer_list< std::pair< K, T >> &list)
bool operator!=(const iterator &other) const
const_iterator begin() const
void sort(Compare comp=Compare())
const_iterator end() const
hm_int erase(const K &key)
const unordered_set * ptr
unordered_map(unordered_map &&other)
Construct map form another map.
const_iterator & operator--()
std::pair< K, T > & operator*()
const_iterator operator--(int)
static hm_uint hash(int32_t a)
static void do_assert(bool cond)