// Created on: 2013-11-12
// Created by: Maxim YAKUNIN (myn)
// Copyright (c) 2002-2014 OPEN CASCADE SAS
//
// This file is part of Open CASCADE Technology software library.
//
// This library is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License version 2.1 as published
// by the Free Software Foundation, with special exception defined in the file
// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
// distribution for complete text of the license and disclaimer of any warranty.
//
// Alternatively, this file may be used under the terms of Open CASCADE
// commercial license or contractual agreement.

#ifndef NCollection_AccAllocator_HeaderFile
#define NCollection_AccAllocator_HeaderFile

#include "NCollection_BaseAllocator.hxx"
#include "NCollection_DataMap.hxx"

//!
//! Class NCollection_AccAllocator - accumulating memory allocator. This
//! class allocates memory on request returning the pointer to the allocated
//! space. The allocation units are grouped in blocks requested from the
//! system as required. This memory is returned to the system when all
//! allocations in a block are freed.
//!
//! By comparison with the standard new() and malloc() calls, this method is
//! faster and consumes very small additional memory to maintain the heap.
//!
//! By comparison with NCollection_IncAllocator, this class requires some more
//! additional memory and a little more time for allocation and deallocation.
//! Memory overhead for NCollection_IncAllocator is 12 bytes per block;
//! average memory overhead for NCollection_AccAllocator is 28 bytes per block.
//!
//! All pointers returned by Allocate() are aligned to 4 byte boundaries.
//! To define the sizeof memory blocks requested from the OS, use the
//! parameter of the constructor (measured in bytes).

class NCollection_AccAllocator : public NCollection_BaseAllocator
{
  // --------- PUBLIC CONSTANTS ---------
public:
  //! Alignment of all allocated objects: 4 bytes
  static constexpr size_t Align = 4;

  //! Default block size
  static constexpr size_t DefaultBlockSize = 24600;

  //! Number of last blocks to check for free space
  static constexpr int MaxLookupBlocks = 16;

  // ---------- PUBLIC METHODS ----------
public:
  //! Constructor
  Standard_EXPORT NCollection_AccAllocator(const size_t theBlockSize = DefaultBlockSize);

  //! Destructor
  Standard_EXPORT ~NCollection_AccAllocator() override;

  //! Allocate memory with given size
  Standard_EXPORT void* Allocate(const size_t theSize) override;

  //! Allocate memory with given size
  void* AllocateOptimal(const size_t theSize) override { return Allocate(theSize); }

  //! Free a previously allocated memory;
  //! memory is returned to the OS when all allocations in some block are freed
  Standard_EXPORT void Free(void* theAddress) override;

  // --------- PROTECTED TYPES ---------
protected:
  //! Size value aligned to a 4 byte boundary
  class AlignedSize
  {
    size_t myValue;

  public:
    constexpr AlignedSize() noexcept
        : myValue(0)
    {
    }

    constexpr AlignedSize(const size_t theValue) noexcept
        : myValue((theValue + Align - 1) & ~(Align - 1))
    {
    }

    constexpr operator size_t() const noexcept { return myValue; }
  };

  //! A pointer aligned to a 4 byte boundary
  class AlignedPtr
  {
    uint8_t* myValue;

  public:
    constexpr AlignedPtr() noexcept
        : myValue(nullptr)
    {
    }

    AlignedPtr(void* const theValue) noexcept
        : myValue((uint8_t*)((size_t)theValue & ~(Align - 1)))
    {
    }

    operator void*() const noexcept { return myValue; }

    operator uint8_t*() const noexcept { return myValue; }

    AlignedPtr operator-(const AlignedSize theValue) const noexcept { return myValue - theValue; }

    AlignedPtr operator+(const AlignedSize theValue) const noexcept { return myValue + theValue; }

    AlignedPtr operator-=(const AlignedSize theValue) noexcept { return myValue -= theValue; }

    AlignedPtr operator+=(const AlignedSize theValue) noexcept { return myValue += theValue; }
  };

  //! A key for the map of blocks
  struct Key
  {
    size_t Value;
  };

  //! Key hasher
  class Hasher
  {
  public:
    //! Returns hash code for the given key
    //! @param theKey the key which hash code is to be computed
    //! @return a computed hash code
    size_t operator()(const Key theKey) const noexcept { return theKey.Value; }

    bool operator()(const Key theKey1, const Key theKey2) const noexcept
    {
      return theKey1.Value == theKey2.Value;
    }
  };

  //! Descriptor of a block
  struct Block
  {
    void*      address;
    AlignedPtr allocStart;
    Block*     prevBlock;
    int        allocCount;

    Block(void* const theAddress, const size_t theSize, Block* thePrevBlock = nullptr) noexcept
        : address(theAddress),
          prevBlock(thePrevBlock),
          allocCount(0)
    {
      SetFreeSize(theSize);
    }

    void SetFreeSize(const size_t theSize) noexcept { allocStart = (uint8_t*)address + theSize; }

    size_t FreeSize() const noexcept { return (uint8_t*)allocStart - (uint8_t*)address; }

    AlignedPtr Allocate(const AlignedSize theSize) noexcept
    {
      allocCount++;
      return allocStart -= theSize;
    }

    void Free() { allocCount--; }

    bool IsEmpty() const noexcept { return allocCount == 0; }
  };

  // --------- PROTECTED METHODS ---------
protected:
  //! Calculate a key for the data map basing on the given address
  inline Key getKey(void* const theAddress) const noexcept
  {
    Key aKey = {(size_t)theAddress / myBlockSize};
    return aKey;
  }

  //! Find a block that the given allocation unit belongs to
  Standard_EXPORT Block* findBlock(void* const theAddress, Key& theKey) noexcept;

  //! Allocate a new block and return a pointer to it
  Standard_EXPORT Block* allocateNewBlock(const size_t theSize);

  // --------- PROHIBITED METHODS ---------
private:
  NCollection_AccAllocator(const NCollection_AccAllocator&)            = delete;
  NCollection_AccAllocator& operator=(const NCollection_AccAllocator&) = delete;

  // --------- PROTECTED DATA ---------
protected:
  AlignedSize                             myBlockSize;
  Block*                                  mypLastBlock;
  NCollection_DataMap<Key, Block, Hasher> myBlocks;

  // Declaration of CASCADE RTTI
public:
  DEFINE_STANDARD_RTTIEXT(NCollection_AccAllocator, NCollection_BaseAllocator)
};

// Definition of HANDLE object using Standard_DefineHandle.hxx
#endif