src/bin/libint/memory.h

/*
 *  Copyright (C) 2004-2021 Edward F. Valeev
 *
 *  This file is part of Libint.
 *
 *  Libint 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 3 of the License, or
 *  (at your option) any later version.
 *
 *  Libint 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 Libint.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
 
#include <limits.h>
#include <list>
#include <smart_ptr.h>
 
#ifndef _libint2_src_bin_libint_memory_h_
#define _libint2_src_bin_libint_memory_h_
 
namespace libint2 {
 
  template <typename A, typename S>
    class MemoryBlock
    {
    public:
      typedef A Address;
      typedef S Size;
 
      MemoryBlock(const Address& address, const Size& size, bool free,
                  const SafePtr<MemoryBlock>& left,
                  const SafePtr<MemoryBlock>& right) :
        address_(address), size_(size), free_(free),
        left_(left), right_(right)
        {
        }
      MemoryBlock(const MemoryBlock& other) :
            address_(other.address_), size_(other.size_), free_(other.free_),
        left_(other.left_), right_(other.right_)
        {
        }
 
      ~MemoryBlock() {}
 
      const MemoryBlock& operator=(const MemoryBlock& other) {
        address_ = other.address_;
        size_ = other.size_;
        free_ = other.free_;
        left_ = other.left_;
        right_ = other.right_;
        return *this;
      }
 
      Address address() const { return address_; }
      Size size() const { return size_; }
      bool free() const { return free_; }
      SafePtr<MemoryBlock> left() const { return left_; }
      SafePtr<MemoryBlock> right() const { return right_; }
      void left(const SafePtr<MemoryBlock>& l) { left_ = l; }
      void right(const SafePtr<MemoryBlock>& r) { right_ = r; }
 
      void set_address(const Address& address) { address_ = address; }
      void set_size(const Size& size) { size_ = size; }
      void set_free(bool free) { free_ = free; }
 
      static bool size_less_than(const SafePtr<MemoryBlock>& i,
                                 const SafePtr<MemoryBlock>& j) {
        return i->size() < j->size();
      }
      static bool size_eq(SafePtr<MemoryBlock> i, Size sz) {
        return i->size() == sz;
      }
      static bool size_geq(SafePtr<MemoryBlock> i, Size sz) {
        return i->size() >= sz;
      }
      static bool address_less_than(const SafePtr<MemoryBlock>& i,
                                    const SafePtr<MemoryBlock>& j) {
        return i->address() < j->address();
      }
      static bool address_eq(SafePtr<MemoryBlock> i, Address a) {
        return i->address() == a;
      }
      static bool is_free(const SafePtr<MemoryBlock>& i) {
        return i->free();
      }
 
      const MemoryBlock& merge(const MemoryBlock& other) {
        if (address() > other.address()) {
          address_ = other.address_;
        }
        size_ += other.size();
        return *this;
      }
 
    private:
      Address address_;
      Size size_;
      bool free_;
      typedef MemoryBlock<Address,Size> this_type;
      SafePtr<this_type> left_;
      SafePtr<MemoryBlock> right_;
 
      MemoryBlock();
    };
 
  class MemoryManager {
  public:
    typedef intptr_t Address;
    typedef size_t Size;
    typedef MemoryBlock<Address,Size> MemBlock;
 
    static const Address InvalidAddress = -1;
 
  protected:
    typedef std::list< SafePtr<MemBlock> > memblkset;
 
  private:
    Size maxmem_;
    memblkset blks_;
    SafePtr<MemBlock> superblock_;
    Size max_memory_used_;
 
    SafePtr<MemBlock> merge_blocks(const SafePtr<MemBlock>& left, const SafePtr<MemBlock>& right);
    SafePtr<MemBlock> merge_to_superblock(const SafePtr<MemBlock>& blk);
    void update_max_memory();
 
 
  public:
    virtual ~MemoryManager();
 
    virtual Address alloc(const Size& size) =0;
    virtual void free(const Address& address);
    Size max_memory_used() const { return max_memory_used_; }
 
    void reset();
 
  protected:
    MemoryManager(const Size& maxmem);
 
    Size maxmem() const { return maxmem_; }
    memblkset& blocks() { return blks_;}
    SafePtr<MemBlock> superblock() const { return superblock_; }
    SafePtr<MemBlock> steal_from_block(const SafePtr<MemBlock>& blk, const Size& size);
    SafePtr<MemBlock> find_block(const Address& a);
 
  };
 
 
  class WorstFitMemoryManager : public MemoryManager {
  public:
    WorstFitMemoryManager(bool search_exact = true, const Size& maxsize = ULONG_MAX);
    virtual ~WorstFitMemoryManager();
 
    Address alloc(const Size& size) override;
 
  private:
    bool search_exact_;
  };
 
  class BestFitMemoryManager : public MemoryManager {
  public:
    BestFitMemoryManager(bool search_exact = true, const Size& tight_fit = 0, const Size& maxsize = ULONG_MAX);
    virtual ~BestFitMemoryManager();
 
    Address alloc(const Size& size) override;
 
  private:
    bool search_exact_;
    Size tight_fit_;
  };
 
  class FirstFitMemoryManager : public MemoryManager {
  public:
    FirstFitMemoryManager(bool search_exact = true, const Size& maxsize = ULONG_MAX);
    virtual ~FirstFitMemoryManager();
 
    Address alloc(const Size& size) override;
 
  private:
    bool search_exact_;
  };
 
  class LastFitMemoryManager : public MemoryManager {
  public:
    LastFitMemoryManager(bool search_exact = true, const Size& maxsize = ULONG_MAX);
    virtual ~LastFitMemoryManager();
 
    Address alloc(const Size& size) override;
 
  private:
    bool search_exact_;
  };
 
  class MemoryManagerFactory {
  public:
    static const unsigned int ntypes = 8;
    SafePtr<MemoryManager> memman(unsigned int type) const;
    std::string label(unsigned int type) const;
  };
 
  typedef MemoryManager::MemBlock MemBlock;
  typedef std::list< MemoryManager::MemBlock > MemBlockSet;
  bool size_lessthan(const MemoryManager::MemBlock& A, const MemoryManager::MemBlock& B);
  bool address_lessthan(const MemoryManager::MemBlock& A, const MemoryManager::MemBlock& B);
  bool can_merge(const MemoryManager::MemBlock& A, const MemoryManager::MemBlock& B);
  void merge(MemBlockSet& blocks);
 
};
 
#endif