/*
-Copyright (C) 2001-2006, William Joseph.
-All Rights Reserved.
+ Copyright (C) 2001-2006, William Joseph.
+ All Rights Reserved.
-This file is part of GtkRadiant.
+ This file is part of GtkRadiant.
-GtkRadiant is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2 of the License, or
-(at your option) any later version.
+ GtkRadiant is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
-GtkRadiant is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+ GtkRadiant is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
-You should have received a copy of the GNU General Public License
-along with GtkRadiant; if not, write to the Free Software
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
-*/
+ You should have received a copy of the GNU General Public License
+ along with GtkRadiant; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
-#if !defined(INCLUDED_CONTAINER_HASHTABLE_H)
+#if !defined( INCLUDED_CONTAINER_HASHTABLE_H )
#define INCLUDED_CONTAINER_HASHTABLE_H
+#include <unordered_map>
+
+template<typename Key, typename Value, typename Hasher, typename KeyEqual = std::equal_to<Key> >
+ using HashTable = std::unordered_map<Key, Value, Hasher, KeyEqual>;
+
+#if 0
#include <cstddef>
#include <algorithm>
#include <functional>
+#include <memory>
#include "debugging/debugging.h"
-
namespace HashTableDetail
{
- inline std::size_t next_power_of_two(std::size_t size)
- {
- std::size_t result = 1;
- while(result < size)
- {
- result <<= 1;
- }
- return result;
- }
-
- struct BucketNodeBase
- {
- BucketNodeBase* next;
- BucketNodeBase* prev;
- };
-
- inline void list_initialise(BucketNodeBase& self)
- {
- self.next = self.prev = &self;
- }
-
- inline void list_swap(BucketNodeBase& self, BucketNodeBase& other)
- {
- BucketNodeBase tmp(self);
- if(other.next == &other)
- {
- list_initialise(self);
- }
- else
- {
- self = other;
- self.next->prev = self.prev->next = &self;
- }
- if(tmp.next == &self)
- {
- list_initialise(other);
- }
- else
- {
- other = tmp;
- other.next->prev = other.prev->next = &other;
- }
- }
-
- inline void node_link(BucketNodeBase* node, BucketNodeBase* next)
- {
- node->next = next;
- node->prev = next->prev;
- next->prev = node;
- node->prev->next = node;
- }
- inline void node_unlink(BucketNodeBase* node)
- {
- node->prev->next = node->next;
- node->next->prev = node->prev;
- }
-
- template<typename Key, typename Value>
- struct KeyValue
- {
- const Key key;
- Value value;
-
- KeyValue(const Key& key_, const Value& value_)
- : key(key_), value(value_)
- {
- }
- };
-
- template<typename Key, typename Value, typename Hash>
- struct BucketNode : public BucketNodeBase
- {
- Hash m_hash;
- KeyValue<Key, Value> m_value;
-
- BucketNode(Hash hash, const Key& key, const Value& value)
- : m_hash(hash), m_value(key, value)
- {
- }
- BucketNode* getNext() const
- {
- return static_cast<BucketNode*>(next);
- }
- BucketNode* getPrev() const
- {
- return static_cast<BucketNode*>(prev);
- }
- };
-
- template<typename Key, typename Value, typename Hash>
- class BucketIterator
- {
- typedef BucketNode<Key, Value, Hash> Node;
- Node* m_node;
-
- void increment()
- {
- m_node = m_node->getNext();
- }
-
- public:
- typedef std::forward_iterator_tag iterator_category;
- typedef std::ptrdiff_t difference_type;
- typedef difference_type distance_type;
- typedef KeyValue<Key, Value> value_type;
- typedef value_type* pointer;
- typedef value_type& reference;
-
- BucketIterator(Node* node) : m_node(node)
- {
- }
-
- Node* node()
- {
- return m_node;
- }
-
- bool operator==(const BucketIterator& other) const
- {
- return m_node == other.m_node;
- }
- bool operator!=(const BucketIterator& other) const
- {
- return !operator==(other);
- }
- BucketIterator& operator++()
- {
- increment();
- return *this;
- }
- BucketIterator operator++(int)
- {
- BucketIterator tmp = *this;
- increment();
- return tmp;
- }
- value_type& operator*() const
- {
- return m_node->m_value;
- }
- value_type* operator->() const
- {
- return &(operator*());
- }
- };
+inline std::size_t next_power_of_two( std::size_t size ){
+ std::size_t result = 1;
+ while ( result < size )
+ {
+ result <<= 1;
+ }
+ return result;
+}
+
+struct BucketNodeBase
+{
+ BucketNodeBase* next;
+ BucketNodeBase* prev;
+};
+
+inline void list_initialise( BucketNodeBase& self ){
+ self.next = self.prev = &self;
+}
+
+inline void list_swap( BucketNodeBase& self, BucketNodeBase& other ){
+ BucketNodeBase tmp( self );
+ if ( other.next == &other ) {
+ list_initialise( self );
+ }
+ else
+ {
+ self = other;
+ self.next->prev = self.prev->next = &self;
+ }
+ if ( tmp.next == &self ) {
+ list_initialise( other );
+ }
+ else
+ {
+ other = tmp;
+ other.next->prev = other.prev->next = &other;
+ }
+}
+
+inline void node_link( BucketNodeBase* node, BucketNodeBase* next ){
+ node->next = next;
+ node->prev = next->prev;
+ next->prev = node;
+ node->prev->next = node;
+}
+inline void node_unlink( BucketNodeBase* node ){
+ node->prev->next = node->next;
+ node->next->prev = node->prev;
+}
+
+template<typename Key, typename Value>
+struct KeyValue
+{
+ const Key key;
+ Value value;
+
+ KeyValue( const Key& key_, const Value& value_ )
+ : key( key_ ), value( value_ ){
+ }
+};
+
+template<typename Key, typename Value, typename Hash>
+struct BucketNode : public BucketNodeBase
+{
+ Hash m_hash;
+ KeyValue<Key, Value> m_value;
+
+ BucketNode( Hash hash, const Key& key, const Value& value )
+ : m_hash( hash ), m_value( key, value ){
+ }
+ BucketNode* getNext() const {
+ return static_cast<BucketNode*>( next );
+ }
+ BucketNode* getPrev() const {
+ return static_cast<BucketNode*>( prev );
+ }
+};
+
+template<typename Key, typename Value, typename Hash>
+class BucketIterator
+{
+typedef BucketNode<Key, Value, Hash> Node;
+Node* m_node;
+
+void increment(){
+ m_node = m_node->getNext();
+}
+
+public:
+typedef std::forward_iterator_tag iterator_category;
+typedef std::ptrdiff_t difference_type;
+typedef difference_type distance_type;
+typedef KeyValue<Key, Value> value_type;
+typedef value_type* pointer;
+typedef value_type& reference;
+
+BucketIterator( Node* node ) : m_node( node ){
+}
+
+Node* node(){
+ return m_node;
+}
+
+bool operator==( const BucketIterator& other ) const {
+ return m_node == other.m_node;
+}
+bool operator!=( const BucketIterator& other ) const {
+ return !operator==( other );
+}
+BucketIterator& operator++(){
+ increment();
+ return *this;
+}
+BucketIterator operator++( int ){
+ BucketIterator tmp = *this;
+ increment();
+ return tmp;
+}
+value_type& operator*() const {
+ return m_node->m_value;
+}
+value_type* operator->() const {
+ return &( operator*() );
+}
+};
}
template<typename Key, typename Value, typename Hasher, typename KeyEqual = std::equal_to<Key> >
class HashTable : private KeyEqual, private Hasher
{
- typedef typename Hasher::hash_type hash_type;
- typedef HashTableDetail::KeyValue<Key, Value> KeyValue;
- typedef HashTableDetail::BucketNode<Key, Value, hash_type> BucketNode;
-
- inline BucketNode* node_create(hash_type hash, const Key& key, const Value& value)
- {
- return new BucketNode(hash, key, value);
- }
- inline void node_destroy(BucketNode* node)
- {
- delete node;
- }
-
- typedef BucketNode* Bucket;
-
- static Bucket* buckets_new(std::size_t count)
- {
- Bucket* buckets = new Bucket[count];
- std::uninitialized_fill(buckets, buckets + count, Bucket(0));
- return buckets;
- }
- static void buckets_delete(Bucket* buckets)
- {
- delete[] buckets;
- }
-
- std::size_t m_bucketCount;
- Bucket* m_buckets;
- std::size_t m_size;
- HashTableDetail::BucketNodeBase m_list;
-
- BucketNode* getFirst()
- {
- return static_cast<BucketNode*>(m_list.next);
- }
- BucketNode* getLast()
- {
- return static_cast<BucketNode*>(&m_list);
- }
+typedef typename Hasher::hash_type hash_type;
+typedef HashTableDetail::KeyValue<Key, Value> KeyValue;
+typedef HashTableDetail::BucketNode<Key, Value, hash_type> BucketNode;
+
+inline BucketNode* node_create( hash_type hash, const Key& key, const Value& value ){
+ return new BucketNode( hash, key, value );
+}
+inline void node_destroy( BucketNode* node ){
+ delete node;
+}
+
+typedef BucketNode* Bucket;
+
+static Bucket* buckets_new( std::size_t count ){
+ Bucket* buckets = new Bucket[count];
+ std::uninitialized_fill( buckets, buckets + count, Bucket( 0 ) );
+ return buckets;
+}
+static void buckets_delete( Bucket* buckets ){
+ delete[] buckets;
+}
+
+std::size_t m_bucketCount;
+Bucket* m_buckets;
+std::size_t m_size;
+HashTableDetail::BucketNodeBase m_list;
+
+BucketNode* getFirst(){
+ return static_cast<BucketNode*>( m_list.next );
+}
+BucketNode* getLast(){
+ return static_cast<BucketNode*>( &m_list );
+}
public:
- typedef KeyValue value_type;
- typedef HashTableDetail::BucketIterator<Key, Value, hash_type> iterator;
+typedef KeyValue value_type;
+typedef HashTableDetail::BucketIterator<Key, Value, hash_type> iterator;
private:
- void initialise()
- {
- list_initialise(m_list);
- }
- hash_type hashKey(const Key& key)
- {
- return Hasher::operator()(key);
- }
-
- std::size_t getBucketId(hash_type hash) const
- {
- return hash & (m_bucketCount - 1);
- }
- Bucket& getBucket(hash_type hash)
- {
- return m_buckets[getBucketId(hash)];
- }
- BucketNode* bucket_find(Bucket bucket, hash_type hash, const Key& key)
- {
- std::size_t bucketId = getBucketId(hash);
- for(iterator i(bucket); i != end(); ++i)
- {
- hash_type nodeHash = i.node()->m_hash;
-
- if(getBucketId(nodeHash) != bucketId)
- {
- return 0;
- }
-
- if(nodeHash == hash && KeyEqual::operator()((*i).key, key))
- {
- return i.node();
- }
- }
- return 0;
- }
- BucketNode* bucket_insert(Bucket& bucket, BucketNode* node)
- {
- // link node into list
- node_link(node, bucket_next(bucket));
- bucket = node;
- return node;
- }
- BucketNode* bucket_next(Bucket& bucket)
- {
- Bucket* end = m_buckets + m_bucketCount;
- for(Bucket* i = &bucket; i != end; ++i)
- {
- if(*i != 0)
- {
- return *i;
- }
- }
- return getLast();
- }
-
- void buckets_resize(std::size_t count)
- {
- BucketNode* first = getFirst();
- BucketNode* last = getLast();
-
- buckets_delete(m_buckets);
-
- m_bucketCount = count;
-
- m_buckets = buckets_new(m_bucketCount);
- initialise();
-
- for(BucketNode* i = first; i != last;)
- {
- BucketNode* node = i;
- i = i->getNext();
- bucket_insert(getBucket((*node).m_hash), node);
- }
- }
- void size_increment()
- {
- if(m_size == m_bucketCount)
- {
- buckets_resize(m_bucketCount == 0 ? 8 : m_bucketCount << 1);
- }
- ++m_size;
- }
- void size_decrement()
- {
- --m_size;
- }
-
- HashTable(const HashTable& other);
- HashTable& operator=(const HashTable& other);
+void initialise(){
+ list_initialise( m_list );
+}
+hash_type hashKey( const Key& key ){
+ return Hasher::operator()( key );
+}
+
+std::size_t getBucketId( hash_type hash ) const {
+ return hash & ( m_bucketCount - 1 );
+}
+Bucket& getBucket( hash_type hash ){
+ return m_buckets[getBucketId( hash )];
+}
+BucketNode* bucket_find( Bucket bucket, hash_type hash, const Key& key ){
+ std::size_t bucketId = getBucketId( hash );
+ for ( iterator i( bucket ); i != end(); ++i )
+ {
+ hash_type nodeHash = i.node()->m_hash;
+
+ if ( getBucketId( nodeHash ) != bucketId ) {
+ return 0;
+ }
+
+ if ( nodeHash == hash && KeyEqual::operator()( ( *i ).first, key ) ) {
+ return i.node();
+ }
+ }
+ return 0;
+}
+BucketNode* bucket_insert( Bucket& bucket, BucketNode* node ){
+ // link node into list
+ node_link( node, bucket_next( bucket ) );
+ bucket = node;
+ return node;
+}
+BucketNode* bucket_next( Bucket& bucket ){
+ Bucket* end = m_buckets + m_bucketCount;
+ for ( Bucket* i = &bucket; i != end; ++i )
+ {
+ if ( *i != 0 ) {
+ return *i;
+ }
+ }
+ return getLast();
+}
+
+void buckets_resize( std::size_t count ){
+ BucketNode* first = getFirst();
+ BucketNode* last = getLast();
+
+ buckets_delete( m_buckets );
+
+ m_bucketCount = count;
+
+ m_buckets = buckets_new( m_bucketCount );
+ initialise();
+
+ for ( BucketNode* i = first; i != last; )
+ {
+ BucketNode* node = i;
+ i = i->getNext();
+ bucket_insert( getBucket( ( *node ).m_hash ), node );
+ }
+}
+void size_increment(){
+ if ( m_size == m_bucketCount ) {
+ buckets_resize( m_bucketCount == 0 ? 8 : m_bucketCount << 1 );
+ }
+ ++m_size;
+}
+void size_decrement(){
+ --m_size;
+}
+
+HashTable( const HashTable& other );
+HashTable& operator=( const HashTable& other );
public:
- HashTable() : m_bucketCount(0), m_buckets(0), m_size(0)
- {
- initialise();
- }
- HashTable(std::size_t bucketCount) : m_bucketCount(HashTableDetail::next_power_of_two(bucketCount)), m_buckets(buckets_new(m_bucketCount)), m_size(0)
- {
- initialise();
- }
- ~HashTable()
- {
- for(BucketNode* i = getFirst(); i != getLast();)
- {
- BucketNode* node = i;
- i = i->getNext();
- node_destroy(node);
- }
- buckets_delete(m_buckets);
- }
-
- iterator begin()
- {
- return iterator(getFirst());
- }
- iterator end()
- {
- return iterator(getLast());
- }
-
- bool empty() const
- {
- return m_size == 0;
- }
- std::size_t size() const
- {
- return m_size;
- }
-
- /// \brief Returns an iterator pointing to the value associated with \p key if it is contained by the hash-table, else \c end().
- iterator find(const Key& key)
- {
- hash_type hash = hashKey(key);
- if(m_bucketCount != 0)
- {
- Bucket bucket = getBucket(hash);
- if(bucket != 0)
- {
- BucketNode* node = bucket_find(bucket, hash, key);
- if(node != 0)
- {
- return iterator(node);
- }
- }
- }
-
- return end();
- }
- /// \brief Adds \p value to the hash-table associated with \p key if it does not exist.
- iterator insert(const Key& key, const Value& value)
- {
- hash_type hash = hashKey(key);
- if(m_bucketCount != 0)
- {
- Bucket& bucket = getBucket(hash);
- if(bucket != 0)
- {
- BucketNode* node = bucket_find(bucket, hash, key);
- if(node != 0)
- {
- return iterator(node);
- }
- }
- }
-
- size_increment();
- return iterator(bucket_insert(getBucket(hash), node_create(hash, key, value)));
- }
-
- /// \brief Removes the value pointed to by \p i from the hash-table.
- ///
- /// \p i must be a deferenceable iterator into the hash-table.
- void erase(iterator i)
- {
- Bucket& bucket = getBucket(i.node()->m_hash);
- BucketNode* node = i.node();
-
- // if this was the last node in the bucket
- if(bucket == node)
- {
- bucket = (node->getNext() == getLast() || &getBucket(node->getNext()->m_hash) != &bucket) ? 0 : node->getNext();
- }
-
- node_unlink(node);
- ASSERT_MESSAGE(node != 0, "tried to erase a non-existent key/value");
- node_destroy(node);
-
- size_decrement();
- }
-
- /// \brief Returns the value identified by \p key if it is contained by the hash-table, else inserts and returns a new default-constructed value associated with \p key.
- Value& operator[](const Key& key)
- {
- hash_type hash = hashKey(key);
- if(m_bucketCount != 0)
- {
- Bucket& bucket = getBucket(hash);
- if(bucket != 0)
- {
- BucketNode* node = bucket_find(bucket, hash, key);
- if(node != 0)
- {
- return node->m_value.value;
- }
- }
- }
- size_increment();
- return bucket_insert(getBucket(hash), node_create(hash, key, Value()))->m_value.value;
- }
- /// \brief Removes the value associated with \p key from the hash-table.
- void erase(const Key& key)
- {
- erase(find(key));
- }
- /// \brief Swaps the contents of the hash-table with \p other.
- void swap(HashTable& other)
- {
- std::swap(m_buckets, other.m_buckets);
- std::swap(m_bucketCount, other.m_bucketCount);
- std::swap(m_size, other.m_size);
- HashTableDetail::list_swap(m_list, other.m_list);
- }
- /// \brief Removes all values from the hash-table.
- void clear()
- {
- HashTable tmp;
- tmp.swap(*this);
- }
+HashTable() : m_bucketCount( 0 ), m_buckets( 0 ), m_size( 0 ){
+ initialise();
+}
+HashTable( std::size_t bucketCount ) : m_bucketCount( HashTableDetail::next_power_of_two( bucketCount ) ), m_buckets( buckets_new( m_bucketCount ) ), m_size( 0 ){
+ initialise();
+}
+~HashTable(){
+ for ( BucketNode* i = getFirst(); i != getLast(); )
+ {
+ BucketNode* node = i;
+ i = i->getNext();
+ node_destroy( node );
+ }
+ buckets_delete( m_buckets );
+}
+
+iterator begin(){
+ return iterator( getFirst() );
+}
+iterator end(){
+ return iterator( getLast() );
+}
+
+bool empty() const {
+ return m_size == 0;
+}
+std::size_t size() const {
+ return m_size;
+}
+
+/// \brief Returns an iterator pointing to the value associated with \p key if it is contained by the hash-table, else \c end().
+iterator find( const Key& key ){
+ hash_type hash = hashKey( key );
+ if ( m_bucketCount != 0 ) {
+ Bucket bucket = getBucket( hash );
+ if ( bucket != 0 ) {
+ BucketNode* node = bucket_find( bucket, hash, key );
+ if ( node != 0 ) {
+ return iterator( node );
+ }
+ }
+ }
+
+ return end();
+}
+/// \brief Adds \p value to the hash-table associated with \p key if it does not exist.
+iterator insert( const Key& key, const Value& value ){
+ hash_type hash = hashKey( key );
+ if ( m_bucketCount != 0 ) {
+ Bucket& bucket = getBucket( hash );
+ if ( bucket != 0 ) {
+ BucketNode* node = bucket_find( bucket, hash, key );
+ if ( node != 0 ) {
+ return iterator( node );
+ }
+ }
+ }
+
+ size_increment();
+ return iterator( bucket_insert( getBucket( hash ), node_create( hash, key, value ) ) );
+}
+
+/// \brief Removes the value pointed to by \p i from the hash-table.
+///
+/// \p i must be a deferenceable iterator into the hash-table.
+void erase( iterator i ){
+ Bucket& bucket = getBucket( i.node()->m_hash );
+ BucketNode* node = i.node();
+
+ // if this was the last node in the bucket
+ if ( bucket == node ) {
+ bucket = ( node->getNext() == getLast() || &getBucket( node->getNext()->m_hash ) != &bucket ) ? 0 : node->getNext();
+ }
+
+ node_unlink( node );
+ ASSERT_MESSAGE( node != 0, "tried to erase a non-existent key/value" );
+ node_destroy( node );
+
+ size_decrement();
+}
+
+/// \brief Returns the value identified by \p key if it is contained by the hash-table, else inserts and returns a new default-constructed value associated with \p key.
+Value& operator[]( const Key& key ){
+ hash_type hash = hashKey( key );
+ if ( m_bucketCount != 0 ) {
+ Bucket& bucket = getBucket( hash );
+ if ( bucket != 0 ) {
+ BucketNode* node = bucket_find( bucket, hash, key );
+ if ( node != 0 ) {
+ return node->m_value.value;
+ }
+ }
+ }
+ size_increment();
+ return bucket_insert( getBucket( hash ), node_create( hash, key, Value() ) )->m_value.value;
+}
+/// \brief Removes the value associated with \p key from the hash-table.
+void erase( const Key& key ){
+ erase( find( key ) );
+}
+/// \brief Swaps the contents of the hash-table with \p other.
+void swap( HashTable& other ){
+ std::swap( m_buckets, other.m_buckets );
+ std::swap( m_bucketCount, other.m_bucketCount );
+ std::swap( m_size, other.m_size );
+ HashTableDetail::list_swap( m_list, other.m_list );
+}
+/// \brief Removes all values from the hash-table.
+void clear(){
+ HashTable tmp;
+ tmp.swap( *this );
+}
};
#endif
+
+#endif
projects / xonotic / netradiant.git / blobdiff