Panda3D
|
00001 // Filename: simpleAllocator.cxx 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 #include "simpleAllocator.h" 00016 00017 //////////////////////////////////////////////////////////////////// 00018 // Function: SimpleAllocator::Destructor 00019 // Access: Published, Virtual 00020 // Description: 00021 //////////////////////////////////////////////////////////////////// 00022 SimpleAllocator:: 00023 ~SimpleAllocator() { 00024 // We're shutting down. Force-free everything remaining. 00025 if (_next != (LinkedListNode *)this) { 00026 MutexHolder holder(_lock); 00027 while (_next != (LinkedListNode *)this) { 00028 nassertv(_next != (LinkedListNode *)NULL); 00029 ((SimpleAllocatorBlock *)_next)->do_free(); 00030 } 00031 } 00032 } 00033 00034 //////////////////////////////////////////////////////////////////// 00035 // Function: SimpleAllocator::output 00036 // Access: Published 00037 // Description: 00038 //////////////////////////////////////////////////////////////////// 00039 void SimpleAllocator:: 00040 output(ostream &out) const { 00041 MutexHolder holder(_lock); 00042 out << "SimpleAllocator, " << _total_size << " of " << _max_size 00043 << " allocated"; 00044 } 00045 00046 //////////////////////////////////////////////////////////////////// 00047 // Function: SimpleAllocator::write 00048 // Access: Published 00049 // Description: 00050 //////////////////////////////////////////////////////////////////// 00051 void SimpleAllocator:: 00052 write(ostream &out) const { 00053 MutexHolder holder(_lock); 00054 out << "SimpleAllocator, " << _total_size << " of " << _max_size 00055 << " allocated"; 00056 00057 SimpleAllocatorBlock *block = (SimpleAllocatorBlock *)_next; 00058 while (block->_next != this) { 00059 SimpleAllocatorBlock *next = (SimpleAllocatorBlock *)block->_next; 00060 00061 out << " " << *block << "\n"; 00062 block = next; 00063 } 00064 } 00065 00066 //////////////////////////////////////////////////////////////////// 00067 // Function: SimpleAllocator::do_alloc 00068 // Access: Protected 00069 // Description: Allocates a new block. Returns NULL if a block of the 00070 // requested size cannot be allocated. 00071 // 00072 // To free the allocated block, call block->free(), or 00073 // simply delete the block pointer. 00074 // 00075 // Assumes the lock is already held. 00076 //////////////////////////////////////////////////////////////////// 00077 SimpleAllocatorBlock *SimpleAllocator:: 00078 do_alloc(size_t size) { 00079 if (size > _contiguous) { 00080 // Don't even bother. 00081 return NULL; 00082 } 00083 00084 // First fit algorithm: walk through all the empty blocks until we 00085 // find one that has enough room. 00086 00087 SimpleAllocatorBlock *block = NULL; 00088 size_t end = 0; 00089 size_t best = 0; 00090 if (_next != this) { 00091 // We have at least one allocated block. 00092 block = (SimpleAllocatorBlock *)_next; 00093 end = block->_start + block->_size; 00094 00095 // Scan until we have reached the last allocated block. 00096 while (block->_next != this) { 00097 SimpleAllocatorBlock *next = (SimpleAllocatorBlock *)block->_next; 00098 size_t free_size = next->_start - end; 00099 if (size <= free_size) { 00100 SimpleAllocatorBlock *new_block = make_block(end, size); 00101 nassertr(new_block->get_allocator() == this, NULL); 00102 00103 new_block->insert_before(next); 00104 _total_size += size; 00105 00106 if (_max_size - _total_size < _contiguous) { 00107 // Since we only have (_max_size - _total_size) bytes 00108 // remaining, it follows that our largest contiguous block 00109 // must be no larger than this. 00110 _contiguous = _max_size - _total_size; 00111 changed_contiguous(); 00112 } 00113 return new_block; 00114 } 00115 if (free_size > best) { 00116 best = free_size; 00117 } 00118 00119 block = next; 00120 end = block->_start + block->_size; 00121 } 00122 } 00123 00124 // No free blocks; check for room at the end. 00125 size_t free_size = _max_size - end; 00126 if (size <= free_size) { 00127 SimpleAllocatorBlock *new_block = make_block(end, size); 00128 nassertr(new_block->get_allocator() == this, NULL); 00129 00130 new_block->insert_before(this); 00131 _total_size += size; 00132 00133 if (_max_size - _total_size < _contiguous) { 00134 // Since we only have (_max_size - _total_size) bytes 00135 // remaining, it follows that our largest contiguous block 00136 // must be no larger than this. 00137 _contiguous = _max_size - _total_size; 00138 changed_contiguous(); 00139 } 00140 return new_block; 00141 } 00142 00143 if (free_size > best) { 00144 best = free_size; 00145 } 00146 00147 // Now that we've walked through the entire list of blocks, we 00148 // really do know accurately what the largest contiguous block is. 00149 if (_contiguous != best) { 00150 _contiguous = best; 00151 changed_contiguous(); 00152 } 00153 00154 // No room for this block. 00155 return NULL; 00156 } 00157 00158 //////////////////////////////////////////////////////////////////// 00159 // Function: SimpleAllocator::make_block 00160 // Access: Protected, Virtual 00161 // Description: Creates a new SimpleAllocatorBlock object. Override 00162 // this function to specialize the block type returned. 00163 //////////////////////////////////////////////////////////////////// 00164 SimpleAllocatorBlock *SimpleAllocator:: 00165 make_block(size_t start, size_t size) { 00166 return new SimpleAllocatorBlock(this, start, size); 00167 } 00168 00169 //////////////////////////////////////////////////////////////////// 00170 // Function: SimpleAllocator::changed_contiguous 00171 // Access: Protected, Virtual 00172 // Description: This callback function is made whenever the estimate 00173 // of contiguous available space changes, either through 00174 // an alloc or free. The lock will be held. 00175 //////////////////////////////////////////////////////////////////// 00176 void SimpleAllocator:: 00177 changed_contiguous() { 00178 } 00179 00180 //////////////////////////////////////////////////////////////////// 00181 // Function: SimpleAllocatorBlock::output 00182 // Access: Published 00183 // Description: 00184 //////////////////////////////////////////////////////////////////// 00185 void SimpleAllocatorBlock:: 00186 output(ostream &out) const { 00187 if (_allocator == (SimpleAllocator *)NULL) { 00188 out << "free block\n"; 00189 } else { 00190 MutexHolder holder(_allocator->_lock); 00191 out << "block of size " << _size << " at " << _start; 00192 } 00193 }