X-Git-Url: http://git.xonotic.org/?a=blobdiff_plain;f=libs%2Fcontainer%2Fhashtable.h;h=6b16bd60b8091092bf650ffabebea3aed1954a1d;hb=d4ba4dcb5644fd978e30a34d2d8b4ad88296f7ad;hp=88d672cfc7f14e83406fa1e778f977bfa5891169;hpb=107765f0e4b543dfc346851ee5b4605cc17eb1c6;p=xonotic%2Fnetradiant.git diff --git a/libs/container/hashtable.h b/libs/container/hashtable.h index 88d672cf..6b16bd60 100644 --- a/libs/container/hashtable.h +++ b/libs/container/hashtable.h @@ -1,180 +1,166 @@ /* -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 + +template > + using HashTable = std::unordered_map; + +#if 0 #include #include #include +#include #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 - struct KeyValue - { - const Key key; - Value value; - - KeyValue(const Key& key_, const Value& value_) - : key(key_), value(value_) - { - } - }; - - template - struct BucketNode : public BucketNodeBase - { - Hash m_hash; - KeyValue m_value; - - BucketNode(Hash hash, const Key& key, const Value& value) - : m_hash(hash), m_value(key, value) - { - } - BucketNode* getNext() const - { - return static_cast(next); - } - BucketNode* getPrev() const - { - return static_cast(prev); - } - }; - - template - class BucketIterator - { - typedef BucketNode 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 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 +struct KeyValue +{ + const Key key; + Value value; + + KeyValue( const Key& key_, const Value& value_ ) + : key( key_ ), value( value_ ){ + } +}; + +template +struct BucketNode : public BucketNodeBase +{ + Hash m_hash; + KeyValue m_value; + + BucketNode( Hash hash, const Key& key, const Value& value ) + : m_hash( hash ), m_value( key, value ){ + } + BucketNode* getNext() const { + return static_cast( next ); + } + BucketNode* getPrev() const { + return static_cast( prev ); + } +}; + +template +class BucketIterator +{ +typedef BucketNode 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 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*() ); +} +}; } @@ -195,280 +181,238 @@ namespace HashTableDetail template > class HashTable : private KeyEqual, private Hasher { - typedef typename Hasher::hash_type hash_type; - typedef HashTableDetail::KeyValue KeyValue; - typedef HashTableDetail::BucketNode 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(m_list.next); - } - BucketNode* getLast() - { - return static_cast(&m_list); - } +typedef typename Hasher::hash_type hash_type; +typedef HashTableDetail::KeyValue KeyValue; +typedef HashTableDetail::BucketNode 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( m_list.next ); +} +BucketNode* getLast(){ + return static_cast( &m_list ); +} public: - typedef KeyValue value_type; - typedef HashTableDetail::BucketIterator iterator; +typedef KeyValue value_type; +typedef HashTableDetail::BucketIterator 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