| 43 | */ |
| 44 | template<typename V, class Hash = std::hash<V>, class KeyEqual = std::equal_to<V>> |
| 45 | class Set { |
| 46 | |
| 47 | private: |
| 48 | |
| 49 | // -------------------- Constants -------------------- // |
| 50 | |
| 51 | /// Default load factor |
| 52 | static constexpr float DEFAULT_LOAD_FACTOR = 0.75; |
| 53 | |
| 54 | /// Invalid index in the array |
| 55 | static constexpr uint64 INVALID_INDEX = -1; |
| 56 | |
| 57 | // -------------------- Attributes -------------------- // |
| 58 | |
| 59 | /// Total number of allocated entries |
| 60 | uint64 mNbAllocatedEntries; |
| 61 | |
| 62 | /// Number of items in the set |
| 63 | uint64 mNbEntries; |
| 64 | |
| 65 | /// Number of buckets and size of the hash table (nbEntries = loadFactor * mHashSize) |
| 66 | uint64 mHashSize ; |
| 67 | |
| 68 | /// Array with all the buckets |
| 69 | uint64* mBuckets; |
| 70 | |
| 71 | /// Array with all the entries (nbEntries = loadFactor * mHashSize) |
| 72 | V* mEntries; |
| 73 | |
| 74 | /// For each entry, index of the next entry at the same bucket |
| 75 | uint64* mNextEntries; |
| 76 | |
| 77 | /// Memory allocator |
| 78 | MemoryAllocator& mAllocator; |
| 79 | |
| 80 | /// Index to the fist free entry |
| 81 | uint64 mFreeIndex; |
| 82 | |
| 83 | // -------------------- Methods -------------------- // |
| 84 | |
| 85 | /// Return the index of the entry with a given value or -1 if there is no entry with this value |
| 86 | uint64 findEntry(const V& value) const { |
| 87 | |
| 88 | if (mHashSize > 0) { |
| 89 | |
| 90 | const size_t hashCode = Hash()(value); |
| 91 | const size_t divider = mHashSize - 1; |
| 92 | const uint64 bucket = static_cast<uint64>(hashCode & divider); |
| 93 | auto keyEqual = KeyEqual(); |
| 94 | |
| 95 | for (uint64 i = mBuckets[bucket]; i != INVALID_INDEX; i = mNextEntries[i]) { |
| 96 | if (Hash()(mEntries[i]) == hashCode && keyEqual(mEntries[i], value)) { |
| 97 | return i; |
| 98 | } |
| 99 | } |
| 100 | } |
| 101 | |
| 102 | return INVALID_INDEX; |