SmallObj.cpp

00001 
00002 // The Loki Library
00003 // Copyright (c) 2001 by Andrei Alexandrescu
00004 // This code accompanies the book:
00005 // Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design 
00006 //     Patterns Applied". Copyright (c) 2001. Addison-Wesley.
00007 // Permission to use, copy, modify, distribute and sell this software for any 
00008 //     purpose is hereby granted without fee, provided that the above  copyright 
00009 //     notice appear in all copies and that both that copyright notice and this 
00010 //     permission notice appear in supporting documentation.
00011 // The author or Addison-Wesley Longman make no representations about the 
00012 //     suitability of this software for any purpose. It is provided "as is" 
00013 //     without express or implied warranty.
00015 
00016 // $Id: SmallObj.cpp 756 2006-10-17 20:05:42Z syntheticpp $
00017 
00018 
00019 #include <loki/SmallObj.h>
00020 
00021 #include <cassert>
00022 #include <vector>
00023 #include <bitset>
00024 
00025 //#define DO_EXTRA_LOKI_TESTS
00026 //#define USE_NEW_TO_ALLOCATE
00027 
00028 #ifdef DO_EXTRA_LOKI_TESTS
00029     #include <iostream>
00030 #endif
00031 
00032 namespace Loki
00033 {
00034 
00068     class Chunk
00069     {
00070     private:
00071         friend class FixedAllocator;
00072 
00078         bool Init( std::size_t blockSize, unsigned char blocks );
00079 
00086         void * Allocate( std::size_t blockSize );
00087 
00096         void Deallocate( void * p, std::size_t blockSize );
00097 
00103         void Reset( std::size_t blockSize, unsigned char blocks );
00104 
00106         void Release();
00107 
00117         bool IsCorrupt( unsigned char numBlocks, std::size_t blockSize,
00118             bool checkIndexes ) const;
00119 
00126         bool IsBlockAvailable( void * p, unsigned char numBlocks,
00127             std::size_t blockSize ) const;
00128 
00130         inline bool HasBlock( void * p, std::size_t chunkLength ) const
00131         {
00132             unsigned char * pc = static_cast< unsigned char * >( p );
00133             return ( pData_ <= pc ) && ( pc < pData_ + chunkLength );
00134         }
00135 
00136         inline bool HasAvailable( unsigned char numBlocks ) const
00137         { return ( blocksAvailable_ == numBlocks ); }
00138 
00139         inline bool IsFilled( void ) const
00140         { return ( 0 == blocksAvailable_ ); }
00141 
00143         unsigned char * pData_;
00145         unsigned char firstAvailableBlock_;
00147         unsigned char blocksAvailable_;
00148     };
00149 
00168     class FixedAllocator
00169     {
00170     private:
00171 
00176         void DoDeallocate( void * p );
00177 
00183         bool MakeNewChunk( void );
00184 
00197         Chunk * VicinityFind( void * p ) const;
00198 
00200         FixedAllocator(const FixedAllocator&);
00202         FixedAllocator& operator=(const FixedAllocator&);
00203 
00205         typedef std::vector< Chunk > Chunks;
00207         typedef Chunks::iterator ChunkIter;
00209         typedef Chunks::const_iterator ChunkCIter;
00210 
00212         static unsigned char MinObjectsPerChunk_;
00213 
00215         static unsigned char MaxObjectsPerChunk_;
00216 
00218         std::size_t blockSize_;
00220         unsigned char numBlocks_;
00221 
00223         Chunks chunks_;
00225         Chunk * allocChunk_;
00227         Chunk * deallocChunk_;
00229         Chunk * emptyChunk_;
00230 
00231     public:
00233         FixedAllocator();
00234 
00236         ~FixedAllocator();
00237 
00239         void Initialize( std::size_t blockSize, std::size_t pageSize );
00240 
00244         void * Allocate( void );
00245 
00251         bool Deallocate( void * p, Chunk * hint );
00252 
00254         inline std::size_t BlockSize() const { return blockSize_; }
00255 
00260         bool TrimEmptyChunk( void );
00261 
00267         bool TrimChunkList( void );
00268 
00272         std::size_t CountEmptyChunks( void ) const;
00273 
00280         bool IsCorrupt( void ) const;
00281 
00286         const Chunk * HasBlock( void * p ) const;
00287         inline Chunk * HasBlock( void * p )
00288         {
00289             return const_cast< Chunk * >(
00290                 const_cast< const FixedAllocator * >( this )->HasBlock( p ) );
00291         }
00292 
00293     };
00294 
00295     unsigned char FixedAllocator::MinObjectsPerChunk_ = 8;
00296     unsigned char FixedAllocator::MaxObjectsPerChunk_ = UCHAR_MAX;
00297 
00298 // Chunk::Init ----------------------------------------------------------------
00299 
00300 bool Chunk::Init( std::size_t blockSize, unsigned char blocks )
00301 {
00302     assert(blockSize > 0);
00303     assert(blocks > 0);
00304     // Overflow check
00305     const std::size_t allocSize = blockSize * blocks;
00306     assert( allocSize / blockSize == blocks);
00307 
00308 #ifdef USE_NEW_TO_ALLOCATE
00309     // If this new operator fails, it will throw, and the exception will get
00310     // caught one layer up.
00311     pData_ = static_cast< unsigned char * >( ::operator new ( allocSize ) );
00312 #else
00313     // malloc can't throw, so its only way to indicate an error is to return
00314     // a NULL pointer, so we have to check for that.
00315     pData_ = static_cast< unsigned char * >( ::std::malloc( allocSize ) );
00316     if ( NULL == pData_ ) return false;
00317 #endif
00318 
00319     Reset( blockSize, blocks );
00320     return true;
00321 }
00322 
00323 // Chunk::Reset ---------------------------------------------------------------
00324 
00325 void Chunk::Reset(std::size_t blockSize, unsigned char blocks)
00326 {
00327     assert(blockSize > 0);
00328     assert(blocks > 0);
00329     // Overflow check
00330     assert((blockSize * blocks) / blockSize == blocks);
00331 
00332     firstAvailableBlock_ = 0;
00333     blocksAvailable_ = blocks;
00334 
00335     unsigned char i = 0;
00336     for ( unsigned char * p = pData_; i != blocks; p += blockSize )
00337     {
00338         *p = ++i;
00339     }
00340 }
00341 
00342 // Chunk::Release -------------------------------------------------------------
00343 
00344 void Chunk::Release()
00345 {
00346     assert( NULL != pData_ );
00347 #ifdef USE_NEW_TO_ALLOCATE
00348     ::operator delete ( pData_ );
00349 #else
00350     ::std::free( static_cast< void * >( pData_ ) );
00351 #endif
00352 }
00353 
00354 // Chunk::Allocate ------------------------------------------------------------
00355 
00356 void* Chunk::Allocate(std::size_t blockSize)
00357 {
00358     if ( IsFilled() ) return NULL;
00359 
00360     assert((firstAvailableBlock_ * blockSize) / blockSize == 
00361         firstAvailableBlock_);
00362     unsigned char * pResult = pData_ + (firstAvailableBlock_ * blockSize);
00363     firstAvailableBlock_ = *pResult;
00364     --blocksAvailable_;
00365 
00366     return pResult;
00367 }
00368 
00369 // Chunk::Deallocate ----------------------------------------------------------
00370 
00371 void Chunk::Deallocate(void* p, std::size_t blockSize)
00372 {
00373     assert(p >= pData_);
00374 
00375     unsigned char* toRelease = static_cast<unsigned char*>(p);
00376     // Alignment check
00377     assert((toRelease - pData_) % blockSize == 0);
00378     unsigned char index = static_cast< unsigned char >(
00379         ( toRelease - pData_ ) / blockSize);
00380 
00381 #if defined(DEBUG) || defined(_DEBUG)
00382     // Check if block was already deleted.  Attempting to delete the same
00383     // block more than once causes Chunk's linked-list of stealth indexes to
00384     // become corrupt.  And causes count of blocksAvailable_ to be wrong.
00385     if ( 0 < blocksAvailable_ )
00386         assert( firstAvailableBlock_ != index );
00387 #endif
00388 
00389     *toRelease = firstAvailableBlock_;
00390     firstAvailableBlock_ = index;
00391     // Truncation check
00392     assert(firstAvailableBlock_ == (toRelease - pData_) / blockSize);
00393 
00394     ++blocksAvailable_;
00395 }
00396 
00397 // Chunk::IsCorrupt -----------------------------------------------------------
00398 
00399 bool Chunk::IsCorrupt( unsigned char numBlocks, std::size_t blockSize,
00400     bool checkIndexes ) const
00401 {
00402 
00403     if ( numBlocks < blocksAvailable_ )
00404     {
00405         // Contents at this Chunk corrupted.  This might mean something has
00406         // overwritten memory owned by the Chunks container.
00407         assert( false );
00408         return true;
00409     }
00410     if ( IsFilled() )
00411         // Useless to do further corruption checks if all blocks allocated.
00412         return false;
00413     unsigned char index = firstAvailableBlock_;
00414     if ( numBlocks <= index )
00415     {
00416         // Contents at this Chunk corrupted.  This might mean something has
00417         // overwritten memory owned by the Chunks container.
00418         assert( false );
00419         return true;
00420     }
00421     if ( !checkIndexes )
00422         // Caller chose to skip more complex corruption tests.
00423         return false;
00424 
00425     /* If the bit at index was set in foundBlocks, then the stealth index was
00426      found on the linked-list.
00427      */
00428     std::bitset< UCHAR_MAX > foundBlocks;
00429     unsigned char * nextBlock = NULL;
00430 
00431     /* The loop goes along singly linked-list of stealth indexes and makes sure
00432      that each index is within bounds (0 <= index < numBlocks) and that the
00433      index was not already found while traversing the linked-list.  The linked-
00434      list should have exactly blocksAvailable_ nodes, so the for loop will not
00435      check more than blocksAvailable_.  This loop can't check inside allocated
00436      blocks for corruption since such blocks are not within the linked-list.
00437      Contents of allocated blocks are not changed by Chunk.
00438 
00439      Here are the types of corrupted link-lists which can be verified.  The
00440      corrupt index is shown with asterisks in each example.
00441 
00442      Type 1: Index is too big.
00443       numBlocks == 64
00444       blocksAvailable_ == 7
00445       firstAvailableBlock_ -> 17 -> 29 -> *101*
00446       There should be no indexes which are equal to or larger than the total
00447       number of blocks.  Such an index would refer to a block beyond the
00448       Chunk's allocated domain.
00449 
00450      Type 2: Index is repeated.
00451       numBlocks == 64
00452       blocksAvailable_ == 5
00453       firstAvailableBlock_ -> 17 -> 29 -> 53 -> *17* -> 29 -> 53 ...
00454       No index should be repeated within the linked-list since that would
00455       indicate the presence of a loop in the linked-list.
00456      */
00457     for ( unsigned char cc = 0; ; )
00458     {
00459         nextBlock = pData_ + ( index * blockSize );
00460         foundBlocks.set( index, true );
00461         ++cc;
00462         if ( cc >= blocksAvailable_ )
00463             // Successfully counted off number of nodes in linked-list.
00464             break;
00465         index = *nextBlock;
00466         if ( numBlocks <= index )
00467         {
00468             /* This catches Type 1 corruptions as shown in above comments.
00469              This implies that a block was corrupted due to a stray pointer
00470              or an operation on a nearby block overran the size of the block.
00471              */
00472             assert( false );
00473             return true;
00474         }
00475         if ( foundBlocks.test( index ) )
00476         {
00477             /* This catches Type 2 corruptions as shown in above comments.
00478              This implies that a block was corrupted due to a stray pointer
00479              or an operation on a nearby block overran the size of the block.
00480              Or perhaps the program tried to delete a block more than once.
00481              */
00482             assert( false );
00483             return true;
00484         }
00485     }
00486     if ( foundBlocks.count() != blocksAvailable_ )
00487     {
00488         /* This implies that the singly-linked-list of stealth indexes was
00489          corrupted.  Ideally, this should have been detected within the loop.
00490          */
00491         assert( false );
00492         return true;
00493     }
00494 
00495     return false;
00496 }
00497 
00498 // Chunk::IsBlockAvailable ----------------------------------------------------
00499 
00500 bool Chunk::IsBlockAvailable( void * p, unsigned char numBlocks,
00501     std::size_t blockSize ) const
00502 {
00503     (void) numBlocks;
00504     
00505     if ( IsFilled() )
00506         return false;
00507 
00508     unsigned char * place = static_cast< unsigned char * >( p );
00509     // Alignment check
00510     assert( ( place - pData_ ) % blockSize == 0 );
00511     unsigned char blockIndex = static_cast< unsigned char >(
00512         ( place - pData_ ) / blockSize );
00513 
00514     unsigned char index = firstAvailableBlock_;
00515     assert( numBlocks > index );
00516     if ( index == blockIndex )
00517         return true;
00518 
00519     /* If the bit at index was set in foundBlocks, then the stealth index was
00520      found on the linked-list.
00521      */
00522     std::bitset< UCHAR_MAX > foundBlocks;
00523     unsigned char * nextBlock = NULL;
00524     for ( unsigned char cc = 0; ; )
00525     {
00526         nextBlock = pData_ + ( index * blockSize );
00527         foundBlocks.set( index, true );
00528         ++cc;
00529         if ( cc >= blocksAvailable_ )
00530             // Successfully counted off number of nodes in linked-list.
00531             break;
00532         index = *nextBlock;
00533         if ( index == blockIndex )
00534             return true;
00535         assert( numBlocks > index );
00536         assert( !foundBlocks.test( index ) );
00537     }
00538 
00539     return false;
00540 }
00541 
00542 // FixedAllocator::FixedAllocator ---------------------------------------------
00543 
00544 FixedAllocator::FixedAllocator()
00545     : blockSize_( 0 )
00546     , numBlocks_( 0 )
00547     , chunks_( 0 )
00548     , allocChunk_( NULL )
00549     , deallocChunk_( NULL )
00550     , emptyChunk_( NULL )
00551 {
00552 }
00553 
00554 // FixedAllocator::~FixedAllocator --------------------------------------------
00555 
00556 FixedAllocator::~FixedAllocator()
00557 {
00558 #ifdef DO_EXTRA_LOKI_TESTS
00559     TrimEmptyChunk();
00560     assert( chunks_.empty() && "Memory leak detected!" );
00561 #endif
00562     for ( ChunkIter i( chunks_.begin() ); i != chunks_.end(); ++i )
00563        i->Release();
00564 }
00565 
00566 // FixedAllocator::Initialize -------------------------------------------------
00567 
00568 void FixedAllocator::Initialize( std::size_t blockSize, std::size_t pageSize )
00569 {
00570     assert( blockSize > 0 );
00571     assert( pageSize >= blockSize );
00572     blockSize_ = blockSize;
00573 
00574     std::size_t numBlocks = pageSize / blockSize;
00575     if ( numBlocks > MaxObjectsPerChunk_ ) numBlocks = MaxObjectsPerChunk_;
00576     else if ( numBlocks < MinObjectsPerChunk_ ) numBlocks = MinObjectsPerChunk_;
00577 
00578     numBlocks_ = static_cast<unsigned char>(numBlocks);
00579     assert(numBlocks_ == numBlocks);
00580 }
00581 
00582 // FixedAllocator::CountEmptyChunks -------------------------------------------
00583 
00584 std::size_t FixedAllocator::CountEmptyChunks( void ) const
00585 {
00586 #ifdef DO_EXTRA_LOKI_TESTS
00587     // This code is only used for specialized tests of the allocator.
00588     // It is #ifdef-ed so that its O(C) complexity does not overwhelm the
00589     // functions which call it.
00590     std::size_t count = 0;
00591     for ( ChunkCIter it( chunks_.begin() ); it != chunks_.end(); ++it )
00592     {
00593         const Chunk & chunk = *it;
00594         if ( chunk.HasAvailable( numBlocks_ ) )
00595             ++count;
00596     }
00597     return count;
00598 #else
00599     return ( NULL == emptyChunk_ ) ? 0 : 1;
00600 #endif
00601 }
00602 
00603 // FixedAllocator::IsCorrupt --------------------------------------------------
00604 
00605 bool FixedAllocator::IsCorrupt( void ) const
00606 {
00607     const bool isEmpty = chunks_.empty();
00608     ChunkCIter start( chunks_.begin() );
00609     ChunkCIter last( chunks_.end() );
00610     const size_t emptyChunkCount = CountEmptyChunks();
00611 
00612     if ( isEmpty )
00613     {
00614         if ( start != last )
00615         {
00616             assert( false );
00617             return true;
00618         }
00619         if ( 0 < emptyChunkCount )
00620         {
00621             assert( false );
00622             return true;
00623         }
00624         if ( NULL != deallocChunk_ )
00625         {
00626             assert( false );
00627             return true;
00628         }
00629         if ( NULL != allocChunk_ )
00630         {
00631             assert( false );
00632             return true;
00633         }
00634         if ( NULL != emptyChunk_ )
00635         {
00636             assert( false );
00637             return true;
00638         }
00639     }
00640 
00641     else
00642     {
00643         const Chunk * front = &chunks_.front();
00644         const Chunk * back  = &chunks_.back();
00645         if ( start >= last )
00646         {
00647             assert( false );
00648             return true;
00649         }
00650         if ( back < deallocChunk_ )
00651         {
00652             assert( false );
00653             return true;
00654         }
00655         if ( back < allocChunk_ )
00656         {
00657             assert( false );
00658             return true;
00659         }
00660         if ( front > deallocChunk_ )
00661         {
00662             assert( false );
00663             return true;
00664         }
00665         if ( front > allocChunk_ )
00666         {
00667             assert( false );
00668             return true;
00669         }
00670 
00671         switch ( emptyChunkCount )
00672         {
00673             case 0:
00674                 if ( emptyChunk_ != NULL )
00675                 {
00676                     assert( false );
00677                     return true;
00678                 }
00679                 break;
00680             case 1:
00681                 if ( emptyChunk_ == NULL )
00682                 {
00683                     assert( false );
00684                     return true;
00685                 }
00686                 if ( back < emptyChunk_ )
00687                 {
00688                     assert( false );
00689                     return true;
00690                 }
00691                 if ( front > emptyChunk_ )
00692                 {
00693                     assert( false );
00694                     return true;
00695                 }
00696                 if ( !emptyChunk_->HasAvailable( numBlocks_ ) )
00697                 {
00698                     // This may imply somebody tried to delete a block twice.
00699                     assert( false );
00700                     return true;
00701                 }
00702                 break;
00703             default:
00704                 assert( false );
00705                 return true;
00706         }
00707         for ( ChunkCIter it( start ); it != last; ++it )
00708         {
00709             const Chunk & chunk = *it;
00710             if ( chunk.IsCorrupt( numBlocks_, blockSize_, true ) )
00711                 return true;
00712         }
00713     }
00714 
00715     return false;
00716 }
00717 
00718 // FixedAllocator::HasBlock ---------------------------------------------------
00719 
00720 const Chunk * FixedAllocator::HasBlock( void * p ) const
00721 {
00722     const std::size_t chunkLength = numBlocks_ * blockSize_;
00723     for ( ChunkCIter it( chunks_.begin() ); it != chunks_.end(); ++it )
00724     {
00725         const Chunk & chunk = *it;
00726         if ( chunk.HasBlock( p, chunkLength ) )
00727             return &chunk;
00728     }
00729     return NULL;
00730 }
00731 
00732 // FixedAllocator::TrimEmptyChunk ---------------------------------------------
00733 
00734 bool FixedAllocator::TrimEmptyChunk( void )
00735 {
00736     // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
00737     assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
00738     if ( NULL == emptyChunk_ ) return false;
00739 
00740     // If emptyChunk_ points to valid Chunk, then chunk list is not empty.
00741     assert( !chunks_.empty() );
00742     // And there should be exactly 1 empty Chunk.
00743     assert( 1 == CountEmptyChunks() );
00744 
00745     Chunk * lastChunk = &chunks_.back();
00746     if ( lastChunk != emptyChunk_ )
00747         std::swap( *emptyChunk_, *lastChunk );
00748     assert( lastChunk->HasAvailable( numBlocks_ ) );
00749     lastChunk->Release();
00750     chunks_.pop_back();
00751 
00752     if ( chunks_.empty() )
00753     {
00754         allocChunk_ = NULL;
00755         deallocChunk_ = NULL;
00756     }
00757     else
00758     {
00759         if ( deallocChunk_ == emptyChunk_ )
00760         {
00761             deallocChunk_ = &chunks_.front();
00762             assert( deallocChunk_->blocksAvailable_ < numBlocks_ );
00763         }
00764         if ( allocChunk_ == emptyChunk_ )
00765         {
00766             allocChunk_ = &chunks_.back();
00767             assert( allocChunk_->blocksAvailable_ < numBlocks_ );
00768         }
00769     }
00770 
00771     emptyChunk_ = NULL;
00772     assert( 0 == CountEmptyChunks() );
00773 
00774     return true;
00775 }
00776 
00777 // FixedAllocator::TrimChunkList ----------------------------------------------
00778 
00779 bool FixedAllocator::TrimChunkList( void )
00780 {
00781     if ( chunks_.empty() )
00782     {
00783         assert( NULL == allocChunk_ );
00784         assert( NULL == deallocChunk_ );
00785     }
00786 
00787     if ( chunks_.size() == chunks_.capacity() )
00788         return false;
00789     // Use the "make-a-temp-and-swap" trick to remove excess capacity.
00790     Chunks( chunks_ ).swap( chunks_ );
00791 
00792     return true;
00793 }
00794 
00795 // FixedAllocator::MakeNewChunk -----------------------------------------------
00796 
00797 bool FixedAllocator::MakeNewChunk( void )
00798 {
00799     bool allocated = false;
00800     try
00801     {
00802         std::size_t size = chunks_.size();
00803         // Calling chunks_.reserve *before* creating and initializing the new
00804         // Chunk means that nothing is leaked by this function in case an
00805         // exception is thrown from reserve.
00806         if ( chunks_.capacity() == size )
00807         {
00808             if ( 0 == size ) size = 4;
00809             chunks_.reserve( size * 2 );
00810         }
00811         Chunk newChunk;
00812         allocated = newChunk.Init( blockSize_, numBlocks_ );
00813         if ( allocated )
00814             chunks_.push_back( newChunk );
00815     }
00816     catch ( ... )
00817     {
00818         allocated = false;
00819     }
00820     if ( !allocated ) return false;
00821 
00822     allocChunk_ = &chunks_.back();
00823     deallocChunk_ = &chunks_.front();
00824     return true;
00825 }
00826 
00827 // FixedAllocator::Allocate ---------------------------------------------------
00828 
00829 void * FixedAllocator::Allocate( void )
00830 {
00831     // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
00832     assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
00833     assert( CountEmptyChunks() < 2 );
00834 
00835     if ( ( NULL == allocChunk_ ) || allocChunk_->IsFilled() )
00836     {
00837         if ( NULL != emptyChunk_ )
00838         {
00839             allocChunk_ = emptyChunk_;
00840             emptyChunk_ = NULL;
00841         }
00842         else
00843         {
00844             for ( ChunkIter i( chunks_.begin() ); ; ++i )
00845             {
00846                 if ( chunks_.end() == i )
00847                 {
00848                     if ( !MakeNewChunk() )
00849                         return NULL;
00850                     break;
00851                 }
00852                 if ( !i->IsFilled() )
00853                 {
00854                     allocChunk_ = &*i;
00855                     break;
00856                 }
00857             }
00858         }
00859     }
00860     else if ( allocChunk_ == emptyChunk_)
00861         // detach emptyChunk_ from allocChunk_, because after 
00862         // calling allocChunk_->Allocate(blockSize_); the chunk 
00863         // is no longer empty.
00864         emptyChunk_ = NULL;
00865 
00866     assert( allocChunk_ != NULL );
00867     assert( !allocChunk_->IsFilled() );
00868     void * place = allocChunk_->Allocate( blockSize_ );
00869 
00870     // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
00871     assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
00872     assert( CountEmptyChunks() < 2 );
00873 
00874     return place;
00875 }
00876 
00877 // FixedAllocator::Deallocate -------------------------------------------------
00878 
00879 bool FixedAllocator::Deallocate( void * p, Chunk * hint )
00880 {
00881     assert(!chunks_.empty());
00882     assert(&chunks_.front() <= deallocChunk_);
00883     assert(&chunks_.back() >= deallocChunk_);
00884     assert( &chunks_.front() <= allocChunk_ );
00885     assert( &chunks_.back() >= allocChunk_ );
00886     assert( CountEmptyChunks() < 2 );
00887 
00888     Chunk * foundChunk = ( NULL == hint ) ? VicinityFind( p ) : hint;
00889     if ( NULL == foundChunk )
00890         return false;
00891 
00892     assert( foundChunk->HasBlock( p, numBlocks_ * blockSize_ ) );
00893 #ifdef LOKI_CHECK_FOR_CORRUPTION
00894     if ( foundChunk->IsCorrupt( numBlocks_, blockSize_, true ) )
00895     {
00896         assert( false );
00897         return false;
00898     }
00899     if ( foundChunk->IsBlockAvailable( p, numBlocks_, blockSize_ ) )
00900     {
00901         assert( false );
00902         return false;
00903     }
00904 #endif
00905     deallocChunk_ = foundChunk;
00906     DoDeallocate(p);
00907     assert( CountEmptyChunks() < 2 );
00908 
00909     return true;
00910 }
00911 
00912 // FixedAllocator::VicinityFind -----------------------------------------------
00913 
00914 Chunk * FixedAllocator::VicinityFind( void * p ) const
00915 {
00916     if ( chunks_.empty() ) return NULL;
00917     assert(deallocChunk_);
00918 
00919     const std::size_t chunkLength = numBlocks_ * blockSize_;
00920     Chunk * lo = deallocChunk_;
00921     Chunk * hi = deallocChunk_ + 1;
00922     const Chunk * loBound = &chunks_.front();
00923     const Chunk * hiBound = &chunks_.back() + 1;
00924 
00925     // Special case: deallocChunk_ is the last in the array
00926     if (hi == hiBound) hi = NULL;
00927 
00928     for (;;)
00929     {
00930         if (lo)
00931         {
00932             if ( lo->HasBlock( p, chunkLength ) ) return lo;
00933             if ( lo == loBound )
00934             {
00935                 lo = NULL;
00936                 if ( NULL == hi ) break;
00937             }
00938             else --lo;
00939         }
00940 
00941         if (hi)
00942         {
00943             if ( hi->HasBlock( p, chunkLength ) ) return hi;
00944             if ( ++hi == hiBound )
00945             {
00946                 hi = NULL;
00947                 if ( NULL == lo ) break;
00948             }
00949         }
00950     }
00951 
00952     return NULL;
00953 }
00954 
00955 // FixedAllocator::DoDeallocate -----------------------------------------------
00956 
00957 void FixedAllocator::DoDeallocate(void* p)
00958 {
00959     // Show that deallocChunk_ really owns the block at address p.
00960     assert( deallocChunk_->HasBlock( p, numBlocks_ * blockSize_ ) );
00961     // Either of the next two assertions may fail if somebody tries to
00962     // delete the same block twice.
00963     assert( emptyChunk_ != deallocChunk_ );
00964     assert( !deallocChunk_->HasAvailable( numBlocks_ ) );
00965     // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
00966     assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
00967 
00968     // call into the chunk, will adjust the inner list but won't release memory
00969     deallocChunk_->Deallocate(p, blockSize_);
00970 
00971     if ( deallocChunk_->HasAvailable( numBlocks_ ) )
00972     {
00973         assert( emptyChunk_ != deallocChunk_ );
00974         // deallocChunk_ is empty, but a Chunk is only released if there are 2
00975         // empty chunks.  Since emptyChunk_ may only point to a previously
00976         // cleared Chunk, if it points to something else besides deallocChunk_,
00977         // then FixedAllocator currently has 2 empty Chunks.
00978         if ( NULL != emptyChunk_ )
00979         {
00980             // If last Chunk is empty, just change what deallocChunk_
00981             // points to, and release the last.  Otherwise, swap an empty
00982             // Chunk with the last, and then release it.
00983             Chunk * lastChunk = &chunks_.back();
00984             if ( lastChunk == deallocChunk_ )
00985                 deallocChunk_ = emptyChunk_;
00986             else if ( lastChunk != emptyChunk_ )
00987                 std::swap( *emptyChunk_, *lastChunk );
00988             assert( lastChunk->HasAvailable( numBlocks_ ) );
00989             lastChunk->Release();
00990             chunks_.pop_back();
00991             if ( ( allocChunk_ == lastChunk ) || allocChunk_->IsFilled() ) 
00992                 allocChunk_ = deallocChunk_;
00993         }
00994         emptyChunk_ = deallocChunk_;
00995     }
00996 
00997     // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
00998     assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
00999 }
01000 
01001 // GetOffset ------------------------------------------------------------------
01004 inline std::size_t GetOffset( std::size_t numBytes, std::size_t alignment )
01005 {
01006     const std::size_t alignExtra = alignment-1;
01007     return ( numBytes + alignExtra ) / alignment;
01008 }
01009 
01010 // DefaultAllocator -----------------------------------------------------------
01019 void * DefaultAllocator( std::size_t numBytes, bool doThrow )
01020 {
01021 #ifdef USE_NEW_TO_ALLOCATE
01022     return doThrow ? ::operator new( numBytes ) :
01023         ::operator new( numBytes, std::nothrow_t() );
01024 #else
01025     void * p = ::std::malloc( numBytes );
01026     if ( doThrow && ( NULL == p ) )
01027         throw std::bad_alloc();
01028     return p;
01029 #endif
01030 }
01031 
01032 // DefaultDeallocator ---------------------------------------------------------
01040 void DefaultDeallocator( void * p )
01041 {
01042 #ifdef USE_NEW_TO_ALLOCATE
01043     ::operator delete( p );
01044 #else
01045     ::std::free( p );
01046 #endif
01047 }
01048 
01049 // SmallObjAllocator::SmallObjAllocator ---------------------------------------
01050 
01051 SmallObjAllocator::SmallObjAllocator( std::size_t pageSize,
01052     std::size_t maxObjectSize, std::size_t objectAlignSize ) :
01053     pool_( NULL ),
01054     maxSmallObjectSize_( maxObjectSize ),
01055     objectAlignSize_( objectAlignSize )
01056 {
01057 #ifdef DO_EXTRA_LOKI_TESTS
01058     std::cout << "SmallObjAllocator " << this << std::endl;
01059 #endif
01060     assert( 0 != objectAlignSize );
01061     const std::size_t allocCount = GetOffset( maxObjectSize, objectAlignSize );
01062     pool_ = new FixedAllocator[ allocCount ];
01063     for ( std::size_t i = 0; i < allocCount; ++i )
01064         pool_[ i ].Initialize( ( i+1 ) * objectAlignSize, pageSize );
01065 }
01066 
01067 // SmallObjAllocator::~SmallObjAllocator --------------------------------------
01068 
01069 SmallObjAllocator::~SmallObjAllocator( void )
01070 {
01071 #ifdef DO_EXTRA_LOKI_TESTS
01072     std::cout << "~SmallObjAllocator " << this << std::endl;
01073 #endif
01074     delete [] pool_;
01075 }
01076 
01077 // SmallObjAllocator::TrimExcessMemory ----------------------------------------
01078 
01079 bool SmallObjAllocator::TrimExcessMemory( void )
01080 {
01081     bool found = false;
01082     const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
01083     std::size_t i = 0;
01084     for ( ; i < allocCount; ++i )
01085     {
01086         if ( pool_[ i ].TrimEmptyChunk() )
01087             found = true;
01088     }
01089     for ( i = 0; i < allocCount; ++i )
01090     {
01091         if ( pool_[ i ].TrimChunkList() )
01092             found = true;
01093     }
01094 
01095     return found;
01096 }
01097 
01098 // SmallObjAllocator::Allocate ------------------------------------------------
01099 
01100 void * SmallObjAllocator::Allocate( std::size_t numBytes, bool doThrow )
01101 {
01102     if ( numBytes > GetMaxObjectSize() )
01103         return DefaultAllocator( numBytes, doThrow );
01104 
01105     assert( NULL != pool_ );
01106     if ( 0 == numBytes ) numBytes = 1;
01107     const std::size_t index = GetOffset( numBytes, GetAlignment() ) - 1;
01108     const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
01109     (void) allocCount;
01110     assert( index < allocCount );
01111 
01112     FixedAllocator & allocator = pool_[ index ];
01113     assert( allocator.BlockSize() >= numBytes );
01114     assert( allocator.BlockSize() < numBytes + GetAlignment() );
01115     void * place = allocator.Allocate();
01116 
01117     if ( ( NULL == place ) && TrimExcessMemory() )
01118         place = allocator.Allocate();
01119 
01120     if ( ( NULL == place ) && doThrow )
01121     {
01122 #ifdef _MSC_VER
01123         throw std::bad_alloc( "could not allocate small object" );
01124 #else
01125         // GCC did not like a literal string passed to std::bad_alloc.
01126         // so just throw the default-constructed exception.
01127         throw std::bad_alloc();
01128 #endif
01129     }
01130     return place;
01131 }
01132 
01133 // SmallObjAllocator::Deallocate ----------------------------------------------
01134 
01135 void SmallObjAllocator::Deallocate( void * p, std::size_t numBytes )
01136 {
01137     if ( NULL == p ) return;
01138     if ( numBytes > GetMaxObjectSize() )
01139     {
01140         DefaultDeallocator( p );
01141         return;
01142     }
01143     assert( NULL != pool_ );
01144     if ( 0 == numBytes ) numBytes = 1;
01145     const std::size_t index = GetOffset( numBytes, GetAlignment() ) - 1;
01146     const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
01147     (void) allocCount;
01148     assert( index < allocCount );
01149     FixedAllocator & allocator = pool_[ index ];
01150     assert( allocator.BlockSize() >= numBytes );
01151     assert( allocator.BlockSize() < numBytes + GetAlignment() );
01152     const bool found = allocator.Deallocate( p, NULL );
01153     (void) found;
01154     assert( found );
01155 }
01156 
01157 // SmallObjAllocator::Deallocate ----------------------------------------------
01158 
01159 void SmallObjAllocator::Deallocate( void * p )
01160 {
01161     if ( NULL == p ) return;
01162     assert( NULL != pool_ );
01163     FixedAllocator * pAllocator = NULL;
01164     const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
01165     Chunk * chunk = NULL;
01166 
01167     for ( std::size_t ii = 0; ii < allocCount; ++ii )
01168     {
01169         chunk = pool_[ ii ].HasBlock( p );
01170         if ( NULL != chunk )
01171         {
01172             pAllocator = &pool_[ ii ];
01173             break;
01174         }
01175     }
01176     if ( NULL == pAllocator )
01177     {
01178         DefaultDeallocator( p );
01179         return;
01180     }
01181 
01182     assert( NULL != chunk );
01183     const bool found = pAllocator->Deallocate( p, chunk );
01184     (void) found;
01185     assert( found );
01186 }
01187 
01188 // SmallObjAllocator::IsCorrupt -----------------------------------------------
01189 
01190 bool SmallObjAllocator::IsCorrupt( void ) const
01191 {
01192     if ( NULL == pool_ )
01193     {
01194         assert( false );
01195         return true;
01196     }
01197     if ( 0 == GetAlignment() )
01198     {
01199         assert( false );
01200         return true;
01201     }
01202     if ( 0 == GetMaxObjectSize() )
01203     {
01204         assert( false );
01205         return true;
01206     }
01207     const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
01208     for ( std::size_t ii = 0; ii < allocCount; ++ii )
01209     {
01210         if ( pool_[ ii ].IsCorrupt() )
01211             return true;
01212     }
01213     return false;
01214 }
01215 
01216 } // end namespace Loki
01217 

Generated on Sun Feb 25 16:52:27 2007 for Loki by  doxygen 1.5.1-p1