
平台论坛博客文库

› 论坛 › 程序设计 › C/C++ › 马上放假，爽，再发我实现的一个内存池算法

[算法] 马上放假，爽，再发我实现的一个内存池算法 [复制链接]

phoneix

白手起家

论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2007-04-30 14:00 |只看该作者 |倒序浏览

这是我的开源程序库的一部分（http://gforge.osdn.net.cn/frs/?group_id=86），
原实现在 ylib*/young/youngc/yc_memory.c 文件内。
源码如下：

用到的定义：

typedef unsigned char ylib_byte_t;
typedef unsigned int ylib_word_t;
#ifndef YLIB_WORD_MAX
#define YLIB_WORD_MAX UINT_MAX
#endif
enum YOUNG_LIBRARY_COMMON_CONSTANT
{
BYTE_BITS = CHAR_BIT,
YLIB_BYTE_MAX = UCHAR_MAX,
CHARACTER_SIZE_MAX = MB_LEN_MAX
};

复制代码

函数声明：
size_t get_pool_alloc_count( void );
size_t get_pool_dealloc_count( void );
void set_pool_lock( void (*lock)(size_t index) );
void set_pool_unlock( void (*unlock)(size_t index) );
size_t memalign( size_t element_size, bool memory_type );
void pool_print( void );
void* pool_alloc( size_t bytes );
/* 只将内存块回收至内存池 */
void pool_dealloc( void* ptr, size_t bytes );
/* 先将内存块回收至内存池，再将内存池中空闲的内存页释放 */
void pool_free( void* ptr, size_t bytes );

复制代码

内存池实现：
/*
* 内存池由 MEMORY_POOL_LISTS 个链表组成，每个链表分别处理不同大小的内存块，
* 每个链表处理的内存块大小＝ (索引 + 1) * MEMORY_POOL_ALIGN
*
* 内存池实现原理图：
* －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
* | 0 | 1 | 2 | 3 | ...... | MEMORY_POOL_LISTS - 1 |
* －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
* |
* |
* | －－－－
* －＞ | next |－－
* |－－－| |
* | use | |
* |－－－| |
* | 页 | |
* －－－－ |
* |
* －－－－－－－－－－
* |
* | －－－－
* －＞| next |－－＞NULL
* |－－－|
* | use | 注：使用该字的二进制位来记录缓存页中各内存块的使用状态
* |－－－|
* | 页 | 注：内存页大小 = (索引 + 1) * MEMORY_POOL_ALIGN * use的位数
* －－－－
*/
/*****************************************************************************/
/*****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "yc_memory.h"
#ifdef __cplusplus
namespace youngc { extern "C" {
#endif
/*****************************************************************************/
/*****************************************************************************/
enum YOUNG_LIBRARY_MEMORY_CONSTANT
{
MEMORY_ALIGN_SIZE = sizeof(int),
MEMORY_POOL_ALIGN = 8,
MEMORY_POOL_MAX_BYTES = 128,
MEMORY_POOL_BLOCKS = sizeof(ylib_word_t) * BYTE_BITS,
MEMORY_POOL_LISTS = MEMORY_POOL_MAX_BYTES / MEMORY_POOL_ALIGN
};
typedef struct memory_page
{
struct memory_page* next; /* 下一个内存页 */
ylib_word_t use; /* 位为0表示未被分配，位为1表示已被分配 */
} page_t;
#define LIST_INDEX( bytes ) \
( ((bytes) + MEMORY_POOL_ALIGN - 1) / MEMORY_POOL_ALIGN - 1 )
/*****************************************************************************/
/*****************************************************************************/
static void (*pool_lock)( size_t ) = NULL;
static void (*pool_unlock)( size_t ) = NULL;
static size_t pool_alloc_count = 0;
static size_t pool_dealloc_count = 0;
static page_t* pool[MEMORY_POOL_LISTS] = { NULL };
/*****************************************************************************/
/*****************************************************************************/
size_t get_pool_alloc_count( void )
{
return pool_alloc_count;
}
size_t get_pool_dealloc_count( void )
{
return pool_dealloc_count;
}
void set_pool_lock( void (*lock)(size_t) )
{
pool_lock = lock;
}
void set_pool_unlock( void (*unlock)(size_t) )
{
pool_unlock = unlock;
}
/*****************************************************************************/
size_t memalign( size_t element_size, bool memory_type )
{
size_t residue = MEMORY_ALIGN_SIZE - 1;
size_t alignsize = element_size & ~residue;
if( element_size & residue )
alignsize += MEMORY_ALIGN_SIZE;
if( memory_type == true && alignsize < sizeof(ylib_inner_t) )
alignsize = sizeof(ylib_inner_t);
return alignsize;
}
/*****************************************************************************/
static void word_to_bits( ylib_word_t val, char* str_last )
{
int i;
ylib_word_t mask = 1;
for( i = 0; i < MEMORY_POOL_BLOCKS; ++i, mask <<= 1 )
*--str_last = val & mask ? '1' : '0';
}
void pool_print( void )
{
int i;
page_t* curr;
char bits[MEMORY_POOL_BLOCKS + 1] = { '\0' };
for( i = 0; i < MEMORY_POOL_LISTS; ++i )
{
curr = pool[i];
printf( "\npool[%d:%d] = %p: ", i,
(i + 1) * MEMORY_POOL_ALIGN, pool[i] );
while( curr )
{
word_to_bits( curr->use, bits + MEMORY_POOL_BLOCKS );
printf( "\n\t" );
printf( "next = %p | use = %s", curr->next, bits );
curr = curr->next;
}
}
}
/*****************************************************************************/
void* pool_alloc( size_t bytes )
{
void* ptr = NULL;
page_t* pg = NULL;
if( bytes > MEMORY_POOL_MAX_BYTES )
{
ptr = malloc( bytes );
}
else
{
size_t index = LIST_INDEX( bytes );
size_t block_size = (index + 1) * MEMORY_POOL_ALIGN;
if( pool_lock )
pool_lock( index );
if( pool[index] )
{
page_t* curr = pool[index];
while( curr ) /* 遍历链中的所有内存页寻找空闲的内存块 */
{
if( curr->use == YLIB_WORD_MAX ) /* 该页中没有空闲块 */
curr = curr->next; /* 进入下一个内存页 */
else /* 该页中有空闲块 */
{
ylib_word_t i, j, mask = 1;
/* 先找到第一个空闲块所在的字节 */
for( i = 0; i < sizeof(ylib_word_t); ++i )
{
ylib_byte_t val = (ylib_byte_t)(curr->use
>> (BYTE_BITS * i));
if( val != YLIB_BYTE_MAX )
{
/* 再查找空闲块所在的位 */
mask <<= BYTE_BITS * i;
for( j = 0; j < BYTE_BITS; ++j, mask <<= 1 )
{
if( !(curr->use & mask) ) /* 当前块未使用 */
{
curr->use |= mask; /* 设置使用标志 */
ptr = (ylib_byte_t*)curr + sizeof(page_t)
+ (i * BYTE_BITS + j) * block_size;
++pool_alloc_count;
if( pool_unlock )
pool_unlock( index );
return ptr;
}
} /* end for j */
} /* end if nbits */
} /* end for i */
} /* end else */
} /* end while */
} /* end if( pool[index] ) */
/* 该链下未分配内存页或无空闲块，此时需增加新的内存页 */
pg = (page_t*)malloc( sizeof(page_t) + (index + 1)
* MEMORY_POOL_ALIGN * MEMORY_POOL_BLOCKS );
if( pg )
{
pg->next = pool[index];
pool[index] = pg;
pg->use = 1;
ptr = (ylib_byte_t*)pool[index] + sizeof(page_t);
}
if( pool_unlock )
pool_unlock( index );
} /* end else */
if( ptr )
++pool_alloc_count;
return ptr;
}
/*****************************************************************************/
void pool_dealloc( void* ptr, size_t bytes )
{
if( !ptr )
return;
if( bytes <= MEMORY_POOL_MAX_BYTES )
{
size_t index = LIST_INDEX( bytes );
size_t pagesize = (index + 1) * MEMORY_POOL_ALIGN * MEMORY_POOL_BLOCKS;
page_t *prev = NULL, *curr = pool[index];
ylib_byte_t *begin, *end, *blk = (ylib_byte_t*)ptr;
if( pool_lock )
pool_lock( index );
while( curr )
{
begin = (ylib_byte_t*)curr + sizeof(page_t);
end = begin + pagesize;
if( blk < begin || end <= blk ) /* 判断ptr是否在当前内存页内 */
{
prev = curr;
curr = curr->next;
}
else
{
/* 检查ptr是否正确 */
if( (blk - begin) % ((index + 1) * MEMORY_POOL_ALIGN) == 0 )
{
ylib_word_t mask = 1;
size_t blk_index = (blk - begin)
/ ((index + 1) * MEMORY_POOL_ALIGN);
mask <<= blk_index;
curr->use &= (~mask);
/* 如果当前内存页已空闲并且非链首，则将当前内存页移至链首 */
if( curr->use == 0 && prev )
{
prev->next = curr->next;
curr->next = pool[index];
pool[index] = curr;
}
++pool_dealloc_count;
}
if( pool_unlock )
pool_unlock( index );
return;
}
} /* end while */
} /* end if */
/* ptr不是由内存池分配 */
free( ptr );
++pool_dealloc_count;
}
/*****************************************************************************/
void pool_free( void* ptr, size_t bytes )
{
if( bytes > MEMORY_POOL_MAX_BYTES )
{
if( ptr )
{
free( ptr );
++pool_dealloc_count;
}
}
else
{
size_t index = LIST_INDEX( bytes );
page_t *erase = NULL, *prev = NULL, *curr = pool[index];
if( ptr )
pool_dealloc( ptr, bytes );
if( pool_lock )
pool_lock( index );
/* 释放空闲页 */
while( curr )
{
if( curr->use != 0 )
{
prev = curr;
curr = curr->next;
}
else
{
erase = curr;
if( prev )
prev->next = curr->next;
else
pool[index] = curr->next;
curr = curr->next;
free( erase );
}
} /* end while */
if( pool_unlock )
pool_unlock( index );
} /* end else */
}
/*****************************************************************************/
/*****************************************************************************/
#ifdef __cplusplus
} }
#endif
/*****************************************************************************/
/*****************************************************************************/

复制代码

其中的 pool_lock 和 pool_unlock 函数指针是由使用者传递的供并发使用时调用的加锁和解锁函数，
因为内存池的每个链可以使用不同的锁，所以我给这两个函数指针类型指定了一个参数，用一传递当前
链的索引号。

[ 本帖最后由 phoneix 于 2007-4-30 16:45 编辑 ]