#pragma once #include "Hash.hpp" #include "../iterator/MapIterator.hpp" #include "../accessor/Accessors.hpp" #include "../accessor/AccessorGroup_HashMap.hpp" #include "../../memory/PoolAllocator.hpp" #include "../../common/specialized.hpp" namespace sprawl { namespace collections { namespace detail { template< typename ValueType, typename mapped_type, size_t Idx, typename... AdditionalAccessors > class HashMap_Impl; template< typename ValueType, typename mapped_type, size_t Idx > class HashMap_Impl<ValueType, mapped_type, Idx> { public: typedef ValueType value_type; typedef MapIterator<ValueType, mapped_type> iterator; typedef MapIterator<ValueType, mapped_type> const const_iterator; typedef sprawl::memory::PoolAllocator<sizeof(mapped_type)> allocator; template<typename RequestedKeyType> inline void Get(RequestedKeyType const&, Specialized<Idx>) { RequestedKeyType::error_invalid_key_index_combination(); } template<typename RequestedKeyType> inline void GetOrInsert(RequestedKeyType const&, Specialized<Idx>) { RequestedKeyType::error_invalid_key_index_combination(); } template<typename RequestedKeyType> inline void find(RequestedKeyType const&, Specialized<Idx>) { RequestedKeyType::error_invalid_key_index_combination(); } template< typename RequestedKeyType> inline void find(RequestedKeyType const&, Specialized<Idx>) const { RequestedKeyType::error_invalid_key_index_combination(); } template<typename RequestedKeyType> inline void cfind(RequestedKeyType const&, Specialized<Idx>) const { RequestedKeyType::error_invalid_key_index_combination(); } template< typename RequestedKeyType> inline void Erase(RequestedKeyType const&, Specialized<Idx>) { RequestedKeyType::error_invalid_key_index_combination(); } inline iterator begin() { return iterator(m_first); } inline const_iterator begin() const { return cbegin(); } inline const_iterator cbegin() const { return const_iterator(m_first); } inline iterator end() { return iterator(nullptr); } inline const_iterator end() const { return cend(); } inline const_iterator cend() const { return const_iterator(nullptr); } template<typename RequestedKeyType> inline void Has(RequestedKeyType const&, Specialized<Idx>) { RequestedKeyType::error_invalid_key_index_combination(); } inline size_t Size() { return m_size; } inline size_t BucketCount() const { return m_bucketCount; } inline size_t BucketSize(int, Specialized<Idx>) const { return ValueType::error_invalid_index(); } inline bool Empty() { return m_size == 0; } void Clear() { mapped_type* ptr_next = nullptr; for (mapped_type* ptr = m_first; ptr != nullptr; ptr = ptr_next) { ptr_next = ptr->next; ptr->~mapped_type(); allocator::free(ptr); } m_first = nullptr; m_last = nullptr; m_size = 0; } void Rehash() { for (mapped_type* ptr = m_first; ptr != nullptr; ptr = ptr->next) { reinsert_(ptr); } } virtual ~HashMap_Impl() { Clear(); } protected: inline bool checkAndInsert_(mapped_type* newItem) { insert_(newItem); return true; } inline void reinsert_(mapped_type*) { // } inline void reserve_(size_t newBucketCount) { m_bucketCount = newBucketCount; } inline void nullout_(mapped_type*) { // } inline void insert_(mapped_type* newItem) { newItem->prev = m_last; if (m_last != nullptr) { m_last->next = newItem; } if (m_first == nullptr) { m_first = newItem; } m_last = newItem; ++m_size; } void erase_(mapped_type* item) { if(item == m_first) { m_first = item->next; } if(item == m_last) { m_last = item->prev; } if(item->prev) { item->prev->next = item->next; } if(item->next) { item->next->prev = item->prev; } --m_size; allocator::free(item); } HashMap_Impl(size_t startingBucketCount) : m_first(nullptr) , m_last(nullptr) , m_size(0) , m_bucketCount(startingBucketCount) { // } HashMap_Impl(HashMap_Impl const& other) : m_first(nullptr) , m_last(nullptr) , m_size(other.m_size) , m_bucketCount(other.m_bucketCount) { // } HashMap_Impl(HashMap_Impl&& other) : m_first(other.m_first) , m_last(other.m_last) , m_size(other.m_size) , m_bucketCount(other.m_bucketCount) { other.m_first = nullptr; other.m_last = nullptr; other.m_size = 0; } mapped_type* m_first; mapped_type* m_last; size_t m_size; size_t m_bucketCount; }; template< typename ValueType, typename mapped_type, size_t Idx, typename Accessor, typename... AdditionalAccessors > class HashMap_Impl<ValueType, mapped_type, Idx, Accessor, AdditionalAccessors...> : public HashMap_Impl< ValueType, mapped_type, Idx + 1, AdditionalAccessors... > { public: typedef HashMap_Impl<ValueType, mapped_type, Idx + 1, AdditionalAccessors...> Base; typedef ValueType value_type; typedef MapIterator<ValueType, mapped_type> iterator; typedef MapIterator<ValueType, mapped_type> const const_iterator; typedef sprawl::memory::PoolAllocator<sizeof(mapped_type)> allocator; using Base::Get; inline ValueType& Get(typename Accessor::key_type const& key, Specialized<Idx> = Specialized<Idx>()) { return get_(key)->Value(); } inline ValueType const& Get(typename Accessor::key_type const& key, Specialized<Idx> = Specialized<Idx>()) const { return get_(key)->Value(); } using Base::GetOrInsert; inline ValueType& GetOrInsert(typename Accessor::key_type const& key, ValueType const& defaultValue, Specialized<Idx> = Specialized<Idx>()) { auto it = find(key, spec); if(it.Valid()) { return it.Value(); } return this->Insert(key, defaultValue).Value(); } inline ValueType& GetOrInsert(typename Accessor::key_type const& key, ValueType&& defaultValue, Specialized<Idx> = Specialized<Idx>()) { auto it = find(key, spec); if(it.Valid()) { return it.Value(); } return this->Insert(key, std::move(defaultValue)).Value(); } inline ValueType& GetOrInsert(typename Accessor::key_type const& key, Specialized<Idx> = Specialized<Idx>()) { auto it = find(key, spec); if(it.Valid()) { return it.Value(); } return this->Insert(key, ValueType()).Value(); } inline ValueType const& GetOrInsert(typename Accessor::key_type const& key, ValueType const& defaultValue, Specialized<Idx> = Specialized<Idx>()) const { return const_cast<HashMap_Impl*>(this)->GetOrInsert(key, defaultValue, spec); } inline ValueType const& GetOrInsert(typename Accessor::key_type const& key, ValueType&& defaultValue, Specialized<Idx> = Specialized<Idx>()) const { return const_cast<HashMap_Impl*>(this)->GetOrInsert(key, std::move(defaultValue), spec); } inline ValueType const& GetOrInsert(typename Accessor::key_type const& key, Specialized<Idx> = Specialized<Idx>()) const { return const_cast<HashMap_Impl*>(this)->GetOrInsert(key, spec); } using Base::find; using Base::cfind; inline iterator find(typename Accessor::key_type const& key, Specialized<Idx> = Specialized<Idx>()) { mapped_type* ret = get_(key); return iterator(ret); } inline const_iterator find(typename Accessor::key_type const& key, Specialized<Idx> = Specialized<Idx>()) const { return cfind(key); } inline const_iterator cfind(typename Accessor::key_type const& key, Specialized<Idx> = Specialized<Idx>()) const { mapped_type* ret = const_cast<mapped_type*>(get_(key)); return const_iterator(ret); } using Base::Has; inline bool Has(typename Accessor::key_type const& key, Specialized<Idx> = Specialized<Idx>()) { return get_(key) != nullptr; } template<int index> inline int BucketSize(int i, Specialized<Idx> spec = Specialized<Idx>()) const { int ret = 0; mapped_type *item = m_thisKeyTable[i]; while(item) { ++ret; item = item->Next(spec); } return ret; } inline void Clear() { for (size_t i = 0; i < this->m_bucketCount; ++i) { m_thisKeyTable[i] = nullptr; } Base::Clear(); } template<typename... Params> inline iterator Insert(Params&&... keysAndValue) { mapped_type* newItem = (mapped_type*)allocator::alloc(); ::new((void*)newItem) mapped_type(std::forward<Params>(keysAndValue)...); if(this->m_size > (this->m_bucketCount*0.5)) { Reserve(this->m_bucketCount * 2 + 1); } if(!checkAndInsert_(newItem)) { newItem->~mapped_type(); allocator::free(newItem); return iterator(nullptr); } return iterator(newItem); } inline void Reserve(size_t newBucketCount) { reserve_(newBucketCount); for (mapped_type* ptr = this->m_first; ptr != nullptr; ptr = ptr->next) { nullout_(ptr); reinsert_(ptr); } } inline void Rehash() { rehash_(); Base::Rehash(); } using Base::Erase; inline void Erase(typename Accessor::key_type const& key, Specialized<Idx> = Specialized<Idx>()) { erase_(get_(key)); } virtual ~HashMap_Impl() { if(m_thisKeyTable) { allocator::free(m_thisKeyTable); } } protected: HashMap_Impl(size_t startingBucketCount) : Base(startingBucketCount) , m_thisKeyTable(nullptr) { // } HashMap_Impl(HashMap_Impl const& other) : Base(other) , m_thisKeyTable(nullptr) { // } HashMap_Impl(HashMap_Impl&& other) : Base(std::move(other)) , m_thisKeyTable(other.m_thisKeyTable) { other.m_thisKeyTable = nullptr; } void reserve_(size_t newBucketCount) { if(m_thisKeyTable) { allocator::free(m_thisKeyTable); } m_thisKeyTable = (mapped_type**)allocator::alloc(newBucketCount); for (size_t i = 0; i < newBucketCount; ++i) { m_thisKeyTable[i] = nullptr; } Base::reserve_(newBucketCount); } inline void nullout_(mapped_type* item) { item->SetNext(spec, nullptr); item->SetPrev(spec, nullptr); Base::nullout_(item); } inline void reinsert_(mapped_type* newItem) { insertHere_(newItem); Base::reinsert_(newItem); } inline void insert_(mapped_type* newItem) { insertHere_(newItem); Base::insert_(newItem); } bool checkAndInsert_(mapped_type* newItem) { typename Accessor::key_type const& key = newItem->Accessor(spec).Key(); size_t hash = hash_(key); newItem->SetHash(spec, hash); size_t index = hash % this->m_bucketCount; mapped_type* hashMatch = m_thisKeyTable[index]; while (hashMatch) { if(hashMatch->Accessor(spec).Key() == key) return hashMatch; hashMatch = hashMatch->Next(spec); } if(hashMatch) { return false; } if(!Base::checkAndInsert_(newItem)) { return false; } insertHere_(newItem, index); return true; } void erase_(mapped_type* item) { mapped_type* prev = item->Prev(spec); mapped_type* next = item->Next(spec); if(prev) { prev->SetNext(spec, next); } else { m_thisKeyTable[item->Idx(spec)] = next; } if (next) { next->SetPrev(spec, prev); } Base::erase_(item); } private: inline void insertHere_(mapped_type* newItem) { size_t idx = newItem->GetHash(spec) % this->m_bucketCount; insertHere_(newItem, idx); } inline void insertHere_(mapped_type* newItem, size_t idx) { mapped_type* next = m_thisKeyTable[idx]; newItem->SetNext(spec, next); if(next != nullptr) { next->SetPrev(spec, newItem); } m_thisKeyTable[idx] = newItem; newItem->SetIndex(spec, idx); } inline mapped_type* get_(typename Accessor::key_type const& key) { size_t hash = hash_(key); size_t idx = hash % this->m_bucketCount; mapped_type* hashMatch = m_thisKeyTable[idx]; while(hashMatch) { if(hashMatch->GetHash(spec) == hash && hashMatch->Accessor(spec).Key() == key) return hashMatch; hashMatch = hashMatch->Next(spec); } return nullptr; } inline mapped_type const* get_(typename Accessor::key_type const& key) const { size_t hash = hash_(key); size_t idx = hash % this->m_bucketCount; mapped_type* hashMatch = m_thisKeyTable[idx]; while(hashMatch) { if(hashMatch->GetHash(spec) == hash && hashMatch->Accessor(spec).Key() == key) return hashMatch; hashMatch = hashMatch->Next(spec); } return nullptr; } inline size_t hash_(typename Accessor::key_type const& val) const { return sprawl::Hash<typename Accessor::key_type>::Compute(val); } void rehash_() { for (size_t i = 0; i < this->m_bucketCount; ++i) { mapped_type* item = m_thisKeyTable[i]; while (item) { mapped_type* item_next = item->Next(spec); item->SetNext(spec, nullptr); item->SetPrev(spec, nullptr); item = item_next; } m_thisKeyTable[i] = nullptr; } } mapped_type** m_thisKeyTable; static Specialized<Idx> spec; }; template< typename ValueType, typename mapped_type, size_t Idx, typename Accessor, typename... AdditionalAccessors > /*static*/ Specialized<Idx> HashMap_Impl<ValueType, mapped_type, Idx, Accessor, AdditionalAccessors...>::spec; } template< typename ValueType, typename... Accessors > class HashMap : public detail::HashMap_Impl<ValueType, detail::MapAccessorGroup<ValueType, Accessors...>, 0, Accessors...> { public: typedef detail::HashMap_Impl<ValueType, detail::MapAccessorGroup<ValueType, Accessors...>, 0, Accessors...> Base; typedef detail::MapAccessorGroup<ValueType, Accessors...> mapped_type; using Base::Get; template<int i, typename T2> inline ValueType& Get(T2 const& key) { return Get(key, Specialized<i>()); } template<int i, typename T2> inline ValueType const& Get(T2 const& key) const { return Get(key, Specialized<i>()); } using Base::GetOrInsert; template<int i, typename T2> inline ValueType& GetOrInsert(T2 const& key, ValueType const& defaultValue) { return GetOrInsert(key, defaultValue, Specialized<i>()); } template<int i, typename T2> inline ValueType const& GetOrInsert(T2 const& key, ValueType const& defaultValue) const { return GetOrInsert(key, defaultValue, Specialized<i>()); } template<int i, typename T2> inline ValueType& GetOrInsert(T2 const& key, ValueType&& defaultValue) { return GetOrInsert(key, std::move(defaultValue), Specialized<i>()); } template<int i, typename T2> inline ValueType const& GetOrInsert(T2 const& key, ValueType&& defaultValue) const { return GetOrInsert(key, std::move(defaultValue), Specialized<i>()); } template<int i, typename T2> inline ValueType& GetOrInsert(T2 const& key) { return GetOrInsert(key, Specialized<i>()); } template<int i, typename T2> inline ValueType const& GetOrInsert(T2 const& key) const { return GetOrInsert(key, Specialized<i>()); } template<typename T2> inline ValueType& operator[](T2 const& key) { return GetOrInsert(key); } template<typename T2> inline ValueType const& operator[](T2 const& key) const { return GetOrInsert(key); } using Base::find; template<int i, typename T2> inline typename Base::iterator find(T2 const& val) { return find(val, Specialized<i>()); } template<int i, typename T2> inline typename Base::iterator find(T2 const& val) const { return find(val, Specialized<i>()); } using Base::cfind; template<int i, typename T2> inline typename Base::iterator cfind(T2 const& val) const { return cfind(val, Specialized<i>()); } using Base::Has; template<int i, typename T2> inline bool Has(T2 const& val) { return Has(val, Specialized<i>()); } using Base::Erase; template<int i, typename T2> inline void Erase(T2 const& val) { return Erase(val, Specialized<i>()); } HashMap(size_t startingBucketCount = 256) : Base(startingBucketCount) { Base::Reserve(startingBucketCount); } HashMap(HashMap const& other) : Base(other) { Base::Reserve(this->m_bucketCount); for (mapped_type* ptr = other.m_first; ptr; ptr = ptr->next) { mapped_type* newPtr = (mapped_type*)Base::allocator::alloc(); ::new((void*)newPtr) mapped_type(*ptr); Base::insert_(newPtr); } } HashMap(HashMap&& other) : Base(std::move(other)) { other.Reserve(other.m_bucketCount); } HashMap& operator=(HashMap const& other) { Base::Clear(); this->m_bucketCount = other.m_bucketCount; this->m_size = other.m_size; Base::Reserve(this->m_bucketCount); for (mapped_type* ptr = other.m_first; ptr; ptr = ptr->next) { mapped_type* newPtr = (mapped_type*)Base::allocator::alloc(); ::new((void*)newPtr) mapped_type(*ptr); Base::insert_(newPtr); } return *this; } }; } }
# | Change | User | Description | Committed | |
---|---|---|---|---|---|
#2 | 18645 | brandon_m_bare | Integrated latest version of libsprawl. | ||
#1 | 15089 | brandon_m_bare | First integration of sprawl. | ||
//guest/ShadauxCat/Sprawl/Mainline/collections/hashmap/HashMap_Variadic.hpp | |||||
#8 | 14222 | ShadauxCat |
Fixed debug compile error on Windows. Linux, Mac, and release Windows were all optimizing out the "spec" static value in BinaryTree, so they didn't mind the missing definition; debug Windows needed the definition there, so it's now been provided. Also made the HashMap spec value static as well. #review-14223 |
||
#7 | 14220 | ShadauxCat |
-Added binary tree implementation (red/black tree) with same multi-key interface as hashmap -Renamed AccessorGroup to MapAccessorGroup to make room for TreeAccessorGroup, which is a lot of duplicated code but had to meet some specific requirements that couldn't be easily fit into the existing AccessorGroup -Fixed HashMap::Clear() not resetting size to 0 -Fixed HashMap::Erase() neither decrementing size nor freeing memory -Changed HashMap to grow before insert instead of after (delaying needed growth until the next insert instead of growing when it detects the next insert will need it) -Fixed a style issue for private function HashMap_Impl::insertHere_() -Fully removed support for Visual Studio 2012 as I have neither the need nor the desire to continue supporting it. The doubled maintenance cost is too high. -Included array unit test that got missed before #review-14221 |
||
#6 | 14163 | ShadauxCat |
-Renamed HashMap functions to follow coding style. Only begin, end, find, and variants are left lowercase, in keeping with C++ algorithm and range-based for support. -Fixed some accounting issues with list and forwardlist; size wasn't properly being maintained. -Made a small pedantic change to ThreadManager to ensure that m_numThreadsSynced got reset to 0 before the NotifyAll() to eliminate the miniscule potential for deadlock it would cause if it happened after another thread had already woken up. #review-14164 |
||
#5 | 14161 | ShadauxCat |
-Added staged option for ThreadManager and corresponding unit test -Added operator[] and getOrInsert() in HashMap. getOrInsert() doesn't follow standard but it's consistent with the rest of the HashMap interface; I'll change them when I go back and redo that interface to fit the style. #review-14162 |
||
#4 | 14081 | ShadauxCat |
-Switching order of keys and values in HashMap::insert(). Keys now come first - a number of parameters equal to the number of keys. (Simple case is simply insert(key, value)) -Added move constructors to AccessorGroup so things can be inserted into the map via rvalue references -Fixed ForwardList's copy constructor copying things in reverse and added a unit test to make sure it doesn't happen again. #review-14079 |
||
#3 | 14066 | ShadauxCat |
-Improved iterating in hashmap - range-based for now gives the ability to access both key and value instead of just value -Slightly improved some of the template aliases -Mega-deprecated VC11 support. Probably doesn't compile anymore. Maintaining it is too much of a headache. #review-14067 |
||
#2 | 12508 | ShadauxCat |
-Added threading library. Currently only functional for Linux; Windows will fail to link. (I will fix this soon.) -Fixed missing move and copy constructors in List and ForwardList -Fixed broken move constructor in HashMap -Fixed missing const get() in HashMap -Fixed broken operator-> in ListIterator -Added sprawl::noncopyable -Added sketch headers for filesystem library -Made StringLiteral hashable, added special hashes for pointers and integers in murmur3 -Fixed compiler warning in async_network -Updated memory allocators to use new threading library for mutexes -Added accessibility to sprawl::StringLiteral to be able toa ccess its pointer and length and perform pointer comparisons #review-12504 |
||
#1 | 11496 | ShadauxCat | Initial checkin: Current states for csbuild and libSprawl |