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