src/butil/containers/flat_map.h

// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.

// Date: Wed Nov 27 12:59:20 CST 2013

// This closed addressing hash-map puts first linked node in bucket array
// directly to save an extra memory indirection. As a result, this map yields
// close performance to raw array on nearly all operations, probably being the
// fastest hashmap for small-sized key/value ever.
//
// Performance comparisons between several maps:
//  [ value = 8 bytes ]
//  Sequentially inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 11/108/55/58
//  Sequentially erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/123/55/37
//  Sequentially inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 10/92/55/54
//  Sequentially erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/67/51/35
//  Sequentially inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 10/100/66/54
//  Sequentially erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/72/55/35
//  [ value = 32 bytes ]
//  Sequentially inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 14/108/56/56
//  Sequentially erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/77/53/38
//  Sequentially inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 14/94/54/53
//  Sequentially erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/66/49/36
//  Sequentially inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 13/106/62/54
//  Sequentially erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/69/53/36
//  [ value = 128 bytes ]
//  Sequentially inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 31/182/96/96
//  Sequentially erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 8/117/51/44
//  Sequentially inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 29/191/100/97
//  Sequentially erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/100/49/44
//  Sequentially inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 30/184/113/114
//  Sequentially erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/99/52/43
//  [ value = 8 bytes ]
//  Randomly inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 11/171/108/60
//  Randomly erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 8/158/126/37
//  Randomly inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 10/159/117/54
//  Randomly erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/153/135/36
//  Randomly inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 12/223/180/55
//  Randomly erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/237/210/48
//  [ value = 32 bytes ]
//  Randomly inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 16/179/108/57
//  Randomly erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/157/120/38
//  Randomly inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 15/168/127/54
//  Randomly erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/164/135/39
//  Randomly inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 19/241/201/56
//  Randomly erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/235/218/54
//  [ value = 128 bytes ]
//  Randomly inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 35/242/154/97
//  Randomly erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/185/119/56
//  Randomly inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 35/262/182/99
//  Randomly erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/215/157/66
//  Randomly inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 44/330/278/114
//  Randomly erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/307/242/90
//  [ value = 8 bytes ]
//  Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/51/52/13
//  Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/98/82/14
//  Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/175/170/14
//  [ value = 32 bytes ]
//  Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 3/52/52/14
//  Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 3/84/82/13
//  Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 3/164/156/14
//  [ value = 128 bytes ]
//  Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 3/54/53/14
//  Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/88/90/13
//  Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/178/185/14
//  [ value = 8 bytes ]
//  Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/51/49/14
//  Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/86/94/14
//  Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/177/171/14
//  [ value = 32 bytes ]
//  Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 3/51/53/14
//  Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 3/98/82/13
//  Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 3/163/156/14
//  [ value = 128 bytes ]
//  Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 3/55/53/14
//  Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/88/89/13
//  Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/177/185/14

#ifndef BUTIL_FLAT_MAP_H
#define BUTIL_FLAT_MAP_H

#include <stdint.h>
#include <functional>
#include <iostream>                               // std::ostream
#include "butil/type_traits.h"
#include "butil/logging.h"
#include "butil/find_cstr.h"
#include "butil/single_threaded_pool.h"            // SingleThreadedPool
#include "butil/containers/hash_tables.h"          // hash<>
#include "butil/bit_array.h"                       // bit_array_*
#include "butil/strings/string_piece.h"            // StringPiece

namespace butil {

template <typename _Map, typename _Element> class FlatMapIterator;
template <typename _Map, typename _Element> class SparseFlatMapIterator;
template <typename K, typename T> class FlatMapElement;
struct FlatMapVoid {}; // Replace void which is not constructible.
template <typename K> struct DefaultHasher;
template <typename K> struct DefaultEqualTo;

struct BucketInfo {
    size_t longest_length;
    double average_length;
};

// NOTE: Objects stored in FlatMap MUST be copyable.
template <typename _K, typename _T,
          // Compute hash code from key.
          // Use src/butil/third_party/murmurhash3 to make better distributions.
          typename _Hash = DefaultHasher<_K>,
          // Test equivalence between stored-key and passed-key.
          // stored-key is always on LHS, passed-key is always on RHS.
          typename _Equal = DefaultEqualTo<_K>,
          bool _Sparse = false,
          typename _Alloc = PtAllocator>
class FlatMap {
public:
    typedef _K key_type;
    typedef _T mapped_type;
    typedef _Alloc allocator_type;
    typedef FlatMapElement<_K, _T> Element;
    typedef typename Element::value_type value_type;
    typedef typename conditional<
        _Sparse, SparseFlatMapIterator<FlatMap, value_type>,
        FlatMapIterator<FlatMap, value_type> >::type iterator;
    typedef typename conditional<
        _Sparse, SparseFlatMapIterator<FlatMap, const value_type>, 
        FlatMapIterator<FlatMap, const value_type> >::type const_iterator;
    typedef _Hash hasher;
    typedef _Equal key_equal;
    struct PositionHint {
        size_t nbucket;
        size_t offset;
        bool at_entry;
        key_type key;
    };
    
    FlatMap(const hasher& hashfn = hasher(), 
            const key_equal& eql = key_equal(),
            const allocator_type& alloc = allocator_type());
    ~FlatMap();
    FlatMap(const FlatMap& rhs);    
    void operator=(const FlatMap& rhs);
    void swap(FlatMap & rhs);

    // Must be called to initialize this map, otherwise insert/operator[]
    // crashes, and seek/erase fails.
    // `nbucket' is the initial number of buckets. `load_factor' is the 
    // maximum value of size()*100/nbucket, if the value is reached, nbucket
    // will be doubled and all items stored will be rehashed which is costly.
    // Choosing proper values for these 2 parameters reduces costs.
    int init(size_t nbucket, u_int load_factor = 80);
    
    // Insert a pair of |key| and |value|. If size()*100/bucket_count() is 
    // more than load_factor(), a resize() will be done.
    // Returns address of the inserted value, NULL on error.
    mapped_type* insert(const key_type& key, const mapped_type& value);

    // Insert a pair of {key, value}. If size()*100/bucket_count() is
    // more than load_factor(), a resize() will be done.
    // Returns address of the inserted value, NULL on error.
    mapped_type* insert(const std::pair<key_type, mapped_type>& kv);

    // Remove |key| and the associated value
    // Returns: 1 on erased, 0 otherwise.
    template <typename K2>
    size_t erase(const K2& key, mapped_type* old_value = NULL);

    // Remove all items. Allocated spaces are NOT returned by system.
    void clear();

    // Remove all items and return all allocated spaces to system.
    void clear_and_reset_pool();
        
    // Search for the value associated with |key|
    // Returns: address of the value
    template <typename K2> mapped_type* seek(const K2& key) const;

    // Get the value associated with |key|. If |key| does not exist,
    // insert with a default-constructed value. If size()*100/bucket_count()
    // is more than load_factor, a resize will be done.
    // Returns reference of the value
    mapped_type& operator[](const key_type& key);

    // Resize this map. This is optional because resizing will be triggered by
    // insert() or operator[] if there're too many items.
    // Returns successful or not.
    bool resize(size_t nbucket);
    
    // Iterators
    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;

    // Iterate FlatMap inconsistently in more-than-one passes. This is used
    // in multi-threaded environment to divide the critical sections of
    // iterating big maps into smaller ones. "inconsistently" means that:
    //  * elements added during iteration may be missed.
    //  * some elements may be iterated more than once.
    //  * iteration is restarted at beginning when the map is resized.
    // Example: (copying all keys in multi-threaded environment)
    //   LOCK;
    //   size_t n = 0;
    //   for (Map::const_iterator it = map.begin(); it != map.end(); ++it) {
    //     if (++n >= 256/*max iterated one pass*/) {
    //       Map::PositionHint hint;
    //       map.save_iterator(it, &hint);
    //       n = 0;
    //       UNLOCK;
    //       LOCK;
    //       it = map.restore_iterator(hint);
    //       if (it == map.begin()) { // resized
    //         keys->clear();
    //       }
    //       if (it == map.end()) {
    //         break;
    //       }
    //     }
    //     keys->push_back(it->first);
    //   }
    //   UNLOCK;
    void save_iterator(const const_iterator&, PositionHint*) const;
    const_iterator restore_iterator(const PositionHint&) const;

    // True if init() was successfully called.
    bool initialized() const { return _buckets != NULL; }

    bool empty() const { return _size == 0; }
    size_t size() const { return _size; }
    size_t bucket_count() const { return _nbucket; }
    u_int load_factor () const { return _load_factor; }

    // Returns #nodes of longest bucket in this map. This scans all buckets.
    BucketInfo bucket_info() const;

    struct Bucket {
        explicit Bucket(const _K& k) : next(NULL)
        { new (element_spaces) Element(k); }
        Bucket(const Bucket& other) : next(NULL)
        { new (element_spaces) Element(other.element()); }
        bool is_valid() const { return next != (const Bucket*)-1UL; }
        void set_invalid() { next = (Bucket*)-1UL; }
        // NOTE: Only be called when is_valid() is true.
        Element& element() {
            void* spaces = element_spaces; // Suppress strict-aliasing
            return *reinterpret_cast<Element*>(spaces);
        }
        const Element& element() const {
            const void* spaces = element_spaces;
            return *reinterpret_cast<const Element*>(spaces);
        }
        Bucket* next;
        char element_spaces[sizeof(Element)];
    };

    allocator_type& get_allocator() { return _pool.get_allocator(); }

private:
template <typename _Map, typename _Element> friend class FlatMapIterator;
template <typename _Map, typename _Element> friend class SparseFlatMapIterator;
    // True if buckets need to be resized before holding `size' elements.
    inline bool is_too_crowded(size_t size) const
    { return size * 100 >= _nbucket * _load_factor; }
        
    size_t _size;
    size_t _nbucket;
    Bucket* _buckets;
    uint64_t* _thumbnail;
    u_int _load_factor;
    hasher _hashfn;
    key_equal _eql;
    SingleThreadedPool<sizeof(Bucket), 1024, 16, allocator_type> _pool;
};

template <typename _K,
          typename _Hash = DefaultHasher<_K>,
          typename _Equal = DefaultEqualTo<_K>,
          bool _Sparse = false,
          typename _Alloc = PtAllocator>
class FlatSet {
public:
    typedef FlatMap<_K, FlatMapVoid, _Hash, _Equal, _Sparse, _Alloc> Map;
    typedef typename Map::key_type key_type;
    typedef typename Map::value_type value_type;
    typedef typename Map::Bucket Bucket;
    typedef typename Map::iterator iterator;
    typedef typename Map::const_iterator const_iterator;
    typedef typename Map::hasher hasher;
    typedef typename Map::key_equal key_equal;
    typedef typename Map::allocator_type allocator_type;
    
    FlatSet(const hasher& hashfn = hasher(), 
            const key_equal& eql = key_equal(),
            const allocator_type& alloc = allocator_type())
        : _map(hashfn, eql, alloc) {}
    void swap(FlatSet & rhs) { _map.swap(rhs._map); }

    int init(size_t nbucket, u_int load_factor = 80)
    { return _map.init(nbucket, load_factor); }

    const void* insert(const key_type& key)
    { return _map.insert(key, FlatMapVoid()); }

    template <typename K2>
    size_t erase(const K2& key) { return _map.erase(key, NULL); }

    void clear() { return _map.clear(); }
    void clear_and_reset_pool() { return _map.clear_and_reset_pool(); }

    template <typename K2>
    const void* seek(const K2& key) const { return _map.seek(key); }

    bool resize(size_t nbucket) { return _map.resize(nbucket); }
    
    iterator begin() { return _map.begin(); }
    iterator end() { return _map.end(); }
    const_iterator begin() const { return _map.begin(); }
    const_iterator end() const { return _map.end(); }

    bool initialized() const { return _map.initialized(); }
    bool empty() const { return _map.empty(); }
    size_t size() const { return _map.size(); }
    size_t bucket_count() const { return _map.bucket_count(); }
    u_int load_factor () const { return _map.load_factor(); }
    BucketInfo bucket_info() const { return _map.bucket_info(); }

private:
    Map _map;
};

template <typename _K, typename _T,
          typename _Hash = DefaultHasher<_K>,
          typename _Equal = DefaultEqualTo<_K> >
class SparseFlatMap : public FlatMap<_K, _T, _Hash, _Equal, true> {
};

template <typename _K,
          typename _Hash = DefaultHasher<_K>,
          typename _Equal = DefaultEqualTo<_K> >
class SparseFlatSet : public FlatSet<_K, _Hash, _Equal, true> {
};

// Implement FlatMapElement
template <typename K, typename T>
class FlatMapElement {
public:
    typedef std::pair<const K, T> value_type;
    // NOTE: Have to initialize _value in this way which is treated by GCC
    // specially that _value is zeroized(POD) or constructed(non-POD). Other
    // methods do not work. For example, if we put _value into the std::pair
    // and do initialization by calling _pair(k, T()), _value will be copy
    // constructed from the defaultly constructed instance(not zeroized for
    // POD) which is wrong generally.
    explicit FlatMapElement(const K& k) : _key(k), _value(T()) {}
    //                                             ^^^^^^^^^^^
    const K& first_ref() const { return _key; }
    T& second_ref() { return _value; }
    T&& second_movable_ref() { return std::move(_value); }
    value_type& value_ref() { return *reinterpret_cast<value_type*>(this); }
    inline static const K& first_ref_from_value(const value_type& v)
    { return v.first; }
    inline static const T& second_ref_from_value(const value_type& v)
    { return v.second; }
    inline static T&& second_movable_ref_from_value(value_type& v)
    { return std::move(v.second); }

private:
    const K _key;
    T _value;
};

template <typename K>
class FlatMapElement<K, FlatMapVoid> {
public:
    typedef const K value_type;
    explicit FlatMapElement(const K& k) : _key(k) {}
    const K& first_ref() const { return _key; }
    FlatMapVoid& second_ref() { return second_ref_from_value(_key); }
    FlatMapVoid& second_movable_ref() { return second_ref(); }
    value_type& value_ref() { return _key; }
    inline static const K& first_ref_from_value(value_type& v) { return v; }
    inline static FlatMapVoid& second_ref_from_value(value_type&) {
        static FlatMapVoid dummy;
        return dummy;
    }
    inline static const FlatMapVoid& second_movable_ref_from_value(value_type& v) {
        return second_ref_from_value(v);
    }
private:
    K _key;
};

// Implement DefaultHasher and DefaultEqualTo
template <typename K>
struct DefaultHasher : public BUTIL_HASH_NAMESPACE::hash<K> {
};

template <>
struct DefaultHasher<std::string> {
    std::size_t operator()(const butil::StringPiece& s) const {
        std::size_t result = 0;
        for (butil::StringPiece::const_iterator
                 i = s.begin(); i != s.end(); ++i) {
            result = result * 101 + *i;
        }
        return result;
    }
    std::size_t operator()(const char* s) const {
        std::size_t result = 0;
        for (; *s; ++s) {
            result = result * 101 + *s;
        }
        return result;
    }
    std::size_t operator()(const std::string& s) const {
        std::size_t result = 0;
        for (std::string::const_iterator i = s.begin(); i != s.end(); ++i) {
            result = result * 101 + *i;
        }
        return result;        
    }
};

template <typename K>
struct DefaultEqualTo : public std::equal_to<K> {
};

template <>
struct DefaultEqualTo<std::string> {
    bool operator()(const std::string& s1, const std::string& s2) const
    { return s1 == s2; }
    bool operator()(const std::string& s1, const butil::StringPiece& s2) const
    { return s1 == s2; }
    bool operator()(const std::string& s1, const char* s2) const
    { return s1 == s2; }
};

// find_cstr and find_lowered_cstr
template <typename _T, typename _Hash, typename _Equal, bool _Sparse>
const _T* find_cstr(const FlatMap<std::string, _T, _Hash, _Equal, _Sparse>& m,
                    const char* key) {
    return m.seek(key);
}

template <typename _T, typename _Hash, typename _Equal, bool _Sparse>
_T* find_cstr(FlatMap<std::string, _T, _Hash, _Equal, _Sparse>& m,
              const char* key) {
    return m.seek(key);
}

template <typename _T, typename _Hash, typename _Equal, bool _Sparse>
const _T* find_cstr(const FlatMap<std::string, _T, _Hash, _Equal, _Sparse>& m,
                    const char* key, size_t length) {
    return m.seek(butil::StringPiece(key, length));
}

template <typename _T, typename _Hash, typename _Equal, bool _Sparse>
_T* find_cstr(FlatMap<std::string, _T, _Hash, _Equal, _Sparse>& m,
              const char* key, size_t length) {
    return m.seek(butil::StringPiece(key, length));
}

template <typename _T, typename _Hash, typename _Equal, bool _Sparse>
const _T* find_lowered_cstr(
    const FlatMap<std::string, _T, _Hash, _Equal, _Sparse>& m,
    const char* key) {
    return m.seek(*tls_stringmap_temp.get_lowered_string(key));
}

template <typename _T, typename _Hash, typename _Equal, bool _Sparse>
_T* find_lowered_cstr(FlatMap<std::string, _T, _Hash, _Equal, _Sparse>& m,
                      const char* key) {
    return m.seek(*tls_stringmap_temp.get_lowered_string(key));
}

template <typename _T, typename _Hash, typename _Equal, bool _Sparse>
const _T* find_lowered_cstr(
    const FlatMap<std::string, _T, _Hash, _Equal, _Sparse>& m,
    const char* key, size_t length) {
    return m.seek(*tls_stringmap_temp.get_lowered_string(key, length));
}

template <typename _T, typename _Hash, typename _Equal, bool _Sparse>
_T* find_lowered_cstr(FlatMap<std::string, _T, _Hash, _Equal, _Sparse>& m,
                      const char* key, size_t length) {
    return m.seek(*tls_stringmap_temp.get_lowered_string(key, length));
}

}  // namespace butil

#include "butil/containers/flat_map_inl.h"

#endif  //BUTIL_FLAT_MAP_H