smallobj.cpp

loki库的源代码。loki库是以模板技术和面向对象技术为基础的c++类库。

                {
                    if ( !MakeNewChunk() )
                        return NULL;
                    break;
                }
                if ( !i->IsFilled() )
                {
                    allocChunk_ = &*i;
                    break;
                }
            }
        }
    }
    else if ( allocChunk_ == emptyChunk_ )
        // detach emptyChunk_ from allocChunk_, because after 
        // calling allocChunk_->Allocate(blockSize_); the chunk 
        // isn't any more empty
        emptyChunk_ = NULL;

    assert( allocChunk_ != NULL );
    assert( !allocChunk_->IsFilled() );
    void * place = allocChunk_->Allocate( blockSize_ );

    // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
    assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );

    return place;
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::Deallocate
// Deallocates a block previously allocated with Allocate
// (undefined behavior if called with the wrong pointer)
////////////////////////////////////////////////////////////////////////////////

bool FixedAllocator::Deallocate( void * p, bool doChecks )
{
    if ( doChecks )
    {
        assert( !chunks_.empty() );
        assert( &chunks_.front() <= deallocChunk_ );
        assert( &chunks_.back() >= deallocChunk_ );
        assert( &chunks_.front() <= allocChunk_ );
        assert( &chunks_.back() >= allocChunk_ );
    }

    Chunk * foundChunk = VicinityFind( p );
    if ( doChecks )
    {
        assert( NULL != foundChunk );
    }
    else if ( NULL == foundChunk )
        return false;

    deallocChunk_ = foundChunk;
    DoDeallocate( p );
    return true;
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::VicinityFind (internal)
// Finds the chunk corresponding to a pointer, using an efficient search
////////////////////////////////////////////////////////////////////////////////

FixedAllocator::Chunk * FixedAllocator::VicinityFind( void * p )
{
    if ( chunks_.empty() ) return NULL;
    assert( deallocChunk_ );

    unsigned char * pc = static_cast< unsigned char * >( p );
    const VC_BROKEN_STD::size_t chunkLength = numBlocks_ * blockSize_;

    Chunk * lo = deallocChunk_;
    Chunk * hi = deallocChunk_ + 1;
    Chunk * loBound = &chunks_.front();
    Chunk * hiBound = &chunks_.back() + 1;
    
    // Special case: deallocChunk_ is the last in the array
    if ( hi == hiBound ) hi = NULL;

    for ( ; ; )
    {
        if ( NULL != lo )
        {
            if ( lo->HasBlock( pc, chunkLength ) ) return lo;
            if ( lo == loBound )
            {
                lo = NULL;
                if ( NULL == hi ) break;
            }
            else --lo;
        }

        if ( NULL != hi )
        {
            if ( hi->HasBlock( pc, chunkLength ) ) return hi;
            if ( ++hi == hiBound )
            {
                hi = NULL;
                if ( NULL == lo ) break;
            }
        }
    }

    return NULL;
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::DoDeallocate (internal)
// Performs deallocation. Assumes deallocChunk_ points to the correct chunk
////////////////////////////////////////////////////////////////////////////////

void FixedAllocator::DoDeallocate(void* p)
{
    assert( deallocChunk_->HasBlock( static_cast< unsigned char * >( p ),
        numBlocks_ * blockSize_ ) );
    // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
    assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );

    // call into the chunk, will adjust the inner list but won't release memory
    deallocChunk_->Deallocate( p, blockSize_ );

    if ( deallocChunk_->HasAvailable( numBlocks_ ) )
    {
        assert( emptyChunk_ != deallocChunk_ );
        // deallocChunk_ is empty, but a Chunk is only released if there are 2
        // empty chunks.  Since emptyChunk_ may only point to a previously
        // cleared Chunk, if it points to something else besides deallocChunk_,
        // then FixedAllocator currently has 2 empty Chunks.
        if ( NULL != emptyChunk_ )
        {
            // If last Chunk is empty, just change what deallocChunk_
            // points to, and release the last.  Otherwise, swap an empty
            // Chunk with the last, and then release it.
            Chunk * lastChunk = &chunks_.back();
            if ( lastChunk == deallocChunk_ )
                deallocChunk_ = emptyChunk_;
            else if ( lastChunk != emptyChunk_ )
                std::swap( *emptyChunk_, *lastChunk );
            assert( lastChunk->HasAvailable( numBlocks_ ) );
            lastChunk->Release();
            chunks_.pop_back();
            allocChunk_ = deallocChunk_;
        }
        emptyChunk_ = deallocChunk_;
    }

    // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
    assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
}

////////////////////////////////////////////////////////////////////////////////
// GetOffset
// Calculates index into array where a FixedAllocator of numBytes is located.
////////////////////////////////////////////////////////////////////////////////

inline VC_BROKEN_STD::size_t GetOffset( VC_BROKEN_STD::size_t numBytes,
    VC_BROKEN_STD::size_t alignment )
{
    const VC_BROKEN_STD::size_t alignExtra = alignment - 1;
    return ( numBytes + alignExtra ) / alignment;
}

////////////////////////////////////////////////////////////////////////////////
// DefaultAllocator
// Call to default allocator when SmallObjAllocator decides not to handle request.
////////////////////////////////////////////////////////////////////////////////

void * DefaultAllocator( VC_BROKEN_STD::size_t numBytes, bool doThrow )
{
#ifdef USE_NEW_TO_ALLOCATE
    return doThrow ? ::operator new( numBytes ) :
        ::operator new( numBytes, std::nothrow_t() );
#else
    void * p = ::malloc( numBytes );
    if ( doThrow && ( NULL == p ) )
        throw std::bad_alloc();
    return p;
#endif
}

////////////////////////////////////////////////////////////////////////////////
// DefaultDeallocator
// Call to default deallocator when SmallObjAllocator decides not to handle request.
////////////////////////////////////////////////////////////////////////////////

void DefaultDeallocator( void * p )
{
#ifdef USE_NEW_TO_ALLOCATE
    ::operator delete( p );
#else
    ::free( p );
#endif
}

////////////////////////////////////////////////////////////////////////////////
// SmallObjAllocator::SmallObjAllocator
// Creates a SmallObjAllocator, and all the FixedAllocators within it.  Each
// FixedAllocator is then initialized to use the correct Chunk size.
////////////////////////////////////////////////////////////////////////////////

SmallObjAllocator::SmallObjAllocator( VC_BROKEN_STD::size_t pageSize,
    VC_BROKEN_STD::size_t maxObjectSize, VC_BROKEN_STD::size_t objectAlignSize ) :
    pool_( NULL ),
    maxSmallObjectSize_( maxObjectSize ),
    objectAlignSize_( objectAlignSize )
{
    assert( 0 != objectAlignSize );
    const VC_BROKEN_STD::size_t allocCount =
        GetOffset( maxObjectSize, objectAlignSize );
    pool_ = new FixedAllocator[ allocCount ];
    for ( VC_BROKEN_STD::size_t i = 0; i < allocCount; ++i )
        pool_[ i ].Initialize( ( i+1 ) * objectAlignSize, pageSize );
}

////////////////////////////////////////////////////////////////////////////////
// SmallObjAllocator::~SmallObjAllocator
// Deletes all memory consumed by SmallObjAllocator.
// This deletes all the FixedAllocator's in the pool.
////////////////////////////////////////////////////////////////////////////////

SmallObjAllocator::~SmallObjAllocator( void )
{
    delete [] pool_;
}

////////////////////////////////////////////////////////////////////////////////
// SmallObjAllocator::Allocate
// Handles request to allocate numBytes for 1 object.
// This acts in constant-time - except for the calls to DefaultAllocator
// and sometimes FixedAllocator::Allocate.  It throws bad_alloc only if the
// doThrow parameter is true and can't allocate another block.  Otherwise, it
// provides the no-throw exception safety level.
////////////////////////////////////////////////////////////////////////////////

void * SmallObjAllocator::Allocate( VC_BROKEN_STD::size_t numBytes, bool doThrow )
{
    if ( numBytes > GetMaxObjectSize() )
        return DefaultAllocator( numBytes, doThrow );

    assert( NULL != pool_ );
    if ( 0 == numBytes ) numBytes = 1;
    const VC_BROKEN_STD::size_t index = GetOffset( numBytes, GetAlignment() ) - 1;
    const VC_BROKEN_STD::size_t allocCount =
        GetOffset( GetMaxObjectSize(), GetAlignment() );
    assert( index < allocCount );

    FixedAllocator & allocator = pool_[ index ];
    assert( allocator.BlockSize() >= numBytes );
    assert( allocator.BlockSize() < numBytes + GetAlignment() );
    void * place = allocator.Allocate();
    if ( ( NULL == place ) && doThrow )
    {
#if _MSC_VER
        throw std::bad_alloc( "could not allocate small object" );
#else
        // GCC did not like a literal string passed to std::bad_alloc.
        // so just throw the default-constructed exception.
        throw std::bad_alloc();
#endif
    }
    return place;
}

////////////////////////////////////////////////////////////////////////////////
// SmallObjAllocator::Deallocate
// Handles request to deallocate numBytes for 1 object.
// This will act in constant-time - except for the calls to DefaultDeallocator
// and sometimes FixedAllocator::Deallocate.  It will never throw.
////////////////////////////////////////////////////////////////////////////////

void SmallObjAllocator::Deallocate( void * p, VC_BROKEN_STD::size_t numBytes )
{
    if ( NULL == p ) return;
    if ( numBytes > GetMaxObjectSize() )
    {
        DefaultDeallocator( p );
        return;
    }
    assert( NULL != pool_ );
    if ( 0 == numBytes ) numBytes = 1;
    const VC_BROKEN_STD::size_t index = GetOffset( numBytes, GetAlignment() ) - 1;
    const VC_BROKEN_STD::size_t allocCount =
        GetOffset( GetMaxObjectSize(), GetAlignment() );
    assert( index < allocCount );
    FixedAllocator & allocator = pool_[ index ];
    assert( allocator.BlockSize() >= numBytes );
    assert( allocator.BlockSize() < numBytes + GetAlignment() );
    const bool found = allocator.Deallocate( p, true );
    assert( found );
}

}; // end namespace Loki

////////////////////////////////////////////////////////////////////////////////
// Change log:
// March 20: fix exception safety issue in FixedAllocator::Allocate 
//     (thanks to Chris Udazvinis for pointing that out)
// June 20, 2001: ported by Nick Thurn to gcc 2.95.3. Kudos, Nick!!!
// Aug 02, 2002: Fix in VicinityFind sent by Pavel Vozenilek
// Nov 26, 2004: Re-implemented by Rich Sposato.
// Jun 22, 2005: Fix in FixedAllocator::Allocate by Chad Lehman
////////////////////////////////////////////////////////////////////////////////

// $Log: SmallObj.cpp,v $
// Revision 1.2  2005/07/22 00:41:07  rich_sposato
// Backported newer implementation of Small-Object Allocator back to VC6 since
// it fixes several old bugs.
//