模拟内存分配、释放管理

memory.c

/* simulate memory management.  Abreto 20130806. */

#ifndef	NULL
#define NULL 			( 0 )
#endif

/* Memory size: 64KiB. */
#define _MEMORY_SIZE	( 64 * 1024 )
/* Maxium number of blocks. */
#define _BLOCK_NUM	( _MEMORY_SIZE/4 )

#define _M_ALLOCATED	( 1 )
#define _M_NALLOCATED	( 0 )

struct _memory_block;
typedef char _memory_t[ _MEMORY_SIZE ];
typedef char * _p_memory_t;
typedef struct _memory_block _memory_block_t, *_p_memory_block_t;
typedef unsigned int _memory_address_t;
typedef unsigned int _memory_block_index_t;
typedef unsigned int _size_t;
typedef unsigned char _sign_t;

struct _memory_block
{
	_memory_address_t	__start;
	_size_t				__size;
	_sign_t				__allocated;
};

_memory_t				__memory__;
_memory_block_t			_blocks_table[ _BLOCK_NUM ] = {{0, _MEMORY_SIZE, _M_NALLOCATED}};
_size_t					_nblocks = 1;

_memory_block_index_t
_memory_block_find_free( _size_t __size )
{
	_memory_block_index_t __i = 0;
	for(__i = 0;__i < _nblocks;++__i)
		if( _blocks_table[__i].__size >= __size && _M_NALLOCATED == _blocks_table[__i].__allocated )
			return __i;
	return _BLOCK_NUM;
}

_memory_block_index_t
_memory_block_find_allocated( _p_memory_t __p )
{
	_memory_block_index_t __i = 0;
	_memory_address_t __s = __p - __memory__;
	for(__i = 0;__i < _nblocks;++__i)
		if( __s == _blocks_table[__i].__start )
			return __i;
	return _BLOCK_NUM;
}

void
_memory_block_insert( _memory_block_t __block )
{
	_memory_block_index_t __i = 0, __j = 0;
	while( __i < _nblocks && _blocks_table[__i].__start < __block.__start )
		++__i;
	for( __j = _nblocks; __j > __i; --__j )
		_blocks_table[__j] = _blocks_table[__j - 1];
	_blocks_table[__i] = __block;
	++ _nblocks;
}

void
_memory_block_remove( _memory_block_index_t __i )
{
	for( __i ; __i < _nblocks-1 ; ++ __i )
		_blocks_table[ __i ] = _blocks_table[ __i + 1 ];
	-- _nblocks;
}

void
_memory_block_merger_free( _memory_block_index_t __i )
{
	_memory_block_index_t __j = 0, __k = __i;

	if( _M_NALLOCATED != _blocks_table[__i].__allocated )
		return;

	/* merger blocks ahead. */
	if( __i > 0 )
	{
		for(__j = __i - 1; __j > 0 && _M_NALLOCATED == _blocks_table[__j].__allocated ; -- __j , -- __i )
		{
			_blocks_table[ __j ].__size = _blocks_table[__j].__size + _blocks_table[__i].__size;
			_memory_block_remove( __i );
		}
		if( __j == 0 && _M_NALLOCATED == _blocks_table[__j].__allocated )
		{
			_blocks_table[ __j ].__size = _blocks_table[__j].__size + _blocks_table[__i].__size;
			_memory_block_remove( __i );
			-- __i;
		}
	}

	/* merger blocks following. */
	for( __j = __i + 1 ; __j < _nblocks && _M_NALLOCATED == _blocks_table[__j].__allocated ; __j )
	{
		_blocks_table[__i].__size += _blocks_table[__j].__size;
		_memory_block_remove( __j ); 
	}

	/* ret */;
}

void *
amalloc( _size_t __size )
{
	_memory_block_t __b;
	_memory_block_index_t __a = _memory_block_find_free( __size );

	

	if( __a == _BLOCK_NUM )
		return NULL;

	if( __size == _blocks_table[__a].__size )
	{
		_blocks_table[__a].__allocated = _M_ALLOCATED;
		return (void *)(  __memory__ + _blocks_table[__a].__start );
	}

	if( _nblocks == _BLOCK_NUM )
		return NULL;

	__b.__start = _blocks_table[__a].__start + __size;
	__b.__size = _blocks_table[__a].__size - __size;
	__b.__allocated = _M_NALLOCATED;
	_memory_block_insert( __b );
	_blocks_table[__a].__size = __size;
	_blocks_table[__a].__allocated = _M_ALLOCATED;

	return (void *)(  __memory__ + _blocks_table[__a].__start );
}

void
free( void * __p )
{
	_memory_block_index_t __f = _memory_block_find_allocated( (_p_memory_t)__p );

	if( _BLOCK_NUM == __f )
		return;

	_blocks_table[__f].__allocated = _M_NALLOCATED;
	_memory_block_merger_free( __f );
}