学步园

对大小固定的对象提供的对象池工具，当对内存分配的请求大小不固定时，使用其它的通用内存池.

fix_obj_pool.h

#ifndef _FIX_OBJ_POOL_H
#define _FIX_OBJ_POOL_H


struct fix_obj_pool;


/*
* obj_size:对象大小
* default_size:默认对象池大小
* align4:返回的对象地址是否需要对齐到4字节
*/
extern struct fix_obj_pool *create_pool(unsigned int obj_size,int default_size,int align4);

extern void destroy_pool(struct fix_obj_pool **pool);

/*
* 分配和回收
*/
extern void *pool_alloc(struct fix_obj_pool*);

extern void  pool_dealloc(struct fix_obj_pool*,void*);

extern unsigned int alignsize(unsigned int obj_size);

extern unsigned int get_free_size(struct fix_obj_pool *pool);

#endif

fix_obj_pool.c

#include "fix_obj_pool.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

static const  char invalid_index = -1;
static const  unsigned int BLOCK_OBJ_SIZE = 128;
struct block
{
	char m_head;
	char m_tail;
	unsigned short m_freesize;
	struct block *m_next_block;
	unsigned int obj_size;//单个对象的大小
	union
	{
		char m_objs[1];
		unsigned int pad;
	};
};

inline void *block_get(struct block *_block,unsigned int index)
{
	return (void*)&_block->m_objs[_block->obj_size * index];
}

inline int  block_check(struct block *_block,void *obj)
{
	if((char*)obj < _block->m_objs || (char*)obj >= (char*)block_get(_block,BLOCK_OBJ_SIZE))
		return 0;
	return 1;
}


void block_destroy(struct block **_block)
{
	free(*_block);
	*_block = 0;
}

void block_init(struct block *_block,unsigned int obj_size)
{
	_block->m_head = 0;
	_block->m_tail = BLOCK_OBJ_SIZE-1;
	_block->m_freesize = BLOCK_OBJ_SIZE;
	_block->obj_size = obj_size;
	int i;
	for(i = 0; i < BLOCK_OBJ_SIZE-1; ++i)
	{
		char *link = (char*)block_get(_block,i);
		*link = i+1;
	}
	char *link = (char*)block_get(_block,BLOCK_OBJ_SIZE-1);
	*link = invalid_index;
	_block->m_next_block = 0;
}

struct block *block_create(unsigned int obj_size)
{
	struct block *_block = malloc(sizeof(*_block) + obj_size*BLOCK_OBJ_SIZE - sizeof(unsigned int));
	block_init(_block,obj_size);
	return _block;
}

void* block_alloc(struct block *_block)
{
	if(_block->m_head == invalid_index)
		return 0;

	char *obj = (char*)block_get(_block,_block->m_head);
	_block->m_head = *obj;

	if(_block->m_head == invalid_index)
		_block->m_tail = invalid_index;		
	*obj = invalid_index;
	--_block->m_freesize;
	return (void*)obj;
}

inline unsigned int block_get_obj_index(struct block *_block,void* obj)
{
	unsigned int offset = (char*)obj - _block->m_objs;
	return offset/_block->obj_size;
}

void block_dealloc(struct block *_block,void* obj)
{
	assert(block_check(_block,obj));
	char *link = (char *)obj;
	*link = invalid_index;
	char index = (char)block_get_obj_index(_block,obj);
	if(_block->m_tail == invalid_index)
	{
		_block->m_head = index;
	}
	else
	{
		*(char*)block_get(_block,_block->m_tail) = index;	
	}
	_block->m_tail = index;
	++_block->m_freesize;
}

inline unsigned char block_getfreesize(struct block *_block)
{
	return _block->m_freesize;
}

inline void block_SetNextBlock(struct block *_block,struct block *next)
{
	_block->m_next_block = next;
}

inline struct block *block_GetNext(struct block *_block)
{
	return _block->m_next_block;
}

inline char *block_GetLastAddr(struct block *_block)
{
	return (char*)block_get(_block,BLOCK_OBJ_SIZE-1);
}

struct chunk
{
	struct block *m_head;
	struct block *m_tail;
	unsigned int m_freesize;
	unsigned int obj_size;
	unsigned int block_count;
	unsigned int block_size;
	struct chunk *m_next;
	struct block m_blocks[1];
};

inline struct block *chunk_get(struct chunk *_chunk,unsigned int index)
{
	char *tmp = (char*)_chunk->m_blocks;
	return (struct block *)&tmp[_chunk->block_size*index];
}

void chunk_init(struct chunk *_chunk,unsigned int block_count,unsigned int block_size,unsigned int obj_size)
{
	_chunk->m_freesize = block_count*BLOCK_OBJ_SIZE;
	_chunk->block_size = block_size;
	_chunk->block_count = block_count;
	unsigned int i;
	for(i = 0; i < block_count; ++i)
	{
		block_init(chunk_get(_chunk,i),obj_size);
	}
	for(i = 0; i < block_count-1; ++i)
	{
		block_SetNextBlock(chunk_get(_chunk,i),chunk_get(_chunk,i+1));
	}
	block_SetNextBlock(chunk_get(_chunk,block_count-1),0);
	_chunk->m_head = chunk_get(_chunk,0);
	_chunk->m_tail = chunk_get(_chunk,block_count-1);
	_chunk->m_next = 0;
}

struct chunk *chunk_create(unsigned int block_count,unsigned int obj_size)
{
	unsigned int block_size = sizeof(struct block) + obj_size * BLOCK_OBJ_SIZE - sizeof(unsigned int);
	unsigned int chunk_size = block_size*block_count;
	struct chunk *_chunk = malloc(sizeof(*_chunk) + chunk_size - sizeof(_chunk->m_blocks));
	chunk_init(_chunk,block_count,block_size,obj_size);
	return _chunk;
}

void chunk_destroy(struct chunk **_chunk)
{
	free(*_chunk);
	*_chunk = 0;
}

void* chunk_alloc(struct chunk *_chunk)
{

	if(!_chunk->m_head)
		return 0;
	void *ret = block_alloc(_chunk->m_head);
	if(block_getfreesize(_chunk->m_head) == 0)
	{
		struct block *next = block_GetNext(_chunk->m_head);
		block_SetNextBlock(_chunk->m_head,0);
		if(!next)
			_chunk->m_head = _chunk->m_tail = 0;
		else
			_chunk->m_head = next;
	}
	--_chunk->m_freesize;
	return ret;				
}

inline int chunk_check(struct chunk *_chunk,void *obj)
{
	if((char*)obj < (char*)_chunk->m_blocks || (char*)obj >= (char*)chunk_get(_chunk,_chunk->block_count))
		return 0;
	return 1;	
}

void chunk_dealloc(struct chunk *_chunk,void* obj)
{
	assert(chunk_check(_chunk,obj));
	int index = (int)(((char*)obj - (char*)&_chunk->m_blocks[0])/_chunk->block_size);
	block_dealloc(chunk_get(_chunk,index),obj);
	
	if(block_getfreesize(chunk_get(_chunk,index)) == 1)
	{
		if(!_chunk->m_tail)
		{
			_chunk->m_head = chunk_get(_chunk,index);
		}
		else
		{
			block_SetNextBlock(_chunk->m_tail,chunk_get(_chunk,index));
		}
		_chunk->m_tail = chunk_get(_chunk,index);
	}
	++_chunk->m_freesize;
}

inline unsigned int chunk_GetFreeSize(struct chunk *_chunk)
{
	return _chunk->m_freesize;
}

inline char *chunk_GetBlocksAddr(struct chunk *_chunk)
{
	return (char*)_chunk->m_blocks;
}

inline char *chunk_GetLastAddr(struct chunk *_chunk)
{
	return (char*)block_GetLastAddr(chunk_get(_chunk,_chunk->block_count-1));
}

inline void chunk_SetNext(struct chunk *_chunk, struct chunk * next)
{
	_chunk->m_next = next;
}

inline struct chunk *chunk_GetNext(struct chunk *_chunk)
{
	return _chunk->m_next;
}

#define DEFAULT_CHUNK_COUNT 128 //当chunk数量大于此值时将采用动态分配
struct fix_obj_pool
{
	struct chunk *m_lastDeAlloc;
	struct chunk *m_head;
	struct chunk *m_tail;
	struct chunk **ptr_chunk;
	unsigned int  chunk_count;
	unsigned int  obj_size;
	int           default_size;
	struct chunk *chunks[DEFAULT_CHUNK_COUNT];
};

unsigned int alignsize(unsigned int obj_size)
{
	if(obj_size % 4 > 0)
		obj_size = (obj_size / 4) * 4 + 4;
	return obj_size;
}


struct fix_obj_pool *create_pool(unsigned int obj_size,int default_size,int align4)
{
	//将default_size规整为128的倍数
	if(default_size <= 0)
		default_size = BLOCK_OBJ_SIZE;
	else
	{
		if(default_size % BLOCK_OBJ_SIZE > 0)
			default_size = (default_size / BLOCK_OBJ_SIZE) * BLOCK_OBJ_SIZE + BLOCK_OBJ_SIZE;
	}

	struct fix_obj_pool *pool = malloc(sizeof(*pool));
	if(pool)
	{
		if(align4)
			obj_size = alignsize(obj_size);
		struct chunk *_chunk = chunk_create(default_size/BLOCK_OBJ_SIZE,obj_size);
		pool->m_lastDeAlloc = 0;
		pool->m_head = pool->m_tail = _chunk;
		pool->chunk_count = 1;
		pool->ptr_chunk = pool->chunks;
		pool->ptr_chunk[0] = _chunk;
		pool->obj_size = obj_size;
		pool->default_size = default_size;
	}
	return pool;
	
}

void destroy_pool(struct fix_obj_pool **pool)
{
	unsigned int i = 0;
	for( ; i < (*pool)->chunk_count; ++i)
		chunk_destroy(&((*pool)->ptr_chunk[i]));
	if((*pool)->ptr_chunk != (*pool)->chunks)
		free((*pool)->ptr_chunk);
	free(*pool);
}


void* pool_alloc(struct fix_obj_pool *pool)
{

	void *ret = chunk_alloc(pool->m_head);
	if(chunk_GetFreeSize(pool->m_head) == 0)
	{
		pool->m_head = chunk_GetNext(pool->m_head);
		if(!pool->m_head)
		{
			//没有空间了，扩展新的块
			struct chunk *_chunk = chunk_create(pool->default_size/BLOCK_OBJ_SIZE,pool->obj_size);
			if(!_chunk)
				return 0;
			pool->m_head = pool->m_tail = _chunk;
			pool->chunk_count++;
			if(pool->chunk_count > DEFAULT_CHUNK_COUNT)
			{
				struct chunk **tmp = malloc(sizeof(*tmp)*pool->chunk_count);
				int i = 0;
				for( ; i < pool->chunk_count - 1;++i)
					tmp[i] = pool->ptr_chunk[i];
				tmp[pool->chunk_count - 1] = _chunk;
				
				if(pool->ptr_chunk != pool->chunks)
					free(pool->ptr_chunk);
				pool->ptr_chunk = tmp;
			}
			
			//对所有的chunk按其地址顺序排序
			unsigned int size = pool->chunk_count;
			int i = size-2;
			for( ; i >= 0; --i)
			{
				if(pool->m_head < pool->ptr_chunk[i])
				{
					struct chunk *tmp = pool->ptr_chunk[i];
					pool->ptr_chunk[i] = pool->m_head;
					pool->ptr_chunk[i+1] = tmp;
				}
				else
				{
					pool->ptr_chunk[i+1] = pool->m_head;
					break;
				}
			}
		}
	}
	return ret;	
}

struct chunk *BinSearch(struct fix_obj_pool *pool,void *obj)
{
	int beg = 0;
	int end = (int)pool->chunk_count;
	int len = end - beg;
	while(len > 0)
	{
		int mid = beg + len/2;
		
		if(chunk_check(pool->ptr_chunk[mid],obj) == 1)
			return pool->ptr_chunk[mid];
		else if((char*)obj > chunk_GetBlocksAddr(pool->ptr_chunk[mid]))
			beg = mid + 1;
		else
			end = mid - 1;
		len = end - beg;
	}
	if(chunk_check(pool->ptr_chunk[beg],obj) == 1)
		return pool->ptr_chunk[beg];
	return 0;
}

void pool_dealloc(struct fix_obj_pool *pool,void* obj)
{
	struct chunk *_chunk = pool->m_lastDeAlloc;
	if(!_chunk || chunk_check(_chunk,obj) == 0)
		_chunk = BinSearch(pool,obj);
	if(_chunk)
	{
		chunk_dealloc(_chunk,obj);
		if(chunk_GetFreeSize(_chunk) == 1)
		{
			if(pool->m_head)
			{
				chunk_SetNext(pool->m_tail,_chunk);
				pool->m_tail = _chunk;
			}
			else
				pool->m_head = pool->m_tail = _chunk;
		}
		pool->m_lastDeAlloc = _chunk;
	}
}

unsigned int get_free_size(struct fix_obj_pool *pool)
{
	unsigned int totalsize = 0;
	int i = 0; 
	for( ; i < pool->chunk_count; ++i)
	{
		totalsize += chunk_GetFreeSize(pool->ptr_chunk[i]);
	}
	return totalsize;
}