1//===- Allocators.h -------------------------------------------------------===//
2//
3//                     The MCLinker Project
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9#ifndef MCLD_SUPPORT_ALLOCATORS_H_
10#define MCLD_SUPPORT_ALLOCATORS_H_
11#include "mcld/ADT/TypeTraits.h"
12#include "mcld/Support/Compiler.h"
13
14#include <cstddef>
15#include <cstdlib>
16
17namespace mcld {
18
19/** \class Chunk
20 *  \brief Chunk is the basic unit of the storage of the LinearAllocator
21 *
22 *  @see LinearAllocator
23 */
24template <typename DataType, size_t ChunkSize>
25class Chunk {
26 public:
27  typedef DataType value_type;
28
29 public:
30  Chunk() : next(NULL), bound(0) {}
31
32  static size_t size() { return ChunkSize; }
33
34  static void construct(value_type* pPtr) { new (pPtr) value_type(); }
35
36  static void construct(value_type* pPtr, const value_type& pValue) {
37    new (pPtr) value_type(pValue);
38  }
39
40  static void destroy(value_type* pPtr) {}
41
42 public:
43  Chunk* next;
44  size_t bound;
45  DataType data[ChunkSize];
46};
47
48template <typename DataType>
49class Chunk<DataType, 0> {
50 public:
51  typedef DataType value_type;
52
53 public:
54  Chunk() : next(NULL), bound(0) {
55    if (m_Size != 0)
56      data = reinterpret_cast<DataType*>(malloc(sizeof(DataType) * m_Size));
57    else
58      data = 0;
59  }
60
61  ~Chunk() {
62    if (data)
63      free(data);
64  }
65
66  static size_t size() { return m_Size; }
67
68  static void setSize(size_t pSize) { m_Size = pSize; }
69
70  static void construct(value_type* pPtr) { new (pPtr) value_type(); }
71
72  static void construct(value_type* pPtr, const value_type& pValue) {
73    new (pPtr) value_type(pValue);
74  }
75
76  static void destroy(value_type* pPtr) { pPtr->~value_type(); }
77
78 public:
79  Chunk* next;
80  size_t bound;
81  DataType* data;
82  static size_t m_Size;
83};
84
85template <typename DataType>
86size_t Chunk<DataType, 0>::m_Size = 0;
87
88template <typename ChunkType>
89class LinearAllocatorBase {
90 public:
91  typedef ChunkType chunk_type;
92  typedef typename ChunkType::value_type value_type;
93  typedef typename ChunkType::value_type* pointer;
94  typedef typename ChunkType::value_type& reference;
95  typedef const typename ChunkType::value_type* const_pointer;
96  typedef const typename ChunkType::value_type& const_reference;
97  typedef size_t size_type;
98  typedef ptrdiff_t difference_type;
99  typedef unsigned char byte_type;
100
101 protected:
102  LinearAllocatorBase() : m_pRoot(NULL), m_pCurrent(NULL), m_AllocatedNum(0) {}
103
104  // LinearAllocatorBase does NOT mean to destroy the allocated memory.
105  // If you want a memory allocator to release memory at destruction, please
106  // use GCFactory series.
107  virtual ~LinearAllocatorBase() {}
108
109 public:
110  pointer address(reference X) const { return &X; }
111
112  const_pointer address(const_reference X) const { return &X; }
113
114  /// standard construct - constructing an object on the location pointed by
115  //  pPtr, and using its copy constructor to initialized its value to pValue.
116  //
117  //  @param pPtr the address where the object to be constructed
118  //  @param pValue the value to be constructed
119  void construct(pointer pPtr, const_reference pValue) {
120    chunk_type::construct(pPtr, pValue);
121  }
122
123  /// default construct - constructing an object on the location pointed by
124  //  pPtr, and using its default constructor to initialized its value to
125  //  pValue.
126  //
127  //  @param pPtr the address where the object to be constructed
128  void construct(pointer pPtr) { chunk_type::construct(pPtr); }
129
130  /// standard destroy - destroy data on arbitrary address
131  //  @para pPtr the address where the data to be destruected.
132  void destroy(pointer pPtr) { chunk_type::destroy(pPtr); }
133
134  /// allocate - allocate N data in order.
135  //  - Disallow to allocate a chunk whose size is bigger than a chunk.
136  //
137  //  @param N the number of allocated data.
138  //  @return the start address of the allocated memory
139  pointer allocate(size_type N) {
140    if (N == 0 || N > chunk_type::size())
141      return 0;
142
143    if (empty())
144      initialize();
145
146    size_type rest_num_elem = chunk_type::size() - m_pCurrent->bound;
147    pointer result = 0;
148    if (N > rest_num_elem)
149      getNewChunk();
150    result = m_pCurrent->data + m_pCurrent->bound;
151    m_pCurrent->bound += N;
152    return result;
153  }
154
155  /// allocate - clone function of allocating one datum.
156  pointer allocate() {
157    if (empty())
158      initialize();
159
160    pointer result = 0;
161    if (chunk_type::size() == m_pCurrent->bound)
162      getNewChunk();
163    result = m_pCurrent->data + m_pCurrent->bound;
164    ++m_pCurrent->bound;
165    return result;
166  }
167
168  /// deallocate - deallocate N data from the pPtr
169  //  - if we can simply release some memory, then do it. Otherwise, do
170  //    nothing.
171  void deallocate(pointer& pPtr, size_type N) {
172    if (N == 0 || N > chunk_type::size() || m_pCurrent->bound == 0 ||
173        N >= m_pCurrent->bound)
174      return;
175    if (!isAvailable(pPtr))
176      return;
177    m_pCurrent->bound -= N;
178    pPtr = 0;
179  }
180
181  /// deallocate - clone function of deallocating one datum
182  void deallocate(pointer& pPtr) {
183    if (m_pCurrent->bound == 0)
184      return;
185    if (!isAvailable(pPtr))
186      return;
187    m_pCurrent->bound -= 1;
188    pPtr = 0;
189  }
190
191  /// isIn - whether the pPtr is in the current chunk?
192  bool isIn(pointer pPtr) const {
193    if (pPtr >= &(m_pCurrent->data[0]) &&
194        pPtr <= &(m_pCurrent->data[chunk_type::size() - 1]))
195      return true;
196    return false;
197  }
198
199  /// isIn - whether the pPtr is allocated, and can be constructed.
200  bool isAvailable(pointer pPtr) const {
201    if (pPtr >= &(m_pCurrent->data[m_pCurrent->bound]) &&
202        pPtr <= &(m_pCurrent->data[chunk_type::size() - 1]))
203      return true;
204    return false;
205  }
206
207  void reset() {
208    m_pRoot = 0;
209    m_pCurrent = 0;
210    m_AllocatedNum = 0;
211  }
212
213  /// clear - clear all chunks
214  void clear() {
215    chunk_type* cur = m_pRoot, *prev;
216    while (cur != 0) {
217      prev = cur;
218      cur = cur->next;
219      for (unsigned int idx = 0; idx != prev->bound; ++idx)
220        destroy(prev->data + idx);
221      delete prev;
222    }
223    reset();
224  }
225
226  // -----  observers  ----- //
227  bool empty() const { return (m_pRoot == 0); }
228
229  size_type max_size() const { return m_AllocatedNum; }
230
231 protected:
232  inline void initialize() {
233    m_pRoot = new chunk_type();
234    m_pCurrent = m_pRoot;
235    m_AllocatedNum += chunk_type::size();
236  }
237
238  inline chunk_type* getNewChunk() {
239    chunk_type* result = new chunk_type();
240    m_pCurrent->next = result;
241    m_pCurrent = result;
242    m_AllocatedNum += chunk_type::size();
243    return result;
244  }
245
246 protected:
247  chunk_type* m_pRoot;
248  chunk_type* m_pCurrent;
249  size_type m_AllocatedNum;
250
251 private:
252  DISALLOW_COPY_AND_ASSIGN(LinearAllocatorBase);
253};
254
255/** \class LinearAllocator
256 *  \brief LinearAllocator is another bump pointer allocator which should be
257 *  limited in use of two-phase memory allocation.
258 *
259 *  Two-phase memory allocation clear separates the use of memory into 'claim'
260 *  and 'release' phases. There are no interleaving allocation and
261 *  deallocation. Interleaving 'allocate' and 'deallocate' increases the size
262 *  of allocated memory, and causes bad locality.
263 *
264 *  The underlying concept of LinearAllocator is a memory pool. LinearAllocator
265 *  is a simple implementation of boost::pool's ordered_malloc() and
266 *  ordered_free().
267 *
268 *  template argument DataType is the DataType to be allocated
269 *  template argument ChunkSize is the number of bytes of a chunk
270 */
271template <typename DataType, size_t ChunkSize>
272class LinearAllocator
273    : public LinearAllocatorBase<Chunk<DataType, ChunkSize> > {
274 public:
275  template <typename NewDataType>
276  struct rebind {
277    typedef LinearAllocator<NewDataType, ChunkSize> other;
278  };
279
280 public:
281  LinearAllocator() : LinearAllocatorBase<Chunk<DataType, ChunkSize> >() {}
282
283  virtual ~LinearAllocator() {}
284};
285
286template <typename DataType>
287class LinearAllocator<DataType, 0>
288    : public LinearAllocatorBase<Chunk<DataType, 0> > {
289 public:
290  template <typename NewDataType>
291  struct rebind {
292    typedef LinearAllocator<NewDataType, 0> other;
293  };
294
295 public:
296  explicit LinearAllocator(size_t pNum)
297      : LinearAllocatorBase<Chunk<DataType, 0> >() {
298    Chunk<DataType, 0>::setSize(pNum);
299  }
300
301  virtual ~LinearAllocator() {}
302};
303
304template <typename DataType>
305class MallocAllocator {
306 public:
307  typedef size_t size_type;
308  typedef ptrdiff_t difference_type;
309  typedef DataType* pointer;
310  typedef const DataType* const_pointer;
311  typedef DataType& reference;
312  typedef const DataType& const_reference;
313  typedef DataType value_type;
314
315  template <typename OtherDataType>
316  struct rebind {
317    typedef MallocAllocator<OtherDataType> other;
318  };
319
320 public:
321  MallocAllocator() throw() {}
322
323  MallocAllocator(const MallocAllocator&) throw() {}
324
325  ~MallocAllocator() throw() {}
326
327  pointer address(reference X) const { return &X; }
328
329  const_pointer address(const_reference X) const { return &X; }
330
331  pointer allocate(size_type pNumOfElements, const void* = 0) {
332    return static_cast<DataType*>(
333        std::malloc(pNumOfElements * sizeof(DataType)));
334  }
335
336  void deallocate(pointer pObject, size_type) {
337    std::free(static_cast<void*>(pObject));
338  }
339
340  size_type max_size() const throw() { return size_t(-1) / sizeof(DataType); }
341
342  void construct(pointer pObject, const DataType& pValue) {
343    ::new (reinterpret_cast<void*>(pObject)) value_type(pValue);
344  }
345
346  void destroy(pointer pObject) { pObject->~DataType(); }
347};
348
349template <>
350class MallocAllocator<void> {
351 public:
352  typedef size_t size_type;
353  typedef ptrdiff_t difference_type;
354  typedef void* pointer;
355  typedef const void* const_pointer;
356  typedef void* reference;
357  typedef const void* const_reference;
358  typedef void* value_type;
359
360  template <typename OtherDataType>
361  struct rebind {
362    typedef MallocAllocator<OtherDataType> other;
363  };
364
365 public:
366  MallocAllocator() throw() {}
367
368  MallocAllocator(const MallocAllocator&) throw() {}
369
370  ~MallocAllocator() throw() {}
371
372  size_type max_size() const throw() { return size_t(-1) / sizeof(void*); }
373
374  pointer address(reference X) const { return X; }
375
376  const_pointer address(const_reference X) const { return X; }
377
378  template <typename DataType>
379  DataType* allocate(size_type pNumOfElements, const void* = 0) {
380    return static_cast<DataType*>(
381        std::malloc(pNumOfElements * sizeof(DataType)));
382  }
383
384  pointer allocate(size_type pNumOfElements, const void* = 0) {
385    return std::malloc(pNumOfElements);
386  }
387
388  template <typename DataType>
389  void deallocate(DataType* pObject, size_type) {
390    std::free(static_cast<void*>(pObject));
391  }
392
393  void deallocate(pointer pObject, size_type) { std::free(pObject); }
394
395  template <typename DataType>
396  void construct(DataType* pObject, const DataType& pValue) { /* do nothing */
397  }
398
399  void construct(pointer pObject, const_reference pValue) { /* do nothing */
400  }
401
402  template <typename DataType>
403  void destroy(DataType* pObject) { /* do nothing */
404  }
405
406  void destroy(pointer pObject) { /* do nothing */
407  }
408};
409
410}  // namespace mcld
411
412#endif  // MCLD_SUPPORT_ALLOCATORS_H_
413