//
// Copyright (C) 2000, 2001 Andrey Slepuhin <pooh@msu.ru>
//
// libp++ 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 of the License, or
// (at your option) any later version.
//
// libp++ 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 libp++; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
// $Source$
// $Revision$
// $Date$
// Author: Andrey Slepuhin <pooh@msu.ru>

#ifndef __pxx_heap_allocator_hh__
#define __pxx_heap_allocator_hh__

#include "pxx_heap.hh"
#include "pxx_allocator.hh"

namespace pxx {

//
// Heap-based allocator class. This allocator uses a modification of
// D.E.Knuth's twins algorithm.
class HeapAllocator :
  public Allocator,
  public Heap
{

private:
  //
  // Free memory block header structure
  struct BlockHeader
  {
    //
    // Block size
    uintptr_t size ;
    //
    // Pointer to the previous free block
    BlockHeader* prev ;
    //
    // Pointer to the next free block
    BlockHeader* next ;
    //
    // Constructor
    BlockHeader (BlockHeader* _prev, BlockHeader* _next, size_t _size = 0) ;

    NO_COPY_CTOR(BlockHeader)
    NO_ASSIGN(BlockHeader)

    //
    // Remove a memory block from free list
    inline void remove () ;
    //
    // Get a size of free memory block
    inline uintptr_t get_size () const ;
    //
    // Set a size of free memory block
    inline void set_size (uintptr_t _size) ;

  };

  //
  // Double linked list of free memory blocks
  struct FreeBlockList :
    public BlockHeader
  {
    //
    // A size of blocks in the list
    size_t size ;
    //
    // Constructor
    inline FreeBlockList () ;

    NO_COPY_CTOR(FreeBlockList)
    NO_ASSIGN(FreeBlockList)

    inline BlockHeader* get () ;
    inline void put (BlockHeader* _block) ;

  };

  //
  // Minimum allowed size of a free block
  static size_t min_free_size ;
  //
  // An array of free block lists ;
  FreeBlockList lists [sizeof(size_t) * 8] ;

  NO_COPY_CTOR(HeapAllocator)
  NO_ASSIGN(HeapAllocator)

public:
  //
  // Constructor
  HeapAllocator (
    size_t _init_size = 0,      // Initial heap size, page size by default
    size_t const _max_size = 0, // Maximum size, not limited by default
    void* const _start = null,
    int _fd = -1
  ) ;
  //
  // Destructor
  ~HeapAllocator () noexcept;
  //
  // Allocate memory block of _size bytes
  void* allocate (size_t _size) ;
  //
  // Free memory block at _ptr
  void deallocate (void* _ptr) ;
  //
  // Resize memory block at _ptr to _size bytes
  void* reallocate (void* _ptr, size_t _size) ;
  //
  // Returns (if possible) a real size (probably larger then given)
  // of memory block to be allocated
  inline size_t get_real_size (size_t _size) const ;
  //
  // Get a size of allocated memory block
  inline size_t get_size (void const* _ptr) const ;
  //
  // Returns (if possible) the start address of allocated block containing a
  // pointer, otherwise returns null
  inline void* get_block (void* _ptr) ;
  //
  // The same as previous, but using block size
  inline void* get_block (void* _ptr, size_t _size) ;
  //
  // Checks whether an address is in allocator address range
  inline bool is_dyn_addr (void* _ptr) ;
  //
  // Dump memory map
  void memory_dump () ;

private:

  void* _reallocate (void* _ptr, size_t _size, size_t _oldsize) ;

  inline void* user_ptr (void* _ptr) const ;

  inline BlockHeader* true_ptr (void* _ptr) const ;

};

}

#endif // __pxx_heap_allocator_hh__