#ifndef CYGONCE_MEMALLOC_MVARIMPL_INL
#define CYGONCE_MEMALLOC_MVARIMPL_INL

//==========================================================================
//
//      mvarimpl.inl
//
//      Memory pool with variable block class declarations
//
//==========================================================================
//####ECOSGPLCOPYRIGHTBEGIN####
// -------------------------------------------
// This file is part of eCos, the Embedded Configurable Operating System.
// Copyright (C) 1998, 1999, 2000, 2001, 2002 Red Hat, Inc.
//
// eCos is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 or (at your option) any later version.
//
// eCos is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License along
// with eCos; if not, write to the Free Software Foundation, Inc.,
// 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
//
// As a special exception, if other files instantiate templates or use macros
// or inline functions from this file, or you compile this file and link it
// with other works to produce a work based on this file, this file does not
// by itself cause the resulting work to be covered by the GNU General Public
// License. However the source code for this file must still be made available
// in accordance with section (3) of the GNU General Public License.
//
// This exception does not invalidate any other reasons why a work based on
// this file might be covered by the GNU General Public License.
//
// Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
// at http://sources.redhat.com/ecos/ecos-license/
// -------------------------------------------
//####ECOSGPLCOPYRIGHTEND####
//==========================================================================
//#####DESCRIPTIONBEGIN####
//
// Author(s):    hmt
// Contributors: jlarmour
// Date:         2000-06-12
// Purpose:      Define Mvarimpl class interface
// Description:  Inline class for constructing a variable block allocator
// Usage:        #include <cyg/memalloc/mvarimpl.hxx>
//
//
//####DESCRIPTIONEND####
//
//==========================================================================

#include <pkgconf/memalloc.h>
#include <cyg/memalloc/mvarimpl.hxx>

#include <cyg/infra/cyg_ass.h>           // assertion support
#include <cyg/infra/cyg_trac.h>          // tracing support

// Simple allocator

// The free list is stored on a doubly linked list, each member of
// which is stored in the body of the free memory.  The head of the
// list has the same structure but its size field is zero.  This
// resides in the memory pool structure.  Always having at least one
// item on the list simplifies the alloc and free code.

// 
inline cyg_int32
Cyg_Mempool_Variable_Implementation::roundup( cyg_int32 size )
{

    size += sizeof(struct memdq);
    size = (size + alignment - 1) & -alignment;
    return size;
}

inline struct Cyg_Mempool_Variable_Implementation::memdq *
Cyg_Mempool_Variable_Implementation::addr2memdq( cyg_uint8 *addr )
{
    struct memdq *dq;
    dq = (struct memdq *)(roundup((cyg_int32)addr) - sizeof(struct memdq));
    return dq;
}

inline struct Cyg_Mempool_Variable_Implementation::memdq *
Cyg_Mempool_Variable_Implementation::alloc2memdq( cyg_uint8 *addr )
{
    return (struct memdq *)(addr - sizeof(struct memdq));
}

inline cyg_uint8 *
Cyg_Mempool_Variable_Implementation::memdq2alloc( struct memdq *dq )
{
    return ((cyg_uint8 *)dq + sizeof(struct memdq));
}

// -------------------------------------------------------------------------

inline void
Cyg_Mempool_Variable_Implementation::insert_free_block( struct memdq *dq )
{
    struct memdq *hdq=&head;

    freemem += dq->size;
#ifdef CYGSEM_MEMALLOC_ALLOCATOR_VARIABLE_COALESCE
// For simple coalescing have the free list be sorted by memory base address
    struct memdq *idq;
    
    for (idq = hdq->next; idq != hdq; idq = idq->next) {
        if (idq > dq)
            break;
    }
    // we want to insert immediately before idq
    dq->next = idq;
    dq->prev = idq->prev;
    idq->prev = dq;
    dq->prev->next = dq;

    // Now do coalescing, but leave the head of the list alone.
    if (dq->next != hdq && (char *)dq + dq->size == (char *)dq->next) {
        dq->size += dq->next->size;
        dq->next = dq->next->next;
        dq->next->prev = dq;
    }
    if (dq->prev != hdq && (char *)dq->prev + dq->prev->size == (char *)dq) {
        dq->prev->size += dq->size;
        dq->prev->next = dq->next;
        dq->next->prev = dq->prev;
        dq = dq->prev;
    }
#else
    dq->prev = hdq;
    dq->next = hdq->next;
    hdq->next = dq;
    dq->next->prev=dq;
#endif
}

// -------------------------------------------------------------------------

inline
Cyg_Mempool_Variable_Implementation::Cyg_Mempool_Variable_Implementation(
        cyg_uint8 *base,
        cyg_int32 size,
        CYG_ADDRWORD align )
{
    CYG_REPORT_FUNCTION();

    CYG_ASSERT( align > 0, "Bad alignment" );
    CYG_ASSERT(0!=align ,"align is zero");
    CYG_ASSERT(0==(align & align-1),"align not a power of 2");

    if ((unsigned)size < sizeof(struct memdq)) {
        bottom = NULL;
        return;
    }

    obase=base;
    osize=size;

    alignment = align;
    while (alignment < (cyg_int32)sizeof(struct memdq))
        alignment += alignment;
    CYG_ASSERT(0==(alignment & alignment-1),"alignment not a power of 2");

    // the memdq for each allocation is always positioned immediately before
    // an aligned address, so that the allocation (i.e. what eventually gets
    // returned from alloc()) is at the correctly aligned address
    // Therefore bottom is set to the lowest available address given the size of
    // struct memdq and the alignment. 
    bottom = (cyg_uint8 *)addr2memdq(base);

    // because we split free blocks by allocating memory from the end, not
    // the beginning, then to preserve alignment, the *top* must also be
    // aligned such that (top-bottom) is a multiple of the alignment
    top = (cyg_uint8 *)((cyg_int32)(base+size+sizeof(struct memdq)) & -alignment) -
        sizeof(struct memdq);
    
    CYG_ASSERT( top > bottom , "heap too small" );
    CYG_ASSERT( top <= (base+size), "top too large" );
    CYG_ASSERT( ((cyg_int32)(top+sizeof(struct memdq)) & alignment-1)==0,
                "top badly aligned" );

    struct memdq *hdq = &head, *dq = (struct memdq *)bottom;
    
    CYG_ASSERT( ((cyg_int32)memdq2alloc(dq) & alignment-1)==0,
                 "bottom badly aligned" );

    hdq->prev = hdq->next = dq;
    hdq->size = 0;
    dq->prev = dq->next = hdq;

    freemem = dq->size = top - bottom;
}

// -------------------------------------------------------------------------

inline
Cyg_Mempool_Variable_Implementation::~Cyg_Mempool_Variable_Implementation()
{
}

// -------------------------------------------------------------------------
// allocation is simple
// First we look down the free list for a large enough block
// If we find a block the right size, we unlink the block from
//    the free list and return a pointer to it.
// If we find a larger block, we chop a piece off the end
//    and return that
// Otherwise we will eventually get back to the head of the list
//    and return NULL
inline cyg_uint8 *
Cyg_Mempool_Variable_Implementation::try_alloc( cyg_int32 size )
{
    struct memdq *dq = &head;
    cyg_uint8 *alloced;

    CYG_REPORT_FUNCTION();

    //  Allow uninitialised (zero sized) heaps because they could exist as a
    //  quirk of the MLT setup where a dynamically sized heap is at the top of
    //  memory.
    if (NULL == bottom)