kernel/hashlib.h

   1 // This is free and unencumbered software released into the public domain.
   2 //
   3 // Anyone is free to copy, modify, publish, use, compile, sell, or
   4 // distribute this software, either in source code form or as a compiled
   5 // binary, for any purpose, commercial or non-commercial, and by any
   6 // means.
   7
   8 // -------------------------------------------------------
   9 // Written by Clifford Wolf <clifford@clifford.at> in 2014
  10 // -------------------------------------------------------
  11
  12 #ifndef HASHLIB_H
  13 #define HASHLIB_H
  14
  15 #include <stdexcept>
  16 #include <algorithm>
  17 #include <string>
  18 #include <vector>
  19
  20 namespace hashlib {
  21
  22 template<typename T> struct hash_ops;
  23 template<typename K, typename T, typename OPS = hash_ops<K>> class dict;
  24 template<typename K, int offset = 0, typename OPS = hash_ops<K>> class idict;
  25 template<typename K, typename OPS = hash_ops<K>> class pool;
  26 template<typename K, typename OPS = hash_ops<K>> class mfp;
  27
  28 const int hashtable_size_trigger = 2;
  29 const int hashtable_size_factor = 3;
  30
  31 // The XOR version of DJB2
  32 inline unsigned int mkhash(unsigned int a, unsigned int b) {
  33         return ((a << 5) + a) ^ b;
  34 }
  35
  36 // traditionally 5381 is used as starting value for the djb2 hash
  37 const unsigned int mkhash_init = 5381;
  38
  39 // The ADD version of DJB2
  40 // (use this version for cache locality in b)
  41 inline unsigned int mkhash_add(unsigned int a, unsigned int b) {
  42         return ((a << 5) + a) + b;
  43 }
  44
  45 inline unsigned int mkhash_xorshift(unsigned int a) {
  46         if (sizeof(a) == 4) {
  47                 a ^= a << 13;
  48                 a ^= a >> 17;
  49                 a ^= a << 5;
  50         } else if (sizeof(a) == 8) {
  51                 a ^= a << 13;
  52                 a ^= a >> 7;
  53                 a ^= a << 17;
  54         } else
  55                 throw std::runtime_error("mkhash_xorshift() only implemented for 32 bit and 64 bit ints");
  56         return a;
  57 }
  58
  59 template<typename T> struct hash_ops {
  60         static inline bool cmp(const T &a, const T &b) {
  61                 return a == b;
  62         }
  63         static inline unsigned int hash(const T &a) {
  64                 return a.hash();
  65         }
  66 };
  67
  68 struct hash_int_ops {
  69         template<typename T>
  70         static inline bool cmp(T a, T b) {
  71                 return a == b;
  72         }
  73 };
  74
  75 template<> struct hash_ops<int32_t> : hash_int_ops
  76 {
  77         static inline unsigned int hash(int32_t a) {
  78                 return a;
  79         }
  80 };
  81 template<> struct hash_ops<int64_t> : hash_int_ops
  82 {
  83         static inline unsigned int hash(int64_t a) {
  84                 return mkhash((unsigned int)(a), (unsigned int)(a >> 32));
  85         }
  86 };
  87
  88 template<> struct hash_ops<std::string> {
  89         static inline bool cmp(const std::string &a, const std::string &b) {
  90                 return a == b;
  91         }
  92         static inline unsigned int hash(const std::string &a) {
  93                 unsigned int v = 0;
  94                 for (auto c : a)
  95                         v = mkhash(v, c);
  96                 return v;
  97         }
  98 };
  99
 100 template<typename P, typename Q> struct hash_ops<std::pair<P, Q>> {
 101         static inline bool cmp(std::pair<P, Q> a, std::pair<P, Q> b) {
 102                 return a == b;
 103         }
 104         static inline unsigned int hash(std::pair<P, Q> a) {
 105                 return mkhash(hash_ops<P>::hash(a.first), hash_ops<Q>::hash(a.second));
 106         }
 107 };
 108
 109 template<typename P, typename Q> struct hash_ops<dict<P, Q>> {
 110         static inline bool cmp(dict<P, Q> a, dict<P, Q> b) {
 111                 return a == b;
 112         }
 113         static inline unsigned int hash(dict<P, Q> a) {
 114                 unsigned int h = mkhash_init;
 115                 for (auto &it : a) {
 116                         h = mkhash(h, hash_ops<P>::hash(it.first));
 117                         h = mkhash(h, hash_ops<Q>::hash(it.second));
 118                 }
 119                 return h;
 120         }
 121 };
 122
 123 template<typename... T> struct hash_ops<std::tuple<T...>> {
 124         static inline bool cmp(std::tuple<T...> a, std::tuple<T...> b) {
 125                 return a == b;
 126         }
 127         template<size_t I = 0>
 128         static inline typename std::enable_if<I == sizeof...(T), unsigned int>::type hash(std::tuple<T...>) {
 129                 return mkhash_init;
 130         }
 131         template<size_t I = 0>
 132         static inline typename std::enable_if<I != sizeof...(T), unsigned int>::type hash(std::tuple<T...> a) {
 133                 typedef hash_ops<typename std::tuple_element<I, std::tuple<T...>>::type> element_ops_t;
 134                 return mkhash(hash<I+1>(a), element_ops_t::hash(std::get<I>(a)));
 135         }
 136 };
 137
 138 template<typename T> struct hash_ops<std::vector<T>> {
 139         static inline bool cmp(std::vector<T> a, std::vector<T> b) {
 140                 return a == b;
 141         }
 142         static inline unsigned int hash(std::vector<T> a) {
 143                 unsigned int h = mkhash_init;
 144                 for (auto k : a)
 145                         h = mkhash(h, hash_ops<T>::hash(k));
 146                 return h;
 147         }
 148 };
 149
 150 struct hash_cstr_ops {
 151         static inline bool cmp(const char *a, const char *b) {
 152                 for (int i = 0; a[i] || b[i]; i++)
 153                         if (a[i] != b[i])
 154                                 return false;
 155                 return true;
 156         }
 157         static inline unsigned int hash(const char *a) {
 158                 unsigned int hash = mkhash_init;
 159                 while (*a)
 160                         hash = mkhash(hash, *(a++));
 161                 return hash;
 162         }
 163 };
 164
 165 struct hash_ptr_ops {
 166         static inline bool cmp(const void *a, const void *b) {
 167                 return a == b;
 168         }
 169         static inline unsigned int hash(const void *a) {
 170                 return (uintptr_t)a;
 171         }
 172 };
 173
 174 struct hash_obj_ops {
 175         static inline bool cmp(const void *a, const void *b) {
 176                 return a == b;
 177         }
 178         template<typename T>
 179         static inline unsigned int hash(const T *a) {
 180                 return a ? a->hash() : 0;
 181         }
 182 };
 183
 184 template<typename T>
 185 inline unsigned int mkhash(const T &v) {
 186         return hash_ops<T>().hash(v);
 187 }
 188
 189 inline int hashtable_size(int min_size)
 190 {
 191         static std::vector<int> zero_and_some_primes = {
 192                 0, 23, 29, 37, 47, 59, 79, 101, 127, 163, 211, 269, 337, 431, 541, 677,
 193                 853, 1069, 1361, 1709, 2137, 2677, 3347, 4201, 5261, 6577, 8231, 10289,
 194                 12889, 16127, 20161, 25219, 31531, 39419, 49277, 61603, 77017, 96281,
 195                 120371, 150473, 188107, 235159, 293957, 367453, 459317, 574157, 717697,
 196                 897133, 1121423, 1401791, 1752239, 2190299, 2737937, 3422429, 4278037,
 197                 5347553, 6684443, 8355563, 10444457, 13055587, 16319519, 20399411,
 198                 25499291, 31874149, 39842687, 49803361, 62254207, 77817767, 97272239,
 199                 121590311, 151987889, 189984863, 237481091, 296851369, 371064217
 200         };
 201
 202         for (auto p : zero_and_some_primes)
 203                 if (p >= min_size) return p;
 204
 205         if (sizeof(int) == 4)
 206                 throw std::length_error("hash table exceeded maximum size. use a ILP64 abi for larger tables.");
 207
 208         for (auto p : zero_and_some_primes)
 209                 if (100129 * p > min_size) return 100129 * p;
 210
 211         throw std::length_error("hash table exceeded maximum size.");
 212 }
 213
 214 template<typename K, typename T, typename OPS>
 215 class dict
 216 {
 217         struct entry_t
 218         {
 219                 std::pair<K, T> udata;
 220                 int next;
 221
 222                 entry_t() { }
 223                 entry_t(const std::pair<K, T> &udata, int next) : udata(udata), next(next) { }
 224                 entry_t(std::pair<K, T> &&udata, int next) : udata(std::move(udata)), next(next) { }
 225         };
 226
 227         std::vector<int> hashtable;
 228         std::vector<entry_t> entries;
 229         OPS ops;
 230
 231 #ifdef NDEBUG
 232         static inline void do_assert(bool) { }
 233 #else
 234         static inline void do_assert(bool cond) {
 235                 if (!cond) throw std::runtime_error("dict<> assert failed.");
 236         }
 237 #endif
 238
 239         int do_hash(const K &key) const
 240         {
 241                 unsigned int hash = 0;
 242                 if (!hashtable.empty())
 243                         hash = ops.hash(key) % (unsigned int)(hashtable.size());
 244                 return hash;
 245         }
 246
 247         void do_rehash()
 248         {
 249                 hashtable.clear();
 250                 hashtable.resize(hashtable_size(entries.capacity() * hashtable_size_factor), -1);
 251
 252                 for (int i = 0; i < int(entries.size()); i++) {
 253                         do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size()));
 254                         int hash = do_hash(entries[i].udata.first);
 255                         entries[i].next = hashtable[hash];
 256                         hashtable[hash] = i;
 257                 }
 258         }
 259
 260         int do_erase(int index, int hash)
 261         {
 262                 do_assert(index < int(entries.size()));
 263                 if (hashtable.empty() || index < 0)
 264                         return 0;
 265
 266                 int k = hashtable[hash];
 267                 do_assert(0 <= k && k < int(entries.size()));
 268
 269                 if (k == index) {
 270                         hashtable[hash] = entries[index].next;
 271                 } else {
 272                         while (entries[k].next != index) {
 273                                 k = entries[k].next;
 274                                 do_assert(0 <= k && k < int(entries.size()));
 275                         }
 276                         entries[k].next = entries[index].next;
 277                 }
 278
 279                 int back_idx = entries.size()-1;
 280
 281                 if (index != back_idx)
 282                 {
 283                         int back_hash = do_hash(entries[back_idx].udata.first);
 284
 285                         k = hashtable[back_hash];
 286                         do_assert(0 <= k && k < int(entries.size()));
 287
 288                         if (k == back_idx) {
 289                                 hashtable[back_hash] = index;
 290                         } else {
 291                                 while (entries[k].next != back_idx) {
 292                                         k = entries[k].next;
 293                                         do_assert(0 <= k && k < int(entries.size()));
 294                                 }
 295                                 entries[k].next = index;
 296                         }
 297
 298                         entries[index] = std::move(entries[back_idx]);
 299                 }
 300
 301                 entries.pop_back();
 302
 303                 if (entries.empty())
 304                         hashtable.clear();
 305
 306                 return 1;
 307         }
 308
 309         int do_lookup(const K &key, int &hash) const
 310         {
 311                 if (hashtable.empty())
 312                         return -1;
 313
 314                 if (entries.size() * hashtable_size_trigger > hashtable.size()) {
 315                         ((dict*)this)->do_rehash();
 316                         hash = do_hash(key);
 317                 }
 318
 319                 int index = hashtable[hash];
 320
 321                 while (index >= 0 && !ops.cmp(entries[index].udata.first, key)) {
 322                         index = entries[index].next;
 323                         do_assert(-1 <= index && index < int(entries.size()));
 324                 }
 325
 326                 return index;
 327         }
 328
 329         int do_insert(const K &key, int &hash)
 330         {
 331                 if (hashtable.empty()) {
 332                         entries.emplace_back(std::pair<K, T>(key, T()), -1);
 333                         do_rehash();
 334                         hash = do_hash(key);
 335                 } else {
 336                         entries.emplace_back(std::pair<K, T>(key, T()), hashtable[hash]);
 337                         hashtable[hash] = entries.size() - 1;
 338                 }
 339                 return entries.size() - 1;
 340         }
 341
 342         int do_insert(const std::pair<K, T> &value, int &hash)
 343         {
 344                 if (hashtable.empty()) {
 345                         entries.emplace_back(value, -1);
 346                         do_rehash();
 347                         hash = do_hash(value.first);
 348                 } else {
 349                         entries.emplace_back(value, hashtable[hash]);
 350                         hashtable[hash] = entries.size() - 1;
 351                 }
 352                 return entries.size() - 1;
 353         }
 354
 355         int do_insert(std::pair<K, T> &&rvalue, int &hash)
 356         {
 357                 if (hashtable.empty()) {
 358                         auto key = rvalue.first;
 359                         entries.emplace_back(std::forward<std::pair<K, T>>(rvalue), -1);
 360                         do_rehash();
 361                         hash = do_hash(key);
 362                 } else {
 363                         entries.emplace_back(std::forward<std::pair<K, T>>(rvalue), hashtable[hash]);
 364                         hashtable[hash] = entries.size() - 1;
 365                 }
 366                 return entries.size() - 1;
 367         }
 368
 369 public:
 370         class const_iterator : public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
 371         {
 372                 friend class dict;
 373         protected:
 374                 const dict *ptr;
 375                 int index;
 376                 const_iterator(const dict *ptr, int index) : ptr(ptr), index(index) { }
 377         public:
 378                 const_iterator() { }
 379                 const_iterator operator++() { index--; return *this; }
 380                 bool operator<(const const_iterator &other) const { return index > other.index; }
 381                 bool operator==(const const_iterator &other) const { return index == other.index; }
 382                 bool operator!=(const const_iterator &other) const { return index != other.index; }
 383                 const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
 384                 const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
 385         };
 386
 387         class iterator : public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
 388         {
 389                 friend class dict;
 390         protected:
 391                 dict *ptr;
 392                 int index;
 393                 iterator(dict *ptr, int index) : ptr(ptr), index(index) { }
 394         public:
 395                 iterator() { }
 396                 iterator operator++() { index--; return *this; }
 397                 bool operator<(const iterator &other) const { return index > other.index; }
 398                 bool operator==(const iterator &other) const { return index == other.index; }
 399                 bool operator!=(const iterator &other) const { return index != other.index; }
 400                 std::pair<K, T> &operator*() { return ptr->entries[index].udata; }
 401                 std::pair<K, T> *operator->() { return &ptr->entries[index].udata; }
 402                 const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
 403                 const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
 404                 operator const_iterator() const { return const_iterator(ptr, index); }
 405         };
 406
 407         dict()
 408         {
 409         }
 410
 411         dict(const dict &other)
 412         {
 413                 entries = other.entries;
 414                 do_rehash();
 415         }
 416
 417         dict(dict &&other)
 418         {
 419                 swap(other);
 420         }
 421
 422         dict &operator=(const dict &other) {
 423                 entries = other.entries;
 424                 do_rehash();
 425                 return *this;
 426         }
 427
 428         dict &operator=(dict &&other) {
 429                 clear();
 430                 swap(other);
 431                 return *this;
 432         }
 433
 434         dict(const std::initializer_list<std::pair<K, T>> &list)
 435         {
 436                 for (auto &it : list)
 437                         insert(it);
 438         }
 439
 440         template<class InputIterator>
 441         dict(InputIterator first, InputIterator last)
 442         {
 443                 insert(first, last);
 444         }
 445
 446         template<class InputIterator>
 447         void insert(InputIterator first, InputIterator last)
 448         {
 449                 for (; first != last; ++first)
 450                         insert(*first);
 451         }
 452
 453         std::pair<iterator, bool> insert(const K &key)
 454         {
 455                 int hash = do_hash(key);
 456                 int i = do_lookup(key, hash);
 457                 if (i >= 0)
 458                         return std::pair<iterator, bool>(iterator(this, i), false);
 459                 i = do_insert(key, hash);
 460                 return std::pair<iterator, bool>(iterator(this, i), true);
 461         }
 462
 463         std::pair<iterator, bool> insert(const std::pair<K, T> &value)
 464         {
 465                 int hash = do_hash(value.first);
 466                 int i = do_lookup(value.first, hash);
 467                 if (i >= 0)
 468                         return std::pair<iterator, bool>(iterator(this, i), false);
 469                 i = do_insert(value, hash);
 470                 return std::pair<iterator, bool>(iterator(this, i), true);
 471         }
 472
 473         std::pair<iterator, bool> insert(std::pair<K, T> &&rvalue)
 474         {
 475                 int hash = do_hash(rvalue.first);
 476                 int i = do_lookup(rvalue.first, hash);
 477                 if (i >= 0)
 478                         return std::pair<iterator, bool>(iterator(this, i), false);
 479                 i = do_insert(std::forward<std::pair<K, T>>(rvalue), hash);
 480                 return std::pair<iterator, bool>(iterator(this, i), true);
 481         }
 482
 483         std::pair<iterator, bool> emplace(K const &key, T const &value)
 484         {
 485                 int hash = do_hash(key);
 486                 int i = do_lookup(key, hash);
 487                 if (i >= 0)
 488                         return std::pair<iterator, bool>(iterator(this, i), false);
 489                 i = do_insert(std::make_pair(key, value), hash);
 490                 return std::pair<iterator, bool>(iterator(this, i), true);
 491         }
 492
 493         std::pair<iterator, bool> emplace(K const &key, T &&rvalue)
 494         {
 495                 int hash = do_hash(key);
 496                 int i = do_lookup(key, hash);
 497                 if (i >= 0)
 498                         return std::pair<iterator, bool>(iterator(this, i), false);
 499                 i = do_insert(std::make_pair(key, std::forward<T>(rvalue)), hash);
 500                 return std::pair<iterator, bool>(iterator(this, i), true);
 501         }
 502
 503         std::pair<iterator, bool> emplace(K &&rkey, T const &value)
 504         {
 505                 int hash = do_hash(rkey);
 506                 int i = do_lookup(rkey, hash);
 507                 if (i >= 0)
 508                         return std::pair<iterator, bool>(iterator(this, i), false);
 509                 i = do_insert(std::make_pair(std::forward<K>(rkey), value), hash);
 510                 return std::pair<iterator, bool>(iterator(this, i), true);
 511         }
 512
 513         std::pair<iterator, bool> emplace(K &&rkey, T &&rvalue)
 514         {
 515                 int hash = do_hash(rkey);
 516                 int i = do_lookup(rkey, hash);
 517                 if (i >= 0)
 518                         return std::pair<iterator, bool>(iterator(this, i), false);
 519                 i = do_insert(std::make_pair(std::forward<K>(rkey), std::forward<T>(rvalue)), hash);
 520                 return std::pair<iterator, bool>(iterator(this, i), true);
 521         }
 522
 523         int erase(const K &key)
 524         {
 525                 int hash = do_hash(key);
 526                 int index = do_lookup(key, hash);
 527                 return do_erase(index, hash);
 528         }
 529
 530         iterator erase(iterator it)
 531         {
 532                 int hash = do_hash(it->first);
 533                 do_erase(it.index, hash);
 534                 return ++it;
 535         }
 536
 537         int count(const K &key) const
 538         {
 539                 int hash = do_hash(key);
 540                 int i = do_lookup(key, hash);
 541                 return i < 0 ? 0 : 1;
 542         }
 543
 544         int count(const K &key, const_iterator it) const
 545         {
 546                 int hash = do_hash(key);
 547                 int i = do_lookup(key, hash);
 548                 return i < 0 || i > it.index ? 0 : 1;
 549         }
 550
 551         iterator find(const K &key)
 552         {
 553                 int hash = do_hash(key);
 554                 int i = do_lookup(key, hash);
 555                 if (i < 0)
 556                         return end();
 557                 return iterator(this, i);
 558         }
 559
 560         const_iterator find(const K &key) const
 561         {
 562                 int hash = do_hash(key);
 563                 int i = do_lookup(key, hash);
 564                 if (i < 0)
 565                         return end();
 566                 return const_iterator(this, i);
 567         }
 568
 569         T& at(const K &key)
 570         {
 571                 int hash = do_hash(key);
 572                 int i = do_lookup(key, hash);
 573                 if (i < 0)
 574                         throw std::out_of_range("dict::at()");
 575                 return entries[i].udata.second;
 576         }
 577
 578         const T& at(const K &key) const
 579         {
 580                 int hash = do_hash(key);
 581                 int i = do_lookup(key, hash);
 582                 if (i < 0)
 583                         throw std::out_of_range("dict::at()");
 584                 return entries[i].udata.second;
 585         }
 586
 587         const T& at(const K &key, const T &defval) const
 588         {
 589                 int hash = do_hash(key);
 590                 int i = do_lookup(key, hash);
 591                 if (i < 0)
 592                         return defval;
 593                 return entries[i].udata.second;
 594         }
 595
 596         T& operator[](const K &key)
 597         {
 598                 int hash = do_hash(key);
 599                 int i = do_lookup(key, hash);
 600                 if (i < 0)
 601                         i = do_insert(std::pair<K, T>(key, T()), hash);
 602                 return entries[i].udata.second;
 603         }
 604
 605         template<typename Compare = std::less<K>>
 606         void sort(Compare comp = Compare())
 607         {
 608                 std::sort(entries.begin(), entries.end(), [comp](const entry_t &a, const entry_t &b){ return comp(b.udata.first, a.udata.first); });
 609                 do_rehash();
 610         }
 611
 612         void swap(dict &other)
 613         {
 614                 hashtable.swap(other.hashtable);
 615                 entries.swap(other.entries);
 616         }
 617
 618         bool operator==(const dict &other) const {
 619                 if (size() != other.size())
 620                         return false;
 621                 for (auto &it : entries) {
 622                         auto oit = other.find(it.udata.first);
 623                         if (oit == other.end() || !(oit->second == it.udata.second))
 624                                 return false;
 625                 }
 626                 return true;
 627         }
 628
 629         bool operator!=(const dict &other) const {
 630                 return !operator==(other);
 631         }
 632
 633         void reserve(size_t n) { entries.reserve(n); }
 634         size_t size() const { return entries.size(); }
 635         bool empty() const { return entries.empty(); }
 636         void clear() { hashtable.clear(); entries.clear(); }
 637
 638         iterator begin() { return iterator(this, int(entries.size())-1); }
 639         iterator element(int n) { return iterator(this, int(entries.size())-1-n); }
 640         iterator end() { return iterator(nullptr, -1); }
 641
 642         const_iterator begin() const { return const_iterator(this, int(entries.size())-1); }
 643         const_iterator element(int n) const { return const_iterator(this, int(entries.size())-1-n); }
 644         const_iterator end() const { return const_iterator(nullptr, -1); }
 645 };
 646
 647 template<typename K, typename OPS>
 648 class pool
 649 {
 650         template<typename, int, typename> friend class idict;
 651
 652 protected:
 653         struct entry_t
 654         {
 655                 K udata;
 656                 int next;
 657
 658                 entry_t() { }
 659                 entry_t(const K &udata, int next) : udata(udata), next(next) { }
 660                 entry_t(K &&udata, int next) : udata(std::move(udata)), next(next) { }
 661         };
 662
 663         std::vector<int> hashtable;
 664         std::vector<entry_t> entries;
 665         OPS ops;
 666
 667 #ifdef NDEBUG
 668         static inline void do_assert(bool) { }
 669 #else
 670         static inline void do_assert(bool cond) {
 671                 if (!cond) throw std::runtime_error("pool<> assert failed.");
 672         }
 673 #endif
 674
 675         int do_hash(const K &key) const
 676         {
 677                 unsigned int hash = 0;
 678                 if (!hashtable.empty())
 679                         hash = ops.hash(key) % (unsigned int)(hashtable.size());
 680                 return hash;
 681         }
 682
 683         void do_rehash()
 684         {
 685                 hashtable.clear();
 686                 hashtable.resize(hashtable_size(entries.capacity() * hashtable_size_factor), -1);
 687
 688                 for (int i = 0; i < int(entries.size()); i++) {
 689                         do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size()));
 690                         int hash = do_hash(entries[i].udata);
 691                         entries[i].next = hashtable[hash];
 692                         hashtable[hash] = i;
 693                 }
 694         }
 695
 696         int do_erase(int index, int hash)
 697         {
 698                 do_assert(index < int(entries.size()));
 699                 if (hashtable.empty() || index < 0)
 700                         return 0;
 701
 702                 int k = hashtable[hash];
 703                 if (k == index) {
 704                         hashtable[hash] = entries[index].next;
 705                 } else {
 706                         while (entries[k].next != index) {
 707                                 k = entries[k].next;
 708                                 do_assert(0 <= k && k < int(entries.size()));
 709                         }
 710                         entries[k].next = entries[index].next;
 711                 }
 712
 713                 int back_idx = entries.size()-1;
 714
 715                 if (index != back_idx)
 716                 {
 717                         int back_hash = do_hash(entries[back_idx].udata);
 718
 719                         k = hashtable[back_hash];
 720                         if (k == back_idx) {
 721                                 hashtable[back_hash] = index;
 722                         } else {
 723                                 while (entries[k].next != back_idx) {
 724                                         k = entries[k].next;
 725                                         do_assert(0 <= k && k < int(entries.size()));
 726                                 }
 727                                 entries[k].next = index;
 728                         }
 729
 730                         entries[index] = std::move(entries[back_idx]);
 731                 }
 732
 733                 entries.pop_back();
 734
 735                 if (entries.empty())
 736                         hashtable.clear();
 737
 738                 return 1;
 739         }
 740
 741         int do_lookup(const K &key, int &hash) const
 742         {
 743                 if (hashtable.empty())
 744                         return -1;
 745
 746                 if (entries.size() * hashtable_size_trigger > hashtable.size()) {
 747                         ((pool*)this)->do_rehash();
 748                         hash = do_hash(key);
 749                 }
 750
 751                 int index = hashtable[hash];
 752
 753                 while (index >= 0 && !ops.cmp(entries[index].udata, key)) {
 754                         index = entries[index].next;
 755                         do_assert(-1 <= index && index < int(entries.size()));
 756                 }
 757
 758                 return index;
 759         }
 760
 761         int do_insert(const K &value, int &hash)
 762         {
 763                 if (hashtable.empty()) {
 764                         entries.emplace_back(value, -1);
 765                         do_rehash();
 766                         hash = do_hash(value);
 767                 } else {
 768                         entries.emplace_back(value, hashtable[hash]);
 769                         hashtable[hash] = entries.size() - 1;
 770                 }
 771                 return entries.size() - 1;
 772         }
 773
 774         int do_insert(K &&rvalue, int &hash)
 775         {
 776                 if (hashtable.empty()) {
 777                         entries.emplace_back(std::forward<K>(rvalue), -1);
 778                         do_rehash();
 779                         hash = do_hash(rvalue);
 780                 } else {
 781                         entries.emplace_back(std::forward<K>(rvalue), hashtable[hash]);
 782                         hashtable[hash] = entries.size() - 1;
 783                 }
 784                 return entries.size() - 1;
 785         }
 786
 787 public:
 788         class const_iterator : public std::iterator<std::forward_iterator_tag, K>
 789         {
 790                 friend class pool;
 791         protected:
 792                 const pool *ptr;
 793                 int index;
 794                 const_iterator(const pool *ptr, int index) : ptr(ptr), index(index) { }
 795         public:
 796                 const_iterator() { }
 797                 const_iterator operator++() { index--; return *this; }
 798                 bool operator==(const const_iterator &other) const { return index == other.index; }
 799                 bool operator!=(const const_iterator &other) const { return index != other.index; }
 800                 const K &operator*() const { return ptr->entries[index].udata; }
 801                 const K *operator->() const { return &ptr->entries[index].udata; }
 802         };
 803
 804         class iterator : public std::iterator<std::forward_iterator_tag, K>
 805         {
 806                 friend class pool;
 807         protected:
 808                 pool *ptr;
 809                 int index;
 810                 iterator(pool *ptr, int index) : ptr(ptr), index(index) { }
 811         public:
 812                 iterator() { }
 813                 iterator operator++() { index--; return *this; }
 814                 bool operator==(const iterator &other) const { return index == other.index; }
 815                 bool operator!=(const iterator &other) const { return index != other.index; }
 816                 K &operator*() { return ptr->entries[index].udata; }
 817                 K *operator->() { return &ptr->entries[index].udata; }
 818                 const K &operator*() const { return ptr->entries[index].udata; }
 819                 const K *operator->() const { return &ptr->entries[index].udata; }
 820                 operator const_iterator() const { return const_iterator(ptr, index); }
 821         };
 822
 823         pool()
 824         {
 825         }
 826
 827         pool(const pool &other)
 828         {
 829                 entries = other.entries;
 830                 do_rehash();
 831         }
 832
 833         pool(pool &&other)
 834         {
 835                 swap(other);
 836         }
 837
 838         pool &operator=(const pool &other) {
 839                 entries = other.entries;
 840                 do_rehash();
 841                 return *this;
 842         }
 843
 844         pool &operator=(pool &&other) {
 845                 clear();
 846                 swap(other);
 847                 return *this;
 848         }
 849
 850         pool(const std::initializer_list<K> &list)
 851         {
 852                 for (auto &it : list)
 853                         insert(it);
 854         }
 855
 856         template<class InputIterator>
 857         pool(InputIterator first, InputIterator last)
 858         {
 859                 insert(first, last);
 860         }
 861
 862         template<class InputIterator>
 863         void insert(InputIterator first, InputIterator last)
 864         {
 865                 for (; first != last; ++first)
 866                         insert(*first);
 867         }
 868
 869         std::pair<iterator, bool> insert(const K &value)
 870         {
 871                 int hash = do_hash(value);
 872                 int i = do_lookup(value, hash);
 873                 if (i >= 0)
 874                         return std::pair<iterator, bool>(iterator(this, i), false);
 875                 i = do_insert(value, hash);
 876                 return std::pair<iterator, bool>(iterator(this, i), true);
 877         }
 878
 879         std::pair<iterator, bool> insert(K &&rvalue)
 880         {
 881                 int hash = do_hash(rvalue);
 882                 int i = do_lookup(rvalue, hash);
 883                 if (i >= 0)
 884                         return std::pair<iterator, bool>(iterator(this, i), false);
 885                 i = do_insert(std::forward<K>(rvalue), hash);
 886                 return std::pair<iterator, bool>(iterator(this, i), true);
 887         }
 888
 889         template<typename... Args>
 890         std::pair<iterator, bool> emplace(Args&&... args)
 891         {
 892                 return insert(K(std::forward<Args>(args)...));
 893         }
 894
 895         int erase(const K &key)
 896         {
 897                 int hash = do_hash(key);
 898                 int index = do_lookup(key, hash);
 899                 return do_erase(index, hash);
 900         }
 901
 902         iterator erase(iterator it)
 903         {
 904                 int hash = do_hash(*it);
 905                 do_erase(it.index, hash);
 906                 return ++it;
 907         }
 908
 909         int count(const K &key) const
 910         {
 911                 int hash = do_hash(key);
 912                 int i = do_lookup(key, hash);
 913                 return i < 0 ? 0 : 1;
 914         }
 915
 916         int count(const K &key, const_iterator it) const
 917         {
 918                 int hash = do_hash(key);
 919                 int i = do_lookup(key, hash);
 920                 return i < 0 || i > it.index ? 0 : 1;
 921         }
 922
 923         iterator find(const K &key)
 924         {
 925                 int hash = do_hash(key);
 926                 int i = do_lookup(key, hash);
 927                 if (i < 0)
 928                         return end();
 929                 return iterator(this, i);
 930         }
 931
 932         const_iterator find(const K &key) const
 933         {
 934                 int hash = do_hash(key);
 935                 int i = do_lookup(key, hash);
 936                 if (i < 0)
 937                         return end();
 938                 return const_iterator(this, i);
 939         }
 940
 941         bool operator[](const K &key)
 942         {
 943                 int hash = do_hash(key);
 944                 int i = do_lookup(key, hash);
 945                 return i >= 0;
 946         }
 947
 948         template<typename Compare = std::less<K>>
 949         void sort(Compare comp = Compare())
 950         {
 951                 std::sort(entries.begin(), entries.end(), [comp](const entry_t &a, const entry_t &b){ return comp(b.udata, a.udata); });
 952                 do_rehash();
 953         }
 954
 955         K pop()
 956         {
 957                 iterator it = begin();
 958                 K ret = *it;
 959                 erase(it);
 960                 return ret;
 961         }
 962
 963         void swap(pool &other)
 964         {
 965                 hashtable.swap(other.hashtable);
 966                 entries.swap(other.entries);
 967         }
 968
 969         bool operator==(const pool &other) const {
 970                 if (size() != other.size())
 971                         return false;
 972                 for (auto &it : entries)
 973                         if (!other.count(it.udata))
 974                                 return false;
 975                 return true;
 976         }
 977
 978         bool operator!=(const pool &other) const {
 979                 return !operator==(other);
 980         }
 981
 982         bool hash() const {
 983                 unsigned int hashval = mkhash_init;
 984                 for (auto &it : entries)
 985                         hashval ^= ops.hash(it.udata);
 986                 return hashval;
 987         }
 988
 989         void reserve(size_t n) { entries.reserve(n); }
 990         size_t size() const { return entries.size(); }
 991         bool empty() const { return entries.empty(); }
 992         void clear() { hashtable.clear(); entries.clear(); }
 993
 994         iterator begin() { return iterator(this, int(entries.size())-1); }
 995         iterator element(int n) { return iterator(this, int(entries.size())-1-n); }
 996         iterator end() { return iterator(nullptr, -1); }
 997
 998         const_iterator begin() const { return const_iterator(this, int(entries.size())-1); }
 999         const_iterator element(int n) const { return const_iterator(this, int(entries.size())-1-n); }
1000         const_iterator end() const { return const_iterator(nullptr, -1); }
1001 };
1002
1003 template<typename K, int offset, typename OPS>
1004 class idict
1005 {
1006         pool<K, OPS> database;
1007
1008 public:
1009         class const_iterator : public std::iterator<std::forward_iterator_tag, K>
1010         {
1011                 friend class idict;
1012         protected:
1013                 const idict &container;
1014                 int index;
1015                 const_iterator(const idict &container, int index) : container(container), index(index) { }
1016         public:
1017                 const_iterator() { }
1018                 const_iterator operator++() { index++; return *this; }
1019                 bool operator==(const const_iterator &other) const { return index == other.index; }
1020                 bool operator!=(const const_iterator &other) const { return index != other.index; }
1021                 const K &operator*() const { return container[index]; }
1022                 const K *operator->() const { return &container[index]; }
1023         };
1024
1025         int operator()(const K &key)
1026         {
1027                 int hash = database.do_hash(key);
1028                 int i = database.do_lookup(key, hash);
1029                 if (i < 0)
1030                         i = database.do_insert(key, hash);
1031                 return i + offset;
1032         }
1033
1034         int at(const K &key) const
1035         {
1036                 int hash = database.do_hash(key);
1037                 int i = database.do_lookup(key, hash);
1038                 if (i < 0)
1039                         throw std::out_of_range("idict::at()");
1040                 return i + offset;
1041         }
1042
1043         int at(const K &key, int defval) const
1044         {
1045                 int hash = database.do_hash(key);
1046                 int i = database.do_lookup(key, hash);
1047                 if (i < 0)
1048                         return defval;
1049                 return i + offset;
1050         }
1051
1052         int count(const K &key) const
1053         {
1054                 int hash = database.do_hash(key);
1055                 int i = database.do_lookup(key, hash);
1056                 return i < 0 ? 0 : 1;
1057         }
1058
1059         void expect(const K &key, int i)
1060         {
1061                 int j = (*this)(key);
1062                 if (i != j)
1063                         throw std::out_of_range("idict::expect()");
1064         }
1065
1066         const K &operator[](int index) const
1067         {
1068                 return database.entries.at(index - offset).udata;
1069         }
1070
1071         void swap(idict &other)
1072         {
1073                 database.swap(other.database);
1074         }
1075
1076         void reserve(size_t n) { database.reserve(n); }
1077         size_t size() const { return database.size(); }
1078         bool empty() const { return database.empty(); }
1079         void clear() { database.clear(); }
1080
1081         const_iterator begin() const { return const_iterator(*this, offset); }
1082         const_iterator element(int n) const { return const_iterator(*this, n); }
1083         const_iterator end() const { return const_iterator(*this, offset + size()); }
1084 };
1085
1086 template<typename K, typename OPS>
1087 class mfp
1088 {
1089         mutable idict<K, 0, OPS> database;
1090         mutable std::vector<int> parents;
1091
1092 public:
1093         typedef typename idict<K, 0, OPS>::const_iterator const_iterator;
1094
1095         int operator()(const K &key) const
1096         {
1097                 int i = database(key);
1098                 parents.resize(database.size(), -1);
1099                 return i;
1100         }
1101
1102         const K &operator[](int index) const
1103         {
1104                 return database[index];
1105         }
1106
1107         int ifind(int i) const
1108         {
1109                 int p = i, k = i;
1110
1111                 while (parents[p] != -1)
1112                         p = parents[p];
1113
1114                 while (k != p) {
1115                         int next_k = parents[k];
1116                         parents[k] = p;
1117                         k = next_k;
1118                 }
1119
1120                 return p;
1121         }
1122
1123         void imerge(int i, int j)
1124         {
1125                 i = ifind(i);
1126                 j = ifind(j);
1127
1128                 if (i != j)
1129                         parents[i] = j;
1130         }
1131
1132         void ipromote(int i)
1133         {
1134                 int k = i;
1135
1136                 while (k != -1) {
1137                         int next_k = parents[k];
1138                         parents[k] = i;
1139                         k = next_k;
1140                 }
1141
1142                 parents[i] = -1;
1143         }
1144
1145         int lookup(const K &a) const
1146         {
1147                 return ifind((*this)(a));
1148         }
1149
1150         const K &find(const K &a) const
1151         {
1152                 int i = database.at(a, -1);
1153                 if (i < 0)
1154                         return a;
1155                 return (*this)[ifind(i)];
1156         }
1157
1158         void merge(const K &a, const K &b)
1159         {
1160                 imerge((*this)(a), (*this)(b));
1161         }
1162
1163         void promote(const K &a)
1164         {
1165                 int i = database.at(a, -1);
1166                 if (i >= 0)
1167                         ipromote(i);
1168         }
1169
1170         void swap(mfp &other)
1171         {
1172                 database.swap(other.database);
1173                 parents.swap(other.parents);
1174         }
1175
1176         void reserve(size_t n) { database.reserve(n); }
1177         size_t size() const { return database.size(); }
1178         bool empty() const { return database.empty(); }
1179         void clear() { database.clear(); parents.clear(); }
1180
1181         const_iterator begin() const { return database.begin(); }
1182         const_iterator element(int n) const { return database.element(n); }
1183         const_iterator end() const { return database.end(); }
1184 };
1185
1186 } /* namespace hashlib */
1187
1188 #endif