TdZdd  1.1
A top-down/breadth-first decision diagram manipulation framework
MemoryPool.hpp
1 /*
2  * TdZdd: a Top-down/Breadth-first Decision Diagram Manipulation Framework
3  * by Hiroaki Iwashita <iwashita@erato.ist.hokudai.ac.jp>
4  * Copyright (c) 2014 ERATO MINATO Project
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a
7  * copy of this software and associated documentation files (the "Software"),
8  * to deal in the Software without restriction, including without limitation
9  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10  * and/or sell copies of the Software, and to permit persons to whom the
11  * Software is furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22  * DEALINGS IN THE SOFTWARE.
23  */
24 
25 #pragma once
26 
27 #include <cassert>
28 #include <iostream>
29 #include <stdexcept>
30 
31 #include "MyVector.hpp"
32 
33 namespace tdzdd {
34 
39 class MemoryPool {
40  struct Unit {
41  Unit* next;
42  };
43 
44  static size_t const UNIT_SIZE = sizeof(Unit);
45  static size_t const BLOCK_UNITS = 400000 / UNIT_SIZE;
46  static size_t const MAX_ELEMENT_UNIS = BLOCK_UNITS / 10;
47 
48  Unit* blockList;
49  size_t nextUnit;
50 
51 public:
52  MemoryPool()
53  : blockList(0), nextUnit(BLOCK_UNITS) {
54  }
55 
56  MemoryPool(MemoryPool const& o)
57  : blockList(0), nextUnit(BLOCK_UNITS) {
58 // if (o.blockList != 0) throw std::runtime_error(
59 // "MemoryPool can't be copied unless it is empty!"); //FIXME
60  }
61 
62 // MemoryPool& operator=(MemoryPool const& o) {
63 // if (o.blockList != 0) throw std::runtime_error(
64 // "MemoryPool can't be copied unless it is empty!"); //FIXME
65 // clear();
66 // return *this;
67 // }
68 
69 // MemoryPool(MemoryPool&& o): blockList(o.blockList), nextUnit(o.nextUnit) {
70 // o.blockList = 0;
71 // }
72 //
73 // MemoryPool& operator=(MemoryPool&& o) {
74 // blockList = o.blockList;
75 // nextUnit = o.nextUnit;
76 // o.blockList = 0;
77 // return *this;
78 // }
79 
80  void moveFrom(MemoryPool& o) {
81  blockList = o.blockList;
82  nextUnit = o.nextUnit;
83  o.blockList = 0;
84  }
85 
86  virtual ~MemoryPool() {
87  clear();
88  }
89 
90  bool empty() const {
91  return blockList == 0;
92  }
93 
94  void clear() {
95  while (blockList != 0) {
96  Unit* block = blockList;
97  blockList = blockList->next;
98  delete[] block;
99  }
100  nextUnit = BLOCK_UNITS;
101  }
102 
103  void reuse() {
104  if (blockList == 0) return;
105  while (blockList->next != 0) {
106  Unit* block = blockList;
107  blockList = blockList->next;
108  delete[] block;
109  }
110  nextUnit = 1;
111  }
112 
113  void splice(MemoryPool& o) {
114  if (blockList != 0) {
115  Unit** rear = &o.blockList;
116  while (*rear != 0) {
117  rear = &(*rear)->next;
118  }
119  *rear = blockList;
120  }
121 
122  blockList = o.blockList;
123  nextUnit = o.nextUnit;
124 
125  o.blockList = 0;
126  o.nextUnit = BLOCK_UNITS;
127  }
128 
129  void* alloc(size_t n) {
130  size_t const elementUnits = (n + UNIT_SIZE - 1) / UNIT_SIZE;
131 
132  if (elementUnits > MAX_ELEMENT_UNIS) {
133  size_t m = elementUnits + 1;
134  Unit* block = new Unit[m];
135  if (blockList == 0) {
136  block->next = 0;
137  blockList = block;
138  }
139  else {
140  block->next = blockList->next;
141  blockList->next = block;
142  }
143  return block + 1;
144  }
145 
146  if (nextUnit + elementUnits > BLOCK_UNITS) {
147  Unit* block = new Unit[BLOCK_UNITS];
148  block->next = blockList;
149  blockList = block;
150  nextUnit = 1;
151  assert(nextUnit + elementUnits <= BLOCK_UNITS);
152  }
153 
154  Unit* p = blockList + nextUnit;
155  nextUnit += elementUnits;
156  return p;
157  }
158 
159  template<typename T>
160  T* allocate(size_t n = 1) {
161  return static_cast<T*>(alloc(sizeof(T) * n));
162  }
163 
164  template<typename T>
165  class Allocator: public std::allocator<T> {
166  public:
167  MemoryPool* pool;
168 
169  template<typename U>
170  struct rebind {
171  typedef Allocator<U> other;
172  };
173 
174  Allocator() throw ()
175  : pool(0) {
176  }
177 
178  Allocator(MemoryPool& pool) throw ()
179  : pool(&pool) {
180  }
181 
182  Allocator(Allocator const& o) throw ()
183  : pool(o.pool) {
184  }
185 
186  Allocator& operator=(Allocator const& o) {
187  pool = o.pool;
188  return *this;
189  }
190 
191  template<typename U>
192  Allocator(Allocator<U> const& o) throw ()
193  : pool(o.pool) {
194  }
195 
196  ~Allocator() throw () {
197  }
198 
199  T* allocate(size_t n, const void* = 0) {
200  return pool->allocate<T>(n);
201  }
202 
203  void deallocate(T*, size_t) {
204  }
205  };
206 
207  template<typename T>
208  Allocator<T> allocator() {
209  return Allocator<T>(*this);
210  }
211 
218  friend std::ostream& operator<<(std::ostream& os, MemoryPool const& o) {
219  int n = 0;
220  for (Unit* p = o.blockList; p != 0; p = p->next) {
221  ++n;
222  }
223  return os << "MemoryPool(" << n << ")";
224  }
225 };
226 
230 typedef MyVector<MemoryPool> MemoryPools;
231 
232 template<>
233 inline void MyVector<MemoryPool>::moveElement(MemoryPool& from,
234  MemoryPool& to) {
235  to.moveFrom(from);
236 }
237 
238 } // namespace tdzdd
friend std::ostream & operator<<(std::ostream &os, MemoryPool const &o)
Send an object to an output stream.
Definition: MemoryPool.hpp:218
Memory pool.
Definition: MemoryPool.hpp:39