hashtable.h

Go to the documentation of this file.

/*
Copyright (C) 2001-2006, William Joseph.
All Rights Reserved.

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 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
*/

#if !defined(INCLUDED_CONTAINER_HASHTABLE_H)
#define INCLUDED_CONTAINER_HASHTABLE_H

#include <cstddef>
#include <algorithm>
#include <functional>
#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*());
    }
};
}


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);
    }

public:

    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);
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;
    }

    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();
    }
    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)));
    }

    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();
    }

    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;
    }
    void erase(const Key& key) {
        erase(find(key));
    }
    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);
    }
    void clear() {
        HashTable tmp;
        tmp.swap(*this);
    }
};

#endif