diff options
Diffstat (limited to 'include/EASTL/internal/intrusive_hashtable.h')
| -rw-r--r-- | include/EASTL/internal/intrusive_hashtable.h | 989 |
1 files changed, 0 insertions, 989 deletions
diff --git a/include/EASTL/internal/intrusive_hashtable.h b/include/EASTL/internal/intrusive_hashtable.h deleted file mode 100644 index dccca5b..0000000 --- a/include/EASTL/internal/intrusive_hashtable.h +++ /dev/null @@ -1,989 +0,0 @@ -///////////////////////////////////////////////////////////////////////////// -// Copyright (c) Electronic Arts Inc. All rights reserved. -///////////////////////////////////////////////////////////////////////////// - -/////////////////////////////////////////////////////////////////////////////// -// This file implements an intrusive hash table, which is a hash table whereby -// the container nodes are the hash table objects themselves. This has benefits -// primarily in terms of memory management. There are some minor limitations -// that result from this. -// -/////////////////////////////////////////////////////////////////////////////// - - - -#ifndef EASTL_INTERNAL_INTRUSIVE_HASHTABLE_H -#define EASTL_INTERNAL_INTRUSIVE_HASHTABLE_H - - -#include <EABase/eabase.h> -#if defined(EA_PRAGMA_ONCE_SUPPORTED) - #pragma once -#endif - -#include <EASTL/internal/config.h> -#include <EASTL/internal/hashtable.h> -#include <EASTL/type_traits.h> -#include <EASTL/iterator.h> -#include <EASTL/functional.h> -#include <EASTL/utility.h> -#include <EASTL/algorithm.h> - -EA_DISABLE_ALL_VC_WARNINGS(); -#include <new> -#include <stddef.h> -#include <string.h> -EA_RESTORE_ALL_VC_WARNINGS(); - - -namespace eastl -{ - - /// intrusive_hash_node - /// - /// A hash_node stores an element in a hash table, much like a - /// linked list node stores an element in a linked list. - /// An intrusive_hash_node additionally can, via template parameter, - /// store a hash code in the node to speed up hash calculations - /// and comparisons in some cases. - /// - /// To consider: Make a version of intrusive_hash_node which is - /// templated on the container type. This would allow for the - /// mpNext pointer to be the container itself and thus allow - /// for easier debugging. - /// - /// Example usage: - /// struct Widget : public intrusive_hash_node{ ... }; - /// - /// struct Dagget : public intrusive_hash_node_key<int>{ ... }; - /// - struct intrusive_hash_node - { - intrusive_hash_node* mpNext; - }; - - - template <typename Key> - struct intrusive_hash_node_key : public intrusive_hash_node - { - typedef Key key_type; - Key mKey; - }; - - - - /// intrusive_node_iterator - /// - /// Node iterators iterate nodes within a given bucket. - /// - /// The bConst parameter defines if the iterator is a const_iterator - /// or an iterator. - /// - template <typename Value, bool bConst> - struct intrusive_node_iterator - { - public: - typedef intrusive_node_iterator<Value, bConst> this_type; - typedef Value value_type; - typedef Value node_type; - typedef ptrdiff_t difference_type; - typedef typename type_select<bConst, const Value*, Value*>::type pointer; - typedef typename type_select<bConst, const Value&, Value&>::type reference; - typedef EASTL_ITC_NS::forward_iterator_tag iterator_category; - - public: - node_type* mpNode; - - public: - intrusive_node_iterator() - : mpNode(NULL) { } - - explicit intrusive_node_iterator(value_type* pNode) - : mpNode(pNode) { } - - intrusive_node_iterator(const intrusive_node_iterator<Value, true>& x) - : mpNode(x.mpNode) { } - - reference operator*() const - { return *mpNode; } - - pointer operator->() const - { return mpNode; } - - this_type& operator++() - { mpNode = static_cast<node_type*>(mpNode->mpNext); return *this; } - - this_type operator++(int) - { this_type temp(*this); mpNode = static_cast<node_type*>(mpNode->mpNext); return temp; } - - }; // intrusive_node_iterator - - - - - /// intrusive_hashtable_iterator_base - /// - /// An intrusive_hashtable_iterator_base iterates the entire hash table and - /// not just nodes within a single bucket. Users in general will use a hash - /// table iterator much more often, as it is much like other container - /// iterators (e.g. vector::iterator). - /// - /// We define a base class here because it is shared by both const and - /// non-const iterators. - /// - template <typename Value> - struct intrusive_hashtable_iterator_base - { - public: - typedef Value value_type; - - protected: - template <typename, typename, typename, typename, size_t, bool, bool> - friend class intrusive_hashtable; - - template <typename, bool> - friend struct intrusive_hashtable_iterator; - - template <typename V> - friend bool operator==(const intrusive_hashtable_iterator_base<V>&, const intrusive_hashtable_iterator_base<V>&); - - template <typename V> - friend bool operator!=(const intrusive_hashtable_iterator_base<V>&, const intrusive_hashtable_iterator_base<V>&); - - value_type* mpNode; // Current node within current bucket. - value_type** mpBucket; // Current bucket. - - public: - intrusive_hashtable_iterator_base(value_type* pNode, value_type** pBucket) - : mpNode(pNode), mpBucket(pBucket) { } - - void increment_bucket() - { - ++mpBucket; - while(*mpBucket == NULL) // We store an extra bucket with some non-NULL value at the end - ++mpBucket; // of the bucket array so that finding the end of the bucket - mpNode = *mpBucket; // array is quick and simple. - } - - void increment() - { - mpNode = static_cast<value_type*>(mpNode->mpNext); - - while(mpNode == NULL) - mpNode = *++mpBucket; - } - - }; // intrusive_hashtable_iterator_base - - - - - /// intrusive_hashtable_iterator - /// - /// An intrusive_hashtable_iterator iterates the entire hash table and not - /// just nodes within a single bucket. Users in general will use a hash - /// table iterator much more often, as it is much like other container - /// iterators (e.g. vector::iterator). - /// - /// The bConst parameter defines if the iterator is a const_iterator - /// or an iterator. - /// - template <typename Value, bool bConst> - struct intrusive_hashtable_iterator : public intrusive_hashtable_iterator_base<Value> - { - public: - typedef intrusive_hashtable_iterator_base<Value> base_type; - typedef intrusive_hashtable_iterator<Value, bConst> this_type; - typedef intrusive_hashtable_iterator<Value, false> this_type_non_const; - typedef typename base_type::value_type value_type; - typedef typename type_select<bConst, const Value*, Value*>::type pointer; - typedef typename type_select<bConst, const Value&, Value&>::type reference; - typedef ptrdiff_t difference_type; - typedef EASTL_ITC_NS::forward_iterator_tag iterator_category; - - public: - intrusive_hashtable_iterator() - : base_type(NULL, NULL) { } - - explicit intrusive_hashtable_iterator(value_type* pNode, value_type** pBucket) - : base_type(pNode, pBucket) { } - - explicit intrusive_hashtable_iterator(value_type** pBucket) - : base_type(*pBucket, pBucket) { } - - intrusive_hashtable_iterator(const this_type_non_const& x) - : base_type(x.mpNode, x.mpBucket) { } - - reference operator*() const - { return *base_type::mpNode; } - - pointer operator->() const - { return base_type::mpNode; } - - this_type& operator++() - { base_type::increment(); return *this; } - - this_type operator++(int) - { this_type temp(*this); base_type::increment(); return temp; } - - }; // intrusive_hashtable_iterator - - - - /// use_intrusive_key - /// - /// operator()(x) returns x.mKey. Used in maps, as opposed to sets. - /// This is a template policy implementation; it is an alternative to - /// the use_self template implementation, which is used for sets. - /// - template <typename Node, typename Key> - struct use_intrusive_key // : public unary_function<T, T> // Perhaps we want to make it a subclass of unary_function. - { - typedef Key result_type; - - const result_type& operator()(const Node& x) const - { return x.mKey; } - }; - - - - /////////////////////////////////////////////////////////////////////////// - /// intrusive_hashtable - /// - template <typename Key, typename Value, typename Hash, typename Equal, - size_t bucketCount, bool bConstIterators, bool bUniqueKeys> - class intrusive_hashtable - { - public: - typedef intrusive_hashtable<Key, Value, Hash, Equal, - bucketCount, bConstIterators, bUniqueKeys> this_type; - typedef Key key_type; - typedef Value value_type; - typedef Value mapped_type; - typedef Value node_type; - typedef uint32_t hash_code_t; - typedef Equal key_equal; - typedef ptrdiff_t difference_type; - typedef eastl_size_t size_type; // See config.h for the definition of eastl_size_t, which defaults to size_t. - typedef value_type& reference; - typedef const value_type& const_reference; - typedef intrusive_node_iterator<value_type, bConstIterators> local_iterator; - typedef intrusive_node_iterator<value_type, true> const_local_iterator; - typedef intrusive_hashtable_iterator<value_type, bConstIterators> iterator; - typedef intrusive_hashtable_iterator<value_type, true> const_iterator; - typedef typename type_select<bUniqueKeys, pair<iterator, bool>, iterator>::type insert_return_type; - typedef typename type_select<bConstIterators, eastl::use_self<Value>, - eastl::use_intrusive_key<Value, key_type> >::type extract_key; - - enum - { - kBucketCount = bucketCount - }; - - protected: - node_type* mBucketArray[kBucketCount + 1]; // '+1' because we have an end bucket which is non-NULL so iterators always stop on it. - size_type mnElementCount; - Hash mHash; // To do: Use base class optimization to make this go away when it is of zero size. - Equal mEqual; // To do: Use base class optimization to make this go away when it is of zero size. - - public: - intrusive_hashtable(const Hash&, const Equal&); - - void swap(this_type& x); - - iterator begin() EA_NOEXCEPT - { - iterator i(mBucketArray); - if(!i.mpNode) - i.increment_bucket(); - return i; - } - - const_iterator begin() const EA_NOEXCEPT - { - const_iterator i(const_cast<node_type**>(mBucketArray)); - if(!i.mpNode) - i.increment_bucket(); - return i; - } - - const_iterator cbegin() const EA_NOEXCEPT - { - return begin(); - } - - iterator end() EA_NOEXCEPT - { return iterator(mBucketArray + kBucketCount); } - - const_iterator end() const EA_NOEXCEPT - { return const_iterator(const_cast<node_type**>(mBucketArray) + kBucketCount); } - - const_iterator cend() const EA_NOEXCEPT - { return const_iterator(const_cast<node_type**>(mBucketArray) + kBucketCount); } - - local_iterator begin(size_type n) EA_NOEXCEPT - { return local_iterator(mBucketArray[n]); } - - const_local_iterator begin(size_type n) const EA_NOEXCEPT - { return const_local_iterator(mBucketArray[n]); } - - const_local_iterator cbegin(size_type n) const EA_NOEXCEPT - { return const_local_iterator(mBucketArray[n]); } - - local_iterator end(size_type) EA_NOEXCEPT - { return local_iterator(NULL); } - - const_local_iterator end(size_type) const EA_NOEXCEPT - { return const_local_iterator(NULL); } - - const_local_iterator cend(size_type) const EA_NOEXCEPT - { return const_local_iterator(NULL); } - - size_type size() const EA_NOEXCEPT - { return mnElementCount; } - - bool empty() const EA_NOEXCEPT - { return mnElementCount == 0; } - - size_type bucket_count() const EA_NOEXCEPT // This function is unnecessary, as the user can directly reference - { return kBucketCount; } // intrusive_hashtable::kBucketCount as a constant. - - size_type bucket_size(size_type n) const EA_NOEXCEPT - { return (size_type)eastl::distance(begin(n), end(n)); } - - size_type bucket(const key_type& k) const EA_NOEXCEPT - { return (size_type)(mHash(k) % kBucketCount); } - - public: - float load_factor() const EA_NOEXCEPT - { return (float)mnElementCount / (float)kBucketCount; } - - public: - insert_return_type insert(value_type& value) - { return DoInsertValue(value, integral_constant<bool, bUniqueKeys>()); } - - insert_return_type insert(const_iterator, value_type& value) - { return insert(value); } // To consider: We might be able to use the iterator argument to specify a specific insertion location. - - template <typename InputIterator> - void insert(InputIterator first, InputIterator last); - - public: - iterator erase(const_iterator position); - iterator erase(const_iterator first, const_iterator last); - size_type erase(const key_type& k); - iterator remove(value_type& value); // Removes by value instead of by iterator. This is an O(1) operation, due to this hashtable being 'intrusive'. - - void clear(); - - public: - iterator find(const key_type& k); - const_iterator find(const key_type& k) const; - - /// Implements a find whereby the user supplies a comparison of a different type - /// than the hashtable value_type. A useful case of this is one whereby you have - /// a container of string objects but want to do searches via passing in char pointers. - /// The problem is that without this kind of find, you need to do the expensive operation - /// of converting the char pointer to a string so it can be used as the argument to the - /// find function. - /// - /// Example usage: - /// hash_set<string> hashSet; - /// hashSet.find_as("hello"); // Use default hash and compare. - /// - /// Example usage (namespaces omitted for brevity): - /// hash_set<string> hashSet; - /// hashSet.find_as("hello", hash<char*>(), equal_to_2<string, char*>()); - /// - template <typename U, typename UHash, typename BinaryPredicate> - iterator find_as(const U& u, UHash uhash, BinaryPredicate predicate); - - template <typename U, typename UHash, typename BinaryPredicate> - const_iterator find_as(const U& u, UHash uhash, BinaryPredicate predicate) const; - - template <typename U> - iterator find_as(const U& u); - - template <typename U> - const_iterator find_as(const U& u) const; - - size_type count(const key_type& k) const; - - // The use for equal_range in a hash_table seems somewhat questionable. - // The primary reason for its existence is to replicate the interface of set/map. - eastl::pair<iterator, iterator> equal_range(const key_type& k); - eastl::pair<const_iterator, const_iterator> equal_range(const key_type& k) const; - - public: - bool validate() const; - int validate_iterator(const_iterator i) const; - - public: - Hash hash_function() const - { return mHash; } - - Equal equal_function() const // Deprecated. Use key_eq() instead, as key_eq is what the new C++ standard - { return mEqual; } // has specified in its hashtable (unordered_*) proposal. - - const key_equal& key_eq() const - { return mEqual; } - - key_equal& key_eq() - { return mEqual; } - - protected: - eastl::pair<iterator, bool> DoInsertValue(value_type&, true_type); // true_type means bUniqueKeys is true. - iterator DoInsertValue(value_type&, false_type); // false_type means bUniqueKeys is false. - - node_type* DoFindNode(node_type* pNode, const key_type& k) const; - - template <typename U, typename BinaryPredicate> - node_type* DoFindNode(node_type* pNode, const U& u, BinaryPredicate predicate) const; - - }; // class intrusive_hashtable - - - - - - /////////////////////////////////////////////////////////////////////// - // node_iterator_base - /////////////////////////////////////////////////////////////////////// - - template <typename Value, bool bConst> - inline bool operator==(const intrusive_node_iterator<Value, bConst>& a, - const intrusive_node_iterator<Value, bConst>& b) - { return a.mpNode == b.mpNode; } - - template <typename Value, bool bConst> - inline bool operator!=(const intrusive_node_iterator<Value, bConst>& a, - const intrusive_node_iterator<Value, bConst>& b) - { return a.mpNode != b.mpNode; } - - - - - /////////////////////////////////////////////////////////////////////// - // hashtable_iterator_base - /////////////////////////////////////////////////////////////////////// - - template <typename Value> - inline bool operator==(const intrusive_hashtable_iterator_base<Value>& a, - const intrusive_hashtable_iterator_base<Value>& b) - { return a.mpNode == b.mpNode; } - - - template <typename Value> - inline bool operator!=(const intrusive_hashtable_iterator_base<Value>& a, - const intrusive_hashtable_iterator_base<Value>& b) - { return a.mpNode != b.mpNode; } - - - - - /////////////////////////////////////////////////////////////////////// - // intrusive_hashtable - /////////////////////////////////////////////////////////////////////// - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::intrusive_hashtable(const H& h, const Eq& eq) - : mnElementCount(0), - mHash(h), - mEqual(eq) - { - memset(mBucketArray, 0, kBucketCount * sizeof(mBucketArray[0])); - mBucketArray[kBucketCount] = reinterpret_cast<node_type*>((uintptr_t)~0); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - void intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::swap(this_type& x) - { - for(size_t i = 0; i < kBucketCount; i++) - eastl::swap(mBucketArray[i], x.mBucketArray[i]); - - eastl::swap(mnElementCount, x.mnElementCount); - eastl::swap(mHash, x.mHash); - eastl::swap(mEqual, x.mEqual); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::iterator - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::find(const key_type& k) - { - const size_type n = (size_type)(mHash(k) % kBucketCount); - node_type* const pNode = DoFindNode(mBucketArray[n], k); - return pNode ? iterator(pNode, mBucketArray + n) : iterator(mBucketArray + kBucketCount); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::const_iterator - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::find(const key_type& k) const - { - const size_type n = (size_type)(mHash(k) % kBucketCount); - node_type* const pNode = DoFindNode(mBucketArray[n], k); - return pNode ? const_iterator(pNode, const_cast<node_type**>(mBucketArray) + n) : const_iterator(const_cast<node_type**>(mBucketArray) + kBucketCount); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - template <typename U, typename UHash, typename BinaryPredicate> - inline typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::iterator - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::find_as(const U& other, UHash uhash, BinaryPredicate predicate) - { - const size_type n = (size_type)(uhash(other) % kBucketCount); - node_type* const pNode = DoFindNode(mBucketArray[n], other, predicate); - return pNode ? iterator(pNode, mBucketArray + n) : iterator(mBucketArray + kBucketCount); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - template <typename U, typename UHash, typename BinaryPredicate> - inline typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::const_iterator - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::find_as(const U& other, UHash uhash, BinaryPredicate predicate) const - { - const size_type n = (size_type)(uhash(other) % kBucketCount); - node_type* const pNode = DoFindNode(mBucketArray[n], other, predicate); - return pNode ? const_iterator(pNode, const_cast<node_type**>(mBucketArray) + n) : const_iterator(const_cast<node_type**>(mBucketArray) + kBucketCount); - } - - - /// intrusive_hashtable_find - /// - /// Helper function that defaults to using hash<U> and equal_to_2<T, U>. - /// This makes it so that by default you don't need to provide these. - /// Note that the default hash functions may not be what you want, though. - /// - /// Example usage. Instead of this: - /// hash_set<string> hashSet; - /// hashSet.find("hello", hash<char*>(), equal_to_2<string, char*>()); - /// - /// You can use this: - /// hash_set<string> hashSet; - /// hashtable_find(hashSet, "hello"); - /// - template <typename H, typename U> - inline typename H::iterator intrusive_hashtable_find(H& hashTable, const U& u) - { return hashTable.find_as(u, eastl::hash<U>(), eastl::equal_to_2<const typename H::key_type, U>()); } - - template <typename H, typename U> - inline typename H::const_iterator intrusive_hashtable_find(const H& hashTable, const U& u) - { return hashTable.find_as(u, eastl::hash<U>(), eastl::equal_to_2<const typename H::key_type, U>()); } - - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - template <typename U> - inline typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::iterator - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::find_as(const U& other) - { return eastl::intrusive_hashtable_find(*this, other); } - // VC++ doesn't appear to like the following, though it seems correct to me. - // So we implement the workaround above until we can straighten this out. - //{ return find_as(other, eastl::hash<U>(), eastl::equal_to_2<const key_type, U>()); } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - template <typename U> - inline typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::const_iterator - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::find_as(const U& other) const - { return eastl::intrusive_hashtable_find(*this, other); } - // VC++ doesn't appear to like the following, though it seems correct to me. - // So we implement the workaround above until we can straighten this out. - //{ return find_as(other, eastl::hash<U>(), eastl::equal_to_2<const key_type, U>()); } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::size_type - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::count(const key_type& k) const - { - const size_type n = (size_type)(mHash(k) % kBucketCount); - size_type result = 0; - extract_key extractKey; // extract_key is empty and thus this ctor is a no-op. - - // To do: Make a specialization for bU (unique keys) == true and take - // advantage of the fact that the count will always be zero or one in that case. - for(node_type* pNode = mBucketArray[n]; pNode; pNode = static_cast<node_type*>(pNode->mpNext)) - { - if(mEqual(k, extractKey(*pNode))) - ++result; - } - return result; - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - eastl::pair<typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::iterator, - typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::iterator> - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::equal_range(const key_type& k) - { - const size_type n = (size_type)(mHash(k) % kBucketCount); - node_type** head = mBucketArray + n; - node_type* pNode = DoFindNode(*head, k); - extract_key extractKey; // extract_key is empty and thus this ctor is a no-op. - - if(pNode) - { - node_type* p1 = static_cast<node_type*>(pNode->mpNext); - - for(; p1; p1 = static_cast<node_type*>(p1->mpNext)) - { - if(!mEqual(k, extractKey(*p1))) - break; - } - - iterator first(pNode, head); - iterator last(p1, head); - - if(!p1) - last.increment_bucket(); - - return eastl::pair<iterator, iterator>(first, last); - } - - return eastl::pair<iterator, iterator>(iterator(mBucketArray + kBucketCount), - iterator(mBucketArray + kBucketCount)); - } - - - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - eastl::pair<typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::const_iterator, - typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::const_iterator> - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::equal_range(const key_type& k) const - { - const size_type n = (size_type)(mHash(k) % kBucketCount); - node_type** head = const_cast<node_type**>(mBucketArray + n); - node_type* pNode = DoFindNode(*head, k); - extract_key extractKey; // extract_key is empty and thus this ctor is a no-op. - - if(pNode) - { - node_type* p1 = static_cast<node_type*>(pNode->mpNext); - - for(; p1; p1 = static_cast<node_type*>(p1->mpNext)) - { - if(!mEqual(k, extractKey(*p1))) - break; - } - - const_iterator first(pNode, head); - const_iterator last(p1, head); - - if(!p1) - last.increment_bucket(); - - return eastl::pair<const_iterator, const_iterator>(first, last); - } - - return eastl::pair<const_iterator, const_iterator>(const_iterator(const_cast<node_type**>(mBucketArray) + kBucketCount), - const_iterator(const_cast<node_type**>(mBucketArray) + kBucketCount)); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::node_type* - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::DoFindNode(node_type* pNode, const key_type& k) const - { - extract_key extractKey; // extract_key is empty and thus this ctor is a no-op. - - for(; pNode; pNode = static_cast<node_type*>(pNode->mpNext)) - { - if(mEqual(k, extractKey(*pNode))) - return pNode; - } - return NULL; - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - template <typename U, typename BinaryPredicate> - inline typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::node_type* - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::DoFindNode(node_type* pNode, const U& other, BinaryPredicate predicate) const - { - extract_key extractKey; // extract_key is empty and thus this ctor is a no-op. - - for(; pNode; pNode = static_cast<node_type*>(pNode->mpNext)) - { - if(predicate(extractKey(*pNode), other)) // Intentionally compare with key as first arg and other as second arg. - return pNode; - } - return NULL; - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - eastl::pair<typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::iterator, bool> - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::DoInsertValue(value_type& value, true_type) // true_type means bUniqueKeys is true. - { - // For sets (as opposed to maps), one could argue that all insertions are successful, - // as all elements are unique. However, the equal function might not think so. - extract_key extractKey; // extract_key is empty and thus this ctor is a no-op. - const size_type n = (size_type)(mHash(extractKey(value)) % kBucketCount); - node_type* const pNode = DoFindNode(mBucketArray[n], extractKey(value)); - - if(pNode == NULL) - { - value.mpNext = mBucketArray[n]; - mBucketArray[n] = &value; - ++mnElementCount; - - return eastl::pair<iterator, bool>(iterator(&value, mBucketArray + n), true); - } - - return eastl::pair<iterator, bool>(iterator(pNode, mBucketArray + n), false); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::iterator - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::DoInsertValue(value_type& value, false_type) // false_type means bUniqueKeys is false. - { - extract_key extractKey; // extract_key is empty and thus this ctor is a no-op. - const size_type n = (size_type)(mHash(extractKey(value)) % kBucketCount); - node_type* const pNodePrev = DoFindNode(mBucketArray[n], extractKey(value)); - - if(pNodePrev == NULL) - { - value.mpNext = mBucketArray[n]; - mBucketArray[n] = &value; - } - else - { - value.mpNext = pNodePrev->mpNext; - pNodePrev->mpNext = &value; - } - - ++mnElementCount; - - return iterator(&value, mBucketArray + n); - } - - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - template <typename InputIterator> - inline void intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::insert(InputIterator first, InputIterator last) - { - for(; first != last; ++first) - insert(*first); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::iterator - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::erase(const_iterator i) - { - iterator iNext(i.mpNode, i.mpBucket); - ++iNext; - - node_type* pNode = i.mpNode; - node_type* pNodeCurrent = *i.mpBucket; - - if(pNodeCurrent == pNode) - *i.mpBucket = static_cast<node_type*>(pNodeCurrent->mpNext); - else - { - // We have a singly-linked list, so we have no choice but to - // walk down it till we find the node before the node at 'i'. - node_type* pNodeNext = static_cast<node_type*>(pNodeCurrent->mpNext); - - while(pNodeNext != pNode) - { - pNodeCurrent = pNodeNext; - pNodeNext = static_cast<node_type*>(pNodeCurrent->mpNext); - } - - pNodeCurrent->mpNext = static_cast<node_type*>(pNodeNext->mpNext); - } - - // To consider: In debug builds set the node mpNext to NULL. - --mnElementCount; - - return iNext; - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::iterator - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::erase(const_iterator first, const_iterator last) - { - while(first != last) - first = erase(first); - return iterator(first.mpNode, first.mpBucket); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::size_type - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::erase(const key_type& k) - { - const size_type n = (size_type)(mHash(k) % kBucketCount); - const size_type nElementCountSaved = mnElementCount; - node_type*& pNodeBase = mBucketArray[n]; - extract_key extractKey; // extract_key is empty and thus this ctor is a no-op. - - // Note by Paul Pedriana: - // We have two loops here, and I'm not finding any easy way to having just one - // loop without changing the requirements of the hashtable node definition. - // It's a problem of taking an address of a variable and converting it to the - // address of another type without knowing what that type is. Perhaps I'm a - // little overly tired, so if there is a simple solution I am probably missing it. - - while(pNodeBase && mEqual(k, extractKey(*pNodeBase))) - { - pNodeBase = static_cast<node_type*>(pNodeBase->mpNext); - --mnElementCount; - } - - node_type* pNodePrev = pNodeBase; - - if(pNodePrev) - { - node_type* pNodeCur; - - while((pNodeCur = static_cast<node_type*>(pNodePrev->mpNext)) != NULL) - { - if(mEqual(k, extractKey(*pNodeCur))) - { - pNodePrev->mpNext = static_cast<node_type*>(pNodeCur->mpNext); - --mnElementCount; // To consider: In debug builds set the node mpNext to NULL. - } - else - pNodePrev = static_cast<node_type*>(pNodePrev->mpNext); - } - } - - return nElementCountSaved - mnElementCount; - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline typename intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::iterator - intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::remove(value_type& value) - { - extract_key extractKey; // extract_key is empty and thus this ctor is a no-op. - const size_type n = (size_type)(mHash(extractKey(value)) % kBucketCount); - - return erase(iterator(&value, &mBucketArray[n])); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline void intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::clear() - { - // To consider: In debug builds set the node mpNext to NULL. - memset(mBucketArray, 0, kBucketCount * sizeof(mBucketArray[0])); - mnElementCount = 0; - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline bool intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::validate() const - { - // Verify that the element count matches mnElementCount. - size_type nElementCount = 0; - - for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp) - ++nElementCount; - - if(nElementCount != mnElementCount) - return false; - - // To do: Verify that individual elements are in the expected buckets. - - return true; - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - int intrusive_hashtable<K, V, H, Eq, bC, bM, bU>::validate_iterator(const_iterator i) const - { - // To do: Come up with a more efficient mechanism of doing this. - - for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp) - { - if(temp == i) - return (isf_valid | isf_current | isf_can_dereference); - } - - if(i == end()) - return (isf_valid | isf_current); - - return isf_none; - } - - - - /////////////////////////////////////////////////////////////////////// - // global operators - /////////////////////////////////////////////////////////////////////// - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline bool operator==(const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& a, - const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& b) - { - return (a.size() == b.size()) && eastl::equal(a.begin(), a.end(), b.begin()); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline bool operator!=(const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& a, - const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& b) - { - return !(a == b); - } - - - // Comparing hash tables for less-ness is an odd thing to do. We provide it for - // completeness, though the user is advised to be wary of how they use this. - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline bool operator<(const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& a, - const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& b) - { - // This requires hash table elements to support operator<. Since the hash table - // doesn't compare elements via less (it does so via equals), we must use the - // globally defined operator less for the elements. - return eastl::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline bool operator>(const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& a, - const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& b) - { - return b < a; - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline bool operator<=(const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& a, - const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& b) - { - return !(b < a); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline bool operator>=(const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& a, - const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& b) - { - return !(a < b); - } - - - template <typename K, typename V, typename H, typename Eq, size_t bC, bool bM, bool bU> - inline void swap(const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& a, - const intrusive_hashtable<K, V, H, Eq, bC, bM, bU>& b) - { - a.swap(b); - } - - -} // namespace eastl - - - -#endif // Header include guard |