src/bin/libint/memory.h

/*
 *  Copyright (C) 2004-2024 Edward F. Valeev
 *
 *  This file is part of Libint compiler.
 *
 *  Libint compiler 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 compiler 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 compiler.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
 
#include <limits.h>
#include <smart_ptr.h>
 
#include <list>
 
#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 std::shared_ptr<MemoryBlock>& left,
              const std::shared_ptr<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_; }
  std::shared_ptr<MemoryBlock> left() const { return left_; }
  std::shared_ptr<MemoryBlock> right() const { return right_; }
  void left(const std::shared_ptr<MemoryBlock>& l) { left_ = l; }
  void right(const std::shared_ptr<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 std::shared_ptr<MemoryBlock>& i,
                             const std::shared_ptr<MemoryBlock>& j) {
    return i->size() < j->size();
  }
  static bool size_eq(std::shared_ptr<MemoryBlock> i, Size sz) {
    return i->size() == sz;
  }
  static bool size_geq(std::shared_ptr<MemoryBlock> i, Size sz) {
    return i->size() >= sz;
  }
  static bool address_less_than(const std::shared_ptr<MemoryBlock>& i,
                                const std::shared_ptr<MemoryBlock>& j) {
    return i->address() < j->address();
  }
  static bool address_eq(std::shared_ptr<MemoryBlock> i, Address a) {
    return i->address() == a;
  }
  static bool is_free(const std::shared_ptr<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;
  std::shared_ptr<this_type> left_;
  std::shared_ptr<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<std::shared_ptr<MemBlock> > memblkset;
 
 private:
  Size maxmem_;
  memblkset blks_;
  std::shared_ptr<MemBlock> superblock_;
  Size max_memory_used_;
 
  std::shared_ptr<MemBlock> merge_blocks(
      const std::shared_ptr<MemBlock>& left,
      const std::shared_ptr<MemBlock>& right);
  std::shared_ptr<MemBlock> merge_to_superblock(
      const std::shared_ptr<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_; }
  std::shared_ptr<MemBlock> superblock() const { return superblock_; }
  std::shared_ptr<MemBlock> steal_from_block(
      const std::shared_ptr<MemBlock>& blk, const Size& size);
  std::shared_ptr<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;
  std::shared_ptr<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);
 
};  // namespace libint2
 
#endif