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