Panda3D

simpleAllocator.cxx

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 }
 All Classes Functions Variables Enumerations