1
////////////////////////////////////////////////////////////////////////////////
3
// Copyright (c) 2001 by Andrei Alexandrescu
4
// This code accompanies the book:
5
// Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design
6
// Patterns Applied". Copyright (c) 2001. Addison-Wesley.
7
// Permission to use, copy, modify, distribute and sell this software for any
8
// purpose is hereby granted without fee, provided that the above copyright
9
// notice appear in all copies and that both that copyright notice and this
10
// permission notice appear in supporting documentation.
11
// The author or Addison-Wesley Longman make no representations about the
12
// suitability of this software for any purpose. It is provided "as is"
13
// without express or implied warranty.
14
////////////////////////////////////////////////////////////////////////////////
16
// $Id: SmallObj.cpp 756 2006-10-17 20:05:42Z syntheticpp $
19
#include <loki/SmallObj.h>
25
//#define DO_EXTRA_LOKI_TESTS
26
//#define USE_NEW_TO_ALLOCATE
28
#ifdef DO_EXTRA_LOKI_TESTS
36
@ingroup SmallObjectGroupInternal
37
Contains info about each allocated Chunk - which is a collection of
38
contiguous blocks. Each block is the same size, as specified by the
39
FixedAllocator. The number of blocks in a Chunk depends upon page size.
40
This is a POD-style struct with value-semantics. All functions and data
41
are private so that they can not be changed by anything other than the
42
FixedAllocator which owns the Chunk.
44
@par Minimal Interface
45
For the sake of runtime efficiency, no constructor, destructor, or
46
copy-assignment operator is defined. The inline functions made by the
47
compiler should be sufficient, and perhaps faster than hand-crafted
48
functions. The lack of these functions allows vector to create and copy
49
Chunks as needed without overhead. The Init and Release functions do
50
what the default constructor and destructor would do. A Chunk is not in
51
a usable state after it is constructed and before calling Init. Nor is
52
a Chunk usable after Release is called, but before the destructor.
55
Down near the lowest level of the allocator, runtime efficiencies trump
56
almost all other considerations. Each function does the minimum required
57
of it. All functions should execute in constant time to prevent higher-
58
level code from unwittingly using a version of Shlemiel the Painter's
62
The first char of each empty block contains the index of the next empty
63
block. These stealth indexes form a singly-linked list within the blocks.
64
A Chunk is corrupt if this singly-linked list has a loop or is shorter
65
than blocksAvailable_. Much of the allocator's time and space efficiency
66
comes from how these stealth indexes are implemented.
71
friend class FixedAllocator;
73
/** Initializes a just-constructed Chunk.
74
@param blockSize Number of bytes per block.
75
@param blocks Number of blocks per Chunk.
76
@return True for success, false for failure.
78
bool Init( std::size_t blockSize, unsigned char blocks );
80
/** Allocate a block within the Chunk. Complexity is always O(1), and
81
this will never throw. Does not actually "allocate" by calling
82
malloc, new, or any other function, but merely adjusts some internal
83
indexes to indicate an already allocated block is no longer available.
84
@return Pointer to block within Chunk.
86
void * Allocate( std::size_t blockSize );
88
/** Deallocate a block within the Chunk. Complexity is always O(1), and
89
this will never throw. For efficiency, this assumes the address is
90
within the block and aligned along the correct byte boundary. An
91
assertion checks the alignment, and a call to HasBlock is done from
92
within VicinityFind. Does not actually "deallocate" by calling free,
93
delete, or other function, but merely adjusts some internal indexes to
94
indicate a block is now available.
96
void Deallocate( void * p, std::size_t blockSize );
98
/** Resets the Chunk back to pristine values. The available count is
99
set back to zero, and the first available index is set to the zeroth
100
block. The stealth indexes inside each block are set to point to the
101
next block. This assumes the Chunk's data was already using Init.
103
void Reset( std::size_t blockSize, unsigned char blocks );
105
/// Releases the allocated block of memory.
108
/** Determines if the Chunk has been corrupted.
109
@param numBlocks Total # of blocks in the Chunk.
110
@param blockSize # of bytes in each block.
111
@param checkIndexes True if caller wants to check indexes of available
112
blocks for corruption. If false, then caller wants to skip some
113
tests tests just to run faster. (Debug version does more checks, but
114
release version runs faster.)
115
@return True if Chunk is corrupt.
117
bool IsCorrupt( unsigned char numBlocks, std::size_t blockSize,
118
bool checkIndexes ) const;
120
/** Determines if block is available.
121
@param p Address of block managed by Chunk.
122
@param numBlocks Total # of blocks in the Chunk.
123
@param blockSize # of bytes in each block.
124
@return True if block is available, else false if allocated.
126
bool IsBlockAvailable( void * p, unsigned char numBlocks,
127
std::size_t blockSize ) const;
129
/// Returns true if block at address P is inside this Chunk.
130
inline bool HasBlock( void * p, std::size_t chunkLength ) const
132
unsigned char * pc = static_cast< unsigned char * >( p );
133
return ( pData_ <= pc ) && ( pc < pData_ + chunkLength );
136
inline bool HasAvailable( unsigned char numBlocks ) const
137
{ return ( blocksAvailable_ == numBlocks ); }
139
inline bool IsFilled( void ) const
140
{ return ( 0 == blocksAvailable_ ); }
142
/// Pointer to array of allocated blocks.
143
unsigned char * pData_;
144
/// Index of first empty block.
145
unsigned char firstAvailableBlock_;
146
/// Count of empty blocks.
147
unsigned char blocksAvailable_;
150
/** @class FixedAllocator
151
@ingroup SmallObjectGroupInternal
152
Offers services for allocating fixed-sized objects. It has a container
153
of "containers" of fixed-size blocks. The outer container has all the
154
Chunks. The inner container is a Chunk which owns some blocks.
156
@par Class Level Invariants
157
- There is always either zero or one Chunk which is empty.
158
- If this has no empty Chunk, then emptyChunk_ is NULL.
159
- If this has an empty Chunk, then emptyChunk_ points to it.
160
- If the Chunk container is empty, then deallocChunk_ and allocChunk_
162
- If the Chunk container is not-empty, then deallocChunk_ and allocChunk_
163
are either NULL or point to Chunks within the container.
164
- allocChunk_ will often point to the last Chunk in the container since
165
it was likely allocated most recently, and therefore likely to have an
172
/** Deallocates the block at address p, and then handles the internal
173
bookkeeping needed to maintain class invariants. This assumes that
174
deallocChunk_ points to the correct chunk.
176
void DoDeallocate( void * p );
178
/** Creates an empty Chunk and adds it to the end of the ChunkList.
179
All calls to the lower-level memory allocation functions occur inside
180
this function, and so the only try-catch block is inside here.
181
@return true for success, false for failure.
183
bool MakeNewChunk( void );
185
/** Finds the Chunk which owns the block at address p. It starts at
186
deallocChunk_ and searches in both forwards and backwards directions
187
from there until it finds the Chunk which owns p. This algorithm
188
should find the Chunk quickly if it is deallocChunk_ or is close to it
189
in the Chunks container. This goes both forwards and backwards since
190
that works well for both same-order and opposite-order deallocations.
191
(Same-order = objects are deallocated in the same order in which they
192
were allocated. Opposite order = objects are deallocated in a last to
193
first order. Complexity is O(C) where C is count of all Chunks. This
195
@return Pointer to Chunk that owns p, or NULL if no owner found.
197
Chunk * VicinityFind( void * p ) const;
200
FixedAllocator(const FixedAllocator&);
202
FixedAllocator& operator=(const FixedAllocator&);
204
/// Type of container used to hold Chunks.
205
typedef std::vector< Chunk > Chunks;
206
/// Iterator through container of Chunks.
207
typedef Chunks::iterator ChunkIter;
208
/// Iterator through const container of Chunks.
209
typedef Chunks::const_iterator ChunkCIter;
211
/// Fewest # of objects managed by a Chunk.
212
static unsigned char MinObjectsPerChunk_;
214
/// Most # of objects managed by a Chunk - never exceeds UCHAR_MAX.
215
static unsigned char MaxObjectsPerChunk_;
217
/// Number of bytes in a single block within a Chunk.
218
std::size_t blockSize_;
219
/// Number of blocks managed by each Chunk.
220
unsigned char numBlocks_;
222
/// Container of Chunks.
224
/// Pointer to Chunk used for last or next allocation.
226
/// Pointer to Chunk used for last or next deallocation.
227
Chunk * deallocChunk_;
228
/// Pointer to the only empty Chunk if there is one, else NULL.
232
/// Create a FixedAllocator which manages blocks of 'blockSize' size.
235
/// Destroy the FixedAllocator and release all its Chunks.
238
/// Initializes a FixedAllocator by calculating # of blocks per Chunk.
239
void Initialize( std::size_t blockSize, std::size_t pageSize );
241
/** Returns pointer to allocated memory block of fixed size - or NULL
242
if it failed to allocate.
244
void * Allocate( void );
246
/** Deallocate a memory block previously allocated with Allocate. If
247
the block is not owned by this FixedAllocator, it returns false so
248
that SmallObjAllocator can call the default deallocator. If the
249
block was found, this returns true.
251
bool Deallocate( void * p, Chunk * hint );
253
/// Returns block size with which the FixedAllocator was initialized.
254
inline std::size_t BlockSize() const { return blockSize_; }
256
/** Releases the memory used by the empty Chunk. This will take
257
constant time under any situation.
258
@return True if empty chunk found and released, false if none empty.
260
bool TrimEmptyChunk( void );
262
/** Releases unused spots from ChunkList. This takes constant time
263
with respect to # of Chunks, but actual time depends on underlying
265
@return False if no unused spots, true if some found and released.
267
bool TrimChunkList( void );
269
/** Returns count of empty Chunks held by this allocator. Complexity
270
is O(C) where C is the total number of Chunks - empty or used.
272
std::size_t CountEmptyChunks( void ) const;
274
/** Determines if FixedAllocator is corrupt. Checks data members to
275
see if any have erroneous values, or violate class invariants. It
276
also checks if any Chunk is corrupt. Complexity is O(C) where C is
277
the number of Chunks. If any data is corrupt, this will return true
278
in release mode, or assert in debug mode.
280
bool IsCorrupt( void ) const;
282
/** Returns true if the block at address p is within a Chunk owned by
283
this FixedAllocator. Complexity is O(C) where C is the total number
284
of Chunks - empty or used.
286
const Chunk * HasBlock( void * p ) const;
287
inline Chunk * HasBlock( void * p )
289
return const_cast< Chunk * >(
290
const_cast< const FixedAllocator * >( this )->HasBlock( p ) );
295
unsigned char FixedAllocator::MinObjectsPerChunk_ = 8;
296
unsigned char FixedAllocator::MaxObjectsPerChunk_ = UCHAR_MAX;
298
// Chunk::Init ----------------------------------------------------------------
300
bool Chunk::Init( std::size_t blockSize, unsigned char blocks )
302
assert(blockSize > 0);
305
const std::size_t allocSize = blockSize * blocks;
306
assert( allocSize / blockSize == blocks);
308
#ifdef USE_NEW_TO_ALLOCATE
309
// If this new operator fails, it will throw, and the exception will get
310
// caught one layer up.
311
pData_ = static_cast< unsigned char * >( ::operator new ( allocSize ) );
313
// malloc can't throw, so its only way to indicate an error is to return
314
// a NULL pointer, so we have to check for that.
315
pData_ = static_cast< unsigned char * >( ::std::malloc( allocSize ) );
316
if ( NULL == pData_ ) return false;
319
Reset( blockSize, blocks );
323
// Chunk::Reset ---------------------------------------------------------------
325
void Chunk::Reset(std::size_t blockSize, unsigned char blocks)
327
assert(blockSize > 0);
330
assert((blockSize * blocks) / blockSize == blocks);
332
firstAvailableBlock_ = 0;
333
blocksAvailable_ = blocks;
336
for ( unsigned char * p = pData_; i != blocks; p += blockSize )
342
// Chunk::Release -------------------------------------------------------------
344
void Chunk::Release()
346
assert( NULL != pData_ );
347
#ifdef USE_NEW_TO_ALLOCATE
348
::operator delete ( pData_ );
350
::std::free( static_cast< void * >( pData_ ) );
354
// Chunk::Allocate ------------------------------------------------------------
356
void* Chunk::Allocate(std::size_t blockSize)
358
if ( IsFilled() ) return NULL;
360
assert((firstAvailableBlock_ * blockSize) / blockSize ==
361
firstAvailableBlock_);
362
unsigned char * pResult = pData_ + (firstAvailableBlock_ * blockSize);
363
firstAvailableBlock_ = *pResult;
369
// Chunk::Deallocate ----------------------------------------------------------
371
void Chunk::Deallocate(void* p, std::size_t blockSize)
375
unsigned char* toRelease = static_cast<unsigned char*>(p);
377
assert((toRelease - pData_) % blockSize == 0);
378
unsigned char index = static_cast< unsigned char >(
379
( toRelease - pData_ ) / blockSize);
381
#if defined(DEBUG) || defined(_DEBUG)
382
// Check if block was already deleted. Attempting to delete the same
383
// block more than once causes Chunk's linked-list of stealth indexes to
384
// become corrupt. And causes count of blocksAvailable_ to be wrong.
385
if ( 0 < blocksAvailable_ )
386
assert( firstAvailableBlock_ != index );
389
*toRelease = firstAvailableBlock_;
390
firstAvailableBlock_ = index;
392
assert(firstAvailableBlock_ == (toRelease - pData_) / blockSize);
397
// Chunk::IsCorrupt -----------------------------------------------------------
399
bool Chunk::IsCorrupt( unsigned char numBlocks, std::size_t blockSize,
400
bool checkIndexes ) const
403
if ( numBlocks < blocksAvailable_ )
405
// Contents at this Chunk corrupted. This might mean something has
406
// overwritten memory owned by the Chunks container.
411
// Useless to do further corruption checks if all blocks allocated.
413
unsigned char index = firstAvailableBlock_;
414
if ( numBlocks <= index )
416
// Contents at this Chunk corrupted. This might mean something has
417
// overwritten memory owned by the Chunks container.
422
// Caller chose to skip more complex corruption tests.
425
/* If the bit at index was set in foundBlocks, then the stealth index was
426
found on the linked-list.
428
std::bitset< UCHAR_MAX > foundBlocks;
429
unsigned char * nextBlock = NULL;
431
/* The loop goes along singly linked-list of stealth indexes and makes sure
432
that each index is within bounds (0 <= index < numBlocks) and that the
433
index was not already found while traversing the linked-list. The linked-
434
list should have exactly blocksAvailable_ nodes, so the for loop will not
435
check more than blocksAvailable_. This loop can't check inside allocated
436
blocks for corruption since such blocks are not within the linked-list.
437
Contents of allocated blocks are not changed by Chunk.
439
Here are the types of corrupted link-lists which can be verified. The
440
corrupt index is shown with asterisks in each example.
442
Type 1: Index is too big.
444
blocksAvailable_ == 7
445
firstAvailableBlock_ -> 17 -> 29 -> *101*
446
There should be no indexes which are equal to or larger than the total
447
number of blocks. Such an index would refer to a block beyond the
448
Chunk's allocated domain.
450
Type 2: Index is repeated.
452
blocksAvailable_ == 5
453
firstAvailableBlock_ -> 17 -> 29 -> 53 -> *17* -> 29 -> 53 ...
454
No index should be repeated within the linked-list since that would
455
indicate the presence of a loop in the linked-list.
457
for ( unsigned char cc = 0; ; )
459
nextBlock = pData_ + ( index * blockSize );
460
foundBlocks.set( index, true );
462
if ( cc >= blocksAvailable_ )
463
// Successfully counted off number of nodes in linked-list.
466
if ( numBlocks <= index )
468
/* This catches Type 1 corruptions as shown in above comments.
469
This implies that a block was corrupted due to a stray pointer
470
or an operation on a nearby block overran the size of the block.
475
if ( foundBlocks.test( index ) )
477
/* This catches Type 2 corruptions as shown in above comments.
478
This implies that a block was corrupted due to a stray pointer
479
or an operation on a nearby block overran the size of the block.
480
Or perhaps the program tried to delete a block more than once.
486
if ( foundBlocks.count() != blocksAvailable_ )
488
/* This implies that the singly-linked-list of stealth indexes was
489
corrupted. Ideally, this should have been detected within the loop.
498
// Chunk::IsBlockAvailable ----------------------------------------------------
500
bool Chunk::IsBlockAvailable( void * p, unsigned char numBlocks,
501
std::size_t blockSize ) const
508
unsigned char * place = static_cast< unsigned char * >( p );
510
assert( ( place - pData_ ) % blockSize == 0 );
511
unsigned char blockIndex = static_cast< unsigned char >(
512
( place - pData_ ) / blockSize );
514
unsigned char index = firstAvailableBlock_;
515
assert( numBlocks > index );
516
if ( index == blockIndex )
519
/* If the bit at index was set in foundBlocks, then the stealth index was
520
found on the linked-list.
522
std::bitset< UCHAR_MAX > foundBlocks;
523
unsigned char * nextBlock = NULL;
524
for ( unsigned char cc = 0; ; )
526
nextBlock = pData_ + ( index * blockSize );
527
foundBlocks.set( index, true );
529
if ( cc >= blocksAvailable_ )
530
// Successfully counted off number of nodes in linked-list.
533
if ( index == blockIndex )
535
assert( numBlocks > index );
536
assert( !foundBlocks.test( index ) );
542
// FixedAllocator::FixedAllocator ---------------------------------------------
544
FixedAllocator::FixedAllocator()
548
, allocChunk_( NULL )
549
, deallocChunk_( NULL )
550
, emptyChunk_( NULL )
554
// FixedAllocator::~FixedAllocator --------------------------------------------
556
FixedAllocator::~FixedAllocator()
558
#ifdef DO_EXTRA_LOKI_TESTS
560
assert( chunks_.empty() && "Memory leak detected!" );
562
for ( ChunkIter i( chunks_.begin() ); i != chunks_.end(); ++i )
566
// FixedAllocator::Initialize -------------------------------------------------
568
void FixedAllocator::Initialize( std::size_t blockSize, std::size_t pageSize )
570
assert( blockSize > 0 );
571
assert( pageSize >= blockSize );
572
blockSize_ = blockSize;
574
std::size_t numBlocks = pageSize / blockSize;
575
if ( numBlocks > MaxObjectsPerChunk_ ) numBlocks = MaxObjectsPerChunk_;
576
else if ( numBlocks < MinObjectsPerChunk_ ) numBlocks = MinObjectsPerChunk_;
578
numBlocks_ = static_cast<unsigned char>(numBlocks);
579
assert(numBlocks_ == numBlocks);
582
// FixedAllocator::CountEmptyChunks -------------------------------------------
584
std::size_t FixedAllocator::CountEmptyChunks( void ) const
586
#ifdef DO_EXTRA_LOKI_TESTS
587
// This code is only used for specialized tests of the allocator.
588
// It is #ifdef-ed so that its O(C) complexity does not overwhelm the
589
// functions which call it.
590
std::size_t count = 0;
591
for ( ChunkCIter it( chunks_.begin() ); it != chunks_.end(); ++it )
593
const Chunk & chunk = *it;
594
if ( chunk.HasAvailable( numBlocks_ ) )
599
return ( NULL == emptyChunk_ ) ? 0 : 1;
603
// FixedAllocator::IsCorrupt --------------------------------------------------
605
bool FixedAllocator::IsCorrupt( void ) const
607
const bool isEmpty = chunks_.empty();
608
ChunkCIter start( chunks_.begin() );
609
ChunkCIter last( chunks_.end() );
610
const size_t emptyChunkCount = CountEmptyChunks();
619
if ( 0 < emptyChunkCount )
624
if ( NULL != deallocChunk_ )
629
if ( NULL != allocChunk_ )
634
if ( NULL != emptyChunk_ )
643
const Chunk * front = &chunks_.front();
644
const Chunk * back = &chunks_.back();
650
if ( back < deallocChunk_ )
655
if ( back < allocChunk_ )
660
if ( front > deallocChunk_ )
665
if ( front > allocChunk_ )
671
switch ( emptyChunkCount )
674
if ( emptyChunk_ != NULL )
681
if ( emptyChunk_ == NULL )
686
if ( back < emptyChunk_ )
691
if ( front > emptyChunk_ )
696
if ( !emptyChunk_->HasAvailable( numBlocks_ ) )
698
// This may imply somebody tried to delete a block twice.
707
for ( ChunkCIter it( start ); it != last; ++it )
709
const Chunk & chunk = *it;
710
if ( chunk.IsCorrupt( numBlocks_, blockSize_, true ) )
718
// FixedAllocator::HasBlock ---------------------------------------------------
720
const Chunk * FixedAllocator::HasBlock( void * p ) const
722
const std::size_t chunkLength = numBlocks_ * blockSize_;
723
for ( ChunkCIter it( chunks_.begin() ); it != chunks_.end(); ++it )
725
const Chunk & chunk = *it;
726
if ( chunk.HasBlock( p, chunkLength ) )
732
// FixedAllocator::TrimEmptyChunk ---------------------------------------------
734
bool FixedAllocator::TrimEmptyChunk( void )
736
// prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
737
assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
738
if ( NULL == emptyChunk_ ) return false;
740
// If emptyChunk_ points to valid Chunk, then chunk list is not empty.
741
assert( !chunks_.empty() );
742
// And there should be exactly 1 empty Chunk.
743
assert( 1 == CountEmptyChunks() );
745
Chunk * lastChunk = &chunks_.back();
746
if ( lastChunk != emptyChunk_ )
747
std::swap( *emptyChunk_, *lastChunk );
748
assert( lastChunk->HasAvailable( numBlocks_ ) );
749
lastChunk->Release();
752
if ( chunks_.empty() )
755
deallocChunk_ = NULL;
759
if ( deallocChunk_ == emptyChunk_ )
761
deallocChunk_ = &chunks_.front();
762
assert( deallocChunk_->blocksAvailable_ < numBlocks_ );
764
if ( allocChunk_ == emptyChunk_ )
766
allocChunk_ = &chunks_.back();
767
assert( allocChunk_->blocksAvailable_ < numBlocks_ );
772
assert( 0 == CountEmptyChunks() );
777
// FixedAllocator::TrimChunkList ----------------------------------------------
779
bool FixedAllocator::TrimChunkList( void )
781
if ( chunks_.empty() )
783
assert( NULL == allocChunk_ );
784
assert( NULL == deallocChunk_ );
787
if ( chunks_.size() == chunks_.capacity() )
789
// Use the "make-a-temp-and-swap" trick to remove excess capacity.
790
Chunks( chunks_ ).swap( chunks_ );
795
// FixedAllocator::MakeNewChunk -----------------------------------------------
797
bool FixedAllocator::MakeNewChunk( void )
799
bool allocated = false;
802
std::size_t size = chunks_.size();
803
// Calling chunks_.reserve *before* creating and initializing the new
804
// Chunk means that nothing is leaked by this function in case an
805
// exception is thrown from reserve.
806
if ( chunks_.capacity() == size )
808
if ( 0 == size ) size = 4;
809
chunks_.reserve( size * 2 );
812
allocated = newChunk.Init( blockSize_, numBlocks_ );
814
chunks_.push_back( newChunk );
820
if ( !allocated ) return false;
822
allocChunk_ = &chunks_.back();
823
deallocChunk_ = &chunks_.front();
827
// FixedAllocator::Allocate ---------------------------------------------------
829
void * FixedAllocator::Allocate( void )
831
// prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
832
assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
833
assert( CountEmptyChunks() < 2 );
835
if ( ( NULL == allocChunk_ ) || allocChunk_->IsFilled() )
837
if ( NULL != emptyChunk_ )
839
allocChunk_ = emptyChunk_;
844
for ( ChunkIter i( chunks_.begin() ); ; ++i )
846
if ( chunks_.end() == i )
848
if ( !MakeNewChunk() )
852
if ( !i->IsFilled() )
860
else if ( allocChunk_ == emptyChunk_)
861
// detach emptyChunk_ from allocChunk_, because after
862
// calling allocChunk_->Allocate(blockSize_); the chunk
863
// is no longer empty.
866
assert( allocChunk_ != NULL );
867
assert( !allocChunk_->IsFilled() );
868
void * place = allocChunk_->Allocate( blockSize_ );
870
// prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
871
assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
872
assert( CountEmptyChunks() < 2 );
877
// FixedAllocator::Deallocate -------------------------------------------------
879
bool FixedAllocator::Deallocate( void * p, Chunk * hint )
881
assert(!chunks_.empty());
882
assert(&chunks_.front() <= deallocChunk_);
883
assert(&chunks_.back() >= deallocChunk_);
884
assert( &chunks_.front() <= allocChunk_ );
885
assert( &chunks_.back() >= allocChunk_ );
886
assert( CountEmptyChunks() < 2 );
888
Chunk * foundChunk = ( NULL == hint ) ? VicinityFind( p ) : hint;
889
if ( NULL == foundChunk )
892
assert( foundChunk->HasBlock( p, numBlocks_ * blockSize_ ) );
893
#ifdef LOKI_CHECK_FOR_CORRUPTION
894
if ( foundChunk->IsCorrupt( numBlocks_, blockSize_, true ) )
899
if ( foundChunk->IsBlockAvailable( p, numBlocks_, blockSize_ ) )
905
deallocChunk_ = foundChunk;
907
assert( CountEmptyChunks() < 2 );
912
// FixedAllocator::VicinityFind -----------------------------------------------
914
Chunk * FixedAllocator::VicinityFind( void * p ) const
916
if ( chunks_.empty() ) return NULL;
917
assert(deallocChunk_);
919
const std::size_t chunkLength = numBlocks_ * blockSize_;
920
Chunk * lo = deallocChunk_;
921
Chunk * hi = deallocChunk_ + 1;
922
const Chunk * loBound = &chunks_.front();
923
const Chunk * hiBound = &chunks_.back() + 1;
925
// Special case: deallocChunk_ is the last in the array
926
if (hi == hiBound) hi = NULL;
932
if ( lo->HasBlock( p, chunkLength ) ) return lo;
936
if ( NULL == hi ) break;
943
if ( hi->HasBlock( p, chunkLength ) ) return hi;
944
if ( ++hi == hiBound )
947
if ( NULL == lo ) break;
955
// FixedAllocator::DoDeallocate -----------------------------------------------
957
void FixedAllocator::DoDeallocate(void* p)
959
// Show that deallocChunk_ really owns the block at address p.
960
assert( deallocChunk_->HasBlock( p, numBlocks_ * blockSize_ ) );
961
// Either of the next two assertions may fail if somebody tries to
962
// delete the same block twice.
963
assert( emptyChunk_ != deallocChunk_ );
964
assert( !deallocChunk_->HasAvailable( numBlocks_ ) );
965
// prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
966
assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
968
// call into the chunk, will adjust the inner list but won't release memory
969
deallocChunk_->Deallocate(p, blockSize_);
971
if ( deallocChunk_->HasAvailable( numBlocks_ ) )
973
assert( emptyChunk_ != deallocChunk_ );
974
// deallocChunk_ is empty, but a Chunk is only released if there are 2
975
// empty chunks. Since emptyChunk_ may only point to a previously
976
// cleared Chunk, if it points to something else besides deallocChunk_,
977
// then FixedAllocator currently has 2 empty Chunks.
978
if ( NULL != emptyChunk_ )
980
// If last Chunk is empty, just change what deallocChunk_
981
// points to, and release the last. Otherwise, swap an empty
982
// Chunk with the last, and then release it.
983
Chunk * lastChunk = &chunks_.back();
984
if ( lastChunk == deallocChunk_ )
985
deallocChunk_ = emptyChunk_;
986
else if ( lastChunk != emptyChunk_ )
987
std::swap( *emptyChunk_, *lastChunk );
988
assert( lastChunk->HasAvailable( numBlocks_ ) );
989
lastChunk->Release();
991
if ( ( allocChunk_ == lastChunk ) || allocChunk_->IsFilled() )
992
allocChunk_ = deallocChunk_;
994
emptyChunk_ = deallocChunk_;
997
// prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
998
assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
1001
// GetOffset ------------------------------------------------------------------
1002
/// @ingroup SmallObjectGroupInternal
1003
/// Calculates index into array where a FixedAllocator of numBytes is located.
1004
inline std::size_t GetOffset( std::size_t numBytes, std::size_t alignment )
1006
const std::size_t alignExtra = alignment-1;
1007
return ( numBytes + alignExtra ) / alignment;
1010
// DefaultAllocator -----------------------------------------------------------
1011
/** @ingroup SmallObjectGroupInternal
1012
Calls the default allocator when SmallObjAllocator decides not to handle a
1013
request. SmallObjAllocator calls this if the number of bytes is bigger than
1014
the size which can be handled by any FixedAllocator.
1015
@param numBytes number of bytes
1016
@param doThrow True if this function should throw an exception, or false if it
1017
should indicate failure by returning a NULL pointer.
1019
void * DefaultAllocator( std::size_t numBytes, bool doThrow )
1021
#ifdef USE_NEW_TO_ALLOCATE
1022
return doThrow ? ::operator new( numBytes ) :
1023
::operator new( numBytes, std::nothrow_t() );
1025
void * p = ::std::malloc( numBytes );
1026
if ( doThrow && ( NULL == p ) )
1027
throw std::bad_alloc();
1032
// DefaultDeallocator ---------------------------------------------------------
1033
/** @ingroup SmallObjectGroupInternal
1034
Calls default deallocator when SmallObjAllocator decides not to handle a
1035
request. The default deallocator could be the global delete operator or the
1036
free function. The free function is the preferred default deallocator since
1037
it matches malloc which is the preferred default allocator. SmallObjAllocator
1038
will call this if an address was not found among any of its own blocks.
1040
void DefaultDeallocator( void * p )
1042
#ifdef USE_NEW_TO_ALLOCATE
1043
::operator delete( p );
1049
// SmallObjAllocator::SmallObjAllocator ---------------------------------------
1051
SmallObjAllocator::SmallObjAllocator( std::size_t pageSize,
1052
std::size_t maxObjectSize, std::size_t objectAlignSize ) :
1054
maxSmallObjectSize_( maxObjectSize ),
1055
objectAlignSize_( objectAlignSize )
1057
#ifdef DO_EXTRA_LOKI_TESTS
1058
std::cout << "SmallObjAllocator " << this << std::endl;
1060
assert( 0 != objectAlignSize );
1061
const std::size_t allocCount = GetOffset( maxObjectSize, objectAlignSize );
1062
pool_ = new FixedAllocator[ allocCount ];
1063
for ( std::size_t i = 0; i < allocCount; ++i )
1064
pool_[ i ].Initialize( ( i+1 ) * objectAlignSize, pageSize );
1067
// SmallObjAllocator::~SmallObjAllocator --------------------------------------
1069
SmallObjAllocator::~SmallObjAllocator( void )
1071
#ifdef DO_EXTRA_LOKI_TESTS
1072
std::cout << "~SmallObjAllocator " << this << std::endl;
1077
// SmallObjAllocator::TrimExcessMemory ----------------------------------------
1079
bool SmallObjAllocator::TrimExcessMemory( void )
1082
const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
1084
for ( ; i < allocCount; ++i )
1086
if ( pool_[ i ].TrimEmptyChunk() )
1089
for ( i = 0; i < allocCount; ++i )
1091
if ( pool_[ i ].TrimChunkList() )
1098
// SmallObjAllocator::Allocate ------------------------------------------------
1100
void * SmallObjAllocator::Allocate( std::size_t numBytes, bool doThrow )
1102
if ( numBytes > GetMaxObjectSize() )
1103
return DefaultAllocator( numBytes, doThrow );
1105
assert( NULL != pool_ );
1106
if ( 0 == numBytes ) numBytes = 1;
1107
const std::size_t index = GetOffset( numBytes, GetAlignment() ) - 1;
1108
const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
1110
assert( index < allocCount );
1112
FixedAllocator & allocator = pool_[ index ];
1113
assert( allocator.BlockSize() >= numBytes );
1114
assert( allocator.BlockSize() < numBytes + GetAlignment() );
1115
void * place = allocator.Allocate();
1117
if ( ( NULL == place ) && TrimExcessMemory() )
1118
place = allocator.Allocate();
1120
if ( ( NULL == place ) && doThrow )
1123
throw std::bad_alloc( "could not allocate small object" );
1125
// GCC did not like a literal string passed to std::bad_alloc.
1126
// so just throw the default-constructed exception.
1127
throw std::bad_alloc();
1133
// SmallObjAllocator::Deallocate ----------------------------------------------
1135
void SmallObjAllocator::Deallocate( void * p, std::size_t numBytes )
1137
if ( NULL == p ) return;
1138
if ( numBytes > GetMaxObjectSize() )
1140
DefaultDeallocator( p );
1143
assert( NULL != pool_ );
1144
if ( 0 == numBytes ) numBytes = 1;
1145
const std::size_t index = GetOffset( numBytes, GetAlignment() ) - 1;
1146
const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
1148
assert( index < allocCount );
1149
FixedAllocator & allocator = pool_[ index ];
1150
assert( allocator.BlockSize() >= numBytes );
1151
assert( allocator.BlockSize() < numBytes + GetAlignment() );
1152
const bool found = allocator.Deallocate( p, NULL );
1157
// SmallObjAllocator::Deallocate ----------------------------------------------
1159
void SmallObjAllocator::Deallocate( void * p )
1161
if ( NULL == p ) return;
1162
assert( NULL != pool_ );
1163
FixedAllocator * pAllocator = NULL;
1164
const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
1165
Chunk * chunk = NULL;
1167
for ( std::size_t ii = 0; ii < allocCount; ++ii )
1169
chunk = pool_[ ii ].HasBlock( p );
1170
if ( NULL != chunk )
1172
pAllocator = &pool_[ ii ];
1176
if ( NULL == pAllocator )
1178
DefaultDeallocator( p );
1182
assert( NULL != chunk );
1183
const bool found = pAllocator->Deallocate( p, chunk );
1188
// SmallObjAllocator::IsCorrupt -----------------------------------------------
1190
bool SmallObjAllocator::IsCorrupt( void ) const
1192
if ( NULL == pool_ )
1197
if ( 0 == GetAlignment() )
1202
if ( 0 == GetMaxObjectSize() )
1207
const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
1208
for ( std::size_t ii = 0; ii < allocCount; ++ii )
1210
if ( pool_[ ii ].IsCorrupt() )
1216
} // end namespace Loki
added
removed
ext/loki/loki-0.1.6/src/SmallObj.cpp
