kernel/hashmap.h

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