kernel/hashlib.h

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