//内存空闲分区的描述
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

//常量定义
#define PROCESS_NAME_LEN 32  
#define MIN_SLICE    10            
#define DEFAULT_MEM_SIZE 1024    
#define DEFAULT_MEM_START 0      

#define MA_FF 1
#define MA_BF 2
#define MA_WF 3
int mem_size=DEFAULT_MEM_SIZE;
int ma_algorithm = MA_FF;          
static int pid = 0;                                     
int flag = 0;                         

struct free_block_type{
    int size;
    int start_addr;
    struct free_block_type *next;
}; 


struct free_block_type *free_block;

//描述已分配的内存块

struct allocated_block{
    int pid;    int size;
    int start_addr;
    char process_name[PROCESS_NAME_LEN];
    struct allocated_block *next;
};

struct allocated_block *allocated_block_head = NULL;

//函数声明
struct free_block_type* init_free_block(int mem_size);
void display_menu();
int set_mem_size();
void set_algorithm();
void rearrange(int algorithm);
int rearrange_FF();
int rearrange_BF();
int rearrange_WF();
int new_process();
int allocate_mem(struct allocated_block *ab);
void kill_process();
int free_mem(struct allocated_block *ab);
int dispose(struct allocated_block *free_ab);
int display_mem_usage();
void do_exit();
struct allocated_block *find_process(int pid);


int main(){
    char choice;      pid=0;
    free_block = init_free_block(mem_size); //初始化空闲区
    while(1) {
    display_menu(); //显示菜单
    fflush(stdin);
    choice=getchar();   //获取用户输入
    switch(choice){
        case '1': set_mem_size(); break;    //设置内存大小
        case '2': set_algorithm();flag=1; break;//设置算法
        case '3': new_process(); flag=1; break;//创建新进程
        case '4': kill_process(); flag=1; break;//删除进程
        case '5': display_mem_usage();   flag=1; break; //显示内存使用
        case '0': do_exit(); exit(0);   //释放链表并退出
        default: break;   
        }   
    }
    return 1;
}


struct free_block_type* init_free_block(int mem_size){
    struct free_block_type *fb;

    fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
    if(fb==NULL){
        printf("No mem\n");
        return NULL;
        }
    fb->size = mem_size;
    fb->start_addr = DEFAULT_MEM_START;
    fb->next = NULL;
    return fb;
}


void display_menu(){
    printf("\n");
    printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
    printf("2 - Select memory allocation algorithm\n");
    printf("3 - New process \n");
    printf("4 - Terminate a process \n");
    printf("5 - Display memory usage \n");
    printf("0 - Exit\n");
}


int set_mem_size(){
    int size;
    if(flag!=0){  //防止重复设置
        printf("Cannot set memory size again\n");
        return 0;
        }
    printf("Total memory size =");
    scanf("%d", &size);
    if(size>0) {
        mem_size = size;
        free_block->size = mem_size;
        }
    flag=1; 
    return 1;
 }
   
 
void set_algorithm(){
    int algorithm;
    while(1) {
        printf("\t1 - First Fit\n");
        printf("\t2 - Best Fit \n");
        printf("\t3 - Worst Fit \n");
        scanf("%d", &algorithm);
        if(algorithm>=1 && algorithm <=3)  {
                ma_algorithm = algorithm;
                break;
            }
        else
                printf("输入有误，请重新输入！\n");
    }
    //按指定算法重新排列空闲区链表
    rearrange(ma_algorithm);
} 


void rearrange(int algorithm){
    switch(algorithm){
        case MA_FF:  rearrange_FF(); break;
        case MA_BF:  rearrange_BF(); break;
        case MA_WF: rearrange_WF(); break;
        }
}
   

int rearrange_FF(){  
    struct free_block_type *temp;
    //使用头插法，thead为临时头,p为最小地址的数据块的前一个结点
    struct free_block_type *thead=NULL,*p=NULL;
    //当前的最小地址
    int min_addr = free_block->start_addr;
    temp = free_block;
   
    while(temp->next!=NULL) {
            if(temp->next->start_addr<min_addr) {
                min_addr = temp->next->start_addr;
                p = temp;
            }
            temp = temp->next; 
        }
        if(NULL!=p) {
            temp = p->next;
            p->next = p->next->next;
            temp->next = free_block;
            free_block = temp;
    }
//printf("2222222222\n");  
//printf("%d\n",free_block->start_addr);
   
    thead = free_block;
    p = free_block;
    temp = free_block->next;
    while(thead->next!=NULL) {
        min_addr = thead->next->start_addr;
        while(temp->next!=NULL) {
            if(temp->next->start_addr<min_addr) {
                min_addr = temp->next->start_addr;
                p = temp;
            }
            temp = temp->next; 
        }
        if(p->next!=thead->next) {
            temp = p->next;
            p->next = p->next->next;
            temp->next = thead->next;
            thead->next = temp;
        }
        thead = thead->next;
        p = thead;
        temp = thead->next;
    }
    //请自行补充
    return 1;
}

int rearrange_BF(){
    struct free_block_type *temp;
    //使用头插法，thead为临时头,p为最小内存的数据块的前一个结点
    struct free_block_type *thead=NULL,*p=NULL;
    //当前的最小内存
    int min_size = free_block->size;
    temp = free_block;
   
    while(temp->next!=NULL) {
            if(temp->next->size<min_size) {
                min_size = temp->next->size;
                p = temp;
            }
            temp = temp->next; 
        }
        if(NULL!=p) {
            temp = p->next;
            p->next = p->next->next;
            temp->next = free_block;
            free_block = temp;
    }
   
    thead = free_block;
    p = free_block;
    temp = free_block->next;
    while(thead->next!=NULL) {
        min_size = thead->next->size;
        while(temp->next!=NULL) {
            if(temp->next->size<min_size) {
                min_size = temp->next->size;
                p = temp;
            }
            temp = temp->next; 
        }
        if(p->next!=thead->next) {
            temp = p->next;
            p->next = p->next->next;
            temp->next = thead->next;
            thead->next = temp;
        }
        thead = thead->next;
        p = thead;
        temp = thead->next;
    }
    //请自行补充
    return 1;
}

int rearrange_WF(){
    struct free_block_type *temp;
    //使用头插法，thead为临时头,p为最大内存的数据块的前一个结点
    struct free_block_type *thead=NULL,*p=NULL;
    //当前的最大内存
    int max_size = free_block->size;
    temp = free_block;
   
    while(temp->next!=NULL) {
            if(temp->next->size>max_size) {
                max_size = temp->next->size;
                p = temp;
            }
            temp = temp->next; 
        }
        if(NULL!=p) {
            temp = p->next;
            p->next = p->next->next;
            temp->next = free_block;
            free_block = temp;
    }
   
    thead = free_block;
    p = free_block;
    temp = free_block->next;
   
    while(thead->next!=NULL) {
        max_size = thead->next->size;
        while(temp->next!=NULL) {
            if(temp->next->size>max_size) {
                max_size = temp->next->size;
                p = temp;
            }
            temp = temp->next; 
        }
        if(p->next!=thead->next) {
            temp = p->next;
            p->next = p->next->next;
            temp->next = thead->next;
            thead->next = temp;
        }
        thead = thead->next;
        p = thead;
        temp = thead->next;
    }
    //请自行补充
    return 1;
}


int new_process(){
    struct allocated_block *ab;
    int size;   
    int ret;
    ab = (struct allocated_block *)malloc(sizeof(struct allocated_block));
    if(!ab) exit(-5);
    ab->next = NULL;
    pid++;
    sprintf(ab->process_name, "PROCESS-d", pid);
    ab->pid = pid;   
    while(1) {
        printf("Memory for %s:", ab->process_name);
        scanf("%d", &size);
        if(size>0) {
            ab->size=size;
            break;
        }
        else printf("输入大小有误，请重新输入\n");
    }
//printf("11111111111111\n");  
    ret = allocate_mem(ab); 
      
//printf("11111111111111\n");         
    if((ret==1) &&(allocated_block_head == NULL)){
        allocated_block_head=ab;
        return 1;      
    }
   
    else if (ret==1) {
        ab->next = allocated_block_head;
        allocated_block_head = ab;
        return 2;        }
    else if(ret==-1){
        printf("Allocation fail\n");
        pid--;
        free(ab);
        return -1;      
     }
    return 3;
}


int allocate_mem(struct allocated_block *ab){
    struct free_block_type *fbt, *pre,*head,*temp,*tt;
    struct allocated_block *tp;
    int request_size=ab->size;
    int sum=0;
    int max;
    head = (struct free_block_type *)malloc(sizeof(struct free_block_type));
    pre = head;
    fbt = free_block;
    pre->next = fbt;
//printf("11111111111111\n");      
    //根据当前算法在空闲分区链表中搜索合适空闲分区进行分配，分配时注意以下情况：
    // 1. 找到可满足空闲分区且分配后剩余空间足够大，则分割
    // 2. 找到可满足空闲分区且但分配后剩余空间比较小，则一起分配
    // 3. 找不可满足需要的空闲分区但空闲分区之和能满足需要，则采用内存紧缩技术，进行空闲分区的合并，然后再分配
    // 4. 在成功分配内存后，应保持空闲分区按照相应算法有序
    // 5. 分配成功则返回1，否则返回-1
    if(ma_algorithm==MA_WF) {
        if(NULL==fbt||fbt->size<request_size)
            return -1;
    }
    else {
        while(NULL!=fbt&&fbt->size<request_size) {
            pre = fbt;
            fbt = fbt->next;
        }
    }
   
    if(NULL==fbt||fbt->size<request_size) {
       
        if(NULL!=free_block->next) {
            sum = free_block->size;
            temp = free_block->next;
            while(NULL!=temp) {
                sum += temp->size;
                if(sum>=request_size)
                    break;
                temp = temp->next;
            }
            if(NULL==temp)
                return -1;
            else {
                pre = free_block;
                max = free_block->start_addr;
                fbt = free_block;
                while(temp->next!=pre) {
                    if(max<pre->start_addr) {
                        max = pre->start_addr;
                        fbt = pre; 
                    }
                    pre = pre->next;
                }
                pre = free_block;  
                while(temp->next!=pre) {   
                    tp = allocated_block_head;
                    tt = free_block;
                    if(pre!=fbt) {
                        while(NULL!=tp) {
                            if(tp->start_addr>pre->start_addr)
                                tp->start_addr = tp->start_addr - pre->size;
                            tp = tp->next;     
                        }
                        while(NULL!=tt) {
                            if(tt->start_addr>pre->start_addr)
                                tt->start_addr = tt->start_addr - pre->size;
                            tt = tt->next; 
                        }
                    }
                    pre = pre->next;
                }
                pre = free_block;
                while(pre!=temp->next) {
                    if(pre!=fbt)
                        free(pre);
                    pre = pre->next;
                }
                free_block = fbt;
                free_block->size = sum;
                free_block->next = temp->next;
                if(free_block->size - request_size < MIN_SLICE) {
                    ab->size = free_block->size;
                    ab->start_addr = free_block->start_addr;
                    pre = free_block;
                    free_block = free_block->next;
                    free(pre);
                }
                else {
                    ab->start_addr = fbt->start_addr;
                    free_block->start_addr = free_block->start_addr + request_size;
                    free_block->size = free_block->size - request_size;
                }
            }  
        }
        else
            return -1; 
           
    }      
    else {
        //将内存块全部分配
        if(fbt->size - request_size < MIN_SLICE) {
            ab->size = fbt->size;
            ab->start_addr = fbt->start_addr;
            if(pre->next==free_block) {
                free_block = fbt->next;
            }
            else   
                pre->next = fbt->next;
            free(fbt);
        }
        else {
            ab->start_addr = fbt->start_addr;
            fbt->start_addr = fbt->start_addr + request_size;
            fbt->size = fbt->size - request_size;
        }
    }
    free(head);
//printf("11111111111111\n");  
    rearrange(ma_algorithm);
    //请自行补充。。。。。
    return 1;
}


void kill_process(){
    struct allocated_block *ab;
    int pid;
    printf("Kill Process, pid=");
    scanf("%d", &pid);
    ab = find_process(pid);
    if(ab!=NULL){
//printf("11111111111111\n");          
        free_mem(ab);
//printf("11111111111111\n");         
        dispose(ab); 
    }
    else {
        printf("没有pid为%d的进程！\n",pid);
    }
}

struct allocated_block *find_process(int pid) {
    struct allocated_block *ab=NULL;
    ab = allocated_block_head;
    while(NULL!=ab&&ab->pid!=pid)
        ab = ab->next;
    return ab;
}


int free_mem(struct allocated_block *ab){
    int algorithm = ma_algorithm;
    struct free_block_type *fbt, *pre=NULL,*head;
    fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
    pre=(struct free_block_type*) malloc(sizeof(struct free_block_type));
    if(!fbt) return -1;
    // 进行可能的合并，基本策略如下
    // 1. 将新释放的结点插入到空闲分区队列末尾
    // 2. 对空闲链表按照地址有序排列
    // 3. 检查并合并相邻的空闲分区
    // 4. 将空闲链表重新按照当前算法排序
    head = pre;
    fbt->start_addr = ab->start_addr;
    fbt->size = ab->size;
    fbt->next = free_block;  //新释放的结点插入到空闲分区链表的表头
    free_block = fbt;    
    rearrange_FF();          //对空闲链表按照地址有序排列
//printf("11111111111111\n");      
    pre->next = free_block;  //求的pre为fbt的前一个结点
    pre->size = 0;
    while(pre->next->start_addr!=fbt->start_addr)
        pre = pre->next;
        //左右分区都存在
    if(0!=pre->size&&NULL!=fbt->next) {
        //左右分区都可合并
        if((pre->start_addr+pre->size)==fbt->start_addr && (fbt->start_addr+fbt->size)==fbt->next->start_addr) {
                pre->size = pre->size + fbt->size + fbt->next->size;
                pre->next = fbt->next->next;
                free(fbt->next);
                free(fbt);
        }
        //左分区可合并
        else if((pre->start_addr+pre->size)==fbt->start_addr) {
                    pre->size = pre->size + fbt->size;
                    pre->next = fbt->next; 
                    free(fbt);
        }
        //右分区可合并
        else if((fbt->start_addr+fbt->size)==fbt->next->start_addr) {
                    fbt->size = fbt->size + fbt->next->size;
                    fbt->next = fbt->next->next;
                    free(fbt->next);
        }
    }
      //左分区不存在
    else if(0==pre->size) {
            if((fbt->start_addr+fbt->size)==fbt->next->start_addr) {
                fbt->size = fbt->size + fbt->next->size;
                fbt->next = fbt->next->next;
                free(fbt->next);
            }  
    }
    //右分区不存在
    else if(NULL==fbt->next) {
            if((pre->start_addr+pre->size)==fbt->start_addr) {
                pre->size = pre->size + fbt->size;
                pre->next = fbt->next; 
                free(fbt);
            }
    }
//printf("33333333333\n"); 
    rearrange(algorithm);
    free(head);
    //请自行补充……
    return 1;
}


int dispose(struct allocated_block *free_ab){
    struct allocated_block *pre, *ab;
   if(free_ab == allocated_block_head) {
     allocated_block_head = allocated_block_head->next;
        free(free_ab);
        return 1;
        }
    pre = allocated_block_head; 
    ab = allocated_block_head->next;
    while(ab!=free_ab){ pre = ab;  ab = ab->next; }
    pre->next = ab->next;
    free(ab);
    return 2;
}
  

int display_mem_usage(){
    struct free_block_type *fbt=free_block;
    struct allocated_block *ab=allocated_block_head;
    if(fbt==NULL) return(-1);
    printf("----------------------------------------------------------\n");

   
    printf("Free Memory:\n");
    printf(" s s\n", "      start_addr", "       size");
    while(fbt!=NULL){
        printf(" d d\n", fbt->start_addr, fbt->size);
        fbt=fbt->next;
        }   
       
    printf("\nUsed Memory:\n");
    printf("s s s s\n", "PID", "ProcessName", "start_addr", " size");
    while(ab!=NULL){
        printf("d s d d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
        ab=ab->next;
        }
    printf("----------------------------------------------------------\n");
    return 0;
}
   
void do_exit() {
}