// **********************************************************************
//
// Copyright (c) 2002
// IONA Technologies, Inc.
// Waltham, MA, USA
//
// All Rights Reserved
//
// **********************************************************************

#ifndef OB_ALLOCATOR_H
#define OB_ALLOCATOR_H

#ifdef HAVE_NEW
#    include <new>
#else
#    include <new.h>
#endif

#include <assert.h>
#include <stdlib.h>

#include <OB/STLConfig.h>

#define OB_STL_CHUNK_SIZE 10
#define OB_STL_CSIZE ((sizeof(T) < sizeof(Link)) ? sizeof(Link) : sizeof(T))

namespace OB 
{

namespace stl 
{

// A pointer to the next block of memory for objects of type T in the
// pool
// COMPILERFIX Should be a nested struct in allocator, but VC++
// 6.0 doesn't like this
class Link 
{
public:
    Link *next;
};

//
// A pool of pre-allocated memory for objects of type T.
//
// TODO:
//
// - Add support for handling allocation of more than one object.
//
// - Add algorithm for determining a "good" number of items to
//   allocate in one chunk.
//
template<class T>
class allocator
{
// COMPILERFIX: Sun's CC 5.1/AIX VAC++ 5.0 requires Align to be public
#if defined(__SUNPRO_CC) || defined(_AIX) 
public:
#else
private:
#endif

    // Force the alignment of the mem member.
    union Align
    {
#ifndef WIN32
	unsigned long long dummy;
#else
	unsigned __int64 dummy;
#endif
	char mem[OB_STL_CHUNK_SIZE * OB_STL_CSIZE];
    };

private:

    // A chunk of pre-allocated memory for objects of type T.
    // The pool is made of a linked list of these chunks.
    // The chunk itself contains a pointer to the next chunk. If there
    // is no "next" chunk, the pointer is 0.
    struct Chunk 
    {
        Chunk* next;
        Align mem;
    };

    // Pointer to the first free block of memory of size sizeof(T) that
    // exists within a chunk
    Link* head_;

    // Pointer to the first chunk of pre-allocated memory
    Chunk* chunks_;

    //
    // The static chunk member (to avoid dynamic allocation if only
    // few elements are allocated).
    //
    Chunk chunk_;

    // There are no more free blocks in any chunk, so we need to create a
    // new chunk at add it to the front of the list of chunks.
    // The blocks in the chunks are chained together, so that the Link in
    // one block points to the next block, and the head_ is set to point to
    // the first block in the chunk.
    void grow()
    {
	Chunk* n = chunks_ ? new Chunk : &chunk_;

        n -> next = chunks_;
        chunks_ = n;

        char* start = n -> mem.mem;
        char* last = &start[(OB_STL_CHUNK_SIZE-1) * OB_STL_CSIZE];
        
        for (char* p = start; p < last; p += OB_STL_CSIZE)
            reinterpret_cast<Link*>(p) -> next =
                reinterpret_cast<Link*>(p + OB_STL_CSIZE);

        reinterpret_cast<Link*>(last) -> next = 0;
        head_ = reinterpret_cast<Link*>(start);
    }
    
public:
    typedef T             value_type;
    typedef T*            pointer;
    typedef const T*      const_pointer;
    typedef T&            reference;
    typedef const T&      const_reference;
    typedef unsigned long size_type;
    
    //
    // Initialize the new allocator
    //
    allocator() : head_(0), chunks_(0)
    {
    }
    
    //
    // Destructor
    //
    ~allocator()
    {
	if(chunks_)
	{
	    Chunk* n = chunks_;
	    
	    while(n -> next)
	    {
		Chunk* p = n;
		n = n -> next;
		delete p;
	    }
	}
    }
    
    //
    // Return a pointer to a contiguous chunk of correctly aligned
    // memory with enough space for n items of type T.
    //
    pointer allocate(size_type n)
    {
        assert(n <= max_size());

        if(head_ == 0)
            grow();
        
        Link* p = head_;
        head_ = p -> next;

        return reinterpret_cast<pointer>(p);
    }

    //
    // Dispose of a contiguous chunk of memory that was returned
    // by this allocator.
    //
    void deallocate(pointer p, size_type n)
    {
        // We aren't handling blocks of more than one object
        assert(n <= max_size());

        Link *b = reinterpret_cast<Link*>(p);
        b -> next = head_;
        head_ = b;
    }
    
    //
    // Return the largest number of items that may be allocated in
    // a contiguous chunk by a call to 'allocate'.
    //
    size_type max_size()
    {
        return 1;
    }
    
    //
    // Initialize the memory at p by copy constructing from t.
    //
    void construct(pointer p, const T& t)
    {
        new ((void*) p) T(t);
    }
    
    //
    // Clean up (destruct) the object at p by calling ~T().
    //
    void destroy(pointer p)
    {
        ((T*) p) -> ~T();
    }
    
    //
    // Return the address of r.
    //
    pointer address(T& r)
    {
        return &r;
    }

    //
    // Return the address of r.
    //
    const_pointer address(const T& r)
    {
        return &r;
    }
}; // End class allocator

} // End namespace stl

} // End namespace OB


#endif
