00001 // Filename: simpleAllocator.I 00002 // Created by: drose (12May07) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 00016 //////////////////////////////////////////////////////////////////// 00017 // Function: SimpleAllocator::Constructor 00018 // Access: Published 00019 // Description: 00020 //////////////////////////////////////////////////////////////////// 00021 INLINE SimpleAllocator:: 00022 SimpleAllocator(size_t max_size, Mutex &lock) : 00023 LinkedListNode(true), 00024 _total_size(0), 00025 _max_size(max_size), 00026 _contiguous(max_size), 00027 _lock(lock) 00028 { 00029 } 00030 00031 //////////////////////////////////////////////////////////////////// 00032 // Function: SimpleAllocator::alloc 00033 // Access: Published 00034 // Description: Allocates a new block. Returns NULL if a block of the 00035 // requested size cannot be allocated. 00036 // 00037 // To free the allocated block, call block->free(), or 00038 // simply delete the block pointer. 00039 //////////////////////////////////////////////////////////////////// 00040 SimpleAllocatorBlock *SimpleAllocator:: 00041 alloc(size_t size) { 00042 MutexHolder holder(_lock); 00043 return do_alloc(size); 00044 } 00045 00046 //////////////////////////////////////////////////////////////////// 00047 // Function: SimpleAllocator::is_empty 00048 // Access: Published 00049 // Description: Returns true if there are no blocks allocated on this 00050 // page, or false if there is at least one. 00051 //////////////////////////////////////////////////////////////////// 00052 INLINE bool SimpleAllocator:: 00053 is_empty() const { 00054 MutexHolder holder(_lock); 00055 return do_is_empty(); 00056 } 00057 00058 //////////////////////////////////////////////////////////////////// 00059 // Function: SimpleAllocator::get_total_size 00060 // Access: Published 00061 // Description: Returns the total size of allocated objects. 00062 //////////////////////////////////////////////////////////////////// 00063 INLINE size_t SimpleAllocator:: 00064 get_total_size() const { 00065 MutexHolder holder(_lock); 00066 return _total_size; 00067 } 00068 00069 //////////////////////////////////////////////////////////////////// 00070 // Function: SimpleAllocator::get_max_size 00071 // Access: Published 00072 // Description: Returns the available space for allocated objects. 00073 //////////////////////////////////////////////////////////////////// 00074 INLINE size_t SimpleAllocator:: 00075 get_max_size() const { 00076 MutexHolder holder(_lock); 00077 return _max_size; 00078 } 00079 00080 //////////////////////////////////////////////////////////////////// 00081 // Function: SimpleAllocator::set_max_size 00082 // Access: Published 00083 // Description: Changes the available space for allocated objects. 00084 // This will not affect any already-allocated objects, 00085 // but will have an effect on future calls to alloc(). 00086 //////////////////////////////////////////////////////////////////// 00087 INLINE void SimpleAllocator:: 00088 set_max_size(size_t max_size) { 00089 MutexHolder holder(_lock); 00090 _max_size = max_size; 00091 } 00092 00093 //////////////////////////////////////////////////////////////////// 00094 // Function: SimpleAllocator::get_contiguous 00095 // Access: Published 00096 // Description: Returns an upper-bound estimate of the size of the 00097 // largest contiguous block that may be allocated. It 00098 // is guaranteed that an attempt to allocate a block 00099 // larger than this will fail, though it is not 00100 // guaranteed that an attempt to allocate a block this 00101 // size or smaller will succeed. 00102 //////////////////////////////////////////////////////////////////// 00103 INLINE size_t SimpleAllocator:: 00104 get_contiguous() const { 00105 MutexHolder holder(_lock); 00106 return _contiguous; 00107 } 00108 00109 //////////////////////////////////////////////////////////////////// 00110 // Function: SimpleAllocator::get_first_block 00111 // Access: Published 00112 // Description: Returns a pointer to the first allocated block, or 00113 // NULL if there are no allocated blocks. 00114 //////////////////////////////////////////////////////////////////// 00115 INLINE SimpleAllocatorBlock *SimpleAllocator:: 00116 get_first_block() const { 00117 MutexHolder holder(_lock); 00118 return (_next == this) ? (SimpleAllocatorBlock *)NULL : (SimpleAllocatorBlock *)_next; 00119 } 00120 00121 //////////////////////////////////////////////////////////////////// 00122 // Function: SimpleAllocator::do_is_empty 00123 // Access: Protected 00124 // Description: Returns true if there are no blocks allocated on this 00125 // page, or false if there is at least one. 00126 // 00127 // Assumes the lock is already held. 00128 //////////////////////////////////////////////////////////////////// 00129 INLINE bool SimpleAllocator:: 00130 do_is_empty() const { 00131 return (_next == this); 00132 } 00133 00134 //////////////////////////////////////////////////////////////////// 00135 // Function: SimpleAllocator::mark_contiguous 00136 // Access: Protected 00137 // Description: Some space has been made available following the 00138 // indicated block. Increase the contiguous space 00139 // accordingly. 00140 // 00141 // Assumes the lock is already held. 00142 //////////////////////////////////////////////////////////////////// 00143 INLINE void SimpleAllocator:: 00144 mark_contiguous(const LinkedListNode *block) { 00145 size_t space; 00146 if (block == this) { 00147 // This is the beginning of the list. 00148 if (_next == this) { 00149 // And the list is empty. 00150 space = _max_size; 00151 } else { 00152 space = ((SimpleAllocatorBlock *)_next)->get_start(); 00153 } 00154 } else { 00155 space = ((SimpleAllocatorBlock *)block)->do_get_max_size() - ((SimpleAllocatorBlock *)block)->get_size(); 00156 } 00157 if (space > _contiguous) { 00158 _contiguous = space; 00159 changed_contiguous(); 00160 } 00161 } 00162 00163 //////////////////////////////////////////////////////////////////// 00164 // Function: SimpleAllocatorBlock::Constructor 00165 // Access: Private 00166 // Description: A SimpleAllocatorBlock must be constructed via the 00167 // SimpleAllocator::alloc() call. 00168 //////////////////////////////////////////////////////////////////// 00169 INLINE SimpleAllocatorBlock:: 00170 SimpleAllocatorBlock(SimpleAllocator *alloc, 00171 size_t start, size_t size) : 00172 _allocator(alloc), 00173 _start(start), 00174 _size(size) 00175 { 00176 } 00177 00178 //////////////////////////////////////////////////////////////////// 00179 // Function: SimpleAllocatorBlock::Destructor 00180 // Access: Published 00181 // Description: The block automatically frees itself when it 00182 // destructs. 00183 //////////////////////////////////////////////////////////////////// 00184 INLINE SimpleAllocatorBlock:: 00185 ~SimpleAllocatorBlock() { 00186 free(); 00187 } 00188 00189 //////////////////////////////////////////////////////////////////// 00190 // Function: SimpleAllocatorBlock::free 00191 // Access: Published 00192 // Description: Releases the allocated space. 00193 //////////////////////////////////////////////////////////////////// 00194 INLINE void SimpleAllocatorBlock:: 00195 free() { 00196 if (_allocator != (SimpleAllocator *)NULL) { 00197 MutexHolder holder(_allocator->_lock); 00198 do_free(); 00199 } 00200 } 00201 00202 //////////////////////////////////////////////////////////////////// 00203 // Function: SimpleAllocatorBlock::get_allocator 00204 // Access: Published 00205 // Description: Returns the SimpleAllocator object that owns this 00206 // block. Returns NULL if the block has been freed. 00207 //////////////////////////////////////////////////////////////////// 00208 INLINE SimpleAllocator *SimpleAllocatorBlock:: 00209 get_allocator() const { 00210 return _allocator; 00211 } 00212 00213 //////////////////////////////////////////////////////////////////// 00214 // Function: SimpleAllocatorBlock::get_start 00215 // Access: Published 00216 // Description: Returns the starting point of this block. It is an 00217 // error to call this if the block has been freed. 00218 //////////////////////////////////////////////////////////////////// 00219 INLINE size_t SimpleAllocatorBlock:: 00220 get_start() const { 00221 nassertr(_allocator != (SimpleAllocator *)NULL, 0); 00222 return _start; 00223 } 00224 00225 //////////////////////////////////////////////////////////////////// 00226 // Function: SimpleAllocatorBlock::get_size 00227 // Access: Published 00228 // Description: Returns the size of this block. It is an 00229 // error to call this if the block has been freed. 00230 //////////////////////////////////////////////////////////////////// 00231 INLINE size_t SimpleAllocatorBlock:: 00232 get_size() const { 00233 nassertr(_allocator != (SimpleAllocator *)NULL, 0); 00234 return _size; 00235 } 00236 00237 //////////////////////////////////////////////////////////////////// 00238 // Function: SimpleAllocatorBlock::is_free 00239 // Access: Published 00240 // Description: Returns true if the block has been freed, false if it 00241 // is still valid. 00242 //////////////////////////////////////////////////////////////////// 00243 INLINE bool SimpleAllocatorBlock:: 00244 is_free() const { 00245 return (_allocator != (SimpleAllocator *)NULL); 00246 } 00247 00248 //////////////////////////////////////////////////////////////////// 00249 // Function: SimpleAllocatorBlock::get_max_size 00250 // Access: Published 00251 // Description: Returns the maximum size this block can be 00252 // reallocated to, as limited by the following block. 00253 //////////////////////////////////////////////////////////////////// 00254 INLINE size_t SimpleAllocatorBlock:: 00255 get_max_size() const { 00256 nassertr(_allocator != (SimpleAllocator *)NULL, 0); 00257 MutexHolder holder(_allocator->_lock); 00258 return do_get_max_size(); 00259 } 00260 00261 //////////////////////////////////////////////////////////////////// 00262 // Function: SimpleAllocatorBlock::realloc 00263 // Access: Published 00264 // Description: Changes the size of this block to the specified size. 00265 // Returns true if the change is accepted, false if 00266 // there was not enough room. 00267 //////////////////////////////////////////////////////////////////// 00268 INLINE bool SimpleAllocatorBlock:: 00269 realloc(size_t size) { 00270 nassertr(_allocator != (SimpleAllocator *)NULL, false); 00271 MutexHolder holder(_allocator->_lock); 00272 return do_realloc(size); 00273 } 00274 00275 //////////////////////////////////////////////////////////////////// 00276 // Function: SimpleAllocatorBlock::get_next_block 00277 // Access: Published 00278 // Description: Returns a pointer to the next allocated block in the 00279 // chain, or NULL if there are no more allocated blocks. 00280 //////////////////////////////////////////////////////////////////// 00281 INLINE SimpleAllocatorBlock *SimpleAllocatorBlock:: 00282 get_next_block() const { 00283 nassertr(_allocator != (SimpleAllocator *)NULL, NULL); 00284 MutexHolder holder(_allocator->_lock); 00285 return (_next == _allocator) ? (SimpleAllocatorBlock *)NULL : (SimpleAllocatorBlock *)_next; 00286 } 00287 00288 //////////////////////////////////////////////////////////////////// 00289 // Function: SimpleAllocatorBlock::do_free 00290 // Access: Protected 00291 // Description: Releases the allocated space. 00292 // 00293 // Assumes the lock is already held. 00294 //////////////////////////////////////////////////////////////////// 00295 INLINE void SimpleAllocatorBlock:: 00296 do_free() { 00297 nassertv(_allocator != (SimpleAllocator *)NULL); 00298 00299 _allocator->_total_size -= _size; 00300 LinkedListNode *prev = _prev; 00301 remove_from_list(); 00302 _allocator->mark_contiguous(prev); 00303 _allocator = NULL; 00304 } 00305 00306 //////////////////////////////////////////////////////////////////// 00307 // Function: SimpleAllocatorBlock::do_get_max_size 00308 // Access: Protected 00309 // Description: Returns the maximum size this block can be 00310 // reallocated to, as limited by the following block. 00311 // 00312 // Assumes the lock is already held. 00313 //////////////////////////////////////////////////////////////////// 00314 INLINE size_t SimpleAllocatorBlock:: 00315 do_get_max_size() const { 00316 size_t end; 00317 if (_next == _allocator) { 00318 end = _allocator->_max_size; 00319 } else { 00320 end = ((SimpleAllocatorBlock *)_next)->_start; 00321 } 00322 return end - _start; 00323 } 00324 00325 //////////////////////////////////////////////////////////////////// 00326 // Function: SimpleAllocatorBlock::do_realloc 00327 // Access: Protected 00328 // Description: Changes the size of this block to the specified size. 00329 // Returns true if the change is accepted, false if 00330 // there was not enough room. 00331 // 00332 // Assumes the lock is already held. 00333 //////////////////////////////////////////////////////////////////// 00334 INLINE bool SimpleAllocatorBlock:: 00335 do_realloc(size_t size) { 00336 if (size > do_get_max_size()) { 00337 return false; 00338 } 00339 00340 _allocator->_total_size -= _size; 00341 _allocator->_total_size += size; 00342 00343 if (size < _size) { 00344 // We're decreasing the block size. 00345 _size = size; 00346 _allocator->mark_contiguous(this); 00347 } else { 00348 // We're increasing the block size. 00349 _size = size; 00350 } 00351 return true; 00352 }