diff options
Diffstat (limited to 'thirdparty/thekla_atlas/nvcore/HashMap.h')
| -rw-r--r-- | thirdparty/thekla_atlas/nvcore/HashMap.h | 174 |
1 files changed, 0 insertions, 174 deletions
diff --git a/thirdparty/thekla_atlas/nvcore/HashMap.h b/thirdparty/thekla_atlas/nvcore/HashMap.h deleted file mode 100644 index 7856d6a8c9..0000000000 --- a/thirdparty/thekla_atlas/nvcore/HashMap.h +++ /dev/null @@ -1,174 +0,0 @@ -// This code is in the public domain -- Ignacio Castaņo <castano@gmail.com> - -#pragma once -#ifndef NV_CORE_HASHMAP_H -#define NV_CORE_HASHMAP_H - -/* -HashMap based on Thatcher Ulrich <tu@tulrich.com> container, donated to the Public Domain. - -I'd like to do something to reduce the amount of code generated with this template. The type of -U is largely irrelevant to the generated code, except for calls to constructors and destructors, -but the combination of all T and U pairs, generate a large amounts of code. - -HashMap is not used in NVTT, so it could be removed from the repository. -*/ - - -#include "Memory.h" -#include "Debug.h" -#include "ForEach.h" -#include "Hash.h" - -namespace nv -{ - class Stream; - - /** Thatcher Ulrich's hash table. - * - * Hash table, linear probing, internal chaining. One - * interesting/nice thing about this implementation is that the table - * itself is a flat chunk of memory containing no pointers, only - * relative indices. If the key and value types of the hash contain - * no pointers, then the hash can be serialized using raw IO. Could - * come in handy. - * - * Never shrinks, unless you explicitly clear() it. Expands on - * demand, though. For best results, if you know roughly how big your - * table will be, default it to that size when you create it. - */ - template<typename T, typename U, typename H = Hash<T>, typename E = Equal<T> > - class NVCORE_CLASS HashMap - { - NV_FORBID_COPY(HashMap); - public: - - /// Default ctor. - HashMap() : entry_count(0), size_mask(-1), table(NULL) { } - - /// Ctor with size hint. - explicit HashMap(int size_hint) : entry_count(0), size_mask(-1), table(NULL) { setCapacity(size_hint); } - - /// Dtor. - ~HashMap() { clear(); } - - - void set(const T& key, const U& value); - void add(const T& key, const U& value); - bool remove(const T& key); - void clear(); - bool isEmpty() const; - bool get(const T& key, U* value = NULL, T* other_key = NULL) const; - bool contains(const T & key) const; - int size() const; - int count() const; - int capacity() const; - void checkExpand(); - void resize(int n); - - void setCapacity(int new_size); - - // Behaves much like std::pair. - struct Entry - { - int next_in_chain; // internal chaining for collisions - uint hash_value; // avoids recomputing. Worthwhile? - T key; - U value; - - Entry() : next_in_chain(-2) {} - Entry(const Entry& e) : next_in_chain(e.next_in_chain), hash_value(e.hash_value), key(e.key), value(e.value) {} - Entry(const T& k, const U& v, int next, int hash) : next_in_chain(next), hash_value(hash), key(k), value(v) {} - - bool isEmpty() const { return next_in_chain == -2; } - bool isEndOfChain() const { return next_in_chain == -1; } - bool isTombstone() const { return hash_value == TOMBSTONE_HASH; } - - void clear() { - key.~T(); // placement delete - value.~U(); // placement delete - next_in_chain = -2; - hash_value = ~TOMBSTONE_HASH; - } - - void makeTombstone() { - key.~T(); - value.~U(); - hash_value = TOMBSTONE_HASH; - } - }; - - - // HashMap enumerator. - typedef int PseudoIndex; - PseudoIndex start() const { PseudoIndex i = 0; findNext(i); return i; } - bool isDone(const PseudoIndex & i) const { nvDebugCheck(i <= size_mask+1); return i == size_mask+1; }; - void advance(PseudoIndex & i) const { nvDebugCheck(i <= size_mask+1); i++; findNext(i); } - -#if NV_NEED_PSEUDOINDEX_WRAPPER - Entry & operator[]( const PseudoIndexWrapper & i ) { - Entry & e = entry(i(this)); - nvDebugCheck(e.isTombstone() == false); - return e; - } - const Entry & operator[]( const PseudoIndexWrapper & i ) const { - const Entry & e = entry(i(this)); - nvDebugCheck(e.isTombstone() == false); - return e; - } -#else - Entry & operator[](const PseudoIndex & i) { - Entry & e = entry(i); - nvDebugCheck(e.isTombstone() == false); - return e; - } - const Entry & operator[](const PseudoIndex & i) const { - const Entry & e = entry(i); - nvDebugCheck(e.isTombstone() == false); - return e; - } -#endif - - - // By default we serialize the key-value pairs compactl y. - template<typename _T, typename _U, typename _H, typename _E> - friend Stream & operator<< (Stream & s, HashMap<_T, _U, _H, _E> & map); - - // This requires more storage, but saves us from rehashing the elements. - template<typename _T, typename _U, typename _H, typename _E> - friend Stream & rawSerialize(Stream & s, HashMap<_T, _U, _H, _E> & map); - - /// Swap the members of this vector and the given vector. - template<typename _T, typename _U, typename _H, typename _E> - friend void swap(HashMap<_T, _U, _H, _E> & a, HashMap<_T, _U, _H, _E> & b); - - private: - static const uint TOMBSTONE_HASH = (uint) -1; - - uint compute_hash(const T& key) const; - - // Find the index of the matching entry. If no match, then return -1. - int findIndex(const T& key) const; - - // Return the index of the newly cleared element. - int removeTombstone(int index); - - // Helpers. - Entry & entry(int index); - const Entry & entry(int index) const; - - void setRawCapacity(int new_size); - - // Move the enumerator to the next valid element. - void findNext(PseudoIndex & i) const; - - - int entry_count; - int size_mask; - Entry * table; - - }; - -} // nv namespace - -#endif // NV_CORE_HASHMAP_H |