submodule/skia/include/private/SkTHash.h

   1 /*
   2  * Copyright 2015 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7
   8 #ifndef SkTHash_DEFINED
   9 #define SkTHash_DEFINED
  10
  11 #include "include/core/SkTypes.h"
  12 #include "include/private/SkChecksum.h"
  13 #include "include/private/SkTemplates.h"
  14
  15 #include <initializer_list>
  16 #include <new>
  17 #include <utility>
  18
  19 // Before trying to use SkTHashTable, look below to see if SkTHashMap or SkTHashSet works for you.
  20 // They're easier to use, usually perform the same, and have fewer sharp edges.
  21
  22 // T and K are treated as ordinary copyable C++ types.
  23 // Traits must have:
  24 //   - static K GetKey(T)
  25 //   - static uint32_t Hash(K)
  26 // If the key is large and stored inside T, you may want to make K a const&.
  27 // Similarly, if T is large you might want it to be a pointer.
  28 template <typename T, typename K, typename Traits = T>
  29 class SkTHashTable {
  30 public:
  31     SkTHashTable()  = default;
  32     ~SkTHashTable() = default;
  33
  34     SkTHashTable(const SkTHashTable&  that) { *this = that; }
  35     SkTHashTable(      SkTHashTable&& that) { *this = std::move(that); }
  36
  37     SkTHashTable& operator=(const SkTHashTable& that) {
  38         if (this != &that) {
  39             fCount     = that.fCount;
  40             fCapacity  = that.fCapacity;
  41             fSlots.reset(that.fCapacity);
  42             for (int i = 0; i < fCapacity; i++) {
  43                 fSlots[i] = that.fSlots[i];
  44             }
  45         }
  46         return *this;
  47     }
  48
  49     SkTHashTable& operator=(SkTHashTable&& that) {
  50         if (this != &that) {
  51             fCount    = that.fCount;
  52             fCapacity = that.fCapacity;
  53             fSlots    = std::move(that.fSlots);
  54
  55             that.fCount = that.fCapacity = 0;
  56         }
  57         return *this;
  58     }
  59
  60     // Clear the table.
  61     void reset() { *this = SkTHashTable(); }
  62
  63     // How many entries are in the table?
  64     int count() const { return fCount; }
  65
  66     // How many slots does the table contain? (Note that unlike an array, hash tables can grow
  67     // before reaching 100% capacity.)
  68     int capacity() const { return fCapacity; }
  69
  70     // Approximately how many bytes of memory do we use beyond sizeof(*this)?
  71     size_t approxBytesUsed() const { return fCapacity * sizeof(Slot); }
  72
  73     // !!!!!!!!!!!!!!!!!                 CAUTION                   !!!!!!!!!!!!!!!!!
  74     // set(), find() and foreach() all allow mutable access to table entries.
  75     // If you change an entry so that it no longer has the same key, all hell
  76     // will break loose.  Do not do that!
  77     //
  78     // Please prefer to use SkTHashMap or SkTHashSet, which do not have this danger.
  79
  80     // The pointers returned by set() and find() are valid only until the next call to set().
  81     // The pointers you receive in foreach() are only valid for its duration.
  82
  83     // Copy val into the hash table, returning a pointer to the copy now in the table.
  84     // If there already is an entry in the table with the same key, we overwrite it.
  85     T* set(T val) {
  86         if (4 * fCount >= 3 * fCapacity) {
  87             this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
  88         }
  89         return this->uncheckedSet(std::move(val));
  90     }
  91
  92     // If there is an entry in the table with this key, return a pointer to it.  If not, null.
  93     T* find(const K& key) const {
  94         uint32_t hash = Hash(key);
  95         int index = hash & (fCapacity-1);
  96         for (int n = 0; n < fCapacity; n++) {
  97             Slot& s = fSlots[index];
  98             if (s.empty()) {
  99                 return nullptr;
 100             }
 101             if (hash == s.hash && key == Traits::GetKey(*s)) {
 102                 return &*s;
 103             }
 104             index = this->next(index);
 105         }
 106         SkASSERT(fCapacity == 0);
 107         return nullptr;
 108     }
 109
 110     // If there is an entry in the table with this key, return it.  If not, null.
 111     // This only works for pointer type T, and cannot be used to find an nullptr entry.
 112     T findOrNull(const K& key) const {
 113         if (T* p = this->find(key)) {
 114             return *p;
 115         }
 116         return nullptr;
 117     }
 118
 119     // Remove the value with this key from the hash table.
 120     void remove(const K& key) {
 121         SkASSERT(this->find(key));
 122
 123         uint32_t hash = Hash(key);
 124         int index = hash & (fCapacity-1);
 125         for (int n = 0; n < fCapacity; n++) {
 126             Slot& s = fSlots[index];
 127             SkASSERT(s.has_value());
 128             if (hash == s.hash && key == Traits::GetKey(*s)) {
 129                this->removeSlot(index);
 130                if (4 * fCount <= fCapacity && fCapacity > 4) {
 131                    this->resize(fCapacity / 2);
 132                }
 133                return;
 134             }
 135             index = this->next(index);
 136         }
 137     }
 138
 139     // Hash tables will automatically resize themselves when set() and remove() are called, but
 140     // resize() can be called to manually grow capacity before a bulk insertion.
 141     void resize(int capacity) {
 142         SkASSERT(capacity >= fCount);
 143         int oldCapacity = fCapacity;
 144         SkDEBUGCODE(int oldCount = fCount);
 145
 146         fCount = 0;
 147         fCapacity = capacity;
 148         SkAutoTArray<Slot> oldSlots = std::move(fSlots);
 149         fSlots = SkAutoTArray<Slot>(capacity);
 150
 151         for (int i = 0; i < oldCapacity; i++) {
 152             Slot& s = oldSlots[i];
 153             if (s.has_value()) {
 154                 this->uncheckedSet(*std::move(s));
 155             }
 156         }
 157         SkASSERT(fCount == oldCount);
 158     }
 159
 160     // Call fn on every entry in the table.  You may mutate the entries, but be very careful.
 161     template <typename Fn>  // f(T*)
 162     void foreach(Fn&& fn) {
 163         for (int i = 0; i < fCapacity; i++) {
 164             if (fSlots[i].has_value()) {
 165                 fn(&*fSlots[i]);
 166             }
 167         }
 168     }
 169
 170     // Call fn on every entry in the table.  You may not mutate anything.
 171     template <typename Fn>  // f(T) or f(const T&)
 172     void foreach(Fn&& fn) const {
 173         for (int i = 0; i < fCapacity; i++) {
 174             if (fSlots[i].has_value()) {
 175                 fn(*fSlots[i]);
 176             }
 177         }
 178     }
 179
 180     // A basic iterator-like class which disallows mutation; sufficient for range-based for loops.
 181     // Intended for use by SkTHashMap and SkTHashSet via begin() and end().
 182     // Adding or removing elements may invalidate all iterators.
 183     template <typename SlotVal>
 184     class Iter {
 185     public:
 186         using TTable = SkTHashTable<T, K, Traits>;
 187
 188         Iter(const TTable* table, int slot) : fTable(table), fSlot(slot) {}
 189
 190         static Iter MakeBegin(const TTable* table) {
 191             return Iter{table, table->firstPopulatedSlot()};
 192         }
 193
 194         static Iter MakeEnd(const TTable* table) {
 195             return Iter{table, table->capacity()};
 196         }
 197
 198         const SlotVal& operator*() const {
 199             return *fTable->slot(fSlot);
 200         }
 201
 202         const SlotVal* operator->() const {
 203             return fTable->slot(fSlot);
 204         }
 205
 206         bool operator==(const Iter& that) const {
 207             // Iterators from different tables shouldn't be compared against each other.
 208             SkASSERT(fTable == that.fTable);
 209             return fSlot == that.fSlot;
 210         }
 211
 212         bool operator!=(const Iter& that) const {
 213             return !(*this == that);
 214         }
 215
 216         Iter& operator++() {
 217             fSlot = fTable->nextPopulatedSlot(fSlot);
 218             return *this;
 219         }
 220
 221         Iter operator++(int) {
 222             Iter old = *this;
 223             this->operator++();
 224             return old;
 225         }
 226
 227     protected:
 228         const TTable* fTable;
 229         int fSlot;
 230     };
 231
 232 private:
 233     // Finds the first non-empty slot for an iterator.
 234     int firstPopulatedSlot() const {
 235         for (int i = 0; i < fCapacity; i++) {
 236             if (fSlots[i].has_value()) {
 237                 return i;
 238             }
 239         }
 240         return fCapacity;
 241     }
 242
 243     // Increments an iterator's slot.
 244     int nextPopulatedSlot(int currentSlot) const {
 245         for (int i = currentSlot + 1; i < fCapacity; i++) {
 246             if (fSlots[i].has_value()) {
 247                 return i;
 248             }
 249         }
 250         return fCapacity;
 251     }
 252
 253     // Reads from an iterator's slot.
 254     const T* slot(int i) const {
 255         SkASSERT(fSlots[i].has_value());
 256         return &*fSlots[i];
 257     }
 258
 259     T* uncheckedSet(T&& val) {
 260         const K& key = Traits::GetKey(val);
 261         SkASSERT(key == key);
 262         uint32_t hash = Hash(key);
 263         int index = hash & (fCapacity-1);
 264         for (int n = 0; n < fCapacity; n++) {
 265             Slot& s = fSlots[index];
 266             if (s.empty()) {
 267                 // New entry.
 268                 s.emplace(std::move(val), hash);
 269                 fCount++;
 270                 return &*s;
 271             }
 272             if (hash == s.hash && key == Traits::GetKey(*s)) {
 273                 // Overwrite previous entry.
 274                 // Note: this triggers extra copies when adding the same value repeatedly.
 275                 s.emplace(std::move(val), hash);
 276                 return &*s;
 277             }
 278
 279             index = this->next(index);
 280         }
 281         SkASSERT(false);
 282         return nullptr;
 283     }
 284
 285     void removeSlot(int index) {
 286         fCount--;
 287
 288         // Rearrange elements to restore the invariants for linear probing.
 289         for (;;) {
 290             Slot& emptySlot = fSlots[index];
 291             int emptyIndex = index;
 292             int originalIndex;
 293             // Look for an element that can be moved into the empty slot.
 294             // If the empty slot is in between where an element landed, and its native slot, then
 295             // move it to the empty slot. Don't move it if its native slot is in between where
 296             // the element landed and the empty slot.
 297             // [native] <= [empty] < [candidate] == GOOD, can move candidate to empty slot
 298             // [empty] < [native] < [candidate] == BAD, need to leave candidate where it is
 299             do {
 300                 index = this->next(index);
 301                 Slot& s = fSlots[index];
 302                 if (s.empty()) {
 303                     // We're done shuffling elements around.  Clear the last empty slot.
 304                     emptySlot.reset();
 305                     return;
 306                 }
 307                 originalIndex = s.hash & (fCapacity - 1);
 308             } while ((index <= originalIndex && originalIndex < emptyIndex)
 309                      || (originalIndex < emptyIndex && emptyIndex < index)
 310                      || (emptyIndex < index && index <= originalIndex));
 311             // Move the element to the empty slot.
 312             Slot& moveFrom = fSlots[index];
 313             emptySlot = std::move(moveFrom);
 314         }
 315     }
 316
 317     int next(int index) const {
 318         index--;
 319         if (index < 0) { index += fCapacity; }
 320         return index;
 321     }
 322
 323     static uint32_t Hash(const K& key) {
 324         uint32_t hash = Traits::Hash(key) & 0xffffffff;
 325         return hash ? hash : 1;  // We reserve hash 0 to mark empty.
 326     }
 327
 328     struct Slot {
 329         Slot() = default;
 330         ~Slot() { this->reset(); }
 331
 332         Slot(const Slot& that) { *this = that; }
 333         Slot& operator=(const Slot& that) {
 334             if (this == &that) {
 335                 return *this;
 336             }
 337             if (hash) {
 338                 if (that.hash) {
 339                     val.storage = that.val.storage;
 340                     hash = that.hash;
 341                 } else {
 342                     this->reset();
 343                 }
 344             } else {
 345                 if (that.hash) {
 346                     new (&val.storage) T(that.val.storage);
 347                     hash = that.hash;
 348                 } else {
 349                     // do nothing, no value on either side
 350                 }
 351             }
 352             return *this;
 353         }
 354
 355         Slot(Slot&& that) { *this = std::move(that); }
 356         Slot& operator=(Slot&& that) {
 357             if (this == &that) {
 358                 return *this;
 359             }
 360             if (hash) {
 361                 if (that.hash) {
 362                     val.storage = std::move(that.val.storage);
 363                     hash = that.hash;
 364                 } else {
 365                     this->reset();
 366                 }
 367             } else {
 368                 if (that.hash) {
 369                     new (&val.storage) T(std::move(that.val.storage));
 370                     hash = that.hash;
 371                 } else {
 372                     // do nothing, no value on either side
 373                 }
 374             }
 375             return *this;
 376         }
 377
 378         T& operator*() & { return val.storage; }
 379         const T& operator*() const& { return val.storage; }
 380         T&& operator*() && { return std::move(val.storage); }
 381         const T&& operator*() const&& { return std::move(val.storage); }
 382
 383         Slot& emplace(T&& v, uint32_t h) {
 384             this->reset();
 385             new (&val.storage) T(std::move(v));
 386             hash = h;
 387             return *this;
 388         }
 389
 390         bool has_value() const { return hash != 0; }
 391         explicit operator bool() const { return this->has_value(); }
 392         bool empty() const { return !this->has_value(); }
 393
 394         void reset() {
 395             if (hash) {
 396                 val.storage.~T();
 397                 hash = 0;
 398             }
 399         }
 400
 401         uint32_t hash = 0;
 402
 403     private:
 404         union Storage {
 405             T storage;
 406             Storage() {}
 407             ~Storage() {}
 408         } val;
 409     };
 410
 411     int fCount    = 0,
 412         fCapacity = 0;
 413     SkAutoTArray<Slot> fSlots;
 414 };
 415
 416 // Maps K->V.  A more user-friendly wrapper around SkTHashTable, suitable for most use cases.
 417 // K and V are treated as ordinary copyable C++ types, with no assumed relationship between the two.
 418 template <typename K, typename V, typename HashK = SkGoodHash>
 419 class SkTHashMap {
 420 public:
 421     // Allow default construction and assignment.
 422     SkTHashMap() = default;
 423
 424     SkTHashMap(SkTHashMap<K, V, HashK>&& that) = default;
 425     SkTHashMap(const SkTHashMap<K, V, HashK>& that) = default;
 426
 427     SkTHashMap<K, V, HashK>& operator=(SkTHashMap<K, V, HashK>&& that) = default;
 428     SkTHashMap<K, V, HashK>& operator=(const SkTHashMap<K, V, HashK>& that) = default;
 429
 430     // Construct with an initializer list of key-value pairs.
 431     struct Pair : public std::pair<K, V> {
 432         using std::pair<K, V>::pair;
 433         static const K& GetKey(const Pair& p) { return p.first; }
 434         static auto Hash(const K& key) { return HashK()(key); }
 435     };
 436
 437     SkTHashMap(std::initializer_list<Pair> pairs) {
 438         fTable.resize(pairs.size() * 5 / 3);
 439         for (const Pair& p : pairs) {
 440             fTable.set(p);
 441         }
 442     }
 443
 444     // Clear the map.
 445     void reset() { fTable.reset(); }
 446
 447     // How many key/value pairs are in the table?
 448     int count() const { return fTable.count(); }
 449
 450     // Is empty?
 451     bool empty() const { return fTable.count() == 0; }
 452
 453     // Approximately how many bytes of memory do we use beyond sizeof(*this)?
 454     size_t approxBytesUsed() const { return fTable.approxBytesUsed(); }
 455
 456     // N.B. The pointers returned by set() and find() are valid only until the next call to set().
 457
 458     // Set key to val in the table, replacing any previous value with the same key.
 459     // We copy both key and val, and return a pointer to the value copy now in the table.
 460     V* set(K key, V val) {
 461         Pair* out = fTable.set({std::move(key), std::move(val)});
 462         return &out->second;
 463     }
 464
 465     // If there is key/value entry in the table with this key, return a pointer to the value.
 466     // If not, return null.
 467     V* find(const K& key) const {
 468         if (Pair* p = fTable.find(key)) {
 469             return &p->second;
 470         }
 471         return nullptr;
 472     }
 473
 474     V& operator[](const K& key) {
 475         if (V* val = this->find(key)) {
 476             return *val;
 477         }
 478         return *this->set(key, V{});
 479     }
 480
 481     // Remove the key/value entry in the table with this key.
 482     void remove(const K& key) {
 483         SkASSERT(this->find(key));
 484         fTable.remove(key);
 485     }
 486
 487     // Call fn on every key/value pair in the table.  You may mutate the value but not the key.
 488     template <typename Fn>  // f(K, V*) or f(const K&, V*)
 489     void foreach(Fn&& fn) {
 490         fTable.foreach([&fn](Pair* p){ fn(p->first, &p->second); });
 491     }
 492
 493     // Call fn on every key/value pair in the table.  You may not mutate anything.
 494     template <typename Fn>  // f(K, V), f(const K&, V), f(K, const V&) or f(const K&, const V&).
 495     void foreach(Fn&& fn) const {
 496         fTable.foreach([&fn](const Pair& p){ fn(p.first, p.second); });
 497     }
 498
 499     // Dereferencing an iterator gives back a key-value pair, suitable for structured binding.
 500     using Iter = typename SkTHashTable<Pair, K>::template Iter<std::pair<K, V>>;
 501
 502     Iter begin() const {
 503         return Iter::MakeBegin(&fTable);
 504     }
 505
 506     Iter end() const {
 507         return Iter::MakeEnd(&fTable);
 508     }
 509
 510 private:
 511     SkTHashTable<Pair, K> fTable;
 512 };
 513
 514 // A set of T.  T is treated as an ordinary copyable C++ type.
 515 template <typename T, typename HashT = SkGoodHash>
 516 class SkTHashSet {
 517 public:
 518     // Allow default construction and assignment.
 519     SkTHashSet() = default;
 520
 521     SkTHashSet(SkTHashSet<T, HashT>&& that) = default;
 522     SkTHashSet(const SkTHashSet<T, HashT>& that) = default;
 523
 524     SkTHashSet<T, HashT>& operator=(SkTHashSet<T, HashT>&& that) = default;
 525     SkTHashSet<T, HashT>& operator=(const SkTHashSet<T, HashT>& that) = default;
 526
 527     // Construct with an initializer list of Ts.
 528     SkTHashSet(std::initializer_list<T> vals) {
 529         fTable.resize(vals.size() * 5 / 3);
 530         for (const T& val : vals) {
 531             fTable.set(val);
 532         }
 533     }
 534
 535     // Clear the set.
 536     void reset() { fTable.reset(); }
 537
 538     // How many items are in the set?
 539     int count() const { return fTable.count(); }
 540
 541     // Is empty?
 542     bool empty() const { return fTable.count() == 0; }
 543
 544     // Approximately how many bytes of memory do we use beyond sizeof(*this)?
 545     size_t approxBytesUsed() const { return fTable.approxBytesUsed(); }
 546
 547     // Copy an item into the set.
 548     void add(T item) { fTable.set(std::move(item)); }
 549
 550     // Is this item in the set?
 551     bool contains(const T& item) const { return SkToBool(this->find(item)); }
 552
 553     // If an item equal to this is in the set, return a pointer to it, otherwise null.
 554     // This pointer remains valid until the next call to add().
 555     const T* find(const T& item) const { return fTable.find(item); }
 556
 557     // Remove the item in the set equal to this.
 558     void remove(const T& item) {
 559         SkASSERT(this->contains(item));
 560         fTable.remove(item);
 561     }
 562
 563     // Call fn on every item in the set.  You may not mutate anything.
 564     template <typename Fn>  // f(T), f(const T&)
 565     void foreach (Fn&& fn) const {
 566         fTable.foreach(fn);
 567     }
 568
 569 private:
 570     struct Traits {
 571         static const T& GetKey(const T& item) { return item; }
 572         static auto Hash(const T& item) { return HashT()(item); }
 573     };
 574
 575 public:
 576     using Iter = typename SkTHashTable<T, T, Traits>::template Iter<T>;
 577
 578     Iter begin() const {
 579         return Iter::MakeBegin(&fTable);
 580     }
 581
 582     Iter end() const {
 583         return Iter::MakeEnd(&fTable);
 584     }
 585
 586 private:
 587     SkTHashTable<T, T, Traits> fTable;
 588 };
 589
 590 #endif//SkTHash_DEFINED