【ICS】 PKU malloclab mark.

这是一份不确定能否通过编译的代码（因为又改了一些奇奇怪怪的地方），但效果还不错（）

虽然（一遍一遍告诉自己别做这种边际收益极低的事情）

74是实现了朴素的链表

92是搞了个朴素的二叉树

/*
 * mm.c
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */


 /*

 2100012959 
 Chen Qizhi
 add a 4 bytes head(32 bits)


对于正常分配的块，我用额外4字节存大小。
                                            pointer
                                                |
  --------------------------------------------- v --------------------------
 | 29 bits for size, [empty] [prev] [cur=1] | values.........................|
 ----------------------------------------------------------------------------

    Add a 4 byte END for easy dealing with boundary situatons and add offset to get pointer being multiplies of 8.

 For a block which valid is false

                                            pointer
                                                |
  --------------------------------------------- v ---------------------------------------------------------
 | 29 bits for size, [empty] [prev] [cur=1] | [leftson 4Byte] [rightson 4Byte]  | [father 4Byte] |  ... |[foot 4Byte] |
 -----------------------------------------------------------------------------------------------------------
if 16 Bytes only, use one bit to mark if it is is 16 Bytes, and merge the father block and foot block.

 
 everytime i extend the heap,USE bigger than 4K instead of what i need.

 using binary search tree to faster the serach and insert

      NODE()
     /      \
   NODE()  NODE()
   / \      /  \
 ..  ..   ...  ....


split for 128,256,512

搞了一个不平衡的普通二叉搜索树（试图添加splay发现得分大寄特寄）
红黑树写不动。

不想加8字节的优化（本质上可以用一个bit来表示，让最小块大小不再是16而是8 


 
 
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "mm.h"
#include "memlib.h"

/* If you want debugging output, use the following macro.  When you hand
 * in, remove the #define DEBUG line. */
#define DEBUG
#ifdef DEBUG
# define dbg_printf(...) printf(__VA_ARGS__)
#else
# define dbg_printf(...)
#endif

/* do not change the following! */
#ifdef DRIVER
/* create aliases for driver tests */
#define malloc mm_malloc
#define free mm_free
#define realloc mm_realloc
#define calloc mm_calloc
#endif /* def DRIVER */

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(p) (((size_t)(p) + (ALIGNMENT-1)) & ~0x7)

#define GET(p) (*(int*)((char*)(p)-4))
#define GET_size(p) (GET(p) & (~0x7))
#define GET_rough_size(p) (GET(p))
#define GET_cur(p) (GET(p) & (1))
#define GET_prev(p) ((GET(p) & 2) >> 1)
#define SET_val(p,sz,prev,cur) GET(p) = (sz)+(prev)*2+(cur)
#define SET_size(p,v) GET(p) = (GET(p) & 3) | (v)
#define SET_cur(p,v) GET(p) = (GET(p) & (~1)) | (v)
#define SET_prev(p,v) GET(p) = (GET(p) & (~2)) | ((v)<<1)
#define NEXT_BLK(p) (char*)((char*)(p) + GET_size(p))
#define PREV_BLK(p) (char*)p-(((*((char*)p-8))&1)?((*(int*)((char*)p-8))&(~0x7)):16) // 小端机成立

#define max(a,b) (a)<(b)?(b):(a)
#define LSON(p) (char*)(p) + (*(int*)(p))
#define RSON(p) (char*)(p) + (*(int*)((char*)(p) + 4))
#define FA(p) (char*)(p) + (*(int*)((char*)(p) + 8))
#define SET_LSON(p,v) (*(int*)(p)) = (int)((v) - (p))
#define SET_RSON(p,v) (*(int*)((char*)(p) + 4)) = (int)((v) - (p))
#define SET_FA(p,v) (*(int*)((char*)(p) + 8)) = (int)((v) - (p))
#define WHICH(fa,p) ((LSON(fa)==(p))?0:1)
#define HAS_LSON(p) ((*(int*)(p)) != 0)
#define HAS_RSON(p) ((*(int*)((char*)(p) + 4)) != 0)
#define HAS_FA(p) ((*(int*)((char*)(p) + 8)) != 0)

void output_heap();// 输出堆
void output_free(char*);// 输出空闲树
void get_out_of_free(char*); // 从空闲树中删除
void insert_free_tree(char*); // 插入到空闲树中
void output_free(char*);
char* find_fit(); // 找到一个合适的空闲块
inline void SET_size_end(char* p,int v){ // 设置尾部
    int* ptr = (int*)(p + GET_size(p) - 8);
    if(GET_size(p) != 16)
        *ptr = GET_size(p) | 0x1;
}

/*
 * Initialize: return -1 on error, 0 on success.
 */
#define PAGE_SIZE 8192
static char *START_POINT,*END_POINT;//尾部指针
//static char *root64;
static char *root128;
static char *root256;
static char *root512;
static char *root513;
#define NOWSIZE PAGE_SIZE
#define NOWLOGSIZE LOG_PAGE_SIZE
static char *heap_pointerl = 0,*heap_pointerr = 0;
#define END_BLOCK_SIZE 4
static int need_init = 1;
static int total;
// int NOWSIZE,NOWLOGSIZE;
char* wrapped_mem_sbrk(size_t sz){ // 扩展堆
    int need = (heap_pointerl + sz - heap_pointerr);// / NOWSIZE * NOWSIZE;
    if(total <= 81920) need = (need + 2048 - 1) / 2048 * 2048; else // 99 -> 100
    need = (need + NOWSIZE - 1) / NOWSIZE * NOWSIZE;
    if(need){
        mem_sbrk(need);
        total += need;
        heap_pointerr += need;
    }
    char* tmp = heap_pointerl;
    heap_pointerl += sz;
    return tmp;
}
int mm_init(void) { // 初始化
    total = 0;
    root128 = NULL;
    root128 = NULL;
    root256 = NULL;
    root512 = NULL;
    root513 = NULL;
    int r = mem_heapsize();
    int rem = (12 - r % 8) % 8;
    if(mem_sbrk(rem) == (void*)-1){
        dbg_printf("\nD malloc %d", rem);
        return -1;
    }
    heap_pointerl = mem_sbrk(1536);
    total += 1536;
    heap_pointerr = heap_pointerl + 1536;
    START_POINT = (char*)wrapped_mem_sbrk(END_BLOCK_SIZE) + 4;
    END_POINT = START_POINT;
    SET_cur(END_POINT,1);
    SET_prev(END_POINT,1);
    return 0;
}

/*
 * malloc
 */

size_t calc_size(size_t size){ // 计算大小
    if(size>=448&&size<=512) size=512; //面向数据的玄学优化(劣化)
    size += 4;
    size = ((size + 7) >> 3) << 3;
    if(size < 16) size = 16;
    //加上4个byte，用来存大小
    //对齐8字节
    //至少16个字节对齐
    return size;
}

static int lastsize = 0;
void *malloc (size_t size) { // 分配
    if(need_init) mm_init(),need_init=0;
    lastsize = size;
    int all_size = (int)calc_size(size);
    char *ptr = NULL;
    ptr = find_fit(all_size);
    if(ptr != NULL){
        return ptr;
    }
    int prev_valid = GET_prev(END_POINT);
    size_t extend_size;
    if(prev_valid == 0){ // 考虑新的情况下可以合并尾部块
        size_t prev_size = GET_size(PREV_BLK(END_POINT));
        get_out_of_free(PREV_BLK(END_POINT));
        extend_size = all_size - prev_size;
    } else{
        extend_size = all_size;
    }
    char *p = wrapped_mem_sbrk(extend_size);
    if ((long)p < 0)
        return NULL;
    else { 
        if(prev_valid == 0) ptr = PREV_BLK(END_POINT);
                       else ptr = END_POINT;
        prev_valid = GET_prev(ptr);
        SET_val(ptr,all_size,prev_valid,1);
        END_POINT = ptr + all_size;

        SET_val(END_POINT,START_POINT-END_POINT,1,1);
        return ptr;
    }
//    return NULL;
}





inline void set_son(char* p,char* prev,char* nxtv,char** root){ 
    // 就你看啊，p这个点的儿子是prev，现在要把prev换成nxtv
    if(p == prev){
        *root = nxtv;
        return ;
    }
    char* lson = LSON(p);
    char* rson = RSON(p);
    // printf("[%p %p]\n",lson,rson);
    if(lson == prev) SET_LSON(p,nxtv); else
    if(rson == prev){
        SET_RSON(p,nxtv);
    }else{
        assert(0);
    }
}


inline void get_out_of_free(char *p){
    // 把p从free这个空闲块搞的树里面取出
    char **root;
    int size = GET_size(p);
    root = size<=128 ? &root128: size<=256 ? &root256 : size <= 512 ? &root512 : &root513;    
    // 根据大小选择root
    char* lson = LSON(p);
    char* rson = RSON(p);
    char* fa = FA(p);
    char* pval,*pval_son;
    if(lson == p && rson == p){
        if(p == *root) *root = NULL;
        else set_son(fa,p,fa,root);
        return ;
    } else
    if(lson != p){
        pval = lson;
        while(HAS_RSON(pval)) pval = RSON(pval);
        pval_son = LSON(pval);
    } else{
        pval = rson;
        while(HAS_LSON(pval)) pval = LSON(pval);
        pval_son = RSON(pval);
    }
    if(pval_son != pval){
        set_son(FA(pval),pval,pval_son,root);
        SET_FA(pval_son,FA(pval));
    }else{
        set_son(FA(pval),pval,FA(pval),root);
    }
    lson = LSON(p);
    rson = RSON(p);
    fa = FA(p);
    if(fa == p){
        *root = pval;
        SET_FA(pval,pval);
    }else {
        set_son(fa,p,pval,root);
        SET_FA(pval,fa);
    }
    if(lson == p) SET_LSON(pval,pval); else{
        SET_LSON(pval,lson);
        SET_FA(lson,pval);
    }
    if(rson == p) SET_RSON(pval,pval); else{
        SET_RSON(pval,rson);
        SET_FA(rson,pval);
    }
}
inline void insert_free_tree(char *ptr){
    char **root;
    int size = GET_size(ptr);
    root = size<=128 ? &root128: size<=256 ? &root256 : size <= 512 ? &root512 : &root513;

    SET_LSON(ptr,ptr);
    SET_RSON(ptr,ptr);
    if(*root == NULL){
        SET_FA(ptr,ptr);
        *root = ptr;
        // output_heap();
        return ;
    }

    size_t hashval = (size_t)ptr % 1049;
    //玄学哈希插入方法，主要是让插入稍微平衡一点，不要让全部相同的时候都一个方向
    //理论上有更科学的插入方法，但是我懒得写了
    //比如第奇数次访问它插入左儿子，偶数次访问插入右儿子
    char* now = *root;
    for(;;){
        if(GET_size(now) > size || (GET_size(now) == size && (size_t)now % 1049 >= hashval)){
            if(HAS_LSON(now)) now = LSON(now); else{
                SET_FA(ptr,now);
                SET_LSON(now,ptr);
                break;
            }
        } else{
            if(HAS_RSON(now)) now = RSON(now); else {
                SET_FA(ptr,now);
                SET_RSON(now,ptr);
                break;
            }
        }
    }
}

inline char* merge(char*p1,char*p2){
    get_out_of_free(p1);
    get_out_of_free(p2);
    int r = GET_size(p1) + GET_size(p2);
    SET_size(p1,r);
    SET_size_end(p1,r);
    insert_free_tree(p1);
    return p1;
}

char* find_fit_root(int size,char* root){
    if(root == NULL) return root;
    char* now = root;
    char* pos = NULL;
    for(;;){
        int psize = GET_size(now);
        if(psize == size) {
            pos = now;
            break;
        }
        if(psize >= size) pos = now;
        if(psize > size || (psize == size && (((size_t)now % 1009) & 1))){
            if(HAS_LSON(now)) now = LSON(now); else break;
        } else{
            if(HAS_RSON(now)) now = RSON(now); else break;
        }
    }
    if(pos == NULL) return NULL;
    if(GET_size(pos) <= size + 8){
        // emmm……就直接合并吧，浪费8字节算了。
        get_out_of_free(pos);
        SET_cur(pos,1);
        SET_prev(NEXT_BLK(pos),1);
        return pos;
     } else{
        get_out_of_free(pos);
        int sz1 = (int)size;
        int sz2 = (int)GET_size(pos) - sz1;
        char* p1 = pos;
        char* p2 = pos + sz1;
        assert(sz2 >= 16);
        SET_size(p1,sz1);
        SET_cur(p1,1);
        SET_val(p2,sz2,1,0);
        SET_size_end(p2,sz2);
        insert_free_tree(p2);
        return p1;
    }

    return NULL;
}

char* find_fit(int size){
    char* tmp = NULL;
    if(size <= 128 && tmp == NULL) tmp = find_fit_root(size,root128);
    if(size <= 512 && tmp == NULL) tmp = find_fit_root(size,root512);
    if(size <= 256 && tmp == NULL) tmp = find_fit_root(size,root256);
    if(tmp == NULL) tmp = find_fit_root(size,root513);
    return tmp;
}


void free (void *ptr) {
    if(ptr == NULL) return ;
    SET_cur(ptr,0);
    SET_prev(NEXT_BLK(ptr),0);
    // output_heap();
    insert_free_tree(ptr);
    int temp_size = GET_size(ptr);
    SET_size_end(ptr,temp_size);
    if(GET_cur(NEXT_BLK(ptr)) == 0){
        ptr = merge(ptr,NEXT_BLK(ptr));
    }
    if(GET_prev(ptr) == 0){
        ptr = merge(PREV_BLK(ptr),ptr);
    }
}

/*
 * realloc - you may want to look at mm-naive.c
 */

void *realloc(void *oldptr, size_t size)
{
    //没有做任何修改。
    size_t oldsize,newsize;
    void *newptr;
    if(size == 0) {
        free(oldptr);
        return 0;
    }
    if(oldptr == NULL) {
        return malloc(size);
    }

    oldsize = GET_size(oldptr);
    newsize = calc_size(size);
    newptr = malloc(size);
    if(newptr == NULL) return 0;
    
    newsize = GET_size(newptr) - 4;
    if(newsize < oldsize) oldsize = newsize;
    memcpy(newptr, oldptr, oldsize);
    free(oldptr);
    return newptr;
}

void output_heap(){
    char* i = START_POINT;
    printf("[%p %p ---->]\n",START_POINT,END_POINT);
    for(;(int*)i!=(int*)END_POINT;i = (char*)NEXT_BLK(i)){
        if(GET_cur(i) == 0){
            printf("[%p %d %d %d [%p %p %p]] -> %p\n",i,GET_size(i),GET_prev(i),GET_cur(i),LSON(i),RSON(i),FA(i),NEXT_BLK(i));
        } else{
            printf("[%p %d %d %d] -> %p\n",i,GET_size(i),GET_prev(i),GET_cur(i),NEXT_BLK(i));
        }
        // sleep(0.2);
    }
    puts("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
}

void output_free(char* root){
    if(root == NULL) return ;
    if(HAS_LSON(root)) output_free(LSON(root));
    printf(" [%p(%d)] ",root,GET_size(root));
    if(HAS_RSON(root)) output_free(RSON(root));
}

/*
 * calloc - you may want to look at mm-naive.c
 * This function is not tested by mdriver, but it is
 * needed to run the traces.
 */
void *calloc (size_t nmemb, size_t size){
    size_t bytes = nmemb * size;
    void *newptr;
    newptr = malloc(bytes);
    memset(newptr, 0, bytes);
    return newptr;
}


/*
 * Return whether the pointer is in the heap.
 * May be useful for debugging.
 */
static int in_heap(const void *p) {
    return p <= mem_heap_hi() && p >= mem_heap_lo();
}

/*
 * Return whether the pointer is aligned.
 * May be useful for debugging.
 */
static int aligned(const void *p) {
    return (size_t)ALIGN(p) == (size_t)p;
}

/*
 * mm_checkheap
 */
void mm_checkheap(int lineno) {
    char* i = START_POINT;
    printf("[%p %p ---->]\n",START_POINT,END_POINT);
    for(;(int*)i!=(int*)END_POINT;i = (char*)NEXT_BLK(i)){
        if(GET_cur(i) == 0){
            printf("[%p %d %d %d [%p %p %p]] -> %p\n",i,GET_size(i),GET_prev(i),GET_cur(i),LSON(i),RSON(i),FA(i),NEXT_BLK(i));
        } else{
            printf("[%p %d %d %d] -> %p\n",i,GET_size(i),GET_prev(i),GET_cur(i),NEXT_BLK(i));
        }
    }
    puts("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
}