-
[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끼리만 합치는듯)
어쨌든 잘 완성해서 힙은 마무리
'C' 카테고리의 다른 글
[C] 230807 MIL 도형조작, 리스트, BMP파일, 멀티쓰레드, 뮤텍스 (0) 2023.08.07 [C] 포인터 변수 a의 (*a)++ / a++ 차이 (0) 2023.07.05 [C] 부호를 고려하는 타입 이진수 범위 (0) 2023.07.05