Based on a simple fixed length memory pool implementation method
- 2020-04-01 23:29:28
- OfStack
It is mainly divided into three parts. MemoryPool is the management memoryPool class. The block represents the memory block, and the chunk represents each storage small block. The relationship between them is that there is a pointer to a certain starting block in the memoryPool, and the connection of the linked list structure is formed by the next pointer before the block, and each block contains the specified number of chunks. Each time memory is allocated, the data address in the chunk is allocated.
< img style = "border = 0 BACKGROUND - IMAGE: none; BORDER - BOTTOM: 0 px; BORDER - LEFT: 0 px; PADDING - LEFT: 0 px; PADDING - RIGHT: 0 px; DISPLAY: inline. BORDER - TOP: 0 px; BORDER - RIGHT: 0 px; PADDING - TOP: 0 px "title = memory pool design document border = 0 SRC =" Alt = memory pool design document / / files.jb51.net/file_images/article/201305/2013050710241119.jpg "width = 888 height = 461 >
Main data structure design:
Block:
struct block {
block * next;//Pointer to the next block
unsigned int numofChunks;
unsigned int numofFreeChunks;//The number of free chunks left
unsigned int blockNum;//The number of the block
char * data;
queue<int> freepos; //The chunk serial number is available for recording
};
MemoryPool:
class memoryPool {
unsigned int initNumofChunks; //The number of chunks per block
unsigned int chunkSize;//The data size of each chunk
unsigned int steps;//Number of chunks per extension
unsigned int numofBlocks;//How many blocks are currently managed
block * blocksPtr;//Point to the start block
block * blocksPtrTail;//Point to the end block
block * firstHasFreeChunksBlock;//Points to the first block that is not empty
};
The Chunk:
ChunkNum: the number in the block where the chunk is located
Block address: block corresponding to this chunk can be quickly found and updated when it is mainly used for free chunk
Data: the starting position of the actual data to be used
Key operating instructions:
Memory allocation:
From firstHasFreeChunksBlock began to locate the first free block, if found, the first element is to get the block freepos team, return the element number corresponding address the chunk of data, and will pop-up freepos team first element, other related attribute update. If not, add a new step chunk and repeat the process.
Memory release:
Pass in the address pointer p to be released. By moving the address of p, the ChunkNum in the chunk and the blockAddress can be found. The block belonging to the chunk can be found through the blockAddress.
Usage:
memoryPool * mp = new memoryPool (256);
char * s = (char *)mp->allocate();
//Some operations
mp->freeMemory(s);
delete mp;
Inadequate:
Without considering the thread safety problem, the implementation scheme can run normally under single thread.
Program source code:
#include <iostream>
#include <queue>
#include <string.h>
#include <ctime>
using namespace std;
struct block {
block * next;
unsigned int numofChunks;//Pointer to the next block
unsigned int numofFreeChunks;//The number of free chunks left
unsigned int blockNum;//The number of the block
char * data;
//The chunk serial number is available for recording
queue<int> freepos;
block(unsigned int _numofChunks ,unsigned int _chunkSize, unsigned int _blockNum){
numofChunks = _numofChunks;
numofFreeChunks = _numofChunks;
blockNum = _blockNum;
next = NULL;
data = new char [numofChunks * (sizeof(unsigned int) + sizeof(void *) + _chunkSize)];
char * p = data;
//Structure of each chunk: the chunk serial number of 4byte + the address of the block to which 4byte belongs + the real data
for(int i=0;i<numofChunks;i++){
char * ptr = p + i * (_chunkSize + sizeof(unsigned int) + sizeof(void *));
unsigned int * num = (unsigned int *)(ptr);
*num = i;
ptr += sizeof(void *);
int * blockpos = (int *) ptr;
*blockpos = (int)this;
freepos.push(i);
}
}
~block(){
delete [] data;
}
};
class memoryPool {
public :
memoryPool(unsigned int _chunkSize = 256, unsigned int _initNumofChunks = 4096, unsigned int _steps = 64){
initNumofChunks = _initNumofChunks;
chunkSize = _chunkSize;
steps = _steps;
numofBlocks = steps;
//When you create a memory pool, you initialize a certain amount of memory space
block * p = new block(initNumofChunks, chunkSize, 0);
blocksPtr = p;
for(int i=1;i<steps;i++){
p->next = new block(initNumofChunks, chunkSize, i);
p = p->next;
blocksPtrTail = p;
}
firstHasFreeChunksBlock = blocksPtr;
}
~memoryPool(){
block * p = blocksPtr;
while(blocksPtr!=NULL){
p = blocksPtr->next;
delete blocksPtr;
blocksPtr = p;
}
}
void * allocate(){
block * p = firstHasFreeChunksBlock;
while(p != NULL && p->numofFreeChunks <= 0) p = p->next;
if(p == NULL){
p = blocksPtrTail;
increaseBlocks();
p = p->next;
firstHasFreeChunksBlock = p;
}
unsigned int pos = p->freepos.front();
void * chunkStart = (void *)(p->data + pos * (chunkSize + sizeof(unsigned int) + sizeof(void *)));
void * res = chunkStart + sizeof(unsigned int) + sizeof(void *);
p->freepos.pop();
p->numofFreeChunks --;
return res;
}
void increaseBlocks(){
block * p = blocksPtrTail;
for(int i=0; i<steps; i++){
p->next = new block(initNumofChunks, chunkSize, numofBlocks);
numofBlocks++;
p = p->next;
blocksPtrTail = p;
}
}
void freeMemory(void * _data){
void * p = _data;
p -= sizeof(void *);
int * blockpos = (int *) p;
block * b = (block *) (*blockpos);
p -= sizeof(unsigned int);
int * num = (int *) p;
b->freepos.push(*num);
b->numofFreeChunks ++;
if (b->numofFreeChunks > 0 && b->blockNum < firstHasFreeChunksBlock->blockNum)
firstHasFreeChunksBlock = b;
}
private :
unsigned int initNumofChunks; //The number of chunks per block
unsigned int chunkSize;//The data size of each chunk
unsigned int steps;//Number of chunks per extension
unsigned int numofBlocks;//How many blocks are currently managed
block * blocksPtr;//Point to the start block
block * blocksPtrTail;//Point to the end block
block * firstHasFreeChunksBlock;//Points to the first block that is not empty
};
//test
void echoPositionNum(char * p){
p -= (sizeof(void *) + sizeof(unsigned int));
int * num = (int *) p;
cout<<*num<<endl;
}
//test
void test0(){
memoryPool mp;
char * s1 = (char *)mp.allocate();
char * s2 = (char *)mp.allocate();
char str [256];
char str2 [256];
char str3 [256];
for(int i=0; i<255; i++) {
str[i] = 'a';str2[i] = 'b';str3[i] = 'c';
}
str[255] = '0';
str2[255] = '0';
strcpy(s1,str);
strcpy(s2,str2);
str3[255] = '0';
echoPositionNum(s1);
cout<<s1<<endl;
mp.freeMemory(s1);
echoPositionNum(s2);
cout<<s2<<endl;
char * s3 = (char *)mp.allocate();
strcpy(s3,str3);
echoPositionNum(s3);
cout<<s3<<endl;
}
void test1(){
clock_t clock_begin = clock();
const int N = 50000;
char * s[N];
int round = 100;
while(round>=0){
round --;
for(int i=0;i<N;i++){
s[i] = new char[256];
}
for(int i=0;i<N;i++){
delete [] s[i];
}
}
clock_t clock_end = clock();
cout<<"Time costt"<<clock_end - clock_begin<<endl;
}
void test2(){
memoryPool mp(256);
clock_t clock_begin = clock();
const int N = 50000;
char * s[N];
int round = 100;
while(round>=0){
round --;
for(int i=0;i<N;i++){
s[i] = (char *)mp.allocate();
}
for(int i=0;i<N;i++){
mp.freeMemory(s[i]);
}
}
clock_t clock_end = clock();
cout<<"Time costt"<<clock_end - clock_begin<<endl;
}
int main()
{
test0();
test1();
test2();
return 0;
}
Operation results:
< img style = "border = 0 BACKGROUND - IMAGE: none; BORDER - BOTTOM: 0 px; BORDER - LEFT: 0 px; PADDING - LEFT: 0 px; PADDING - RIGHT: 0 px; DISPLAY: inline. BORDER - TOP: 0 px; BORDER - RIGHT: 0 px; PADDING - TOP: 0 px "title = image border = 0 Alt = image SRC =" / / files.jb51.net/file_images/article/201305/2013050710241121.png ">