// Copyright (c) 2016 Baidu, Inc.
// 
// Licensed 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.

// Author: Ge,Jun (gejun@baidu.com)
// Date: Sat Dec  3 13:11:32 CST 2016

#ifndef BUTIL_POOLED_MAP_H
#define BUTIL_POOLED_MAP_H

#include "butil/single_threaded_pool.h"
#include <new>
#include <map>

namespace butil {
namespace details {
template <class T1, size_t BLOCK_SIZE> class PooledAllocator;
}

// A drop-in replacement for std::map to improve insert/erase performance slightly
//
// When do use PooledMap?
//   A std::map with 10~100 elements. insert/erase performance will be slightly
//   improved. Performance of find() is unaffected.
// When do NOT use PooledMap?
//   When the std::map has less that 10 elements, PooledMap is probably slower
//   because it allocates BLOCK_SIZE memory at least. When the std::map has more than
//   100 elements, you should use butil::FlatMap instead.

// insert/erase comparisons between several maps:
// [ value = 8 bytes ]
// Sequentially inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 15/114/54/60
// Sequentially erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/123/56/37
// Sequentially inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 9/92/56/54
// Sequentially erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 3/68/51/35
// Sequentially inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 10/99/63/54
// Sequentially erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/73/54/35
// [ value = 32 bytes ]
// Sequentially inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 14/107/57/57
// Sequentially erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/75/53/37
// Sequentially inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 13/94/55/53
// Sequentially erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/67/50/37
// Sequentially inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 13/102/63/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 35/160/96/98
// Sequentially erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/96/53/42
// Sequentially inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 30/159/98/98
// Sequentially erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/82/49/43
// Sequentially inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 29/155/114/116
// Sequentially erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/81/53/43

// [ value = 8 bytes ]
// Randomly inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 13/168/103/59
// Randomly erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/159/125/37
// Randomly inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 10/157/115/54
// Randomly erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/175/138/36
// Randomly inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 11/219/177/56
// Randomly erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/229/207/47
// [ value = 32 bytes ]
// Randomly inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 17/178/112/57
// Randomly erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/149/117/38
// Randomly inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 15/169/135/54
// Randomly erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/157/129/39
// Randomly inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 19/242/203/55
// Randomly erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/233/218/54
// [ value = 128 bytes ]
// Randomly inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 36/214/145/96
// Randomly erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/166/122/53
// Randomly inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 36/230/174/100
// Randomly erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/193/153/65
// Randomly inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 45/304/270/115
// Randomly erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/299/246/88

template <typename K, typename V, size_t BLOCK_SIZE = 512,
          typename C = std::less<K> >
class PooledMap
    : public std::map<K, V, C, details::PooledAllocator<std::pair<const K, V>, BLOCK_SIZE> > {
    
};

namespace details {
// Specialize for void
template <size_t BLOCK_SIZE>
class PooledAllocator<void, BLOCK_SIZE> {
public:
    typedef void * pointer;
    typedef const void* const_pointer;
    typedef void value_type;
    template <class U1> struct rebind {
        typedef PooledAllocator<U1, BLOCK_SIZE> other;
    };
};

template <class T1, size_t BLOCK_SIZE>
class PooledAllocator {
public:
    typedef T1 value_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T1* pointer;
    typedef const T1* const_pointer;
    typedef T1& reference;
    typedef const T1& const_reference;
    template <class U1> struct rebind {
        typedef PooledAllocator<U1, BLOCK_SIZE> other;
    };
    
public:
    PooledAllocator() {}
    PooledAllocator(const PooledAllocator&) {}
    template <typename U1, size_t BS2>
    PooledAllocator(const PooledAllocator<U1, BS2>&) {}
    void operator=(const PooledAllocator&) {}
    template <typename U1, size_t BS2>
    void operator=(const PooledAllocator<U1, BS2>&) {}

    void swap(PooledAllocator& other) { _pool.swap(other._pool); }

    // Convert references to pointers.
    pointer address(reference r) const { return &r; }
    const_pointer address(const_reference r) const { return &r; }

    // Allocate storage for n values of T1.
    pointer allocate(size_type n, PooledAllocator<void, 0>::const_pointer = 0) {
        if (n == 1) {
            return (pointer)_pool.get();
        } else {
            return (pointer)malloc(n * sizeof(T1));
        }
    }

    // Deallocate storage obtained by a call to allocate.
    void deallocate(pointer p, size_type n) {
        if (n == 1) {
            return _pool.back(p);
        } else {
            free(p);
        }
    }

    // Return the largest possible storage available through a call to allocate.
    size_type max_size() const { return 0xFFFFFFFF / sizeof(T1); }

    void construct(pointer ptr) { ::new (ptr) T1; }
    void construct(pointer ptr, const T1& val) { ::new (ptr) T1(val); }
    template <class U1> void construct(pointer ptr, const U1& val)
    { ::new (ptr) T1(val); }

    void destroy(pointer p) { p->T1::~T1(); }

private:
    butil::SingleThreadedPool<sizeof(T1), BLOCK_SIZE, 1> _pool;
};

// Return true if b could be used to deallocate storage obtained through a
// and vice versa. It's clear that our allocator can't be exchanged.
template <typename T1, size_t S1, typename T2, size_t S2>
bool operator==(const PooledAllocator<T1, S1>&, const PooledAllocator<T2, S2>&)
{ return false; }
template <typename T1, size_t S1, typename T2, size_t S2>
bool operator!=(const PooledAllocator<T1, S1>& a, const PooledAllocator<T2, S2>& b)
{ return !(a == b); }

} // namespace details
} // namespace butil

// Since this allocator can't be exchanged(check impl. of operator==) nor
// copied, specializing swap() is a must to make map.swap() work.
#if !defined(BUTIL_CXX11_ENABLED)
#include <algorithm>  // std::swap until C++11
#else
#include <utility>    // std::swap since C++11
#endif

namespace std {
template <class T1, size_t BLOCK_SIZE>
inline void swap(::butil::details::PooledAllocator<T1, BLOCK_SIZE> &lhs,
                 ::butil::details::PooledAllocator<T1, BLOCK_SIZE> &rhs){
    lhs.swap(rhs);
}
}  // namespace std

#endif  // BUTIL_POOLED_MAP_H