smallobj.cpp

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

////////////////////////////////////////////////////////////////////////////////
// The Loki Library
// Copyright (c) 2001 by Andrei Alexandrescu
// This code accompanies the book:
// Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design 
//     Patterns Applied". Copyright (c) 2001. Addison-Wesley.
// Permission to use, copy, modify, distribute and sell this software for any 
//     purpose is hereby granted without fee, provided that the above copyright 
//     notice appear in all copies and that both that copyright notice and this 
//     permission notice appear in supporting documentation.
// The author or Addison-Wesley Longman make no representations about the 
//     suitability of this software for any purpose. It is provided "as is" 
//     without express or implied warranty.
////////////////////////////////////////////////////////////////////////////////

// $Header: /cvsroot/loki-lib/loki/include/noncc/MSVC/1300/SmallObj.cpp,v 1.3 2005/07/28 07:02:58 syntheticpp Exp $


#include "SmallObj.h"

#include <cassert>
#include <vector>
#include <algorithm>
#include <functional>


using namespace Loki;


namespace Loki
{

////////////////////////////////////////////////////////////////////////////////
// class FixedAllocator
// Offers services for allocating fixed-sized objects
////////////////////////////////////////////////////////////////////////////////

    class FixedAllocator
    {
    private:
        struct Chunk
        {
            bool Init( std::size_t blockSize, unsigned char blocks );
            void* Allocate(std::size_t blockSize);
            void Deallocate(void* p, std::size_t blockSize);
            void Reset(std::size_t blockSize, unsigned char blocks);
            void Release();
            inline bool HasBlock( unsigned char * p, std::size_t chunkLength ) const
            { return ( pData_ <= p ) && ( p < pData_ + chunkLength ); }

            inline bool HasAvailable( unsigned char numBlocks ) const
            { return ( blocksAvailable_ == numBlocks ); }

            inline bool IsFilled( void ) const
            { return ( 0 == blocksAvailable_ ); }

            unsigned char* pData_;
            unsigned char
                firstAvailableBlock_,
                blocksAvailable_;
        };

        // Internal functions
        void DoDeallocate(void* p);

        bool MakeNewChunk( void );

        Chunk * VicinityFind( void * p );

        /// Not implemented.
        FixedAllocator(const FixedAllocator&);
        /// Not implemented.
        FixedAllocator& operator=(const FixedAllocator&);

        // Data
        std::size_t blockSize_;
        unsigned char numBlocks_;
        typedef std::vector<Chunk> Chunks;
        typedef Chunks::iterator ChunkIter;
        typedef Chunks::const_iterator ChunkCIter;
        Chunks chunks_;
        Chunk* allocChunk_;
        Chunk* deallocChunk_;
        Chunk * emptyChunk_;

    public:
        // Create a FixedAllocator able to manage blocks of 'blockSize' size
        FixedAllocator();
        ~FixedAllocator();

        void Initialize( std::size_t blockSize, std::size_t pageSize );

        // Allocate a memory block
        void * Allocate( void );

        // Deallocate a memory block previously allocated with Allocate()
        // (if that's not the case, the behavior is undefined)
        bool Deallocate( void * p, bool doChecks );
        // Returns the block size with which the FixedAllocator was initialized
        inline std::size_t BlockSize() const
        { return blockSize_; }

    };


////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::Chunk::Init
// Initializes a chunk object
////////////////////////////////////////////////////////////////////////////////

bool FixedAllocator::Chunk::Init( std::size_t blockSize, unsigned char blocks )
{
    assert(blockSize > 0);
    assert(blocks > 0);
    // Overflow check
    const std::size_t allocSize = blockSize * blocks;
    assert( allocSize / blockSize == blocks);

#ifdef USE_NEW_TO_ALLOCATE
    // If this new operator fails, it will throw, and the exception will get
    // caught one layer up.
    pData_ = new unsigned char[ allocSize ];
#else
    // malloc can't throw, so its only way to indicate an error is to return
    // a NULL pointer, so we have to check for that.
    pData_ = static_cast< unsigned char * >( ::malloc( allocSize ) );
    if ( NULL == pData_ ) return false;
#endif

    Reset( blockSize, blocks );
    return true;
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::Chunk::Reset
// Clears an already allocated chunk
////////////////////////////////////////////////////////////////////////////////

void FixedAllocator::Chunk::Reset(std::size_t blockSize, unsigned char blocks)
{
    assert(blockSize > 0);
    assert(blocks > 0);
    // Overflow check
    assert((blockSize * blocks) / blockSize == blocks);

    firstAvailableBlock_ = 0;
    blocksAvailable_ = blocks;

    unsigned char i = 0;
    unsigned char* p = pData_;
    for (; i != blocks; p += blockSize)
    {
        *p = ++i;
    }
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::Chunk::Release
// Releases the data managed by a chunk
////////////////////////////////////////////////////////////////////////////////

void FixedAllocator::Chunk::Release()
{
    assert( NULL != pData_ );
#ifdef USE_NEW_TO_ALLOCATE
    delete [] pData_;
#else
    ::free( static_cast< void * >( pData_ ) );
#endif
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::Chunk::Allocate
// Allocates a block from a chunk
////////////////////////////////////////////////////////////////////////////////

void* FixedAllocator::Chunk::Allocate(std::size_t blockSize)
{
    if ( IsFilled() ) return NULL;

    assert((firstAvailableBlock_ * blockSize) / blockSize == 
        firstAvailableBlock_);
    unsigned char * pResult = pData_ + (firstAvailableBlock_ * blockSize);
    firstAvailableBlock_ = *pResult;
    --blocksAvailable_;

    return pResult;
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::Chunk::Deallocate
// Dellocates a block from a chunk
////////////////////////////////////////////////////////////////////////////////

void FixedAllocator::Chunk::Deallocate(void* p, std::size_t blockSize)
{
    assert(p >= pData_);

    unsigned char* toRelease = static_cast<unsigned char*>(p);
    // Alignment check
    assert((toRelease - pData_) % blockSize == 0);

    *toRelease = firstAvailableBlock_;
    firstAvailableBlock_ = static_cast<unsigned char>(
        (toRelease - pData_) / blockSize);
    // Truncation check
    assert(firstAvailableBlock_ == (toRelease - pData_) / blockSize);

    ++blocksAvailable_;
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::FixedAllocator
// Creates a FixedAllocator object of a fixed block size
////////////////////////////////////////////////////////////////////////////////

FixedAllocator::FixedAllocator()
    : blockSize_( 0 )
    , allocChunk_( NULL )
    , deallocChunk_( NULL )
    , emptyChunk_( NULL )
{
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::~FixedAllocator
////////////////////////////////////////////////////////////////////////////////

FixedAllocator::~FixedAllocator()
{
    for ( ChunkIter i( chunks_.begin() ); i != chunks_.end(); ++i )
       i->Release();
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::Initialize
// Initializes the operational constraints for the FixedAllocator
////////////////////////////////////////////////////////////////////////////////

void FixedAllocator::Initialize( std::size_t blockSize, std::size_t pageSize )
{
    assert( blockSize > 0 );
    assert( pageSize >= blockSize );
    blockSize_ = blockSize;

    std::size_t numBlocks = pageSize / blockSize;
    if (numBlocks > UCHAR_MAX) numBlocks = UCHAR_MAX;
    else if ( numBlocks < 8 ) numBlocks = 8;

    numBlocks_ = static_cast<unsigned char>(numBlocks);
    assert(numBlocks_ == numBlocks);
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::MakeNewChunk
// Allocates a new Chunk for a FixedAllocator.
////////////////////////////////////////////////////////////////////////////////

bool FixedAllocator::MakeNewChunk( void )
{
    bool allocated = false;
    try
    {
        // Calling chunks_.reserve *before* creating and initializing the new
        // Chunk means that nothing is leaked by this function in case an
        // exception is thrown from reserve.
        chunks_.reserve( chunks_.size() + 1 );
        Chunk newChunk;
        allocated = newChunk.Init( blockSize_, numBlocks_ );
        if ( allocated )
            chunks_.push_back( newChunk );
    }
    catch ( ... )
    {
        allocated = false;
    }
    if ( !allocated ) return false;

    allocChunk_ = &chunks_.back();
    deallocChunk_ = &chunks_.front();
    return true;
}

////////////////////////////////////////////////////////////////////////////////
// FixedAllocator::Allocate
// Allocates a block of fixed size
////////////////////////////////////////////////////////////////////////////////

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

    if ( ( NULL == allocChunk_ ) || allocChunk_->IsFilled() )
    {
        if ( NULL != emptyChunk_ )
        {
            allocChunk_ = emptyChunk_;
            emptyChunk_ = NULL;
        }
        else
        {
            for ( ChunkIter i( chunks_.begin() ); ; ++i )
            {
                if ( chunks_.end() == i )
                {
                    if ( !MakeNewChunk() )
                        return NULL;