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
  14 #include <stdexcept>
  15 #include <algorithm>
  16 #include <string>
  17 #include <vector>
  18
  19 namespace hashlib {
  20
  21 const int hashtable_size_trigger = 2;
  22 const int hashtable_size_factor = 3;
  23
  24 // The XOR version of DJB2
  25 inline unsigned int mkhash(unsigned int a, unsigned int b) {
  26         return ((a << 5) + a) ^ b;
  27 }
  28
  29 // traditionally 5381 is used as starting value for the djb2 hash
  30 const unsigned int mkhash_init = 5381;
  31
  32 // The ADD version of DJB2
  33 // (usunsigned int mkhashe this version for cache locality in b)
  34 inline unsigned int mkhash_add(unsigned int a, unsigned int b) {
  35         return ((a << 5) + a) + b;
  36 }
  37
  38 inline unsigned int mkhash_xorshift(unsigned int a) {
  39         if (sizeof(a) == 4) {
  40                 a ^= a << 13;
  41                 a ^= a >> 17;
  42                 a ^= a << 5;
  43         } else if (sizeof(a) == 8) {
  44                 a ^= a << 13;
  45                 a ^= a >> 7;
  46                 a ^= a << 17;
  47         } else
  48                 throw std::runtime_error("mkhash_xorshift() only implemented for 32 bit and 64 bit ints");
  49         return a;
  50 }
  51
  52 template<typename T> struct hash_ops {
  53         static inline bool cmp(const T &a, const T &b) {
  54                 return a == b;
  55         }
  56         static inline unsigned int hash(const T &a) {
  57                 return a.hash();
  58         }
  59 };
  60
  61 template<> struct hash_ops<int> {
  62         template<typename T>
  63         static inline bool cmp(T a, T b) {
  64                 return a == b;
  65         }
  66         template<typename T>
  67         static inline unsigned int hash(T a) {
  68                 return a;
  69         }
  70 };
  71
  72 template<> struct hash_ops<std::string> {
  73         static inline bool cmp(const std::string &a, const std::string &b) {
  74                 return a == b;
  75         }
  76         static inline unsigned int hash(const std::string &a) {
  77                 unsigned int v = 0;
  78                 for (auto c : a)
  79                         v = mkhash(v, c);
  80                 return v;
  81         }
  82 };
  83
  84 template<typename P, typename Q> struct hash_ops<std::pair<P, Q>> {
  85         static inline bool cmp(std::pair<P, Q> a, std::pair<P, Q> b) {
  86                 return a == b;
  87         }
  88         static inline unsigned int hash(std::pair<P, Q> a) {
  89                 hash_ops<P> p_ops;
  90                 hash_ops<Q> q_ops;
  91                 return mkhash(p_ops.hash(a.first), q_ops.hash(a.second));
  92         }
  93 };
  94
  95 template<typename T> struct hash_ops<std::vector<T>> {
  96         static inline bool cmp(std::vector<T> a, std::vector<T> b) {
  97                 return a == b;
  98         }
  99         static inline unsigned int hash(std::vector<T> a) {
 100                 hash_ops<T> t_ops;
 101                 unsigned int h = mkhash_init;
 102                 for (auto k : a)
 103                         h = mkhash(h, t_ops.hash(k));
 104                 return h;
 105         }
 106 };
 107
 108 struct hash_cstr_ops {
 109         static inline bool cmp(const char *a, const char *b) {
 110                 for (int i = 0; a[i] || b[i]; i++)
 111                         if (a[i] != b[i])
 112                                 return false;
 113                 return true;
 114         }
 115         static inline unsigned int hash(const char *a) {
 116                 unsigned int hash = mkhash_init;
 117                 while (*a)
 118                          hash = mkhash(hash, *(a++));
 119                  return hash;
 120         }
 121 };
 122
 123 struct hash_ptr_ops {
 124         static inline bool cmp(const void *a, const void *b) {
 125                 return a == b;
 126         }
 127         static inline unsigned int hash(const void *a) {
 128                 return (unsigned long)a;
 129         }
 130 };
 131
 132 struct hash_obj_ops {
 133         static inline bool cmp(const void *a, const void *b) {
 134                 return a == b;
 135         }
 136         template<typename T>
 137         static inline unsigned int hash(const T *a) {
 138                 return a->hash();
 139         }
 140 };
 141
 142 inline int hashtable_size(int min_size)
 143 {
 144         static std::vector<int> zero_and_some_primes = {
 145                 0, 23, 29, 37, 47, 59, 79, 101, 127, 163, 211, 269, 337, 431, 541, 677,
 146                 853, 1069, 1361, 1709, 2137, 2677, 3347, 4201, 5261, 6577, 8231, 10289,
 147                 12889, 16127, 20161, 25219, 31531, 39419, 49277, 61603, 77017, 96281,
 148                 120371, 150473, 188107, 235159, 293957, 367453, 459317, 574157, 717697,
 149                 897133, 1121423, 1401791, 1752239, 2190299, 2737937, 3422429, 4278037,
 150                 5347553, 6684443, 8355563, 10444457, 13055587, 16319519, 20399411,
 151                 25499291, 31874149, 39842687, 49803361, 62254207, 77817767, 97272239,
 152                 121590311, 151987889, 189984863, 237481091, 296851369, 371064217
 153         };
 154
 155         for (auto p : zero_and_some_primes)
 156                 if (p >= min_size) return p;
 157
 158         if (sizeof(int) == 4)
 159                 throw std::length_error("hash table exceeded maximum size. use a ILP64 abi for larger tables.");
 160
 161         for (auto p : zero_and_some_primes)
 162                 if (100129 * p > min_size) return 100129 * p;
 163
 164         throw std::length_error("hash table exceeded maximum size.");
 165 }
 166
 167 template<typename K, typename T, typename OPS = hash_ops<K>> class dict;
 168 template<typename K, int offset = 0, typename OPS = hash_ops<K>> class idict;
 169 template<typename K, typename OPS = hash_ops<K>> class pool;
 170
 171 template<typename K, typename T, typename OPS>
 172 class dict
 173 {
 174         struct entry_t
 175         {
 176                 std::pair<K, T> udata;
 177                 int next;
 178
 179                 entry_t() { }
 180                 entry_t(const std::pair<K, T> &udata, int next) : udata(udata), next(next) { }
 181                 entry_t(std::pair<K, T> &&udata, int next) : udata(std::move(udata)), next(next) { }
 182         };
 183
 184         std::vector<int> hashtable;
 185         std::vector<entry_t> entries;
 186         OPS ops;
 187
 188 #ifdef NDEBUG
 189         static inline void do_assert(bool) { }
 190 #else
 191         static inline void do_assert(bool cond) {
 192                 if (!cond) throw std::runtime_error("dict<> assert failed.");
 193         }
 194 #endif
 195
 196         int do_hash(const K &key) const
 197         {
 198                 unsigned int hash = 0;
 199                 if (!hashtable.empty())
 200                         hash = ops.hash(key) % (unsigned int)(hashtable.size());
 201                 return hash;
 202         }
 203
 204         void do_rehash()
 205         {
 206                 hashtable.clear();
 207                 hashtable.resize(hashtable_size(entries.size() * hashtable_size_factor), -1);
 208
 209                 for (int i = 0; i < int(entries.size()); i++) {
 210                         do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size()));
 211                         int hash = do_hash(entries[i].udata.first);
 212                         entries[i].next = hashtable[hash];
 213                         hashtable[hash] = i;
 214                 }
 215         }
 216
 217         int do_erase(int index, int hash)
 218         {
 219                 do_assert(index < int(entries.size()));
 220                 if (hashtable.empty() || index < 0)
 221                         return 0;
 222
 223                 int k = hashtable[hash];
 224                 do_assert(0 <= k && k < int(entries.size()));
 225
 226                 if (k == index) {
 227                         hashtable[hash] = entries[index].next;
 228                 } else {
 229                         while (entries[k].next != index) {
 230                                 k = entries[k].next;
 231                                 do_assert(0 <= k && k < int(entries.size()));
 232                         }
 233                         entries[k].next = entries[index].next;
 234                 }
 235
 236                 int back_idx = entries.size()-1;
 237
 238                 if (index != back_idx)
 239                 {
 240                         int back_hash = do_hash(entries[back_idx].udata.first);
 241
 242                         k = hashtable[back_hash];
 243                         do_assert(0 <= k && k < int(entries.size()));
 244
 245                         if (k == back_idx) {
 246                                 hashtable[back_hash] = index;
 247                         } else {
 248                                 while (entries[k].next != back_idx) {
 249                                         k = entries[k].next;
 250                                         do_assert(0 <= k && k < int(entries.size()));
 251                                 }
 252                                 entries[k].next = index;
 253                         }
 254
 255                         entries[index] = std::move(entries[back_idx]);
 256                 }
 257
 258                 entries.pop_back();
 259
 260                 if (entries.empty())
 261                         hashtable.clear();
 262
 263                 return 1;
 264         }
 265
 266         int do_lookup(const K &key, int &hash) const
 267         {
 268                 if (hashtable.empty())
 269                         return -1;
 270
 271                 if (entries.size() * hashtable_size_trigger > hashtable.size()) {
 272                         ((dict*)this)->do_rehash();
 273                         hash = do_hash(key);
 274                 }
 275
 276                 int index = hashtable[hash];
 277
 278                 while (index >= 0 && !ops.cmp(entries[index].udata.first, key)) {
 279                         index = entries[index].next;
 280                         do_assert(-1 <= index && index < int(entries.size()));
 281                 }
 282
 283                 return index;
 284         }
 285
 286         int do_insert(const K &key, int &hash)
 287         {
 288                 if (hashtable.empty()) {
 289                         entries.push_back(entry_t(std::pair<K, T>(key, T()), -1));
 290                         do_rehash();
 291                         hash = do_hash(key);
 292                 } else {
 293                         entries.push_back(entry_t(std::pair<K, T>(key, T()), hashtable[hash]));
 294                         hashtable[hash] = entries.size() - 1;
 295                 }
 296                 return entries.size() - 1;
 297         }
 298
 299         int do_insert(const std::pair<K, T> &value, int &hash)
 300         {
 301                 if (hashtable.empty()) {
 302                         entries.push_back(entry_t(value, -1));
 303                         do_rehash();
 304                         hash = do_hash(value.first);
 305                 } else {
 306                         entries.push_back(entry_t(value, hashtable[hash]));
 307                         hashtable[hash] = entries.size() - 1;
 308                 }
 309                 return entries.size() - 1;
 310         }
 311
 312 public:
 313         class const_iterator : public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
 314         {
 315                 friend class dict;
 316         protected:
 317                 const dict *ptr;
 318                 int index;
 319                 const_iterator(const dict *ptr, int index) : ptr(ptr), index(index) { }
 320         public:
 321                 const_iterator() { }
 322                 const_iterator operator++() { index--; return *this; }
 323                 bool operator<(const const_iterator &other) const { return index > other.index; }
 324                 bool operator==(const const_iterator &other) const { return index == other.index; }
 325                 bool operator!=(const const_iterator &other) const { return index != other.index; }
 326                 const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
 327                 const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
 328         };
 329
 330         class iterator : public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
 331         {
 332                 friend class dict;
 333         protected:
 334                 dict *ptr;
 335                 int index;
 336                 iterator(dict *ptr, int index) : ptr(ptr), index(index) { }
 337         public:
 338                 iterator() { }
 339                 iterator operator++() { index--; return *this; }
 340                 bool operator<(const iterator &other) const { return index > other.index; }
 341                 bool operator==(const iterator &other) const { return index == other.index; }
 342                 bool operator!=(const iterator &other) const { return index != other.index; }
 343                 std::pair<K, T> &operator*() { return ptr->entries[index].udata; }
 344                 std::pair<K, T> *operator->() { return &ptr->entries[index].udata; }
 345                 const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
 346                 const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
 347                 operator const_iterator() const { return const_iterator(ptr, index); }
 348         };
 349
 350         dict()
 351         {
 352         }
 353
 354         dict(const dict &other)
 355         {
 356                 entries = other.entries;
 357                 do_rehash();
 358         }
 359
 360         dict(dict &&other)
 361         {
 362                 swap(other);
 363         }
 364
 365         dict &operator=(const dict &other) {
 366                 entries = other.entries;
 367                 do_rehash();
 368                 return *this;
 369         }
 370
 371         dict &operator=(dict &&other) {
 372                 clear();
 373                 swap(other);
 374                 return *this;
 375         }
 376
 377         dict(const std::initializer_list<std::pair<K, T>> &list)
 378         {
 379                 for (auto &it : list)
 380                         insert(it);
 381         }
 382
 383         template<class InputIterator>
 384         dict(InputIterator first, InputIterator last)
 385         {
 386                 insert(first, last);
 387         }
 388
 389         template<class InputIterator>
 390         void insert(InputIterator first, InputIterator last)
 391         {
 392                 for (; first != last; ++first)
 393                         insert(*first);
 394         }
 395
 396         std::pair<iterator, bool> insert(const K &key)
 397         {
 398                 int hash = do_hash(key);
 399                 int i = do_lookup(key, hash);
 400                 if (i >= 0)
 401                         return std::pair<iterator, bool>(iterator(this, i), false);
 402                 i = do_insert(key, hash);
 403                 return std::pair<iterator, bool>(iterator(this, i), true);
 404         }
 405
 406         std::pair<iterator, bool> insert(const std::pair<K, T> &value)
 407         {
 408                 int hash = do_hash(value.first);
 409                 int i = do_lookup(value.first, hash);
 410                 if (i >= 0)
 411                         return std::pair<iterator, bool>(iterator(this, i), false);
 412                 i = do_insert(value, hash);
 413                 return std::pair<iterator, bool>(iterator(this, i), true);
 414         }
 415
 416         int erase(const K &key)
 417         {
 418                 int hash = do_hash(key);
 419                 int index = do_lookup(key, hash);
 420                 return do_erase(index, hash);
 421         }
 422
 423         iterator erase(iterator it)
 424         {
 425                 int hash = do_hash(it->first);
 426                 do_erase(it.index, hash);
 427                 return ++it;
 428         }
 429
 430         int count(const K &key) const
 431         {
 432                 int hash = do_hash(key);
 433                 int i = do_lookup(key, hash);
 434                 return i < 0 ? 0 : 1;
 435         }
 436
 437         int count(const K &key, const_iterator it) const
 438         {
 439                 int hash = do_hash(key);
 440                 int i = do_lookup(key, hash);
 441                 return i < 0 || i > it.index ? 0 : 1;
 442         }
 443
 444         iterator find(const K &key)
 445         {
 446                 int hash = do_hash(key);
 447                 int i = do_lookup(key, hash);
 448                 if (i < 0)
 449                         return end();
 450                 return iterator(this, i);
 451         }
 452
 453         const_iterator find(const K &key) const
 454         {
 455                 int hash = do_hash(key);
 456                 int i = do_lookup(key, hash);
 457                 if (i < 0)
 458                         return end();
 459                 return const_iterator(this, i);
 460         }
 461
 462         T& at(const K &key)
 463         {
 464                 int hash = do_hash(key);
 465                 int i = do_lookup(key, hash);
 466                 if (i < 0)
 467                         throw std::out_of_range("dict::at()");
 468                 return entries[i].udata.second;
 469         }
 470
 471         const T& at(const K &key) const
 472         {
 473                 int hash = do_hash(key);
 474                 int i = do_lookup(key, hash);
 475                 if (i < 0)
 476                         throw std::out_of_range("dict::at()");
 477                 return entries[i].udata.second;
 478         }
 479
 480         T& operator[](const K &key)
 481         {
 482                 int hash = do_hash(key);
 483                 int i = do_lookup(key, hash);
 484                 if (i < 0)
 485                         i = do_insert(std::pair<K, T>(key, T()), hash);
 486                 return entries[i].udata.second;
 487         }
 488
 489         template<typename Compare = std::less<K>>
 490         void sort(Compare comp = Compare())
 491         {
 492                 std::sort(entries.begin(), entries.end(), [comp](const entry_t &a, const entry_t &b){ return comp(b.udata.first, a.udata.first); });
 493                 do_rehash();
 494         }
 495
 496         void swap(dict &other)
 497         {
 498                 hashtable.swap(other.hashtable);
 499                 entries.swap(other.entries);
 500         }
 501
 502         bool operator==(const dict &other) const {
 503                 if (size() != other.size())
 504                         return false;
 505                 for (auto &it : entries) {
 506                         auto oit = other.find(it.udata.first);
 507                         if (oit == other.end() || !(oit->second == it.udata.second))
 508                                 return false;
 509                 }
 510                 return true;
 511         }
 512
 513         bool operator!=(const dict &other) const {
 514                 return !operator==(other);
 515         }
 516
 517         size_t size() const { return entries.size(); }
 518         bool empty() const { return entries.empty(); }
 519         void clear() { hashtable.clear(); entries.clear(); }
 520
 521         iterator begin() { return iterator(this, int(entries.size())-1); }
 522         iterator end() { return iterator(nullptr, -1); }
 523
 524         const_iterator begin() const { return const_iterator(this, int(entries.size())-1); }
 525         const_iterator end() const { return const_iterator(nullptr, -1); }
 526 };
 527
 528 template<typename K, typename OPS>
 529 class pool
 530 {
 531         template<typename, int, typename> friend class idict;
 532
 533 protected:
 534         struct entry_t
 535         {
 536                 K udata;
 537                 int next;
 538
 539                 entry_t() { }
 540                 entry_t(const K &udata, int next) : udata(udata), next(next) { }
 541         };
 542
 543         std::vector<int> hashtable;
 544         std::vector<entry_t> entries;
 545         OPS ops;
 546
 547 #ifdef NDEBUG
 548         static inline void do_assert(bool) { }
 549 #else
 550         static inline void do_assert(bool cond) {
 551                 if (!cond) throw std::runtime_error("pool<> assert failed.");
 552         }
 553 #endif
 554
 555         int do_hash(const K &key) const
 556         {
 557                 unsigned int hash = 0;
 558                 if (!hashtable.empty())
 559                         hash = ops.hash(key) % (unsigned int)(hashtable.size());
 560                 return hash;
 561         }
 562
 563         void do_rehash()
 564         {
 565                 hashtable.clear();
 566                 hashtable.resize(hashtable_size(entries.size() * hashtable_size_factor), -1);
 567
 568                 for (int i = 0; i < int(entries.size()); i++) {
 569                         do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size()));
 570                         int hash = do_hash(entries[i].udata);
 571                         entries[i].next = hashtable[hash];
 572                         hashtable[hash] = i;
 573                 }
 574         }
 575
 576         int do_erase(int index, int hash)
 577         {
 578                 do_assert(index < int(entries.size()));
 579                 if (hashtable.empty() || index < 0)
 580                         return 0;
 581
 582                 int k = hashtable[hash];
 583                 if (k == index) {
 584                         hashtable[hash] = entries[index].next;
 585                 } else {
 586                         while (entries[k].next != index) {
 587                                 k = entries[k].next;
 588                                 do_assert(0 <= k && k < int(entries.size()));
 589                         }
 590                         entries[k].next = entries[index].next;
 591                 }
 592
 593                 int back_idx = entries.size()-1;
 594
 595                 if (index != back_idx)
 596                 {
 597                         int back_hash = do_hash(entries[back_idx].udata);
 598
 599                         k = hashtable[back_hash];
 600                         if (k == back_idx) {
 601                                 hashtable[back_hash] = index;
 602                         } else {
 603                                 while (entries[k].next != back_idx) {
 604                                         k = entries[k].next;
 605                                         do_assert(0 <= k && k < int(entries.size()));
 606                                 }
 607                                 entries[k].next = index;
 608                         }
 609
 610                         entries[index] = std::move(entries[back_idx]);
 611                 }
 612
 613                 entries.pop_back();
 614
 615                 if (entries.empty())
 616                         hashtable.clear();
 617
 618                 return 1;
 619         }
 620
 621         int do_lookup(const K &key, int &hash) const
 622         {
 623                 if (hashtable.empty())
 624                         return -1;
 625
 626                 if (entries.size() * hashtable_size_trigger > hashtable.size()) {
 627                         ((pool*)this)->do_rehash();
 628                         hash = do_hash(key);
 629                 }
 630
 631                 int index = hashtable[hash];
 632
 633                 while (index >= 0 && !ops.cmp(entries[index].udata, key)) {
 634                         index = entries[index].next;
 635                         do_assert(-1 <= index && index < int(entries.size()));
 636                 }
 637
 638                 return index;
 639         }
 640
 641         int do_insert(const K &value, int &hash)
 642         {
 643                 if (hashtable.empty()) {
 644                         entries.push_back(entry_t(value, -1));
 645                         do_rehash();
 646                         hash = do_hash(value);
 647                 } else {
 648                         entries.push_back(entry_t(value, hashtable[hash]));
 649                         hashtable[hash] = entries.size() - 1;
 650                 }
 651                 return entries.size() - 1;
 652         }
 653
 654 public:
 655         class const_iterator : public std::iterator<std::forward_iterator_tag, K>
 656         {
 657                 friend class pool;
 658         protected:
 659                 const pool *ptr;
 660                 int index;
 661                 const_iterator(const pool *ptr, int index) : ptr(ptr), index(index) { }
 662         public:
 663                 const_iterator() { }
 664                 const_iterator operator++() { index--; return *this; }
 665                 bool operator==(const const_iterator &other) const { return index == other.index; }
 666                 bool operator!=(const const_iterator &other) const { return index != other.index; }
 667                 const K &operator*() const { return ptr->entries[index].udata; }
 668                 const K *operator->() const { return &ptr->entries[index].udata; }
 669         };
 670
 671         class iterator : public std::iterator<std::forward_iterator_tag, K>
 672         {
 673                 friend class pool;
 674         protected:
 675                 pool *ptr;
 676                 int index;
 677                 iterator(pool *ptr, int index) : ptr(ptr), index(index) { }
 678         public:
 679                 iterator() { }
 680                 iterator operator++() { index--; return *this; }
 681                 bool operator==(const iterator &other) const { return index == other.index; }
 682                 bool operator!=(const iterator &other) const { return index != other.index; }
 683                 K &operator*() { return ptr->entries[index].udata; }
 684                 K *operator->() { return &ptr->entries[index].udata; }
 685                 const K &operator*() const { return ptr->entries[index].udata; }
 686                 const K *operator->() const { return &ptr->entries[index].udata; }
 687                 operator const_iterator() const { return const_iterator(ptr, index); }
 688         };
 689
 690         pool()
 691         {
 692         }
 693
 694         pool(const pool &other)
 695         {
 696                 entries = other.entries;
 697                 do_rehash();
 698         }
 699
 700         pool(pool &&other)
 701         {
 702                 swap(other);
 703         }
 704
 705         pool &operator=(const pool &other) {
 706                 entries = other.entries;
 707                 do_rehash();
 708                 return *this;
 709         }
 710
 711         pool &operator=(pool &&other) {
 712                 clear();
 713                 swap(other);
 714                 return *this;
 715         }
 716
 717         pool(const std::initializer_list<K> &list)
 718         {
 719                 for (auto &it : list)
 720                         insert(it);
 721         }
 722
 723         template<class InputIterator>
 724         pool(InputIterator first, InputIterator last)
 725         {
 726                 insert(first, last);
 727         }
 728
 729         template<class InputIterator>
 730         void insert(InputIterator first, InputIterator last)
 731         {
 732                 for (; first != last; ++first)
 733                         insert(*first);
 734         }
 735
 736         std::pair<iterator, bool> insert(const K &value)
 737         {
 738                 int hash = do_hash(value);
 739                 int i = do_lookup(value, hash);
 740                 if (i >= 0)
 741                         return std::pair<iterator, bool>(iterator(this, i), false);
 742                 i = do_insert(value, hash);
 743                 return std::pair<iterator, bool>(iterator(this, i), true);
 744         }
 745
 746         int erase(const K &key)
 747         {
 748                 int hash = do_hash(key);
 749                 int index = do_lookup(key, hash);
 750                 return do_erase(index, hash);
 751         }
 752
 753         iterator erase(iterator it)
 754         {
 755                 int hash = do_hash(*it);
 756                 do_erase(it.index, hash);
 757                 return ++it;
 758         }
 759
 760         int count(const K &key) const
 761         {
 762                 int hash = do_hash(key);
 763                 int i = do_lookup(key, hash);
 764                 return i < 0 ? 0 : 1;
 765         }
 766
 767         int count(const K &key, const_iterator it) const
 768         {
 769                 int hash = do_hash(key);
 770                 int i = do_lookup(key, hash);
 771                 return i < 0 || i > it.index ? 0 : 1;
 772         }
 773
 774         iterator find(const K &key)
 775         {
 776                 int hash = do_hash(key);
 777                 int i = do_lookup(key, hash);
 778                 if (i < 0)
 779                         return end();
 780                 return iterator(this, i);
 781         }
 782
 783         const_iterator find(const K &key) const
 784         {
 785                 int hash = do_hash(key);
 786                 int i = do_lookup(key, hash);
 787                 if (i < 0)
 788                         return end();
 789                 return const_iterator(this, i);
 790         }
 791
 792         bool operator[](const K &key)
 793         {
 794                 int hash = do_hash(key);
 795                 int i = do_lookup(key, hash);
 796                 return i >= 0;
 797         }
 798
 799         template<typename Compare = std::less<K>>
 800         void sort(Compare comp = Compare())
 801         {
 802                 std::sort(entries.begin(), entries.end(), [comp](const entry_t &a, const entry_t &b){ return comp(b.udata, a.udata); });
 803                 do_rehash();
 804         }
 805
 806         void swap(pool &other)
 807         {
 808                 hashtable.swap(other.hashtable);
 809                 entries.swap(other.entries);
 810         }
 811
 812         bool operator==(const pool &other) const {
 813                 if (size() != other.size())
 814                         return false;
 815                 for (auto &it : entries)
 816                         if (!other.count(it.udata))
 817                                 return false;
 818                 return true;
 819         }
 820
 821         bool operator!=(const pool &other) const {
 822                 return !operator==(other);
 823         }
 824
 825         size_t size() const { return entries.size(); }
 826         bool empty() const { return entries.empty(); }
 827         void clear() { hashtable.clear(); entries.clear(); }
 828
 829         iterator begin() { return iterator(this, int(entries.size())-1); }
 830         iterator end() { return iterator(nullptr, -1); }
 831
 832         const_iterator begin() const { return const_iterator(this, int(entries.size())-1); }
 833         const_iterator end() const { return const_iterator(nullptr, -1); }
 834 };
 835
 836 template<typename K, int offset, typename OPS>
 837 class idict
 838 {
 839         pool<K, OPS> database;
 840
 841 public:
 842         typedef typename pool<K, OPS>::const_iterator const_iterator;
 843
 844         int operator()(const K &key)
 845         {
 846                 int hash = database.do_hash(key);
 847                 int i = database.do_lookup(key, hash);
 848                 if (i < 0)
 849                         i = database.do_insert(key, hash);
 850                 return i + offset;
 851         }
 852
 853         int at(const K &key) const
 854         {
 855                 int hash = database.do_hash(key);
 856                 int i = database.do_lookup(key, hash);
 857                 if (i < 0)
 858                         throw std::out_of_range("idict::at()");
 859                 return i + offset;
 860         }
 861
 862         int count(const K &key) const
 863         {
 864                 int hash = database.do_hash(key);
 865                 int i = database.do_lookup(key, hash);
 866                 return i < 0 ? 0 : 1;
 867         }
 868
 869         void expect(const K &key, int i)
 870         {
 871                 int j = (*this)(key);
 872                 if (i != j)
 873                         throw std::out_of_range("idict::expect()");
 874         }
 875
 876         const K &operator[](int index) const
 877         {
 878                 return database.entries.at(index - offset).udata;
 879         }
 880
 881         const_iterator begin() const { return database.begin(); }
 882         const_iterator end() const { return database.end(); }
 883 };
 884
 885 } /* namespace hashlib */
 886
 887 #endif