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) {
119 template<>
struct hash_ops<long> : hash_int_ops
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) {
148 template<
typename... T>
struct hash_ops<std::tuple<T...>> {
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)));
163 template<
typename T>
struct hash_ops<std::vector<T>> {
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++)
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;
241 template<
typename K,
typename OPS = hash_ops<K>>
class unordered_set;
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)
328 hm_int k = hashtable[hash];
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())
389 hm_int index = hashtable[hash];
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>>
473 class iterator :
public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
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);
605 hm_int hash = do_hash(key);
606 hm_int i = do_lookup(key, hash);
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);
674 for (
auto &it : entries) {
675 auto oit = other.
find(it.udata.first);
676 if (oit == other.
end() || !(oit->second == it.udata.second))
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(); }
704 template<
typename K,
typename OPS>
707 template<
typename, hm_
int,
typename>
friend class idict;
731 if (!cond)
throw std::runtime_error(
"unordered_set<> assert failed.");
786 while (
entries[k].next != index) {
795 if (index != back_idx)
803 while (
entries[k].next != back_idx) {
841 while (index >= 0 && !
ops.cmp(
entries[index].udata, key)) {
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)
973 return std::pair<iterator, bool>(
iterator(
this, i),
false);
975 return std::pair<iterator, bool>(
iterator(
this, i),
true);
996 return i < 0 ? 0 : 1;
1003 return i < 0 || i > it.
index ? 0 : 1;
1031 template<
typename Compare = std::less<K>>
1032 void sort(Compare comp = Compare())
1056 if (!other.
count(it.udata))
1077 template<
typename K, hm_
int offset,
typename OPS>
1099 throw std::out_of_range(
"idict::at()");
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);
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);
hm_int operator()(const K &key)
const K & operator[](hm_int index) const
void expect(const K &key, hm_int i)
const_iterator begin() const
hm_int at(const K &key) const
unordered_set< K, OPS >::const_iterator const_iterator
hm_int count(const K &key) const
const_iterator end() const
hm_int at(const K &key, hm_int defval) const
hm_int operator()(const K &key) const
hm_int lookup(const K &a) const
const K & operator[](hm_int index) const
const K & find(const K &a) const
hm_int ifind(hm_int i) const
const_iterator begin() const
idict< K, 0, OPS >::const_iterator const_iterator
void imerge(hm_int i, hm_int j)
const_iterator end() const
void merge(const K &a, const K &b)
const_iterator & operator--()
const_iterator(const unordered_map *iptr, hm_int iindex)
bool operator!=(const const_iterator &other) const
const_iterator operator++(int)
const_iterator operator--(int)
const unordered_map * ptr
bool operator==(const const_iterator &other) const
const_iterator & operator++()
const std::pair< K, T > * operator->() const
bool operator<(const const_iterator &other) const
const std::pair< K, T > & operator*() const
const std::pair< K, T > * operator->() const
std::pair< K, T > & operator*()
const std::pair< K, T > & operator*() const
bool operator!=(const iterator &other) const
iterator(unordered_map *iptr, hm_int iindex)
std::pair< K, T > * operator->()
bool operator<(const iterator &other) const
bool operator==(const iterator &other) const
T at(const K &key, const T &defval) const
Return data if existent or default value.
iterator find(const K &key)
Search for key. Return iterator.
hm_int count(const K &key, const_iterator it) const
Check if key exists and matches iterator.
unordered_map & operator=(const unordered_map &other)
const_iterator end() const
unordered_map(const std::initializer_list< std::pair< K, T >> &list)
unordered_map(unordered_map &&other)
Construct map form another map.
hm_int count(const K &key) const
Check if key exists.
bool operator!=(const unordered_map &other) const
const_iterator begin() const
std::pair< iterator, bool > insert(const std::pair< K, T > &value)
Insert key-value pair.
const T & at(const K &key) const
Const data access by key.
T & operator[](const K &key)
Data access or empty insert.
void swap(unordered_map &other)
void sort(Compare comp=Compare())
Sort data entries.
bool operator==(const unordered_map &other) const
const_iterator find(const K &key) const
Search for key. Return const_iterator.
std::pair< iterator, bool > insert(const K &key)
User insert as key lookup.
void insert(InputIterator first, InputIterator last)
Insert Iterator range.
iterator erase(iterator it)
Erase by iterator.
unordered_map()
Empty constructor.
T & at(const K &key)
Data access by key.
unordered_map(InputIterator first, InputIterator last)
Construct from Iterator range.
unordered_map & operator=(unordered_map &&other)
hm_int erase(const K &key)
Erase by key.
unordered_map(const unordered_map &other)
Construct from another map.
bool operator==(const const_iterator &other) const
const K & operator*() const
const K * operator->() const
const_iterator operator--(int)
bool operator!=(const const_iterator &other) const
const_iterator & operator--()
const_iterator & operator++()
const_iterator operator++(int)
const_iterator(const unordered_set *iptr, hm_int iindex)
const unordered_set * ptr
bool operator!=(const iterator &other) const
const K * operator->() const
const K & operator*() const
iterator(unordered_set *iptr, hm_int iindex)
bool operator==(const iterator &other) const
Custom unordered_set implementation.
unordered_set(InputIterator first, InputIterator last)
unordered_set(unordered_set &&other)
Construct from another set.
unordered_set & operator=(unordered_set &&other)
iterator find(const K &key)
std::pair< iterator, bool > insert(const K &value)
const_iterator end() const
void sort(Compare comp=Compare())
hm_int erase(const K &key)
const_iterator find(const K &key) const
bool operator==(const unordered_set &other) const
hm_int do_erase(hm_int index, hm_int hash)
Remove an entry.
unordered_set(const unordered_set &other)
Construct from another set.
unordered_set(const std::initializer_list< K > &list)
OPS ops
the hash generator
unordered_set & operator=(const unordered_set &other)
iterator erase(iterator it)
void do_rehash()
Resize the hashtable and compute new hashes.
const_iterator begin() const
hm_int do_hash(const K &key) const
Generate a hash from a key.
std::vector< entry_t > entries
the stored entries
std::vector< hm_int > hashtable
the hashtable
static void do_assert(bool cond)
void swap(unordered_set &other)
hm_int do_lookup(const K &key, hm_int &hash) const
Return hash and index for a key.
bool operator[](const K &key)
unordered_set()
Empty constructor.
bool operator!=(const unordered_set &other) const
hm_int count(const K &key) const
void insert(InputIterator first, InputIterator last)
hm_int count(const K &key, const_iterator it) const
hm_int do_insert(const K &value, hm_int &hash)
Insert a pair consisting of a key and a default (empty) value.
unsigned long int hm_uint
const hm_int hashtable_size_trigger
hm_int hashtable_size(hm_int min_size)
const hm_uint mkhash_init
hm_uint mkhash_add(hm_uint a, hm_uint b)
hm_uint mkhash(hm_uint a, hm_uint b)
const hm_int hashtable_size_factor
hm_uint mkhash_xorshift(hm_uint a)
static hm_uint hash(const char *a)
static bool cmp(const char *a, const char *b)
static bool cmp(T a, T b)
static hm_uint hash(const T *a)
static bool cmp(const void *a, const void *b)
static hm_uint hash(int32_t a)
static hm_uint hash(int64_t a)
static hm_uint hash(std::pair< P, Q > a)
static bool cmp(std::pair< P, Q > a, std::pair< P, Q > b)
static hm_uint hash(const std::string &a)
static bool cmp(const std::string &a, const std::string &b)
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::tuple< T... > a, std::tuple< T... > b)
static hm_uint hash(std::vector< T > a)
static bool cmp(std::vector< T > a, std::vector< T > b)
static hm_uint hash(const T &a)
static bool cmp(const T &a, const T &b)
static hm_uint hash(const void *a)
static bool cmp(const void *a, const void *b)
entry_t(const K &idata, hm_int inext)