Panda3D
 All Classes Functions Variables Enumerations
simpleAllocator.I
1 // Filename: simpleAllocator.I
2 // Created by: drose (12May07)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 
16 ////////////////////////////////////////////////////////////////////
17 // Function: SimpleAllocator::Constructor
18 // Access: Published
19 // Description:
20 ////////////////////////////////////////////////////////////////////
21 INLINE SimpleAllocator::
22 SimpleAllocator(size_t max_size, Mutex &lock) :
23  LinkedListNode(true),
24  _total_size(0),
25  _max_size(max_size),
26  _contiguous(max_size),
27  _lock(lock)
28 {
29 }
30 
31 ////////////////////////////////////////////////////////////////////
32 // Function: SimpleAllocator::alloc
33 // Access: Published
34 // Description: Allocates a new block. Returns NULL if a block of the
35 // requested size cannot be allocated.
36 //
37 // To free the allocated block, call block->free(), or
38 // simply delete the block pointer.
39 ////////////////////////////////////////////////////////////////////
41 alloc(size_t size) {
42  MutexHolder holder(_lock);
43  return do_alloc(size);
44 }
45 
46 ////////////////////////////////////////////////////////////////////
47 // Function: SimpleAllocator::is_empty
48 // Access: Published
49 // Description: Returns true if there are no blocks allocated on this
50 // page, or false if there is at least one.
51 ////////////////////////////////////////////////////////////////////
52 INLINE bool SimpleAllocator::
53 is_empty() const {
54  MutexHolder holder(_lock);
55  return do_is_empty();
56 }
57 
58 ////////////////////////////////////////////////////////////////////
59 // Function: SimpleAllocator::get_total_size
60 // Access: Published
61 // Description: Returns the total size of allocated objects.
62 ////////////////////////////////////////////////////////////////////
63 INLINE size_t SimpleAllocator::
64 get_total_size() const {
65  MutexHolder holder(_lock);
66  return _total_size;
67 }
68 
69 ////////////////////////////////////////////////////////////////////
70 // Function: SimpleAllocator::get_max_size
71 // Access: Published
72 // Description: Returns the available space for allocated objects.
73 ////////////////////////////////////////////////////////////////////
74 INLINE size_t SimpleAllocator::
75 get_max_size() const {
76  MutexHolder holder(_lock);
77  return _max_size;
78 }
79 
80 ////////////////////////////////////////////////////////////////////
81 // Function: SimpleAllocator::set_max_size
82 // Access: Published
83 // Description: Changes the available space for allocated objects.
84 // This will not affect any already-allocated objects,
85 // but will have an effect on future calls to alloc().
86 ////////////////////////////////////////////////////////////////////
87 INLINE void SimpleAllocator::
88 set_max_size(size_t max_size) {
89  MutexHolder holder(_lock);
90  _max_size = max_size;
91 }
92 
93 ////////////////////////////////////////////////////////////////////
94 // Function: SimpleAllocator::get_contiguous
95 // Access: Published
96 // Description: Returns an upper-bound estimate of the size of the
97 // largest contiguous block that may be allocated. It
98 // is guaranteed that an attempt to allocate a block
99 // larger than this will fail, though it is not
100 // guaranteed that an attempt to allocate a block this
101 // size or smaller will succeed.
102 ////////////////////////////////////////////////////////////////////
103 INLINE size_t SimpleAllocator::
104 get_contiguous() const {
105  MutexHolder holder(_lock);
106  return _contiguous;
107 }
108 
109 ////////////////////////////////////////////////////////////////////
110 // Function: SimpleAllocator::get_first_block
111 // Access: Published
112 // Description: Returns a pointer to the first allocated block, or
113 // NULL if there are no allocated blocks.
114 ////////////////////////////////////////////////////////////////////
117  MutexHolder holder(_lock);
118  return (_next == this) ? (SimpleAllocatorBlock *)NULL : (SimpleAllocatorBlock *)_next;
119 }
120 
121 ////////////////////////////////////////////////////////////////////
122 // Function: SimpleAllocator::do_is_empty
123 // Access: Protected
124 // Description: Returns true if there are no blocks allocated on this
125 // page, or false if there is at least one.
126 //
127 // Assumes the lock is already held.
128 ////////////////////////////////////////////////////////////////////
129 INLINE bool SimpleAllocator::
130 do_is_empty() const {
131  return (_next == this);
132 }
133 
134 ////////////////////////////////////////////////////////////////////
135 // Function: SimpleAllocator::mark_contiguous
136 // Access: Protected
137 // Description: Some space has been made available following the
138 // indicated block. Increase the contiguous space
139 // accordingly.
140 //
141 // Assumes the lock is already held.
142 ////////////////////////////////////////////////////////////////////
143 INLINE void SimpleAllocator::
144 mark_contiguous(const LinkedListNode *block) {
145  size_t space;
146  if (block == this) {
147  // This is the beginning of the list.
148  if (_next == this) {
149  // And the list is empty.
150  space = _max_size;
151  } else {
152  space = ((SimpleAllocatorBlock *)_next)->get_start();
153  }
154  } else {
155  space = ((SimpleAllocatorBlock *)block)->do_get_max_size() - ((SimpleAllocatorBlock *)block)->get_size();
156  }
157  if (space > _contiguous) {
158  _contiguous = space;
159  changed_contiguous();
160  }
161 }
162 
163 ////////////////////////////////////////////////////////////////////
164 // Function: SimpleAllocatorBlock::Constructor
165 // Access: Private
166 // Description: A SimpleAllocatorBlock must be constructed via the
167 // SimpleAllocator::alloc() call.
168 ////////////////////////////////////////////////////////////////////
169 INLINE SimpleAllocatorBlock::
170 SimpleAllocatorBlock(SimpleAllocator *alloc,
171  size_t start, size_t size) :
172  _allocator(alloc),
173  _start(start),
174  _size(size)
175 {
176 }
177 
178 ////////////////////////////////////////////////////////////////////
179 // Function: SimpleAllocatorBlock::Destructor
180 // Access: Published
181 // Description: The block automatically frees itself when it
182 // destructs.
183 ////////////////////////////////////////////////////////////////////
186  free();
187 }
188 
189 ////////////////////////////////////////////////////////////////////
190 // Function: SimpleAllocatorBlock::free
191 // Access: Published
192 // Description: Releases the allocated space.
193 ////////////////////////////////////////////////////////////////////
194 INLINE void SimpleAllocatorBlock::
195 free() {
196  if (_allocator != (SimpleAllocator *)NULL) {
197  MutexHolder holder(_allocator->_lock);
198  do_free();
199  }
200 }
201 
202 ////////////////////////////////////////////////////////////////////
203 // Function: SimpleAllocatorBlock::get_allocator
204 // Access: Published
205 // Description: Returns the SimpleAllocator object that owns this
206 // block. Returns NULL if the block has been freed.
207 ////////////////////////////////////////////////////////////////////
209 get_allocator() const {
210  return _allocator;
211 }
212 
213 ////////////////////////////////////////////////////////////////////
214 // Function: SimpleAllocatorBlock::get_start
215 // Access: Published
216 // Description: Returns the starting point of this block. It is an
217 // error to call this if the block has been freed.
218 ////////////////////////////////////////////////////////////////////
219 INLINE size_t SimpleAllocatorBlock::
220 get_start() const {
221  nassertr(_allocator != (SimpleAllocator *)NULL, 0);
222  return _start;
223 }
224 
225 ////////////////////////////////////////////////////////////////////
226 // Function: SimpleAllocatorBlock::get_size
227 // Access: Published
228 // Description: Returns the size of this block. It is an
229 // error to call this if the block has been freed.
230 ////////////////////////////////////////////////////////////////////
231 INLINE size_t SimpleAllocatorBlock::
232 get_size() const {
233  nassertr(_allocator != (SimpleAllocator *)NULL, 0);
234  return _size;
235 }
236 
237 ////////////////////////////////////////////////////////////////////
238 // Function: SimpleAllocatorBlock::is_free
239 // Access: Published
240 // Description: Returns true if the block has been freed, false if it
241 // is still valid.
242 ////////////////////////////////////////////////////////////////////
243 INLINE bool SimpleAllocatorBlock::
244 is_free() const {
245  return (_allocator != (SimpleAllocator *)NULL);
246 }
247 
248 ////////////////////////////////////////////////////////////////////
249 // Function: SimpleAllocatorBlock::get_max_size
250 // Access: Published
251 // Description: Returns the maximum size this block can be
252 // reallocated to, as limited by the following block.
253 ////////////////////////////////////////////////////////////////////
254 INLINE size_t SimpleAllocatorBlock::
255 get_max_size() const {
256  nassertr(_allocator != (SimpleAllocator *)NULL, 0);
257  MutexHolder holder(_allocator->_lock);
258  return do_get_max_size();
259 }
260 
261 ////////////////////////////////////////////////////////////////////
262 // Function: SimpleAllocatorBlock::realloc
263 // Access: Published
264 // Description: Changes the size of this block to the specified size.
265 // Returns true if the change is accepted, false if
266 // there was not enough room.
267 ////////////////////////////////////////////////////////////////////
268 INLINE bool SimpleAllocatorBlock::
269 realloc(size_t size) {
270  nassertr(_allocator != (SimpleAllocator *)NULL, false);
271  MutexHolder holder(_allocator->_lock);
272  return do_realloc(size);
273 }
274 
275 ////////////////////////////////////////////////////////////////////
276 // Function: SimpleAllocatorBlock::get_next_block
277 // Access: Published
278 // Description: Returns a pointer to the next allocated block in the
279 // chain, or NULL if there are no more allocated blocks.
280 ////////////////////////////////////////////////////////////////////
282 get_next_block() const {
283  nassertr(_allocator != (SimpleAllocator *)NULL, NULL);
284  MutexHolder holder(_allocator->_lock);
285  return (_next == _allocator) ? (SimpleAllocatorBlock *)NULL : (SimpleAllocatorBlock *)_next;
286 }
287 
288 ////////////////////////////////////////////////////////////////////
289 // Function: SimpleAllocatorBlock::do_free
290 // Access: Protected
291 // Description: Releases the allocated space.
292 //
293 // Assumes the lock is already held.
294 ////////////////////////////////////////////////////////////////////
295 INLINE void SimpleAllocatorBlock::
296 do_free() {
297  nassertv(_allocator != (SimpleAllocator *)NULL);
298 
299  _allocator->_total_size -= _size;
300  LinkedListNode *prev = _prev;
301  remove_from_list();
302  _allocator->mark_contiguous(prev);
303  _allocator = NULL;
304 }
305 
306 ////////////////////////////////////////////////////////////////////
307 // Function: SimpleAllocatorBlock::do_get_max_size
308 // Access: Protected
309 // Description: Returns the maximum size this block can be
310 // reallocated to, as limited by the following block.
311 //
312 // Assumes the lock is already held.
313 ////////////////////////////////////////////////////////////////////
314 INLINE size_t SimpleAllocatorBlock::
315 do_get_max_size() const {
316  size_t end;
317  if (_next == _allocator) {
318  end = _allocator->_max_size;
319  } else {
320  end = ((SimpleAllocatorBlock *)_next)->_start;
321  }
322  return end - _start;
323 }
324 
325 ////////////////////////////////////////////////////////////////////
326 // Function: SimpleAllocatorBlock::do_realloc
327 // Access: Protected
328 // Description: Changes the size of this block to the specified size.
329 // Returns true if the change is accepted, false if
330 // there was not enough room.
331 //
332 // Assumes the lock is already held.
333 ////////////////////////////////////////////////////////////////////
334 INLINE bool SimpleAllocatorBlock::
335 do_realloc(size_t size) {
336  if (size > do_get_max_size()) {
337  return false;
338  }
339 
340  _allocator->_total_size -= _size;
341  _allocator->_total_size += size;
342 
343  if (size < _size) {
344  // We're decreasing the block size.
345  _size = size;
346  _allocator->mark_contiguous(this);
347  } else {
348  // We're increasing the block size.
349  _size = size;
350  }
351  return true;
352 }
~SimpleAllocatorBlock()
The block automatically frees itself when it destructs.
An implementation of a very simple block allocator.
size_t get_contiguous() const
Returns an upper-bound estimate of the size of the largest contiguous block that may be allocated...
bool is_empty() const
Returns true if there are no blocks allocated on this page, or false if there is at least one...
SimpleAllocatorBlock * alloc(size_t size)
Allocates a new block.
SimpleAllocatorBlock * get_first_block() const
Returns a pointer to the first allocated block, or NULL if there are no allocated blocks...
A standard mutex, or mutual exclusion lock.
Definition: pmutex.h:44
A lightweight C++ object whose constructor calls acquire() and whose destructor calls release() on a ...
Definition: mutexHolder.h:29
bool realloc(size_t size)
Changes the size of this block to the specified size.
This just stores the pointers to implement a doubly-linked list of some kind of object.
A single block as returned from SimpleAllocator::alloc().
size_t get_start() const
Returns the starting point of this block.
size_t get_max_size() const
Returns the maximum size this block can be reallocated to, as limited by the following block...
size_t get_total_size() const
Returns the total size of allocated objects.
void free()
Releases the allocated space.
bool is_free() const
Returns true if the block has been freed, false if it is still valid.
size_t get_size() const
Returns the size of this block.
size_t get_max_size() const
Returns the available space for allocated objects.
SimpleAllocatorBlock * get_next_block() const
Returns a pointer to the next allocated block in the chain, or NULL if there are no more allocated bl...
SimpleAllocator * get_allocator() const
Returns the SimpleAllocator object that owns this block.
void set_max_size(size_t max_size)
Changes the available space for allocated objects.