#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 singly linked list.
//
// On an 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();
}