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