OtherHashMaps.h

Go to the documentation of this file.

#ifndef TrackingTools_TrajectoryCleaning_src_OtherHashMaps
#define TrackingTools_TrajectoryCleaning_src_OtherHashMaps

#include <map>
#include <vector>
#include <memory>
#include <list>
#include <iterator>
#include <boost/unordered_map.hpp>
#include <boost/range.hpp>
#include <boost/type_traits.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/logical.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/if.hpp>

#include <iostream>

namespace cmsutil { 

/*** The concept is the same of std::map<K, std::vector<V>>, but the implementation is much different (and the interface is not really compatible)
 *   It works only for K and V objects with trivial destructors (primitive types and bare pointers are fine)
 *   The main implementation difference w.r.t. unordered_map<K, std::vector<V>> is that this map is optimized to do very few memory allocations
 *   (in particular, clear does not redeme memory so if you just clear the map instead of deleting it you won't call malloc each time you fill it)
 *   The map doesn't rehash, so you should set a reasonable number of buckets (that you can change also when clearing the map)
 *   Note that too many buckets will make your map slow to clear (and possibly more prone to cache misses).
 *   Although it can take an allocator as template argument, it has been tested only with std::allocator.
 *   When used in the TrajectoryCleanerBySharedHits it works and it does improve the performance. Any other usecase was not checked at all.
 * */
template<typename K, typename V, typename Hasher=boost::hash<K>, typename Equals=std::equal_to<K>, typename Alloc=std::allocator<V> >
class SimpleAllocHashMultiMap {
    // taking Alloc definition from http://www.codeproject.com/KB/cpp/allocator.aspx
    BOOST_MPL_ASSERT( (boost::mpl::and_<boost::has_trivial_destructor<K>, boost::has_trivial_destructor<V> > ));
    public:
        typedef Hasher hasher;
        typedef SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc> map_type;
        typedef typename boost::mpl::if_<typename boost::is_pointer<V>, V, V const &>::type value_ref; // otherwise we get problems with 'const' if V is a pointer

        SimpleAllocHashMultiMap(size_t buckets, size_t keyRowSize, size_t valueRowSize, size_t maxRows=50) ;

        ~SimpleAllocHashMultiMap() ;

        void clear(size_t newBucketSize=0) { 
            if (newBucketSize != 0) {
                if (newBucketSize > bucketCapacity_) {
                    ptrAlloc_.deallocate(buckets_, bucketCapacity_);
                    bucketCapacity_ = newBucketSize;
                    buckets_ = ptrAlloc_.allocate(bucketCapacity_);
                }
                bucketSize_ = newBucketSize;
            }
            memset(buckets_, 0, bucketSize_ * sizeof(KeyItem *));
            currentKeyRow_ = keyRows_.begin();
            nextKeyItem_ = keyRows_.front(); keyEndMarker_ = nextKeyItem_ + keyRowSize_;
            currentValueRow_ = valueRows_.begin();
            nextValueItem_ = valueRows_.front(); valueEndMarker_ = nextValueItem_ + valueRowSize_;
            if ((keyRows_.size() > maxRows_) || (valueRows_.size() > maxRows_)) freeRows();
        }
        void freeRows() ;

        bool empty() const { return nextKeyItem_ == keyRows_.front(); }

        void insert(K const &key, value_ref value );

        struct ValueItem {
            ValueItem(ValueItem *next1, value_ref val) : next(next1), value(val) {}
            ValueItem * next;
            V           value;
            typedef V value_type;
            const value_type & operator()() const { return value; }
        };

        struct KeyItem {
            KeyItem (KeyItem *next1, K const &key1, ValueItem *val1) : key(key1), next(next1), value(val1) {}
            K           key;
            KeyItem   * next;
            ValueItem * value;
            typedef KeyItem value_type;
            const value_type & operator()() const { return *this; }
        };

        template<typename Item>
        class item_iterator { 
            public:
                typedef ::std::forward_iterator_tag iterator_category;
                typedef const typename Item::value_type  value_type;
                typedef const value_type & reference;
                typedef const value_type * pointer;
                typedef ptrdiff_t difference_type;
                typedef item_iterator<Item> self_type;

                item_iterator() : it_(0) {}
                item_iterator(const Item *it) : it_(it) {}
                const value_type & operator*()  const { return   (*it_)(); }
                const value_type * operator->() const { return & (*it_)(); }
                self_type & operator++() { 
                    if (it_ != 0) it_ = it_->next; 
                    return *this; 
                }
                bool operator==(const self_type &other) const { return it_ == other.it_; }
                bool operator!=(const self_type &other) const { return it_ != other.it_; }
                bool good() const { return (it_ != 0); }
            private:
                const Item *it_;
        };
        typedef item_iterator<ValueItem> value_iterator;

        value_iterator values(K const &key) ;

    private:
        typedef typename Alloc::template rebind<KeyItem>::other   KeyItemAllocator;
        typedef typename Alloc::template rebind<KeyItem *>::other KeyItemPtrAllocator;
        typedef typename Alloc::template rebind<ValueItem>::other ValueItemAllocator;

        // --- buckets ---
        size_t bucketSize_, bucketCapacity_;
        KeyItem ** buckets_;
        // --- keys ---
        size_t keyRowSize_; 
        std::list<KeyItem *> keyRows_;
        typename std::list<KeyItem *>::iterator currentKeyRow_; // last row that is currently in use. nextItem_ and the last valid item are both on this row. it is never rows_.end()
        KeyItem   *nextKeyItem_, *keyEndMarker_;
        // --- values ---
        size_t valueRowSize_;
        std::list<ValueItem *> valueRows_;
        typename std::list<ValueItem *>::iterator currentValueRow_; // last row that is currently in use. nextItem_ and the last valid item are both on this row. it is never rows_.end()
        ValueItem   *nextValueItem_, *valueEndMarker_;
        // --- other ---
        size_t maxRows_;
        Hasher hasher_;
        Equals eq_; 
        KeyItemAllocator    keyAlloc_;
        ValueItemAllocator  valueAlloc_;
        KeyItemPtrAllocator ptrAlloc_;

        KeyItem   * push_back_(K const &key,   KeyItem   *next) ; 
        ValueItem * push_back_(value_ref value, ValueItem *next) ; 
        KeyItem   & find_or_insert_(K const &key) ;
    public:
        void dump() {
            std::cout << "Dumping HASH MULTIMAP" << std::endl;
            std::cout << "  Key items: " << (std::distance(keyRows_.begin(), currentKeyRow_) * keyRowSize_ + (nextKeyItem_ - *currentKeyRow_)) << std::endl;
            std::cout << "  Value items: " << (std::distance(valueRows_.begin(), currentValueRow_) * valueRowSize_ + (nextValueItem_ - *currentValueRow_)) << std::endl;
            size_t row = 0;
            std::cout << "  Buckets (size " << bucketSize_ << ", capacity " << bucketCapacity_ << ")";
            for (KeyItem **p = buckets_; p != buckets_ + bucketSize_; ++p, ++row) {
                std::cout << "      ["<<row<<"] " << *p << std::endl;
            }
            row = 0;
            std::cout << "  Key Items " << std::endl;
            for (typename std::list<KeyItem *>::iterator it = keyRows_.begin(), last = keyRows_.end(); it != last; ++it, ++row) {
                KeyItem *lastI = *it + keyRowSize_;
                std::cout << "   Key Row " << row <<  " (of size  " << keyRowSize_ << ")" << std::endl;
                for (KeyItem *p = *it; p != lastI; ++p) {
                    std::cout << "      @ " << p << " [" << p->key << ", @" << p->value <<"], next = " << p->next << std::endl;
                    if ((it == currentKeyRow_) && (p == nextKeyItem_ - 1)) {
                        std::cout << "      ^^^ this was the last valid item." << std::endl;
                        last = 0; break;
                    }
                }
                if (lastI == 0) break;
            }
            row = 0;
            std::cout << "  Value Items " << std::endl;
            for (typename std::list<ValueItem *>::iterator it = valueRows_.begin(), last = valueRows_.end(); it != last; ++it, ++row) {
                ValueItem *lastI = *it + valueRowSize_;
                std::cout << "   Value Row " << row <<  " (of size  " << valueRowSize_ << ")" << std::endl;
                for (ValueItem *p = *it; p != lastI; ++p) {
                    std::cout << "      @ " << p << " [" << p->value <<"], next = " << p->next << std::endl;
                    if ((it == currentValueRow_) && (p == nextValueItem_ - 1)) {
                        std::cout << "      ^^^ this was the last valid item." << std::endl;
                        last = 0; break;
                    }
                }
                if (lastI == 0) break;
            }
            std::cout << "  End of dump" << std::endl; 
            
        }
};

template<typename K, typename V, typename Hasher, typename Equals, typename Alloc>
SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::SimpleAllocHashMultiMap(size_t buckets, size_t keyRowSize, size_t valueRowSize, size_t maxRows) :
    bucketSize_(buckets), bucketCapacity_(bucketSize_),
    keyRowSize_(keyRowSize),
    valueRowSize_(valueRowSize),
    maxRows_(maxRows)
{
    buckets_ = ptrAlloc_.allocate(bucketCapacity_);
    keyRows_.push_back(keyAlloc_.allocate(keyRowSize_));
    valueRows_.push_back(valueAlloc_.allocate(valueRowSize_));
    clear();
}
template<typename K, typename V, typename Hasher, typename Equals, typename Alloc>
SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::~SimpleAllocHashMultiMap() 
{
    for (typename std::list<KeyItem *>::iterator it = keyRows_.begin(), last = keyRows_.end(); it != last; ++it) {
        keyAlloc_.deallocate(*it, keyRowSize_);
    }
    for (typename std::list<ValueItem *>::iterator it = valueRows_.begin(), last = valueRows_.end(); it != last; ++it) {
        valueAlloc_.deallocate(*it, valueRowSize_);
    }
    ptrAlloc_.deallocate(buckets_, bucketCapacity_);
}

template<typename K, typename V, typename Hasher, typename Equals, typename Alloc>
void 
SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::freeRows() {
   if (keyRows_.size() > maxRows_) {
        //std::cerr << "Freeing key rows, current size is " << keyRows_.size() << std::endl;
        typename std::list<KeyItem *>::iterator it = keyRows_.begin(), last = keyRows_.end(); 
        for (std::advance(it, maxRows_); it != last; ++it) {
            keyAlloc_.deallocate(*it, keyRowSize_);
        }
        keyRows_.resize(maxRows_);
   } 
   if (valueRows_.size() > maxRows_) {
        //std::cerr << "Freeing value rows, current size is " << valueRows_.size() << std::endl;
        typename std::list<ValueItem *>::iterator it = valueRows_.begin(), last = valueRows_.end(); 
        for (std::advance(it, maxRows_); it != last; ++it) {
            valueAlloc_.deallocate(*it, valueRowSize_);
        }
        valueRows_.resize(maxRows_);
   } 
}

template<typename K, typename V, typename Hasher, typename Equals, typename Alloc>
typename SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::KeyItem * 
SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::push_back_(K const &key, KeyItem *next) { 
    if (nextKeyItem_ == keyEndMarker_) {
        ++currentKeyRow_; 
        if (currentKeyRow_ == keyRows_.end()) {
            keyRows_.push_back(keyAlloc_.allocate(keyRowSize_));
            currentKeyRow_ = keyRows_.end(); --currentKeyRow_; // end - 1 doesn't work!
        }
        nextKeyItem_  = *currentKeyRow_;
        keyEndMarker_ = nextKeyItem_ + keyRowSize_; 
    }
    keyAlloc_.construct(nextKeyItem_, KeyItem(next, key, 0));
    nextKeyItem_++;
    return (nextKeyItem_-1);
}
template<typename K, typename V, typename Hasher, typename Equals, typename Alloc>
typename SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::ValueItem * 
SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::push_back_(value_ref value, ValueItem *next) { 
    if (nextValueItem_ == valueEndMarker_) {
        ++currentValueRow_; 
        if (currentValueRow_ == valueRows_.end()) {
            valueRows_.push_back(valueAlloc_.allocate(valueRowSize_));
            currentValueRow_ = valueRows_.end(); --currentValueRow_; // end - 1 doesn't work!
        }
        nextValueItem_  = *currentValueRow_;
        valueEndMarker_ = nextValueItem_ + valueRowSize_; 
    }
    valueAlloc_.construct(nextValueItem_, ValueItem(next, value));
    nextValueItem_++;
    return (nextValueItem_-1);
}

template<typename K, typename V, typename Hasher, typename Equals, typename Alloc>
typename SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::KeyItem &
SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::find_or_insert_(K const &key) {
    //std::cout << "Find or insert for key " << key << std::endl;
    size_t hash = hasher_(key);
    KeyItem * & buck = buckets_[hash % bucketSize_];
    KeyItem * curr = buck;
    while (curr) {
        if (eq_(curr->key, key)) {
            //std::cout << "  Key " << key << " was found." << std::endl;
            return *curr;
        } 
        curr = curr->next;
    } 
    buck = push_back_(key, buck);
    return *buck;
}

template<typename K, typename V, typename Hasher, typename Equals, typename Alloc>
void SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::insert(K const &key, value_ref value) {
    //std::cout << "Pushing back value " << value << " for key " << key << std::endl;
    KeyItem &k = find_or_insert_(key);
    //std::cout << "Key " << (k.value ? "exists" : " is new") << std::endl;
    k.value = push_back_(value, k.value);
}

template<typename K, typename V, typename Hasher, typename Equals, typename Alloc>
typename SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::value_iterator
SimpleAllocHashMultiMap<K,V,Hasher,Equals,Alloc>::values(K const &key) {
    //std::cout << "Gettinv values for key " << key << std::endl;
    size_t hash = hasher_(key);
    for (KeyItem * curr = buckets_[hash % bucketSize_]; curr; curr = curr->next) {
        if (eq_(curr->key, key)) return value_iterator(curr->value);
    }
    return value_iterator();
}


/*** Very very simple map implementation
 *   It's just a std::vector<pair<key,value>>, and the operator[] does a linear search to find the key (it's O(N) time, both if the key exists and if it doesn't)
 *   Anyway, if your map is very small and if you clear it often, it performs better than more complex variants
 *   Semantics is as std::map, except that only very few methods are implemented.
 * */
template<typename K, typename V>
class UnsortedDumbVectorMap {
    public:
        typedef std::pair<K,V> value_type;
        typedef typename std::vector<value_type>::const_iterator const_iterator;
        typedef typename std::vector<value_type>::iterator       iterator; // but please don't mutate the keys

        void clear() { data_.clear(); }
        bool empty() const { return data_.empty(); }
        const_iterator begin() const { return data_.begin(); } 
        const_iterator end()   const { return data_.end(); } 
        iterator begin()  { return data_.begin(); } 
        iterator end()    { return data_.end(); } 
        
        V & operator[](const K &k) {
            for (typename std::vector<value_type>::iterator it = data_.begin(), ed = data_.end(); it != ed; ++it) {
                if (it->first == k) return it->second;
            }
            data_.push_back(value_type(k,V()));
            return data_.back().second;
        }


        UnsortedDumbVectorMap() {}
        
    private:
        std::vector<value_type> data_;

};

} // namespace 

#endif