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