LIBINT  2.1.0-stable
src/bin/libint/memory.h
1 /*
2  * This file is a part of Libint.
3  * Copyright (C) 2004-2014 Edward F. Valeev
4  *
5  * This program is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation, either version 2 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program. If not, see http://www.gnu.org/licenses/.
17  *
18  */
19 
20 #include <limits.h>
21 #include <list>
22 #include <smart_ptr.h>
23 
24 #ifndef _libint2_src_bin_libint_memory_h_
25 #define _libint2_src_bin_libint_memory_h_
26 
27 using namespace std;
28 
29 namespace libint2 {
30 
34  template <typename A, typename S>
36  {
37  public:
38  typedef A Address;
39  typedef S Size;
40 
41  MemoryBlock(const Address& address, const Size& size, bool free,
42  const SafePtr<MemoryBlock>& left,
43  const SafePtr<MemoryBlock>& right) :
44  address_(address), size_(size), free_(free),
45  left_(left), right_(right)
46  {
47  }
48  MemoryBlock(const MemoryBlock& other) :
49  address_(other.address_), size_(other.size_), free_(other.free_),
50  left_(other.left_), right_(other.right_)
51  {
52  }
53 
54  ~MemoryBlock() {}
55 
57  const MemoryBlock& operator=(const MemoryBlock& other) {
58  address_ = other.address_;
59  size_ = other.size_;
60  free_ = other.free_;
61  left_ = other.left_;
62  right_ = other.right_;
63  return *this;
64  }
65 
67  Address address() const { return address_; }
69  Size size() const { return size_; }
71  bool free() const { return free_; }
73  SafePtr<MemoryBlock> left() const { return left_; }
75  SafePtr<MemoryBlock> right() const { return right_; }
77  void left(const SafePtr<MemoryBlock>& l) { left_ = l; }
79  void right(const SafePtr<MemoryBlock>& r) { right_ = r; }
80 
82  void set_address(const Address& address) { address_ = address; }
84  void set_size(const Size& size) { size_ = size; }
86  void set_free(bool free) { free_ = free; }
87 
89  static bool size_less_than(const SafePtr<MemoryBlock>& i,
90  const SafePtr<MemoryBlock>& j) {
91  return i->size() < j->size();
92  }
96  static bool size_eq(SafePtr<MemoryBlock> i, Size sz) {
97  return i->size() == sz;
98  }
102  static bool size_geq(SafePtr<MemoryBlock> i, Size sz) {
103  return i->size() >= sz;
104  }
106  static bool address_less_than(const SafePtr<MemoryBlock>& i,
107  const SafePtr<MemoryBlock>& j) {
108  return i->address() < j->address();
109  }
113  static bool address_eq(SafePtr<MemoryBlock> i, Address a) {
114  return i->address() == a;
115  }
117  static bool is_free(const SafePtr<MemoryBlock>& i) {
118  return i->free();
119  }
120 
122  const MemoryBlock& merge(const MemoryBlock& other) {
123  if (address() > other.address()) {
124  address_ = other.address_;
125  }
126  size_ += other.size();
127  return *this;
128  }
129 
130  private:
131  Address address_;
132  Size size_;
133  bool free_;
135  SafePtr<this_type> left_;
136  SafePtr<MemoryBlock> right_;
137 
138  MemoryBlock();
139  };
140 
147  public:
149  typedef intptr_t Address;
150  typedef size_t Size;
152 
153  static const Address InvalidAddress = -1;
154 
155  protected:
156  typedef std::list< SafePtr<MemBlock> > memblkset;
157 
158  private:
160  Size maxmem_;
162  memblkset blks_;
164  SafePtr<MemBlock> superblock_;
166  Size max_memory_used_;
167 
168  SafePtr<MemBlock> merge_blocks(const SafePtr<MemBlock>& left, const SafePtr<MemBlock>& right);
169  SafePtr<MemBlock> merge_to_superblock(const SafePtr<MemBlock>& blk);
170  void update_max_memory();
171 
172 
173  public:
174  virtual ~MemoryManager();
175 
177  virtual Address alloc(const Size& size) =0;
179  virtual void free(const Address& address);
181  Size max_memory_used() const { return max_memory_used_; }
182 
184  void reset();
185 
186  protected:
187  MemoryManager(const Size& maxmem);
188 
190  Size maxmem() const { return maxmem_; }
192  memblkset& blocks() { return blks_;}
194  SafePtr<MemBlock> superblock() const { return superblock_; }
196  SafePtr<MemBlock> steal_from_block(const SafePtr<MemBlock>& blk, const Size& size);
198  SafePtr<MemBlock> find_block(const Address& a);
199 
200  };
201 
202 
208  public:
209  WorstFitMemoryManager(bool search_exact = true, const Size& maxsize = ULONG_MAX);
210  virtual ~WorstFitMemoryManager();
211 
213  Address alloc(const Size& size);
214 
215  private:
217  bool search_exact_;
218  };
219 
227  public:
228  BestFitMemoryManager(bool search_exact = true, const Size& tight_fit = 0, const Size& maxsize = ULONG_MAX);
229  virtual ~BestFitMemoryManager();
230 
232  Address alloc(const Size& size);
233 
234  private:
236  bool search_exact_;
238  Size tight_fit_;
239  };
240 
246  public:
247  FirstFitMemoryManager(bool search_exact = true, const Size& maxsize = ULONG_MAX);
248  virtual ~FirstFitMemoryManager();
249 
251  Address alloc(const Size& size);
252 
253  private:
255  bool search_exact_;
256  };
257 
263  public:
264  LastFitMemoryManager(bool search_exact = true, const Size& maxsize = ULONG_MAX);
265  virtual ~LastFitMemoryManager();
266 
268  Address alloc(const Size& size);
269 
270  private:
272  bool search_exact_;
273  };
274 
279  public:
280  static const unsigned int ntypes = 8;
281  SafePtr<MemoryManager> memman(unsigned int type) const;
282  std::string label(unsigned int type) const;
283  };
284 
289  typedef std::list< MemoryManager::MemBlock > MemBlockSet;
290  bool size_lessthan(const MemoryManager::MemBlock& A, const MemoryManager::MemBlock& B);
291  bool address_lessthan(const MemoryManager::MemBlock& A, const MemoryManager::MemBlock& B);
295  void merge(MemBlockSet& blocks);
296 
297 };
298 
299 #endif
MemoryManagerFactory is a very dumb factory for MemoryManagers.
Definition: src/bin/libint/memory.h:278
void merge(MemBlockSet &blocks)
Merge blocks, if possible.
Definition: memory.cc:588
void set_free(bool free)
Sets block&#39;s free status.
Definition: src/bin/libint/memory.h:86
void set_address(const Address &address)
Sets the address.
Definition: src/bin/libint/memory.h:82
Defaults definitions for various parameters assumed by Libint.
Definition: algebra.cc:23
static bool size_less_than(const SafePtr< MemoryBlock > &i, const SafePtr< MemoryBlock > &j)
Returns true if the size of *i is less than the size of *j.
Definition: src/bin/libint/memory.h:89
Definition: stdarray.h:18
static bool size_eq(SafePtr< MemoryBlock > i, Size sz)
Returns true if the size of *i equals sz.
Definition: src/bin/libint/memory.h:96
SafePtr< MemoryBlock > left() const
Returns the left adjacent block.
Definition: src/bin/libint/memory.h:73
LastFitMemoryManager allocates memory by finding last suitable free block.
Definition: src/bin/libint/memory.h:262
bool can_merge(const MemoryManager::MemBlock &A, const MemoryManager::MemBlock &B)
True if can merge blocks.
Definition: memory.cc:578
BestFitMemoryManager allocates memory by trying to find a suitable free block, which is is larger tha...
Definition: src/bin/libint/memory.h:226
void set_size(const Size &size)
Sets the size.
Definition: src/bin/libint/memory.h:84
SafePtr< MemBlock > superblock() const
Returns the superblock.
Definition: src/bin/libint/memory.h:194
Address address() const
Returns address.
Definition: src/bin/libint/memory.h:67
memblkset & blocks()
Returns blocks.
Definition: src/bin/libint/memory.h:192
Class MemoryManager handles allocation and deallocation of raw memory (stack) provided at runtime of ...
Definition: src/bin/libint/memory.h:146
MemoryBlock<Address,Size> describes a block of raw memory addressed via Address and size described by...
Definition: src/bin/libint/memory.h:35
const MemoryBlock & merge(const MemoryBlock &other)
Merge A to this (does not check if merge can happen – can_merge(*this,*A) must be already satisfied)...
Definition: src/bin/libint/memory.h:122
bool free() const
Returns true if the block is free.
Definition: src/bin/libint/memory.h:71
intptr_t Address
Negative Address is used to denote an invalid address – hence signed integer.
Definition: src/bin/libint/memory.h:149
WorstFitMemoryManager allocates memory by trying to find the largest-possible free block...
Definition: src/bin/libint/memory.h:207
Size size() const
Returns size.
Definition: src/bin/libint/memory.h:69
FirstFitMemoryManager allocates memory by finding first suitable free block.
Definition: src/bin/libint/memory.h:245
static bool is_free(const SafePtr< MemoryBlock > &i)
Returns true if *i is free.
Definition: src/bin/libint/memory.h:117
static bool size_geq(SafePtr< MemoryBlock > i, Size sz)
Returns true if the size of *i greater or equal than sz.
Definition: src/bin/libint/memory.h:102
Size maxmem() const
Returns maxmem.
Definition: src/bin/libint/memory.h:190
static bool address_less_than(const SafePtr< MemoryBlock > &i, const SafePtr< MemoryBlock > &j)
Returns true if the address of *i is less than the address of *j.
Definition: src/bin/libint/memory.h:106
void right(const SafePtr< MemoryBlock > &r)
Sets the right adjacent block.
Definition: src/bin/libint/memory.h:79
static bool address_eq(SafePtr< MemoryBlock > i, Address a)
Returns true if the address of *i equals a.
Definition: src/bin/libint/memory.h:113
void left(const SafePtr< MemoryBlock > &l)
Sets the left adjacent block.
Definition: src/bin/libint/memory.h:77
Size max_memory_used() const
Returns the max amount of memory used up to this moment.
Definition: src/bin/libint/memory.h:181
SafePtr< MemoryBlock > right() const
Returns the right adjacent block.
Definition: src/bin/libint/memory.h:75
const MemoryBlock & operator=(const MemoryBlock &other)
copy A to this
Definition: src/bin/libint/memory.h:57