SheafSystem  0.0.0.0
ptr_linked_pool.impl.h
1 
2 //
3 // Copyright (c) 2014 Limit Point Systems, Inc.
4 //
5 // Licensed under the Apache License, Version 2.0 (the "License");
6 // you may not use this file except in compliance with the License.
7 // You may obtain a copy of the License at
8 //
9 // http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 //
17 
18 // Implementations for class ptr_linked_pool.
19 
20 #ifndef PTR_LINKED_POOL_IMPL_H
21 #define PTR_LINKED_POOL_IMPL_H
22 
23 #ifndef SHEAF_DLL_SPEC_H
24 #include "SheafSystem/sheaf_dll_spec.h"
25 #endif
26 
27 #ifndef PTR_LINKED_POOL_H
28 #include "SheafSystem/ptr_linked_pool.h"
29 #endif
30 
31 #ifndef ASSERT_CONTRACT_H
32 #include "SheafSystem/assert_contract.h"
33 #endif
34 
35 #ifndef BLOCK_IMPL_H
36 #include "SheafSystem/block.impl.h"
37 #endif
38 
39 #ifndef STD_IOMANIP_H
40 #include "SheafSystem/std_iomanip.h"
41 #endif
42 
43 namespace sheaf
44 {
45 
47 template <typename T>
48 size_t
50 capacity() const
51 {
52 
53  return _capacity;
54 }
55 
57 template <typename T>
58 size_t
61 {
62  return _capacity - _free_size;
63 }
64 
66 template <typename T>
67 size_t
69 free_size() const
70 {
71  return _free_size;
72 }
73 
75 template <typename T>
76 T*
79 {
80  T* result = 0;
81 
82  define_old_variable(size_t old_allocated_size = allocated_size());
83 
84  if (_free_list == 0 )
85  {
86  // Free list is empty, extend the ptr_linked_pool
87 
88  reserve(2*_capacity);
89  }
90 
91  result = _free_list;
92  if (result != 0 )
93  {
94  // Have valid result, remove it from the free list
95 
96  _free_list = result->next();
97  --_free_size;
98 
99  // Make sure no interaction between use of next
100  // by free list and other uses of next.
101 
102  result->put_next(0);
103  }
104 
105  // Postconditions:
106 
107  ensure(result !=0);
108  ensure(allocated_size() == old_allocated_size + 1);
109 
110  return result;
111 }
112 
113 
115 template <typename T>
116 void
118 deallocate(T* xobject)
119 {
120 
121  // Preconditions:
122 
123  require(xobject != 0);
124  require(unexecutable("xobject is allocated"));
125 
126  // Body:
127 
128  define_old_variable(size_t old_free_size = _free_size);
129  define_old_variable(size_t old_allocated_size = allocated_size());
130 
131  xobject->put_next(_free_list);
132  _free_list = xobject;
133  ++_free_size;
134 
135  // Postconditions:
136 
137  ensure(free_size() == old_free_size + 1);
138  ensure(allocated_size() == old_allocated_size - 1);
139 
140  // Exit:
141 }
142 
143 template <typename T>
144 void
146 print() const
147 {
148  print(std::cout);
149 }
150 
151 
152 template <typename T>
153 void
155 print(std::ostream& xos) const
156 {
157  // Preconditions:
158 
159  // Body:
160 
161  using namespace std;
162 
163  xos << " capacity: " << capacity()
164  << " free_size: " << free_size()
165  << " allocated_size: " << allocated_size()
166  << endl;
167 
168  int lcol_pos = 0;
169  xos << "pool contents: " << endl;
170  typename singly_linked_list<block<T>*>::const_iterator citr;
171  for(citr = _chunk_list.begin(); citr != _chunk_list.end(); ++citr)
172  {
173  for(size_t i=0; i<(*citr)->ct(); ++i)
174  {
175  xos << " " << (*citr)->item(i);
176  lcol_pos++;
177  if(lcol_pos == 9)
178  {
179  xos << endl;
180  lcol_pos = 0;
181  }
182  }
183  }
184  xos << endl;
185 
186  // Postconditions:
187 
188  // Exit:
189 
190 }
191 
193 template <typename T>
195 ptr_linked_pool(size_t xcapacity)
196 {
197 
198  // Preconditions:
199 
200  // Body:
201 
202  _capacity = 0;
203  _free_size = 0;
204  _free_list = 0;
205 
206  reserve(xcapacity);
207 
208  // Postconditions:
209 
210  ensure(free_size() == xcapacity);
211  ensure(allocated_size() == 0);
212 
213  // Exit:
214 
215 }
216 
218 template <typename T>
221 {
222  clear();
223 }
224 
225 template <typename T>
226 void
228 reserve(size_t xcapacity)
229 {
230 
231  // Preconditions:
232 
233  require(xcapacity > 0);
234 
235  // Body:
236 
237  define_old_variable(size_t old_free_size = _free_size);
238 
239  size_t old_capacity = _capacity;
240 
241  if(xcapacity > _capacity)
242  {
243  // Allocate a new chunk of storage.
244 
245  size_t lchunk_size = xcapacity - old_capacity;
246  block<T>* lchunk = new block<T>(lchunk_size);
247  lchunk->set_ct(lchunk_size);
248  _chunk_list.push_front(lchunk);
249 
250  // String the chunk together into a list.
251 
252  T* lptr = lchunk->base();
253  for(size_t i=0; i<(lchunk_size-1); ++i)
254  {
255  T* lnext_ptr = lptr+1;
256  lptr->put_next(lnext_ptr);
257  lptr = lnext_ptr;
258  }
259  lptr->put_next(0);
260 
261  // Put the new chunk on the free list.
262 
263  if(_free_list == 0)
264  {
265  // The free list is empty;
266  // make it point to the new chunk.
267 
268  _free_list = lchunk->base();
269  }
270  else
271  {
272  // The free list is not empty;
273  // find its end.
274 
275  lptr = _free_list;
276 
277  while(lptr->next() != 0)
278  {
279  lptr = lptr->next();
280  }
281 
282  assertion((lptr != 0) && (lptr->next() == 0));
283 
284  // Append the new chunk to the end of the list.
285 
286  lptr->put_next(lchunk->base());
287  }
288 
289  // Update size and capacity.
290 
291  _free_size += lchunk_size;
292  _capacity += lchunk_size;
293  }
294 
295  // Postconditions:
296 
297  ensure(capacity() >= xcapacity);
298  ensure(free_size() >= old_free_size);
299 
300  // Exit:
301 
302  return;
303 }
304 
306 template <typename T>
307 void
310 {
311  // Preconditions:
312 
313 
314  // Body:
315 
316  // Clear the chunk list and delete all the chunks.
317 
318  while(!_chunk_list.empty())
319  {
320  block<T>* lchunk = _chunk_list.front();
321  delete lchunk;
322  _chunk_list.pop_front();
323  }
324 
325  _capacity = 0;
326  _free_size = 0;
327  _free_list = 0;
328 
329  // Postconditions:
330 
331  ensure(capacity() == 0);
332  ensure(free_size() == 0);
333  ensure(allocated_size() == 0);
334 
335  // Exit:
336 
337  return;
338 }
339 
340 //==============================================================================
341 // NON-MEMBER FUNCTIONS
342 //==============================================================================
343 
344 template <typename T>
345 std::ostream&
346 operator<< (std::ostream& xos, const ptr_linked_pool<T>& xp)
347 {
348  // Preconditions:
349 
350  // Body:
351 
352  xp.print(xos);
353 
354  // Postconditions:
355 
356  // Exit:
357 
358  return xos;
359 }
360 
361 } // namespace sheaf
362 
363 #endif // ifndef PTR_LINKED_POOL_IMPL_H
void reserve(size_t xcapacity)
Makes capacity at least xcapacity.
void clear()
Deletes all the objects in the pool.
size_t capacity() const
The number of objects, either free or allocated, currently in the pool.
T * allocate()
Allocate next available object from the free list.
size_t allocated_size() const
The size of allocated list.
STL namespace.
ptr_linked_pool(size_t xcapacity=1024)
Creates an instance with capacity xcapacity.
iterator begin()
Returns an iterator to the first element of the container.
void deallocate(T *xobject)
Deallocate xobject.
void print() const
Prints the data members of this on cout. Intended for use debugging.
pointer_type base() const
The underlying storage array.
iterator end()
Returns an iterator to the element following the last element of the container.
Namespace for the sheaves component of the sheaf system.
size_t free_size() const
The size of free list.
An auto_block with a no-initialization initialization policy.
Wrapper class for forward_list or slist depending on compiler. The class replicates the minimum subse...