#ifndef MEMORY_C
#define MEMORY_C
//#define TEST_MEMORY
#define IOS
#define DEBUG
//#define TEST_LITTLE
/*本系统开了一个特定大小的栈区，在这个区域上模拟堆存储管理
* 提供了两个关键的函数 malloc(int) 和free(void *)
*
* *这个版本的系统，使用了一个256k大小的栈
* 分成256大份，每份1k大小，
* 如果用户申请大于1k大小的空间，
* 则直接用伙伴算法通过大的Buddy_table(大表)找到一块合适大小的空闲块；
*
* 如果用户申请小于1k大小的空间，
* 则在一个1k的空闲块上,建立一个小的Buddy_table(小表)
* 一个小表管理32块，大小是32字节的小块。
* 一个小表分配完之后，建立新的一个小表，直到大表的空间也满为止
*
* 空间分配完的话，再申请空间时候，报memory full错
* */
#define NULL 0
#ifdef IOS
#include<iostream>
using namespace std;
#endif
#define malloc my_malloc
#define free my_free
#define UCHAR unsigned char
#define USHORT unsigned short
void * malloc(int size); //分配一段空间
void free(void *); //释放一个指针#define NULL 0
void free_little(void * addr);
void free_big(void * addr);
#define FALSE 0
#define TRUE 1
#define BIG_BLOCK_SIZE 1024 //大块每个1k
#define BIG_BLOCK_MAX 256//有多少个1k的大块
#define STACK_MAX BIG_BLOCK_SIZE*BIG_BLOCK_MAX //
#define BLOCKID_MAX 2*BIG_BLOCK_MAX //二叉树结点
//第一个结点分割1024*128+1024*128,第2，3个进一步分割
//1+2+4...+2^8=2^^9-1 ,
#define LITTLE_BLOCK_SIZE 32 //32个字节一个小块
#define LITTLE_BLOCK_MAX BIG_BLOCK_SIZE/LITTLE_BLOCK_SIZE //1024/32
#define LITTLE_BLOCKID_MAX 2*LITTLE_BLOCK_MAX
char SYS_STACK[STACK_MAX];//存储池
struct Buddy_address_table{
void * address[BIG_BLOCK_MAX];//起始地址
USHORT occu_id[BIG_BLOCK_MAX];//hash位置是否占用,0表示未占用，非0的话指向占用的id
bool semi[BLOCKID_MAX];//是否被部分占用，用这个数组表示一棵二叉
bool occupied[BLOCKID_MAX];//是否被完全占用，用这个数组表示一棵二叉树
};
Buddy_address_table bd={NULL};
struct Little_Buddy{
void * address[LITTLE_BLOCK_MAX];//起始地址
UCHAR occu_id[LITTLE_BLOCK_MAX];//hash位置是否占用,0表示未占用，非0的话指向占用的id
bool semi[LITTLE_BLOCKID_MAX];//是否被部分占用，用这个数组表示一棵二叉树
bool occupied[LITTLE_BLOCKID_MAX];//是否被完全占用，用这个数组表示一棵二叉树
int idx;//小表本身在大表中的idx(释放小表时要用到)
bool full;
};
void *find_little_space(Little_Buddy * lb,int i,int size,void * addr);
void * find_space(int i, int size,void * addr);
void error(int x){
#ifdef DEBUG
#endif
};
int big_size(int idx){
int s=STACK_MAX;
int i;
while(idx!=1){
s=s/2;
if(idx%2==0){
idx=idx/2;
}
else{
idx=(idx-1)/2;
}
}
return s;
}
int little_size(int idx){
int s=BIG_BLOCK_SIZE;
int i;
while(idx!=1){
s=s/2;
if(idx%2==0){
idx=idx/2;
}
else{
idx=(idx-1)/2;
}
}
return s;
}
//建立一个释放信息栈，每次受到释放信号的时候，不马上释放，而是先进栈
//栈满或者空间已经满时，一起释放，提高效率
//
Little_Buddy * lb_list[BIG_BLOCK_MAX]={NULL};
//最多BIG_BLOCK_MAX个小表--一个大BUDDY块可以是一个小BUDY表
int get_idx_little(Little_Buddy * lb, void *addr){
int i=(int)addr;
int k=i%LITTLE_BLOCK_MAX;
while(lb->occu_id[k]){
k++;
if(k==LITTLE_BLOCK_MAX){
k=0;
}
}
return k;//找到addre的插入位置
}
int get_idx(void *addr){
int i=(int)addr;
int k=i%BIG_BLOCK_MAX;
while(bd.occu_id[k]){
k++;
if(k==BIG_BLOCK_MAX){
k=0;
}
}
return k;//找到addre的插入位置
}
void * malloc(int size){
void * addr;
int idx;//查到的空闲块id
#ifdef DEBUG
cout<<"target space:"<<size<<endl;
#endif
if(size<=BIG_BLOCK_SIZE){//比较小的块，用小表分配
int i=0;
while(lb_list[i]!=NULL && lb_list[i]->full!=1){
#ifdef DEBUG
cout<<"search little"<<endl;
#endif
//已经建立的小表中，未满的表
if(addr=find_little_space(lb_list[i],1,size,lb_list[i])){
return addr;
}
i++;
}
//现有小表中找不到足够空间，建立新的小表
if(addr=find_space(1,BIG_BLOCK_SIZE,SYS_STACK)){//在大表中找到空间
lb_list[i]=(Little_Buddy*)addr;// 小表本身所占的空间
//little table initialize
int j;
for(j=0;j<LITTLE_BLOCKID_MAX;j++){
lb_list[i]->occupied[j]=FALSE;
lb_list[i]->semi[j]=FALSE;
}
for(j=0;j<LITTLE_BLOCK_MAX;j++){
lb_list[i]->occu_id[j]=0;
}
lb_list[i]->idx=idx;
//去掉小表本身的空间
find_little_space(lb_list[i],1,sizeof(Little_Buddy),addr);
//通过小表所描述的空闲块空间查找合适小空闲块
if(addr=find_little_space(lb_list[i],1,size,addr)){
return addr;
}
else{
return NULL;
}
}
}
return find_space(1,size,SYS_STACK);//从根结点开始找可用空间
}
//
//
void *find_little_space(Little_Buddy * lb,int i,int size,void * addr){
if(LITTLE_BLOCK_SIZE>size){size=LITTLE_BLOCK_SIZE;}
int sz=little_size(i);
if(LITTLE_BLOCKID_MAX<i){return NULL;}
if(lb->occupied[i]){return NULL;};
//半可用空间
if(lb->semi[i]){
#ifdef DETAIL
cout<<"semi"<<i<<" "<<sz<<" "<<size<<endl;
#endif
if(sz<=2*size){
return NULL;
}
else{
if(!lb->occupied[2*i]){
void * adr;
if(adr=find_little_space(lb,2*i,size,addr)){
return adr;
}
}
else{
char * ad=(char*)addr;
return find_little_space(lb,2*i+1,size,ad+sz/2);
}
}
}
//是完全可用空间
if(sz>=size){//存在可用空间
#ifdef DETAIL
cout<<"space:"<<i<<" "<<sz<<" "<<size<<endl;
#endif
if(sz>=2*size ){//还太大，继续分小的
lb->semi[i]==1;//本身半占
void * adr;
if (adr= find_little_space(lb,2*i,size,addr)){
return adr;
}
else{
char * ad=(char*)addr;
return find_little_space(lb,2*i+1,size,ad+sz/2);
};
}
//找到合适的可用空间
int k=get_idx_little(lb,addr);
lb->address[k]=addr;
lb->occu_id[k]=i;//记下对应地址的id 小表
lb->occupied[i]=TRUE;
#ifdef DEBUG
cout<<"space:"<<i<<" "<<sz<<" "<<size<<endl;
#endif
return addr;//返回存储空间首地址
}
else{
//所申请的块的大小已经超过这个小表的最大限度
lb->full=1;
return NULL;
}
}
//
//
void * find_space(int i, int size,void * addr){// 从 index开始找大小是size 的块
if(BIG_BLOCK_SIZE>size){size=BIG_BLOCK_SIZE;}
int sz=big_size(i);
#ifdef DETAIL
cout<<i<<" "<<sz<<" "<<size<<endl;
#endif
if(BLOCKID_MAX<i){return NULL;}
if(bd.occupied[i]){
#ifdef DETAIL
cout<<"occupied:"<<i<<endl;
#endif
return NULL;
}
//半可用空间
if(bd.semi[i]){
if(sz<=2*size){
return NULL;
}
else{
if(!bd.occupied[2*i]){
void * adr;
if(adr=find_space(2*i,size,addr)){
return adr;
}
}
else{
char * ad=(char*)addr;
return find_space(2*i+1,size,ad+sz/2);
}
}
}
//是完全可用空间
if(sz>=size){//存在可用空间
if(sz>=2*size ){//还太大，继续分小的
bd.semi[i]==1;//本身半占
void * adr;
if (adr= find_space(2*i,size,addr)){
return adr;
}
else{
char * ad=(char*)addr;
return find_space(2*i+1,size,ad+sz/2);
};
}
//找到合适的可用空间
int k=get_idx(addr);
bd.address[k]=addr;
bd.occu_id[k]=i;//记下对应地址的id 小表
bd.occupied[i]=TRUE;
#ifdef DEBUG
cout<<i<<" "<<sz<<" "<<size<<endl;
#endif
return addr;//返回存储空间首地址
}
else{
//所申请的块的大小已经超过这个表的最大限度
#ifdef DEBUG
cout<<"memory full"<<endl;
#endif
return NULL;
}
#ifdef DETAIL
cout<<"begin to assign "<<i<<endl;
#endif
if(!bd.occupied[i] && sz>size){//存在可用空间
if(sz>2*size){//还太大，继续分小的
bd.occupied[i]==TRUE;//本身不空
#ifdef DETAIL
cout<<"virtual assign"<<i<<" "<<sz<<endl<<endl;
#endif
void * adr;
if (adr= find_space(2*i,size,addr)){
bd.occupied[2*i]=1;//左结点不空
return adr;
}
else{
char * ad=(char *)addr;
bd.occupied[2*i+1]=1;//左结点不空
return find_space(2*i+1,size,ad+sz/2);
};
}
else{ //找到合适的可用空间
int k=get_idx(addr);
bd.address[k]=addr;
bd.occu_id[k]=i;//记下对应地址的id 小表
#ifdef DETAIL
cout<<"occu_id: "<<k<<" "<<(int)addr<<endl;
#endif
#ifdef DEBUG
cout<<"best suit:"<<i<<" "<<sz<<endl;
#endif
return bd.address[k];//返回存储空间首地址和空间大小
}
}
else{
#ifdef DETAIL
cout<<"begin search sub_node"<<endl;
#endif
if(bd.occupied[i]){//本块占用
void * adr;
if(adr=find_space(2*i,size,addr)){//找左结点
return adr;
} else{
char * ad=(char*)addr;
return find_space(2*i+1,size,ad+sz/2);
}
}
else{//所申请的块的大小已经超过最大限度
error(98);
#ifdef DEBUG
if(1==i){
cout<<"memory full"<<endl;
}
#endif
return NULL;
}
}
}
//
//
void free_big_id(int k){//释放上层虚结点
if(0==k){
#ifdef DEBUG1
cout<<"root "<<endl;
#endif
return;
}
if(1==k){
#ifdef DEBUG
cout<<"root freed"<<endl;
#endif
bd.occupied[1]=FALSE;//清空索引所指向的空间
bd.semi[1]=FALSE;//清空索引所指向的空间
return;
}
if(0==k%2){//左结点
#ifdef DETAIL
cout<<k<<" left virutal freed"<<endl;
#endif
if(!bd.occupied[k+1]|| !bd.semi[k+1]){//右边也空
#ifdef DETAIL
cout<<k+1<<" right blank too"<<endl;
#endif
free_big_id(k/2);
bd.occupied[k]=FALSE;//清空索引所指向的空间
bd.semi[k]=FALSE;//清空索引所指向的空间
}
}
else{//是右结点
#ifdef DETAIL
cout<<k<<" right virutal freed"<<endl;
#endif
if(!bd.occupied[k-1] || !bd.semi[k-1]){//左边也空
#ifdef DEBUG
cout<<k-1<<"left blank too"<<endl;
#endif
free_big_id((k-1)/2);
bd.occupied[k]=FALSE;//清空索引所指向的空间
bd.semi[k]=FALSE;//清空索引所指向的空间
}
}
}//end
//
//
int memory_size_little(void * addr){
int target=(int)addr;
int d;
for(int d=0;d<BIG_BLOCK_MAX;d++){
int head=(int)lb_list[d];
int tail=(int)((char*)lb_list[d]+BIG_BLOCK_SIZE);
if(target>=head &&target<tail){
int k=target%LITTLE_BLOCK_MAX;
Little_Buddy * p=lb_list[d];
while(p->address[k]!=addr ||!p->occu_id[k]){
k++;
if(k==BIG_BLOCK_MAX){
k=0;
}
}
return little_size(p->occu_id[k]);
}
}
return -1;
}
int memory_size_big(void * addr){
int target=(int)addr;
int head=target%BIG_BLOCK_MAX;
int tail=head;
#ifdef DETAIL
cout<<head<<" "<<(int)addr<<endl;
#endif
if(bd.address[head]==addr && bd.occu_id[head]!=0 ){
;
}
else{
head++;
while(
tail!=head &&
(bd.occu_id[head]==0 || bd.address[head]!=addr )
){
#ifdef DEBUG
// cout<<(int)bd.address[head]<<" ";
#endif
head++;
if(head==BIG_BLOCK_MAX){
head=0;
}
}
}
int k=head;
if(head==tail){
return memory_size_little(addr);
}
return big_size(bd.occu_id[k]);
}
//
void free_big(void * addr){
int target=(int)addr;
int head=target%BIG_BLOCK_MAX;
int tail=head;
#ifdef DETAIL
cout<<head<<" "<<(int)addr<<endl;
#endif
if(bd.address[head]==addr && bd.occu_id[head]!=0 ){
;
}
else{
head++;
while(
tail!=head &&
(bd.occu_id[head]==0 || bd.address[head]!=addr )
){
#ifdef DEBUG
// cout<<(int)bd.address[head]<<" ";
#endif
head++;
if(head==BIG_BLOCK_MAX){
head=0;
}
}
}
int k=head;
if(head==tail){
free_little(addr);
}
if(1==bd.occu_id[k]){//不是根结点
#ifdef DEBUG
cout<<"big root freed"<<endl;
#endif
bd.occupied[1]=FALSE;//清空索引所指向的空间
bd.semi[1]=FALSE;//清空索引所指向的空间
bd.occu_id[k]=0;//空出一个索引位置
return;
}
if(bd.occu_id[k]%2==0 ){//左结点
#ifdef DEBUG
cout<<bd.occu_id[k]<<"left real freed"<<endl;
#endif
if(!bd.occupied[bd.occu_id[k]+1]){//右边也空
free_big_id(bd.occu_id[k]/2);
}
}
else{//是右结点
#ifdef DEBUG
cout<<bd.occu_id[k]<<"right real freed"<<endl;
#endif
if(!bd.occupied[bd.occu_id[k]-1]){//左边也空
free_big_id((bd.occu_id[k]-1)/2);
}
}
bd.occupied[bd.occu_id[k]]=FALSE;//清空索引所指向的空间
bd.semi[bd.occu_id[k]]=FALSE;//清空索引所指向的空间
bd.occu_id[k]=0;//空出一个索引位置
}
//
void free_little_id(Little_Buddy * p,int k){
if(0==k){
#ifdef DEBUG
cout<<"root "<<endl;
#endif
return;
}
if(1==k){
#ifdef DEBUG
cout<<"little root freed "<<endl;
#endif
p->occupied[1]=FALSE;//清空索引所指向的空间
p->semi[1]=FALSE;//清空索引所指向的空间
return;
}
if(0==k%2){//左结点
#ifdef DEBUG1
cout<<k<<" left virutal freed"<<endl;
#endif
if(!p->occupied[k+1] || !p->semi[k+1]){//右边也空
#ifdef DEBUG1
cout<<k+1<<" right blank too"<<endl;
#endif
free_little_id(p,k/2);
p->occupied[k]=FALSE;//清空索引所指向的空间
p->semi[k]=FALSE;//清空索引所指向的空间
}
}
else{//是右结点
#ifdef DEBUG1
cout<<k<<" right virutal freed"<<endl;
#endif
if(!p->occupied[k-1]||!p->semi[k-1]){//左边也空
#ifdef DEBUG1
cout<<k-1<<"left blank too"<<endl;
#endif
free_little_id(p,(k-1)/2);
p->occupied[k]=FALSE;//清空索引所指向的空间
}
}
}//end free_little_id
//
//
void free_little(void * addr){
int target=(int)addr;
int d;
for(int d=0;d<BIG_BLOCK_MAX;d++){
int head=(int)lb_list[d];
int tail=(int)((char*)lb_list[d]+BIG_BLOCK_SIZE);
if(target>=head &&target<tail){
int k=target%LITTLE_BLOCK_MAX;
Little_Buddy * p=lb_list[d];
while(p->address[k]!=addr ||!p->occu_id[k]){
k++;
if(k==BIG_BLOCK_MAX){
k=0;
}
}
int id=p->occu_id[k];
p->occupied[id]=FALSE;
p->semi[id]=FALSE;
#ifdef DEBUG1
cout<<"idx"<<k<<endl<<endl;
#endif
if(id==1){//是小表根结点
free(p);//释放掉小表根
#ifdef DEBUG
cout<<"free little table"<<endl<<endl;
#endif
}
if(id%2==0){//左结点
if(!p->occupied[id+1] &&!p->semi[id+1]){//右边也空
#ifdef DEBUG
cout<<" right also blank:"<<id<<endl<<endl;
#endif
free_little_id(p,id/2);//释放上层结点
return;
}
}
else{//右结点
if(!p->occupied[p->occu_id[k]-1]){//左边也空
#ifdef DEBUG
cout<<"left also blank:"<<p->occu_id[k]<<endl<<endl;
#endif
free_little_id(p,(id-1)/2);//释放上层结点
return;
}
}
}
}
}
//
//
void free(void * addr){
int target=(int)addr;
int base=(int)SYS_STACK;
if(target<base ||target>base+STACK_MAX){return;}
if((target-base)% BIG_BLOCK_SIZE==0){//是大表上的结点，BIG_BLOCK_SIZE为单位分配
#ifdef DEBUG
cout<<"free_big"<<endl;
#endif
free_big(addr);
}
else{//小表
#ifdef DEBUG
cout<<"free_little"<<endl;
#endif
free_little(addr);
}
}
int memory_size(void * addr){ // chech that how many space has assign to it
int target=(int)addr;
int base=(int)SYS_STACK;
if(target<base ||target>base+STACK_MAX){return -1;}
if((target-base)% BIG_BLOCK_SIZE==0){//是大表上的结点，BIG_BLOCK_SIZE为单位分配
#ifdef DEBUG
cout<<"free_big"<<endl;
#endif
return memory_size_big(addr);
}
else{//小表
#ifdef DEBUG
cout<<"size_little"<<endl;
#endif
return memory_size_little(addr);
}
}
/*
*99 未知错误
98 空间不足
96 释放一个buddy系统中没有的地址（指针）
*
* */
#ifdef TEST_MEMORY
int main(){
double * d[10];
#ifdef TEST_BIG
int * a=(int*)malloc(1000*sizeof(int));
a[999]=1;
free(a);
double * d[10];
d[0]=(double *)malloc(2000*sizeof(double));
d[1]=(double *)malloc(2000*sizeof(double));
d[2]=(double *)malloc(4000*sizeof(double));
d[3]=(double *)malloc(8000*sizeof(double));
int i;
for(i=0;i<4;i++){
free(d[i]);
}
//d[0]=(double *)malloc(8000*sizeof(double));
d[1]=(double *)malloc(16000*sizeof(double));
//d[2]=(double *)malloc(4000*sizeof(double));
//d[3]=(double *)malloc(8000*sizeof(double));
d[1][15999]=1;
free(d[1]);
d[1]=(double *)malloc(32000*sizeof(double));
free(d[1]);
d[1]=(double *)malloc(42000*sizeof(double));
#endif
#ifdef TEST_LITTLE
d[0]=(double *)malloc(2);
d[1]=(double *)malloc(4);
d[2]=(double *)malloc(8);
d[3]=(double *)malloc(16);
d[4]=(double *)malloc(32);
d[5]=(double *)malloc(64);
int i;
for(i=0;i<6;i++){
free(d[i]);
}
#endif
}
#endif //endif TEST_MEMORY
#endif//endif MEMORY_C
