alloctor.cpp

开放源码的编译器open watcom 1.6.0版的源代码

#include <iostream.h>
#include <wclist.h>
#include <wclistit.h>
#include <wcskip.h>
#include <wcskipit.h>
#include <stdlib.h>

#pragma warning 549 9

const int ElemsPerBlock = 50;

//
// Simple block allocation class.  Allocate blocks for ElemsPerBlock
// elements, and use part of the block for each of the next ElemsPerBlock
// allocations, incrementing the number allocated elements.  Repeat getting
// more blocks as needed.
//
// Store the blocks in an intrusive single linked list.
//
// On a element deallocation, assume we allocated the memory and just
// decrement the count of allocated elements.  When the count gets to zero,
// free all allocated blocks
//
// This implementation assumes sizeof( char ) == 1
// 

class BlockAlloc {
private:
    // the size of elements (in bytes)
    unsigned elem_size;			

    // number of elements allocated
    unsigned num_allocated;		

    // free space of this number of elements available in first block
    unsigned num_free_in_block;		

    // list of blocks used to store elements (block are chunks of memory,
    // pointed by (char *) pointers.
    WCPtrSList<char> block_list;
   
    // pointer to the first block in the list 
    char *curr_block;

public:
    inline BlockAlloc( unsigned size ) 
    		: elem_size( size ), num_allocated( 0 )
		, num_free_in_block( 0 ) {};
		

    inline ~BlockAlloc() {
	block_list.clearAndDestroy();
    };
    
    // get memory for an element using block allocation 
    void *allocator( size_t elem_size );

    // free memory for an element using block allocation and deallocation
    void deallocator( void *old_ptr, size_t elem_size );
};
		

void *BlockAlloc::allocator( size_t size ) {
    // need a new block to perform allocation
    if( num_free_in_block == 0 ) {
	// allocate memory for ElemsPerBlock elements
	curr_block = new char[ size * ElemsPerBlock ];
	if( curr_block == 0 ) {
	    // allocation failed
	    return( 0 );
	}
	// add new block to beginning of list
	if( !block_list.insert( curr_block ) ) {
	    // allocation of list element failed
	    delete( curr_block );
	    return( 0 );
	}
	num_free_in_block = ElemsPerBlock;
    }
    
    // curr block points to a block of memory with some free memory
    num_allocated++;
    num_free_in_block--;
    // return pointer to a free part of the block, starting at the end
    // of the block
    return( curr_block + num_free_in_block * size );
}
	

void BlockAlloc::deallocator( void *, size_t ) {
    // just decrement the count
    // don't free anything until all elements are deallocated
    num_allocated--;
    if( num_allocated == 0 ) {
	// all the elements allocated BlockAlloc object have now been
	// deallocated, free all the blocks
	block_list.clearAndDestroy();
	num_free_in_block = 0;
    }
}
	



const unsigned NumTestElems = 200;

// array with random elements
static unsigned test_elems[ NumTestElems ];

static void fill_test_elems() {
    for( int i = 0; i < NumTestElems; i++ ) {
	test_elems[ i ] = rand();
    }
} 



void test_isv_list();
void test_val_list();
void test_val_skip_list();


void main() {
    fill_test_elems();

    test_isv_list();
    test_val_list();
    test_val_skip_list();
}


// An intrusive list class

class isvInt : public WCSLink {
public:
    static BlockAlloc memory_manage;
    int data;

    isvInt( int datum ) : data( datum ) {};

    void *operator new( size_t size ) {
	return( memory_manage.allocator( size ) );
    };

    void operator delete( void *old, size_t size ) {
	memory_manage.deallocator( old, size );
    };
};

// define static member data
BlockAlloc isvInt::memory_manage( sizeof( isvInt ) );


void test_isv_list() {
    WCIsvSList<isvInt> list;
    
    for( int i = 0; i < NumTestElems; i++ ) {
	list.insert( new isvInt( test_elems[ i ] ) );
    }

    WCIsvSListIter<isvInt> iter( list );
    while( ++iter ) {
	cout << iter.current()->data << " ";
    }
    cout << "\n\n\n";
    list.clearAndDestroy();
}


// WCValSList<int> memory allocator/dealloctor support
static BlockAlloc val_list_manager( WCValSListItemSize( int ) );

static void *val_list_alloc( size_t size ) {
    return( val_list_manager.allocator( size ) );
}

static void val_list_dealloc( void *old, size_t size ) {
    val_list_manager.deallocator( old, size );
}


// test WCValSList<int>
void test_val_list() {
    WCValSList<int> list( &val_list_alloc, &val_list_dealloc );
    
    for( int i = 0; i < NumTestElems; i++ ) {
	list.insert( test_elems[ i ] );
    }
    
    WCValSListIter<int> iter( list );
    while( ++iter ) {
	cout << iter.current() << " ";
    }
    cout << "\n\n\n";
    list.clear();
}


// skip list allocator dealloctors: just use allocator and dealloctor
// functions on skip list elements with one and two pointers
// (this will handle 94% of the elements)
const int one_ptr_size = WCValSkipListItemSize( int, 1 );
const int two_ptr_size = WCValSkipListItemSize( int, 2 );

static BlockAlloc one_ptr_manager( one_ptr_size );
static BlockAlloc two_ptr_manager( two_ptr_size );

static void *val_skip_list_alloc( size_t size ) {
    switch( size ) {
	case one_ptr_size:
	    return( one_ptr_manager.allocator( size ) );
	case two_ptr_size:
	    return( two_ptr_manager.allocator( size ) );
	default:
	    return( new char[ size ] );
    }
}

static void val_skip_list_dealloc( void *old, size_t size ) {
    switch( size ) {
	case one_ptr_size:
	    one_ptr_manager.deallocator( old, size );
	    break;
	case two_ptr_size:
	    two_ptr_manager.deallocator( old, size );
	    break;
	default:
	    delete old;
	    break;
    }
}


// test WCValSkipList<int>
void test_val_skip_list() {
    WCValSkipList<int> skiplist( WCSKIPLIST_PROB_QUARTER
    			       , WCDEFAULT_SKIPLIST_MAX_PTRS
			       , &val_skip_list_alloc
    			       , &val_skip_list_dealloc );
    
    for( int i = 0; i < NumTestElems; i++ ) {
	skiplist.insert( test_elems[ i ] );
    }
    
    WCValSkipListIter<int> iter( skiplist );
    while( ++iter ) {
	cout << iter.current() << " ";
    }
    cout << "\n\n\n";
    skiplist.clear();
}