/* Demonstration of custom allocators in C++ */
/* Copyright (C) 1992,2005 Joel Yliluoma (http://iki.fi/bisqwit/) */

#include <algorithm>

#define USE_STATIC_ALLOCATOR 1

/* This is an implementation of a memory allocator that allocates and frees
 * memory from a pool whose size has been fixed at compile-time and which
 * will be allocated by the operating system before this program starts
 * executing.
 * In Linux, each page of the buffer curiously is marked as "swapped"
 * (not stored in RAM, but not stored in swap either) until it's written
 * into the first time.
 */
template<typename T,int Max>
struct StaticAllocatorImplementation
{
    static void* Alloc(unsigned amount=1) throw(std::bad_alloc)
    {
        unsigned pos = FindArea(amount);
        if(pos+amount > Max)
        {
            throw std::bad_alloc();
        }
        
        std::fill_n(used+pos, amount, true);
        count += amount;
        if(pos == firstfree) { firstfree += amount; firstfree = Find1(); }
        
        void* ptr = buffer + sizeof(T)*(pos);
        return ptr;
    }
    static void Free(T* ptr, unsigned amount=1) throw()
    {
        char* byteptr = (char*)ptr;
        unsigned pos = (byteptr - buffer) / sizeof(T);

        if(pos < firstfree) firstfree=pos;

        std::fill_n(used+pos, amount, false);
        count -= amount;
    }
private:
    static inline unsigned FindArea(unsigned length) throw()
    {
        return std::search_n(used+firstfree,used+Max, length, false) - used;
    }
    static inline unsigned Find1() throw()
    {
        return std::find(used+firstfree,used+Max, false) - used;
    }

    static char buffer[Max*sizeof(T)];
    static bool used[Max];
    static unsigned firstfree,count;
};
template<typename T,int Max> char StaticAllocatorImplementation<T,Max>::buffer[];
template<typename T,int Max> bool StaticAllocatorImplementation<T,Max>::used[] = {false};
template<typename T,int Max> unsigned StaticAllocatorImplementation<T,Max>::count = 0;
template<typename T,int Max> unsigned StaticAllocatorImplementation<T,Max>::firstfree = 0;


/* This turns the StaticAllocatorImplementation into an "allocator"
 * that can be used in creation of STL objects.
 */
template<typename T,int Max>
struct StaticAllocator
{
    typedef T*       pointer;
    typedef const T* const_pointer;
    typedef T&       reference;
    typedef const T& const_reference;
    typedef unsigned size_type;
    typedef ptrdiff_t difference_type;
    
    StaticAllocator()                                throw() { }
    StaticAllocator(const StaticAllocator& )         throw() { }

    template<typename T2>
    StaticAllocator(const StaticAllocator<T2,Max>& ) throw() { }

    template<typename T2>
    struct rebind
    { typedef StaticAllocator<T2,Max> other; };
    
    inline bool operator==(const StaticAllocator& b) const throw() { return true; }    

    static pointer allocate(const size_type n, const void* = 0) throw(std::bad_alloc)
    {
        if(!n) return 0;

        /* This statement allocates "n * sizeof(T)" bytes of memory
         * and returns the pointer to the allocated memory.
         */
        return (T*)allocator.Alloc(n);
    }
    
    static void deallocate(const pointer p, const size_type n) throw()
    {
        /* This statement deallocates "n * sizeof(T)" bytes of memory
         * from the location pointed by "p". The number "n" is expected
         * to be the same as it was when the memory was allocated.
         */
        if(p&&n) allocator.Free(p, n);
    }
    
    static inline size_type max_size() throw() { return Max; }
    static void construct(const pointer p, const_reference val)
    {
        /* This statement constructs the object pointed by "p"
         * using the copy constructor with default value from "val".
         * "p" is expected to point into an uninitialized memory
         * region that is big enough to hold an instance of "T".
         * The value of "p" isn't changed.
         */
        new(p) T(val);
    }
    static void destroy(const pointer p)
    {
        /* This statement destructs the object pointed by "p".
         * After this call, "p" will point into an uninitialized
         * memory region that can be freed.
         * The value of "p" isn't changed.
         */
        p->~T();
    }

private:
    typedef StaticAllocatorImplementation<T,Max> Allocator;
    
    static Allocator allocator;
};
template<typename T,int Max>
StaticAllocatorImplementation<T,Max> StaticAllocator<T,Max>::allocator;



/* Demonstrate the usage of allocators. */
#include <iostream>
#include <string>
#include <map>

int main(void)
{
#ifdef USE_STATIC_ALLOCATOR
    /* Use the allocator for both the map and the string objects. */
    /* The map and the strings have their own pools to allocate from. */
    enum { MaxMapNodes = 3, MaxCharCount=54 };
    
    typedef std::basic_string<char,std::char_traits<char>,
                              StaticAllocator<char,MaxCharCount> > StringType;
    typedef std::map<StringType, unsigned,
                     std::less<StringType>,
                     StaticAllocator<std::pair<const StringType,unsigned>, MaxMapNodes>
                    > MapType;
#else
    typedef std::map<std::string, unsigned> MapType;
#endif
    
    /* Example code. */
    MapType tmp;
    
    static const char* words[] =
    {"kissa","koira","kissa","koira","kissa","kissa","koira","lehmä"};
    const unsigned nwords = sizeof(words)/sizeof(*words);
    for(unsigned a=0; a<nwords; ++a)
        ++tmp[words[a]];
    
    for(MapType::const_iterator i=tmp.begin(); i!=tmp.end(); ++i)
        std::cout << i->first << ": " << i->second << "\n";
    
    return 0;
    
}