00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00015
00016
00017
00018
00019 #include <loki/SmallObj.h>
00020
00021 #include <cassert>
00022 #include <vector>
00023 #include <bitset>
00024
00025
00026
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
00299
00300 bool Chunk::Init( std::size_t blockSize, unsigned char blocks )
00301 {
00302 assert(blockSize > 0);
00303 assert(blocks > 0);
00304
00305 const std::size_t allocSize = blockSize * blocks;
00306 assert( allocSize / blockSize == blocks);
00307
00308 #ifdef USE_NEW_TO_ALLOCATE
00309
00310
00311 pData_ = static_cast< unsigned char * >( ::operator new ( allocSize ) );
00312 #else
00313
00314
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
00324
00325 void Chunk::Reset(std::size_t blockSize, unsigned char blocks)
00326 {
00327 assert(blockSize > 0);
00328 assert(blocks > 0);
00329
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
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
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
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
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
00383
00384
00385 if ( 0 < blocksAvailable_ )
00386 assert( firstAvailableBlock_ != index );
00387 #endif
00388
00389 *toRelease = firstAvailableBlock_;
00390 firstAvailableBlock_ = index;
00391
00392 assert(firstAvailableBlock_ == (toRelease - pData_) / blockSize);
00393
00394 ++blocksAvailable_;
00395 }
00396
00397
00398
00399 bool Chunk::IsCorrupt( unsigned char numBlocks, std::size_t blockSize,
00400 bool checkIndexes ) const
00401 {
00402
00403 if ( numBlocks < blocksAvailable_ )
00404 {
00405
00406
00407 assert( false );
00408 return true;
00409 }
00410 if ( IsFilled() )
00411
00412 return false;
00413 unsigned char index = firstAvailableBlock_;
00414 if ( numBlocks <= index )
00415 {
00416
00417
00418 assert( false );
00419 return true;
00420 }
00421 if ( !checkIndexes )
00422
00423 return false;
00424
00425
00426
00427
00428 std::bitset< UCHAR_MAX > foundBlocks;
00429 unsigned char * nextBlock = NULL;
00430
00431
00432
00433
00434
00435
00436
00437
00438
00439
00440
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450
00451
00452
00453
00454
00455
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
00464 break;
00465 index = *nextBlock;
00466 if ( numBlocks <= index )
00467 {
00468
00469
00470
00471
00472 assert( false );
00473 return true;
00474 }
00475 if ( foundBlocks.test( index ) )
00476 {
00477
00478
00479
00480
00481
00482 assert( false );
00483 return true;
00484 }
00485 }
00486 if ( foundBlocks.count() != blocksAvailable_ )
00487 {
00488
00489
00490
00491 assert( false );
00492 return true;
00493 }
00494
00495 return false;
00496 }
00497
00498
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
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
00520
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
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
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
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
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
00583
00584 std::size_t FixedAllocator::CountEmptyChunks( void ) const
00585 {
00586 #ifdef DO_EXTRA_LOKI_TESTS
00587
00588
00589
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
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
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
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
00733
00734 bool FixedAllocator::TrimEmptyChunk( void )
00735 {
00736
00737 assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
00738 if ( NULL == emptyChunk_ ) return false;
00739
00740
00741 assert( !chunks_.empty() );
00742
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
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
00790 Chunks( chunks_ ).swap( chunks_ );
00791
00792 return true;
00793 }
00794
00795
00796
00797 bool FixedAllocator::MakeNewChunk( void )
00798 {
00799 bool allocated = false;
00800 try
00801 {
00802 std::size_t size = chunks_.size();
00803
00804
00805
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
00828
00829 void * FixedAllocator::Allocate( void )
00830 {
00831
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
00862
00863
00864 emptyChunk_ = NULL;
00865
00866 assert( allocChunk_ != NULL );
00867 assert( !allocChunk_->IsFilled() );
00868 void * place = allocChunk_->Allocate( blockSize_ );
00869
00870
00871 assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
00872 assert( CountEmptyChunks() < 2 );
00873
00874 return place;
00875 }
00876
00877
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
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
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
00956
00957 void FixedAllocator::DoDeallocate(void* p)
00958 {
00959
00960 assert( deallocChunk_->HasBlock( p, numBlocks_ * blockSize_ ) );
00961
00962
00963 assert( emptyChunk_ != deallocChunk_ );
00964 assert( !deallocChunk_->HasAvailable( numBlocks_ ) );
00965
00966 assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
00967
00968
00969 deallocChunk_->Deallocate(p, blockSize_);
00970
00971 if ( deallocChunk_->HasAvailable( numBlocks_ ) )
00972 {
00973 assert( emptyChunk_ != deallocChunk_ );
00974
00975
00976
00977
00978 if ( NULL != emptyChunk_ )
00979 {
00980
00981
00982
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
00998 assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
00999 }
01000
01001
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
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
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
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
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
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
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
01126
01127 throw std::bad_alloc();
01128 #endif
01129 }
01130 return place;
01131 }
01132
01133
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
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
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 }
01217