ABOUT ME

공부 개인 기록용 블로그입니다

Today
Yesterday
Total
  • [C] 230711 TIL // heap 구현
    C 2023. 7. 11. 13:49
    #include <stdlib.h>
    #include <string.h>
    #include "heap_tools.h"
    
    void heap_init(Heap* h){
    	set_header(h->pool, 'f', MaxHeapL - 5);
    	memset(h->head, 0, MaxHeadL);
    }
    
    char** heap_alloc(Heap* h, int sz){
    	char* p= 0;
    	if (p = find_free(h, sz)){
    		set_header(p+(sz+5), 'f', *((int*)(p+1)) - (sz+5));
    		set_header(p, 'a', sz);		
    	}
    	return head_push_back(h, p);
    
    }
    
    void heap_free(Heap* h, char** p){
    	set_header(*p, 'f', *((int*)((*p)+1)));
    	head_pop_at(h, *p);
    }
    
    void heap_defrag(Heap* h){
    	char* dst = find_free(h, 0);
    	for (char* p = dst + *((int*)(dst+1)) + 5; p - (h->pool) < MaxHeapL-5; ){
    		int sz = *((int*)(p+1));
    
    		if(*p == 'f'){
    			*((int*)(dst+1)) += sz + 5;
    			set_null(p, 5);
    			p+= sz + 5;
    
    		}else if(*p == 'a'){
    			int dst_sz = *((int*)(dst+1));
    			set_header(dst, 'a', sz);
    			set_null(p, 5);
    			set_header(dst+(sz+5), 'f', dst_sz);
    			head_refresh(h, p, dst);
    			dst= find_free(h, 0);
    			p= dst + *((int*)(dst+1)) + 5;
    		}
    	}
    }
    #define MaxHeapL 260
    #define MaxHeadL MaxHeapL/6 + 1
    
    typedef struct{
    	char pool[MaxHeapL];
    	char* head[MaxHeadL];
    } Heap;
    
    void set_null(char* p, int n){
    	for (int j= 0; j< n; j++)
    		p[j] = 0;
    }
    
    void set_header(char* addr, char header, int sz){
    	*addr = header;
    	*((int*)(addr+1))= sz;
    }
    
    char* find_free(Heap* h, int sz){
    	for (int i=0; i< MaxHeapL; i++){
    		if (h->pool[i] == 'a')
    			i += *((int*)&(h->pool[i+1])) + 4;
    		else if (h->pool[i] == 'f'){
    			if (*((int*)(&h->pool[i+1])) >= sz + 5)
    				return &(h->pool[i]);
    			i += *((int*)&(h->pool[i+1])) + 4;
    		}
    	}
    	return 0;
    }
    
    void head_refresh(Heap* h, char* befo, char* aftr){
    	for (int i= 0; i< MaxHeadL; i++){
    		if (h->head[i] == befo){
    			h->head[i] = aftr;
    			break;
    		}
    	}
    }
    
    char** head_push_back(Heap* h, char* p){
    	for (int i= 0; i< MaxHeadL; i++){
    		if(h->head[i] == 0){
    			h->head[i] = p;
    			return &(h->head[i]);
    		}
    	}
    }
    
    void head_pop_at(Heap* h, char* p){
    	for (int i= 0; i< MaxHeadL; i++){
    		if (h->head[i] == p){
    // 			for (int j=i; j < h->n; j++)
    // 				h->head[j] = h->head[j+1];
    			h->head[i] = 0;
    			break;
    		}
    	}
    }

     

    기본적인 힙의 작동 방식을 스택에 구현해봤다

     

    처음엔 힙의 헤더 뒤 4바이트 공간에 16진수로 저장해야겠단 생각을 못하고,

    10진수로 저장했었다

    20을 저장하려고 하면 각각의 바이트에

    a 0 0 2 0 이런식으로 각각의 자리수마다 char로 형변환해서 저장함..  (틀린방법인데 쓸데없이 복잡했었음 코드도 길고)

     

    대표님께서 보시고는 이게 뭐냐고 하시고 ㅎ

     

    16진수로 하라고 하셔서 다시 짰는데 훨씬 쉬워졌음

     

    16진수로 제대로 저장하도록 구현했다

     

    처음엔 헤더 뒤 주소에 숫자를 할당하면 255 초과 시 0으로 초기화되어 저장을 못해서,

    16^2 초과시마다 주소 바이트마다 옮겨가며 새로 저장해야 하나 해서 복잡해졌었는데

     

    1바이트였던 p를 (int *)p 로 형변환하여 4바이트로 바꿔주니 알아서 잘 저장 되었음

     

    heap 자체는 금방 구현 했는데, 낭비되는 공간이 없도록 조각모음을 구현하려다 보니 하루를 다 썼다.

     

    free() 후 조각모음을 한 뒤에, 메모리들의 위치가 변경되기 때문에

    메모리의 위치를 가리킬 테이블을 만들어서 저장했는데,

     

    대표님꼐서 이건 힙방식이 아니라 좀더 복잡한 파일 시스템 방식이라고 하셨다

    (힙은 근처의 free끼리만 합치는듯)

     

    어쨌든 잘 완성해서 힙은 마무리

Designed by Tistory.