maphash.h

Go to the documentation of this file.

// Evo C++ Library
/* Copyright 2019 Justin Crowell
Distributed under the BSD 2-Clause License -- see included file LICENSE.txt for details.
*/

#pragma once
#ifndef INCL_evo_maphash_h
#define INCL_evo_maphash_h

#include "map.h"
#include "array.h"
#include "ptrlist.h"
#include "impl/hash.h"

// Disable certain MSVC warnings for this file
#if defined(_MSC_VER)
    #pragma warning(push)
    #pragma warning(disable:4457)
#endif

namespace evo {


// Internal implementation macros -- only used in this file
#define EVO_IMPL_MAPHASH_SIZEMASK(SIZE)  (SIZE - 1)
#define EVO_IMPL_MAPHASH_THRESHOLD(SIZE) ((SIZE / 10) * 7)


template<class TKey, class TValue, class THash=CompareHash<TKey>, class TSize=SizeT>
class MapHash : public Map<TKey,TValue,TSize> {
protected:
    using Map<TKey,TValue,TSize>::size_;

public:
    EVO_CONTAINER_TYPE;
#if defined(_MSC_VER) || defined(EVO_OLDCC) // avoid errors with older compilers and MSVC
    typedef Map<TKey,TValue,TSize> MapBaseType;                 
    typedef typename MapBaseType::Size Size;
    typedef typename MapBaseType::Key Key;
    typedef typename MapBaseType::Value Value;
    typedef typename MapBaseType::Item Item;
    typedef typename MapBaseType::IterKey IterKey;
    typedef typename MapBaseType::IterItem IterItem;
#else
    using typename Map<TKey,TValue,TSize>::MapBaseType;
    using typename Map<TKey,TValue,TSize>::Size;
    using typename Map<TKey,TValue,TSize>::Key;
    using typename Map<TKey,TValue,TSize>::Value;
    using typename Map<TKey,TValue,TSize>::Item;
    using typename Map<TKey,TValue,TSize>::IterKey;
    using typename Map<TKey,TValue,TSize>::IterItem;
#endif
    typedef MapHash<TKey,TValue,THash,TSize> ThisType;          
    typedef THash Hash;                                         

    typedef typename IteratorBi<ThisType>::Const Iter;          
    typedef IteratorBi<ThisType>                 IterM;         

    MapHash() : Map<TKey,TValue,TSize>(false)
        { }

    MapHash(const MapBaseType& src) : Map<TKey,TValue,TSize>(false) {
        for (typename MapBaseType::Iter iter(src); iter; ++iter)
            getitem(iter->first).second = iter->second;
    }

    MapHash(const ThisType& src) : Map<TKey,TValue,TSize>(false), buckets_(src.buckets_), data_(src.data_) {
        size_ = src.size_;
    }

#if defined(EVO_CPP11)
    using typename MapBaseType::InitPair;   

    MapHash(const std::initializer_list<InitPair>& init) : MapHash() {
        assert( init.size() < IntegerT<Size>::MAX );
        capacitymin((Size)init.size());
        for (const auto& item : init)
            add(item.key, item.value);
    }

    MapHash(ThisType&& src) : Map<TKey,TValue,TSize>(false), buckets_(std::move(src.buckets_)), data_(std::move(src.data_)) {
        MapBaseType::size_ = src.MapBaseType::size_;
        src.MapBaseType::size_ = 0;
    }

    ThisType& operator=(ThisType&& src) {
        buckets_ = std::move(src.buckets_);
        data_ = std::move(src.data_);
        MapBaseType::size_ = src.MapBaseType::size_;
        src.MapBaseType::size_ = 0;
        return *this;
    }
#endif

    const ThisType& asconst() const {
        return *this;
    }

    // SET

    ThisType& operator=(const MapBaseType& src)
        { set(src); return *this; }

    ThisType& operator=(const ThisType& src)
        { set(src); return *this; }

    ThisType& set()
        { buckets_.set(); size_ = 0; return *this; }

    ThisType& set(const MapBaseType& src) {
        clear();
        for (typename MapBaseType::Iter iter(src); iter; ++iter)
            getitem(iter->first).second = iter->second;
        return *this;
    }

    ThisType& set(const ThisType& src) {
        buckets_.set(src.buckets_);
        data_ = src.data_;
        size_ = src.size_;
        return *this;
    }

    ThisType& setempty()
        { buckets_.setempty(); size_ = 0; return *this; }

    ThisType& clear()
        { buckets_.clear(); size_ = 0; return *this; }

    // INFO

    bool null() const
        { return buckets_.null(); }

    bool shared() const
        { return buckets_.shared(); }

    Size capacity() const
        { return buckets_.size(); }

    // COMPARE

    using MapBaseType::operator==;
    using MapBaseType::operator!=;

    // FIND

    Iter cbegin() const
        { return Iter(*this); }

    Iter cend() const
        { return Iter(); }

    IterM begin()
        { return IterM(*this); }

    Iter begin() const
        { return Iter(*this); }

    IterM end()
        { return IterM(); }

    Iter end() const
        { return Iter(); }

    bool contains(const Key& key) const
        { return (find(key) != NULL); }

    const Value* find(const Key& key) const {
        if (size_ > 0) {
            const Bucket* bucket = buckets_.item( data_.hash(key) & data_.sizemask );
            if (bucket != NULL) {
                if (key == bucket->first.first) {
                    return &bucket->first.second;
                } else {
                    Size index;
                    const Item* item = bucket->search(index, key, data_);
                    if (item != NULL)
                        return &item->second;
                }
            }
        }
        return NULL;
    }

    Value* findM(const Key& key) {
        if (size_ > 0) {
            Bucket* bucket = buckets_.itemM( data_.hash(key) & data_.sizemask );
            if (bucket != NULL) {
                if (key == bucket->first.first) {
                    return &bucket->first.second;
                } else {
                    Size index;
                    Item* item = (Item*)bucket->search(index, key, data_);
                    if (item != NULL)
                        return &item->second;
                }
            }
        }
        return NULL;
    }

    Iter iter(const Key& key) const {
        if (size_ > 0) {
            IterKey iterkey( data_.hash(key) & data_.sizemask );
            const Bucket* bucket = buckets_.item(iterkey.a);
            if (bucket != NULL) {
                if (bucket->first.first == key) {
                    return Iter(*this, iterkey, (IterItem*)&bucket->first);
                } else {
                    const IterItem* item = (IterItem*)bucket->search(iterkey.b, key, data_);
                    if (item != NULL) {
                        ++iterkey.b;
                        return Iter(*this, iterkey, item);
                    }
                }
            }
        }
        return Iter(*this, iterEND);
    }

    IterM iterM(const Key& key) {
        if (size_ > 0) {
            IterKey iterkey( data_.hash(key) & data_.sizemask );
            Bucket* bucket = buckets_.itemM(iterkey.a);
            if (bucket != NULL) {
                if (bucket->first.first == key) {
                    return IterM(*this, iterkey, (IterItem*)&bucket->first);
                } else {
                    IterItem* item = (IterItem*)bucket->search(iterkey.b, key, data_);
                    if (item != NULL) {
                        ++iterkey.b;
                        return IterM(*this, iterkey, item);
                    }
                }
            }
        }
        return IterM(*this, iterEND);
    }

    Item& getitem(const Key& key, bool* created=NULL) {
        if (data_.threshold == 0) {
            // Empty, resize buckets
            buckets_.resize(SIZE_INIT);
            data_.sizemask  = EVO_IMPL_MAPHASH_SIZEMASK(SIZE_INIT);
            data_.threshold = EVO_IMPL_MAPHASH_THRESHOLD(SIZE_INIT);
        } else if (size_ >= data_.threshold) {
            // Reached size threshold, time to grow
            Size newsize = buckets_.size() << 1;
            data_.sizemask  = EVO_IMPL_MAPHASH_SIZEMASK(newsize);
            data_.threshold = EVO_IMPL_MAPHASH_THRESHOLD(newsize);

            // Grow and rehash
            Buckets oldbuckets;
            buckets_.swap(oldbuckets);
            buckets_.resize(newsize);

            bool created;
            const Bucket* bucket;
            const Bucket** cur = (const Bucket**)oldbuckets.data();
            for (const Bucket** end=cur+oldbuckets.size(); cur < end; ++cur) {
                if ((bucket=*cur) != NULL) {
                    for (Size i=0, iend=bucket->others.size(); i <= iend; ++i) {
                        const Item* item = (i == 0 ? &bucket->first : &bucket->others[i-1]);
                        Bucket* newbucket = buckets_.getitem(data_.hash(item->first) & data_.sizemask, &created);
                        if (created)
                            newbucket->first = *item;
                        else {
                            Size index;
                            Item* newitem = (Item*)newbucket->search(index, item->first, data_);
                            if (newitem == NULL)
                                newbucket->others.insert(index, *item);
                            else
                                newitem->second = item->second;
                        }
                    }
                }
            }
        }

        // Get item, create if needed
        bool created_item;
        Item* item;
        Bucket* bucket = buckets_.getitem((data_.hash(key) & data_.sizemask), &created_item);
        if (created_item) {
            ++size_;
            item = &bucket->first;
            item->first = key;
        } else if (bucket->first.first == key) {
            item = &bucket->first;
        } else {
            Size index;
            item = (Item*)bucket->search(index, key, data_);
            if (item == NULL) {
                created_item = true;
                ++size_;
                item = (Item*)&(bucket->others[bucket->others.insertnew(index, 1)]);
                item->first = key;
            }
        }
        if (created != NULL)
            *created = created_item;
        return *item;
    }

    Value& get(const Key& key, bool* created=NULL)
        { return getitem(key, created).second; }

    // INFO_SET

    Value& operator[](const Key& key)
        { return getitem(key, NULL).second; }

    ThisType& unshare()
        { buckets_.unshare(); return *this; }

    ThisType& capacity(Size size) {
        const Size cursize = buckets_.size();
        if (size != cursize) {
            // Find new size (must be power of 2)
            Size newsize = SIZE_INIT;
            while (newsize < size)  newsize <<= 1;
            while (newsize < size_) newsize <<= 1;

            if (newsize != cursize) {
                // Reached size threshold, time to grow
                data_.sizemask  = EVO_IMPL_MAPHASH_SIZEMASK(newsize);
                data_.threshold = EVO_IMPL_MAPHASH_THRESHOLD(newsize);
                if (size_ == 0) {
                    // Empty, just resize buckets
                    buckets_.resize(newsize);
                } else {
                    // Resize and rehash
                    Buckets oldbuckets;
                    buckets_.swap(oldbuckets);
                    buckets_.resize(newsize);

                    bool created;
                    const Bucket* bucket;
                    const Bucket** cur = (const Bucket**)oldbuckets.data();
                    for (const Bucket** end=cur+oldbuckets.size(); cur < end; ++cur) {
                        if ((bucket=*cur) != NULL) {
                            for (Size i=0, iend=bucket->others.size(); i <= iend; ++i) {
                                const Item* item = (i == 0 ? &bucket->first : &bucket->others[i-1]);
                                Bucket* newbucket = buckets_.getitem(data_.hash(item->first) & data_.sizemask, &created);
                                if (created)
                                    newbucket->first = *item;
                                else {
                                    Size index;
                                    Item* newitem = (Item*)newbucket->search(index, item->first, data_);
                                    if (newitem == NULL)
                                        newbucket->others.insert(index, *item);
                                    else
                                        newitem->second = item->second;
                                }
                            }
                        }
                    }
                }
            }
        }
        return *this;
    }

    ThisType& capacitymin(Size min) {
        if (min > buckets_.size())
            capacity(min);
        return *this;
    }

    ThisType& reserve(Size size)
        { return capacitymin(size_ + size); }

    // RESIZE

    void resize(Size size) {
        Size newsize = MIN_SIZE;
        while (newsize < size) newsize <<= 1;
        if (newsize != buckets_.size()) {
            data_.sizemask  = EVO_IMPL_MAPHASH_SIZEMASK(newsize);
            data_.threshold = EVO_IMPL_MAPHASH_THRESHOLD(newsize);
            Buckets oldbuckets;
            buckets_.swap(oldbuckets);
            buckets_.resize(newsize);

            bool created;
            const Bucket* bucket;
            const Bucket** cur = (const Bucket**)oldbuckets.data();
            for (const Bucket** end=cur+oldbuckets.size(); cur < end; ++cur) {
                if ((bucket=*cur) != NULL) {
                    for (Size i=0, iend=bucket->others.size(); i <= iend; ++i) {
                        const Item* item = (i == 0 ? &bucket->first : &bucket->others[i-1]);
                        Bucket* newbucket = buckets_.getitem(data_.hash(item->first) & data_.sizemask, &created);
                        if (created)
                            newbucket->first = *item;
                        else {
                            Size index;
                            Item* newitem = (Item*)newbucket->search(index, item->first, data_);
                            if (newitem == NULL)
                                newbucket->others.insert(index, *item);
                            else
                                newitem->second = item->second;
                        }
                    }
                }
            }
        }
    }

    // ADD

    Item& add(const Key& key, const Value& value, bool update=true) {
        bool created_val;
        Item& upditem = getitem(key, &created_val);
        if (created_val || update)
            upditem.second = value;
        return upditem;
    }

    Item& add(const Item& item, bool update=true)
        { return add(item.first, item.second, update); }

    ThisType& add(const MapBaseType& map, bool update=true) {
        if (this != &map) {
            reserve(map.size());
            for (typename MapBaseType::Iter iter(map); iter; ++iter)
                add(iter->first, iter->second, update);
        }
        return *this;
    }

    // REMOVE

    bool remove(const Key& key) {
        bool result;
        Size bucket_index = data_.hash(key) & data_.sizemask;
        Bucket* bucket = buckets_.itemM(bucket_index);
        if (bucket != NULL) {
            Size index;
            if (bucket->first.first == key) {
                if (bucket->others.size() > 0) {
                    // Remove "first" and replace with last item in "others"
                    Item* item1 = &bucket->first;
                    Item* item2 = bucket->others.data();
                    EVO_IMPL_CONTAINER_SWAP(item1, item2, Item);
                    bucket->others.remove(0);
                } else
                    // Remove bucket since "first" is only item
                    buckets_.remove(bucket_index);
                result = true;
                --size_;
            } else if (bucket->search(index, key, data_) != NULL) {
                // Remove from "others"
                bucket->others.remove(index);
                result = true;
                --size_;
            } else
                result = false;
        } else
            result = false;
        return result;
    }

    bool remove(typename MapBaseType::IterM& iter, IteratorDir dir=iterNONE)
        { return remove((IterM&)iter, dir); }

    bool remove(IterM& iter, IteratorDir dir=iterNONE) {
        if (iter && this == &iter.getParent()) {
            IterKey& iterkey = iter.getKey();
            assert( iterkey.a < buckets_.size() );
            Bucket* bucket = buckets_.itemM(iterkey.a);
            assert( bucket != NULL );
            if (iterkey.b > 0) {
                // Remove from "others"
                bucket->others.remove(iterkey.b-1);
            } else {
                if (bucket->others.size() > 0) {
                    // Remove "first" and replace with last item in "others"
                    Item* item1 = &bucket->first;
                    Item* item2 = bucket->others.data();
                    EVO_IMPL_CONTAINER_SWAP(item1, item2, Item);
                    bucket->others.remove(0);
                } else {
                    // Remove bucket since "first" is only item
                    buckets_.remove(iterkey.a);
                    bucket = NULL;
                }
            }

            // Update size and iterator
            if (--size_ > 0 && dir != iterNONE) {
                if (dir == iterRV) {
                    // Previous
                    if (iterkey.b > 0 && bucket != NULL) {
                        iter.setData( (IterItem*)(--iterkey.b == 0 ? &(bucket->first) : &(bucket->others[iterkey.b-1])) );
                    } else {
                        bucket = (Bucket*)buckets_.iterPrev(iterkey.a);
                        if (bucket != NULL) {
                            iterkey.b = bucket->others.size();
                            iter.setData( (IterItem*)(iterkey.b == 0 ? &bucket->first : &(bucket->others[iterkey.b-1])) );
                        } else
                            iter = iterEND;
                    }
                } else {
                    // Next
                    if (bucket != NULL && iterkey.b <= bucket->others.size()) {
                        iter.setData( (IterItem*)(iterkey.b == 0 ? &bucket->first : &(bucket->others[iterkey.b-1])) );
                    } else {
                        iterkey.b = 0;
                        if ((bucket=(Bucket*)buckets_.iterNext(iterkey.a)) != NULL)
                            iter.setData( (IterItem*)&bucket->first );
                        else
                            iter = iterEND;
                    }
                }
            } else
                iter = iterEND;
            return true;
        }
        return false;
    }

    // INTERNAL

    // Testing methods
#if EVO_UNIT_TEST_MODE
    Size utCollisions() const {
        Size count = 0;
        for (typename Buckets::Iter iter(buckets_); iter; ++iter)
            count += iter->others.size();
        return count;
    }
#endif

    // Iterator support methods
    void iterInitMutable()
        { buckets_.unshare(); }
    const IterItem* iterFirst(IterKey& key) const {
        key.b = 0;
        if (size_ > 0)
            return (IterItem*)&(buckets_.iterFirst(key.a)->first);
        key.a = END;
        return NULL;
    }
    const IterItem* iterNext(IterKey& key) const {
        if (key.a != END) {
            const Bucket* bucket = buckets_.item(key.a);
            if (++key.b <= bucket->others.size())
                return (IterItem*)&(bucket->others[key.b-1]);
            key.b = 0;
            if ((bucket=buckets_.iterNext(key.a)) != NULL)
                return (IterItem*)&bucket->first;
        }
        return NULL;
    }
    const IterItem* iterLast(IterKey& key) const {
        if (size_ > 0) {
            const Bucket* bucket = buckets_.iterLast(key.a);
            assert( bucket != NULL );
            key.b = bucket->others.size();
            return (IterItem*)(key.b == 0 ? &bucket->first : &(bucket->others[key.b-1]));
        }
        key.a = END;
        key.b = 0;
        return NULL;

    }
    const IterItem* iterPrev(IterKey& key) const {
        if (key.a != END) {
            if (key.b > 0) {
                return (IterItem*)(--key.b == 0 ? &(buckets_.item(key.a)->first) : &(buckets_.item(key.a)->others[key.b-1]));
            } else {
                const Bucket* bucket = buckets_.iterPrev(key.a);
                if (bucket != NULL) {
                    key.b = bucket->others.size();
                    return (IterItem*)(key.b == 0 ? &bucket->first : &(bucket->others[key.b-1]));
                }
            }
            key.a = END;
        }
        return NULL;
    }
protected:
    const Item* getiter(IterKey& iterkey, const Key& key) const {
        if (size_ > 0) {
            iterkey.a = (data_.hash(key) & data_.sizemask);
            const Bucket* bucket = buckets_.item(iterkey.a);
            if (bucket != NULL) {
                if (bucket->first.first == key) {
                    iterkey.b = 0;
                    return &bucket->first;
                } else {
                    const Item* item = bucket->search(iterkey.b, key, data_);
                    if (item != NULL) {
                        ++iterkey.b;
                        return item;
                    }
                }
            }
        }
        iterkey.a = END;
        iterkey.b = 0;
        return NULL;
    }

private:
    static const Size SIZE_INIT = 64; // initial hash size -- must be power of 2
    static const Size MIN_SIZE  = 8;  // minimum hash size -- must be power of 2

    struct Bucket {
        Item        first;
        Array<Item> others;

        Bucket() {
        }
        Bucket(const Bucket& src) : first(src.first), others(src.others) {
        }

        // Search "others" for key, using compare, set index (insertion point if not found)
        const Item* search(Size& index, const Key& key, const typename Hash::CompareBase& compare) const {
            int cmp;
            Size left = 0, right = others.size(), mid = 0;
            const Item* items = others.data();
            while (left < right) {
                mid = left + ((right-left) / 2);
                const Item* item = items + mid;
                cmp = compare(key, item->first);
                if (cmp < 0) {
                    right = mid;
                } else if (cmp == 0) {
                    index = mid;
                    return item;
                } else
                    left = mid + 1;
            }
            index = left;
            return NULL;
        }

    private:
        // Copying is done via copy constructor
        Bucket& operator=(const Bucket&) EVO_ONCPP11(= delete);
    };

    typedef PtrList<Bucket,Size> Buckets;

    Buckets buckets_;

    // Use inheritance to reduce size bloat with empty Hash
    struct Data : public THash {
        Size sizemask;
        Size threshold;

        Data() : sizemask(0), threshold(0) {
        }
        Data(const Data& data) : Hash(data), sizemask(data.sizemask), threshold(data.threshold) {
        }
        Data& operator=(const Data& data) {
            THash::operator=(data);
            sizemask = data.sizemask;
            threshold = data.threshold;
            return *this;
        }

    #if defined(EVO_CPP11)
        Data(Data&& data) : THash(std::move((THash&&)data)), sizemask(data.sizemask), threshold(data.threshold) {
            data.sizemask = 0;
            data.threshold = 0;
        }
        Data& operator=(Data&& data) {
            THash::operator=(std::move((THash&&)data));
            sizemask = data.sizemask;
            threshold = data.threshold;
            data.sizemask = 0;
            data.threshold = 0;
            return *this;
        }
    #endif
    };

    Data data_;
};

#undef EVO_IMPL_MAPHASH_SIZEMASK
#undef EVO_IMPL_MAPHASH_THRESHOLD


#if defined(INCL_evo_string_h) || defined(DOXYGEN)

typedef MapHash<String,String> StrHash;
#endif


}
#if defined(_MSC_VER)
    #pragma warning(pop)
#endif
#endif