动态内存分配算法
/* 工程名称： W32_Alloc */
/* Alloc.h */
#ifndef __ALLOC_H
#define __ALLOC_H
#include "Alloc.cpp"
#endif
/* Alloc.cpp */
typedef unsigned int WORD;
typedef enum { sUsed = 1, sFree = 0 } blk_state;
typedef struct mcb {
blk_state s; /* block state */
WORD *pBegin; /* begining of allocated address */
WORD *pEnd; /* ending of allocated address */
size_t size; /* allocated size */
struct mcb *next;
struct mcb *prev;
} mcb_t; /* memory control block */
typedef struct {
mcb_t *blk_head; /* mcb linked-list head and tail */
mcb_t *blk_tail;
WORD *blk_free; /* free block ptr */
WORD *ptos; /* pointer of stack top */
size_t stack_size; /* stack size */
size_t used_size; /* used size */
} mcbc_t; /* memory control block container */
mcbc_t *c; /* global container */
inline mcbc_t *
init_container( WORD *ptos, int stack_size ) {
mcbc_t *ret = (mcbc_t *)malloc(sizeof(mcbc_t));
assert(ret);
ret->ptos = ptos;
ret->blk_head = (mcb_t *)0;
ret->blk_tail = (mcb_t *)0;
ret->blk_free = ptos;
ret->stack_size = stack_size;
ret->used_size = (int)0;
return ret;
}
inline void
bind_container( mcbc_t *con ) {
c = con;
}
inline void
throw_container( void ) {
mcb_t *p, *bak;
if(c) {
/* free linked-list */
p = c->blk_head;
while(p) {
bak = p->next;
free(p);
p = bak;
}
/* free container */
free(c);
c = (mcbc_t *)0;
}
}
inline void *
allocate( size_t size ) {
assert(c); /* ensure container has been binded */
size_t reminder = c->stack_size - c->used_size; /* calc reminder */
size_t split_size;
size_t ss;
mcb_t *p, *bak;
void *ret;
if(!size)
return (void *)0;
/* general size convert to stack offset */
if(!(size % sizeof(WORD)))
ss = size / sizeof(WORD);
else
ss = size / sizeof(WORD) + 1;
if( reminder < ss )
return (void *)0; /* not enough space for allocating */
if(!c->blk_head) {
/* no mcb in linked-list, create one */
p = (mcb_t *)malloc(sizeof(mcb_t));
assert(p);
ret = (void *)c->ptos;
c->blk_free += ss;
c->used_size += ss;
p->pBegin = c->ptos;
p->pEnd = c->blk_free;
p->s = sUsed;
p->size = size;
p->next = (mcb_t *)0;
p->prev = (mcb_t *)0;
c->blk_head = c->blk_tail = p;
return ret;
}
else {
/* find free block */
p = c->blk_head;
while(p) {
if(p->size >= ss && p->s == sFree) {
ret = (void *)p->pBegin;
/* p->size > ss, split it! */
if(p->size > ss) {
split_size = p->size - ss;
/* recalc end boundary */
p->pEnd = (WORD *)(p->pBegin + ss);
p->size = ss;
p->s = sUsed;
bak = (mcb_t *)malloc(sizeof(mcb_t));
assert(bak);
/* insert mcb */
bak->prev = p;
if(p->next) {
p->next->prev = bak;
bak->next = p->next;
}
else {
bak->next = (mcb_t *)0;
c->blk_tail = bak;
}
p->next = bak;
/* constructing a splited control block */
bak->pBegin = p->pEnd;
bak->pEnd = (WORD *)(bak->pBegin + split_size);
bak->size = split_size;
bak->s = sFree;
}
else
p->s = sUsed;
c->used_size += ss;
return ret;
}
p = p->next;
}
/* no matched block, create one at tail */
ret = (void *)c->blk_free;
c->blk_free += ss;
c->used_size += ss;
p = (mcb_t *)malloc(sizeof(mcb_t));
assert(p);
p->pBegin = (WORD *)ret;
p->pEnd = c->blk_free;
p->prev = c->blk_tail;
p->next = (mcb_t *)0;
p->size = ss;
p->s = sUsed;
c->blk_tail->next = p;
c->blk_tail = p;
return ret;
}
}
inline int
release( void *ptr ) {
assert(c);
mcb_t *p = (mcb_t *)0;
mcb_t *pLeft = (mcb_t *)0;
mcb_t *pRight = (mcb_t *)0;
p = c->blk_head;
while(p) {
/* free matched block */
if(p->pBegin == (WORD *)ptr) {
p->s = sFree;
c->used_size -= p->size;
/* merge free neighbours */
pLeft = p->prev;
pRight = p->next;
while( (pLeft && pLeft->s == sFree) || (pRight && pRight->s == sFree) ) {
/* merge left neighbour */
if(pLeft && pLeft->s == sFree) {
p->pBegin = pLeft->pBegin;
p->size += pLeft->size;
/* destory left neighbour */
p->prev = pLeft->prev;
if(pLeft->prev)
pLeft->prev->next = p;
else
c->blk_head = p;
free(pLeft);
}
/* merge right neighbour */
if(pRight && pRight->s == sFree) {
p->pEnd = pRight->pEnd;
p->size += pRight->size;
/* destory right neighbour */
p->next = pRight->next;
if(pRight->next)
pRight->next->prev = p;
else
c->blk_tail = p;
free(pRight);
}
/* reload neighbours */
pLeft = p->prev;
pRight = p->next;
}
/* on success */
return 0;
}
p = p->next;
}
/* no block matched */
return 1;
}
/* main.cpp */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <assert.h>
#include "Alloc.h"
WORD stk[8 * 1024]; /* 16Kbytes */
int main() {
char *s1,*s2,*s3;
mcbc_t *con = init_container(stk, 8*1024);
bind_container(con);
s1 = (char *)allocate(12);
s2 = (char *)allocate(4);
s3 = (char *)allocate(5);
strcpy(s1,"Hello,world");
strcpy(s2,"ABC");
strcpy(s3,"1234");
printf("%s,%s,%s\n",s1,s2,s3);
getch();
release((void *)s1);
release((void *)s2);
s1 = (char *)allocate(16);
strcpy(s1,"Hello,world,ABC");
printf("%s %s %s\n",s1,s2,s3);
getch();
release((void *)s1);
release((void *)s3);
throw_container();
return 0;
}
