A.I.M.S algorithms


geodesic_memory.h
Go to the documentation of this file.
1 //Copyright (C) 2008 Danil Kirsanov, MIT License
2 #ifndef _GEODESIC_MEMORY_20071231
3 #define _GEODESIC_MEMORY_20071231
4 
5 //two fast and simple memory allocators
6 
7 #include <vector>
8 #include <assert.h>
9 #include <math.h>
10 
11 namespace geodesic{
12 
13 template<class T> //quickly allocates multiple elements of a given type; no deallocation
15 {
16 public:
17  typedef T* pointer;
18 
19  SimlpeMemoryAllocator(unsigned block_size = 0,
20  unsigned max_number_of_blocks = 0)
21  {
22  reset(block_size,
23  max_number_of_blocks);
24  };
25 
27 
28  void reset(unsigned block_size,
29  unsigned max_number_of_blocks)
30  {
31  m_block_size = block_size;
32  m_max_number_of_blocks = max_number_of_blocks;
33 
34 
35  m_current_position = 0;
36 
37  m_storage.reserve(max_number_of_blocks);
38  m_storage.resize(1);
39  m_storage[0].resize(block_size);
40  };
41 
42  pointer allocate(unsigned const n) //allocate n units
43  {
44  assert(n < m_block_size);
45 
46  if(m_current_position + n >= m_block_size)
47  {
48  m_storage.push_back( std::vector<T>() );
49  m_storage.back().resize(m_block_size);
50  m_current_position = 0;
51  }
52  pointer result = & m_storage.back()[m_current_position];
53  m_current_position += n;
54 
55  return result;
56  };
57 private:
58  std::vector<std::vector<T> > m_storage;
59  unsigned m_block_size; //size of a single block
60  unsigned m_max_number_of_blocks; //maximum allowed number of blocks
61  unsigned m_current_position; //first unused element inside the current block
62 };
63 
64 
65 template<class T> //quickly allocates and deallocates single elements of a given type
67 {
68 public:
69  typedef T* pointer;
70 
71  MemoryAllocator(unsigned block_size = 1024,
72  unsigned max_number_of_blocks = 1024)
73  {
74  reset(block_size,
75  max_number_of_blocks);
76  };
77 
79 
80  void clear()
81  {
82  reset(m_block_size,
83  m_max_number_of_blocks);
84  }
85 
86  void reset(unsigned block_size,
87  unsigned max_number_of_blocks)
88  {
89  m_block_size = block_size;
90  m_max_number_of_blocks = max_number_of_blocks;
91 
92  assert(m_block_size > 0);
93  assert(m_max_number_of_blocks > 0);
94 
95  m_current_position = 0;
96 
97  m_storage.reserve(max_number_of_blocks);
98  m_storage.resize(1);
99  m_storage[0].resize(block_size);
100 
101  m_deleted.clear();
102  m_deleted.reserve(2*block_size);
103  };
104 
105  pointer allocate() //allocates single unit of memory
106  {
107  pointer result;
108  if(m_deleted.empty())
109  {
110  if(m_current_position + 1 >= m_block_size)
111  {
112  m_storage.push_back( std::vector<T>() );
113  m_storage.back().resize(m_block_size);
114  m_current_position = 0;
115  }
116  result = & m_storage.back()[m_current_position];
117  ++m_current_position;
118  }
119  else
120  {
121  result = m_deleted.back();
122  m_deleted.pop_back();
123  }
124 
125  return result;
126  };
127 
128  void deallocate(pointer p) //allocate n units
129  {
130  if(m_deleted.size() < m_deleted.capacity())
131  {
132  m_deleted.push_back(p);
133  }
134  };
135 
136 private:
137  std::vector<std::vector<T> > m_storage;
138  unsigned m_block_size; //size of a single block
139  unsigned m_max_number_of_blocks; //maximum allowed number of blocks
140  unsigned m_current_position; //first unused element inside the current block
141 
142  std::vector<pointer> m_deleted; //pointers to deleted elemets
143 };
144 
145 
147 {
148 public:
150  m_num_bytes(0)
151  {}
152 
153  void clear()
154  {
155  m_num_bytes = 0;
156  m_buffer = std::auto_ptr<double>();
157  }
158 
159  template<class T>
160  T* allocate(unsigned n)
161  {
162  double wanted = n*sizeof(T);
163  if(wanted > m_num_bytes)
164  {
165  unsigned new_size = (unsigned) ceil(wanted / (double)sizeof(double));
166  m_buffer = std::auto_ptr<double>(new double[new_size]);
167  m_num_bytes = new_size*sizeof(double);
168  }
169 
170  return (T*)m_buffer.get();
171  }
172 
173  template <class T>
174  T* get()
175  {
176  return (T*)m_buffer.get();
177  }
178 
179  template<class T>
180  unsigned capacity()
181  {
182  return (unsigned)floor((double)m_num_bytes/(double)sizeof(T));
183  };
184 
185 private:
186 
187  std::auto_ptr<double> m_buffer;
188  unsigned m_num_bytes;
189 };
190 
191 
192 } //geodesic
193 
194 #endif //_GEODESIC_MEMORY_20071231
void reset(unsigned block_size, unsigned max_number_of_blocks)
pointer allocate(unsigned const n)
T * allocate(unsigned n)
SimlpeMemoryAllocator(unsigned block_size=0, unsigned max_number_of_blocks=0)
void reset(unsigned block_size, unsigned max_number_of_blocks)
MemoryAllocator(unsigned block_size=1024, unsigned max_number_of_blocks=1024)