hash_map.h

Go to the documentation of this file.

/*
 *  GiNaC Copyright (C) 1999-2011 Johannes Gutenberg University Mainz, Germany
 *
 *  This program 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.
 *
 *  This program 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 this program; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 */

#ifndef GINAC_HASH_MAP_H
#define GINAC_HASH_MAP_H

#include <algorithm>
#include <functional>
#include <iterator>
#include <list>
#include <utility>

namespace GiNaC {

/*
 *  "Hashmap Light" - buckets only contain one value, quadratic probing,
 *  grows automatically
 */

namespace internal {

// List of prime numbers shamelessly stolen from GCC STL
enum { num_primes = 29 };

static const unsigned long prime_list[num_primes] =
{
    31ul,        53ul,         97ul,         193ul,       389ul,
    769ul,       1543ul,       3079ul,       6151ul,      12289ul,
    24593ul,     49157ul,      98317ul,      196613ul,    393241ul,
    786433ul,    1572869ul,    3145739ul,    6291469ul,   12582917ul,
    25165843ul,  50331653ul,   100663319ul,  201326611ul, 402653189ul,
    805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
};

inline unsigned long next_prime(unsigned long n)
{
    const unsigned long *first = prime_list;
    const unsigned long *last = prime_list + num_primes;
    const unsigned long *pos = std::lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

} // namespace internal


// Define default arguments
template <typename T, template <class> class A = std::allocator>
class exhashmap;


template <typename T, template <class> class A>
class exhashmap {
public:
    static const unsigned min_num_buckets = 31; // must be prime

    // Standard types
    typedef ex key_type;
    typedef T mapped_type;
    typedef std::pair<key_type, T> value_type;
    typedef ex_is_less key_compare;
    typedef ex_is_equal key_equal;
    typedef value_type & reference;
    typedef const value_type & const_reference;
    typedef value_type * pointer;
    typedef const value_type * const_pointer;

protected:
    // Private types
    enum bucket_state {
        EMPTY,  
        USED,   
        ERASED  
    };
    typedef std::pair<bucket_state, value_type> Bucket;

public:
    // More standard types
    typedef A<Bucket> allocator_type;

protected:
    // More private types
    typedef std::vector<Bucket, allocator_type> Table;

    typedef typename Table::iterator table_iterator;
    typedef typename Table::const_iterator table_const_iterator;

public:
    // Iterators
    template <typename Pointer, typename Reference, class TableIterator>
    class exhashmap_iterator : public std::iterator<std::forward_iterator_tag, value_type, typename Table::difference_type, Pointer, Reference> {
    protected:
        friend class exhashmap;

    public:
        exhashmap_iterator() {}
        exhashmap_iterator(TableIterator t, TableIterator te)
         : it(t), table_end(te) {}

        // Allow iterator to const_iterator conversion
        template <typename P, typename R, class TI>
        exhashmap_iterator(const exhashmap_iterator<P, R, TI> &other)
         : it(other.get_it_()), table_end(other.get_table_end_()) {}

        typename exhashmap_iterator::reference operator*() const
        {
            return it->second;
        }

        typename exhashmap_iterator::pointer operator->() const
        {
            return &(it->second);
        }

        exhashmap_iterator &operator++()
        {
            increment();
            return *this;
        }

        exhashmap_iterator operator++(int)
        {
            exhashmap_iterator tmp = *this;
            increment();
            return tmp;
        }

        template <typename P, typename R, class TI>
        bool operator==(const exhashmap_iterator<P, R, TI> &other) const
        {
            return it == other.get_it_();
        }

        template <typename P, typename R, class TI>
        bool operator!=(const exhashmap_iterator<P, R, TI> &other) const
        {
            return it != other.get_it_();
        }

        // Private access function
        TableIterator get_it_() const { return it; }
        TableIterator get_table_end_() const { return table_end; }

    protected:
        TableIterator it;        
        TableIterator table_end; 

        void increment()
        {
            if (it != table_end)
                ++it;

            // Skip empty and erased buckets
            while (it != table_end && it->first != USED)
                ++it;
        }
    };

    typedef exhashmap_iterator<value_type*, value_type&, table_iterator> iterator;
    typedef exhashmap_iterator<const value_type*, const value_type&, table_const_iterator> const_iterator;

    // More standard types
    typedef typename Table::size_type size_type;
    typedef typename Table::difference_type difference_type;

    class value_compare : public std::binary_function<value_type, value_type, bool>, private key_compare {
        friend class exhashmap;
    public:
        bool operator()(const value_type &lhs, const value_type &rhs) const
        {
            return key_compare::operator()(lhs.first, rhs.first);
        }

        bool operator()(const key_type &lhs, const value_type &rhs) const
        {
            return key_compare::operator()(lhs, rhs.first);
        }

        bool operator()(const value_type &lhs, const key_type &rhs) const
        {
            return key_compare::operator()(lhs.first, rhs);
        }
    };

protected:
    // Private data
    size_type num_entries; 
    size_type num_buckets; 
    Table hashtab;         

    static size_type hash_index(const key_type &x, size_type nbuckets)
    {
        return x.gethash() % nbuckets;
    }

    static table_iterator find_bucket(const key_type &x, table_iterator tab, size_type nbuckets);
    static table_const_iterator find_bucket(const key_type &x, table_const_iterator tab, size_type nbuckets);
    static table_iterator find_bucket_for_insertion(const key_type &x, table_iterator tab, size_type nbuckets);

    table_iterator find_bucket(const key_type &x)
    {
        return find_bucket(x, hashtab.begin(), num_buckets);
    }

    table_const_iterator find_bucket(const key_type &x) const
    {
        return find_bucket(x, hashtab.begin(), num_buckets);
    }

    table_iterator find_bucket_for_insertion(const key_type &x)
    {
        return find_bucket_for_insertion(x, hashtab.begin(), num_buckets);
    }

    size_type hwm() const
    {
        // Try to keep at least 25% of the buckets free
        return num_buckets - (num_buckets >> 2);
    }

    void grow();

public:
    // 23.3.1.1 Construct/copy/destroy
    exhashmap()
     : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}

    explicit exhashmap(size_type nbuckets)
     : num_entries(0), num_buckets(internal::next_prime(nbuckets)), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}

    template <class InputIterator>
    exhashmap(InputIterator first, InputIterator last)
     : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type())))
    {
        insert(first, last);
    }

    exhashmap &operator=(const exhashmap &other)
    {
        exhashmap(other).swap(*this);
        return *this;
    }

    // Iterators
    iterator begin()
    {
        // Find first used bucket
        table_iterator bucket = hashtab.begin();
        while (bucket != hashtab.end() && bucket->first != USED)
            ++bucket;
        return iterator(bucket, hashtab.end());
    }

    const_iterator begin() const
    {
        // Find first used bucket
        table_const_iterator bucket = hashtab.begin();
        while (bucket != hashtab.end() && bucket->first != USED)
            ++bucket;
        return const_iterator(bucket, hashtab.end());
    }

    iterator end()
    {
        return iterator(hashtab.end(), hashtab.end());
    }

    const_iterator end() const
    {
        return const_iterator(hashtab.end(), hashtab.end());
    }

    // Capacity
    bool empty() const
    {
        return num_entries == 0;
    }

    size_type size() const
    {
        return num_entries;
    }

    size_type max_size() const
    {
        return hashtab.max_size();
    }

    size_type bucket_count() const
    {
        return num_buckets;
    }

    // 23.3.1.2 Element access
    T &operator[](const key_type &x)
    {
        return insert(value_type(x, mapped_type())).first->second;
    }

    // Modifiers
    std::pair<iterator, bool> insert(const value_type &x);

    iterator insert(iterator pos, const value_type &x)
    {
        return insert(x).first;
    }

    template <class InputIterator>
    void insert(InputIterator first, InputIterator last)
    {
        for (; first != last; ++first)
            insert(*first);
    }

    void erase(iterator position)
    {
        table_iterator bucket = position.get_it_();
        bucket->first = ERASED;
        bucket->second.first = 0;
        --num_entries;
    }

    size_type erase(const key_type &x);

    void swap(exhashmap &other)
    {
        hashtab.swap(other.hashtab);
        std::swap(num_buckets, other.num_buckets);
        std::swap(num_entries, other.num_entries);
    }

    void clear();

    // Observers
    key_compare key_comp() const
    {
        return key_compare();
    }

    value_compare value_comp() const
    {
        return value_compare();
    }

    // 23.3.1.3 Map operations
    iterator find(const key_type &x);
    const_iterator find(const key_type &x) const;

    size_type count(const key_type &x) const
    {
        return find(x) == end() ? 0 : 1;
    }

    std::pair<iterator, iterator> equal_range(const key_type &x)
    {
        iterator i = find(x);
        if (i == end())
            return std::make_pair(i, i);
        else {
            iterator j = ++i;
            return std::make_pair(i, j);
        }
    }

    std::pair<const_iterator, const_iterator> equal_range(const key_type &x) const
    {
        const_iterator i = find(x);
        if (i == end())
            return std::make_pair(i, i);
        else {
            const_iterator j = ++i;
            return std::make_pair(i, j);
        }
    }

    friend bool operator==(const exhashmap &lhs, const exhashmap &rhs)
    {
        if (lhs.num_entries != rhs.num_entries || lhs.num_buckets != rhs.num_buckets)
            return false;

        // We can't compare the tables directly as the elements may be
        // in different order due to the collision handling. We therefore
        // look up each value from the lhs map in the rhs map separately.
        for (const_iterator itl = lhs.begin(); itl != lhs.end(); ++itl) {
            const_iterator itr = rhs.find(itl->first);
            if (itr == rhs.end())
                return false;
            if (itl->second != itr->second)
                return false;
        }
        return true;
    }

    friend bool operator!=(const exhashmap &lhs, const exhashmap &rhs)
    {
        return !(lhs == rhs);
    }

#if 0
    void dump() const
    {
        std::clog << "num_entries = " << num_entries << std::endl;
        std::clog << "num_buckets = " << num_buckets << std::endl;
        size_type t = 0;
        for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it, ++t) {
            std::clog << " bucket " << t << ": ";
            std::clog << (it->first == EMPTY ? "free" : (it->first == USED ? "used" : "erased")) << ", " << it->second.first << " -> " << it->second.second << std::endl;
        }
    }
#endif
};

template <typename T, template <class> class A>
inline typename exhashmap<T, A>::table_iterator exhashmap<T, A>::find_bucket(const key_type &x, table_iterator tab, size_type nbuckets)
{
    // Quadratic probing
    size_type h = hash_index(x, nbuckets);
    size_type d = 1;
    table_iterator it = tab + h;
    while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
        h = (h + d) % nbuckets;
        d += 2;
        it = tab + h;
    }
    return it;
}

template <typename T, template <class> class A>
inline typename exhashmap<T, A>::table_const_iterator exhashmap<T, A>::find_bucket(const key_type &x, table_const_iterator tab, size_type nbuckets)
{
    // Quadratic probing
    size_type h = hash_index(x, nbuckets);
    size_type d = 1;
    table_const_iterator it = tab + h;
    while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
        h = (h + d) % nbuckets;
        d += 2;
        it = tab + h;
    }
    return it;
}

template <typename T, template <class> class A>
inline typename exhashmap<T, A>::table_iterator exhashmap<T, A>::find_bucket_for_insertion(const key_type &x, table_iterator tab, size_type nbuckets)
{
    // Quadratic probing
    size_type h = hash_index(x, nbuckets);
    size_type d = 1;
    table_iterator it = tab + h;
    while (it->first != EMPTY && !key_equal()(it->second.first, x)) {
        h = (h + d) % nbuckets;
        d += 2;
        it = tab + h;
    }
    return it;
}

template <typename T, template <class> class A>
void exhashmap<T, A>::grow()
{
    // Allocate new empty hash table
    size_type new_num_buckets = internal::next_prime(num_buckets + 1);
    Table new_hashtab;
    new_hashtab.resize(new_num_buckets);
    for (table_iterator it = new_hashtab.begin(); it != new_hashtab.end(); ++it)
        it->first = EMPTY;

    // Re-insert all elements into new table
    for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it) {
        if (it->first == USED) {
            table_iterator bucket = find_bucket(it->second.first, new_hashtab.begin(), new_num_buckets);
            *bucket = *it;
        }
    }

    // Swap with the old table
    hashtab.swap(new_hashtab);
    num_buckets = new_num_buckets;
}

template <typename T, template <class> class A>
std::pair<typename exhashmap<T, A>::iterator, bool> exhashmap<T, A>::insert(const value_type &x)
{
    table_iterator bucket = find_bucket_for_insertion(x.first);
    if (bucket->first == USED) {
        // Value already in map
        return std::make_pair(iterator(bucket, hashtab.end()), false);
    } else {
        // Insert new value
        bucket->first = USED;
        bucket->second = x;
        ++num_entries;
        if (num_entries >= hwm()) {
            grow();
            bucket = find_bucket(x.first);
        }
        return std::make_pair(iterator(bucket, hashtab.end()), true);
    }
}

template <typename T, template <class> class A>
typename exhashmap<T, A>::size_type exhashmap<T, A>::erase(const key_type &x)
{
    iterator i = find(x);
    if (i != end()) {
        erase(i);
        return 1;
    } else
        return 0;
}

template <typename T, template <class> class A>
typename exhashmap<T, A>::iterator exhashmap<T, A>::find(const key_type &x)
{
    table_iterator bucket = find_bucket(x);
    if (bucket->first == USED)
        return iterator(bucket, hashtab.end());
    else
        return end();
}

template <typename T, template <class> class A>
typename exhashmap<T, A>::const_iterator exhashmap<T, A>::find(const key_type &x) const
{
    table_const_iterator bucket = find_bucket(x);
    if (bucket->first == USED)
        return const_iterator(bucket, hashtab.end());
    else
        return end();
}

template <typename T, template <class> class A>
void exhashmap<T, A>::clear()
{
    for (table_iterator i = hashtab.begin(); i != hashtab.end(); ++i) {
        i->first = EMPTY;
        i->second.first = 0;
        i->second.second = mapped_type();
    }
    num_entries = 0;
}

} // namespace GiNaC


// Specializations of Standard Library algorithms
namespace std {

template <typename T, template <class> class A>
inline void swap(GiNaC::exhashmap<T, A> &lhs, GiNaC::exhashmap<T, A> &rhs)
{
    lhs.swap(rhs);
}

} // namespace std

#endif // ndef GINAC_HASH_MAP_H