728x90
implicit 구현
매크로부터 아래처럼 작성하면 된다.
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(p) (((size_t)(p) + (ALIGNMENT-1)) & ~0x7)
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12)
#define OVERHEAD 8 // padding?
#define MAX(x, y) ((x) > (y) ? (x) : (y)) // 최대값
#define PACK(size, alloc) ((size) | (alloc)) // 헤더에 사이즈 + 할당, 연결하기
#define GET(p) (*(unsigned int *)(p)) // 값 가져오기
#define PUT(p, val) (*(unsigned int *)(p) =(int)(val)) // 헤더에 값 넣기
#define GET_SIZE(p) (GET(p) & ~0x7) // 사이즈
#define GET_ALLOC(p) (GET(p) & 0x1) // 할당여부
#define HDRP(bp) ((char *)(bp) - WSIZE) // 헤더
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 푸터
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE((char *)(bp)-WSIZE)) // 다음 블록
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp)-DSIZE)) // 이전 블록
초기화는 아래와 같은 식으로 진행하였다.
static void *coalesce(void *bp);
void *extend_heap(size_t words);
static char *heap_listp;
static char *last_access_ptr;
int mm_init(void) {
if((heap_listp = mem_sbrk(4 * WSIZE)) == NULL) {
return -1;
}
PUT(heap_listp, 0); // padding
PUT(heap_listp + WSIZE, PACK(OVERHEAD, 1)); // 헤더
PUT(heap_listp + DSIZE, PACK(OVERHEAD, 1)); // 푸터
PUT(heap_listp + WSIZE + DSIZE, PACK(0, 1)); // 에필로그
heap_listp += DSIZE;
last_access_ptr = heap_listp;
return 0;
}last_access_ptr은 next fit을 위한 포인터이다. 16칸 짜리 heap을 만들고, 거기에 0, 8(프롤로그 헤더), 8(프롤로그 푸터), 0(에필로그 헤더)으로 블록을 할당한다. 즉 헤더와 푸터 경계태그에 크기가 8이라는 것을 부여하고, 에필로그에는 크기 0으로 만듭니다. 그리고 8의 배수 정렬을 위해서 padding으로 4바이트를 넣은 것 입니다. 아래와 같은 그림처럼 되어있다고 생각하면 됩니다.
실습 자료의 경우 헤더 풋터 뒷부분에 블록들을 할당하였지만, 저는 header와 footer사이에 포인터를 옮겨서 사용했습니다.
※ 기존 ppt에서는 extend_heap을 통해 CHUNKSIZE / WISZE 만큼 힙을 추가로 늘려주는 코드가 존재하였 습니다만, 이렇게 되면 util 측정에서 heap을 조금 사용하는 경우에도 초기 heap의 크기로 인하여 성능이 나 쁘게 나오는 경우가 있어서 제거하였습니다.
그 다음은 next_fit으로 구현한 find_fit입니다. 입력으로 들어온 값이 0이면 할당할 필요가 없기 때문에 return하고, 그게 아니라면 계속 진행합니다. next_fit이기 때문에 포인터를 사용합니다.
찾기 시작하는 포인터의 헤더를 가져와서 할당여부를 파악합니다. 할당되어있다면 지나갑니다. 사이즈가 작아도 지나갑니다. 그렇게 할당가능하고, 사이즈도 들어갈 수 있는 블록을 찾습니다.
static void *find_fit(size_t asize) {
if(asize == 0) {
return NULL;
}
char *bp = last_access_ptr;
while(1) {
int is_allocated = GET_ALLOC(HDRP(bp));
size_t block_size = GET_SIZE(HDRP(bp));
if((block_size >= asize) && (is_allocated == 0)) {
return bp;
}
if((block_size == 0) && (is_allocated == 1)) {
return NULL;
}
bp = NEXT_BLKP(bp);
}
}
이 과정에서 가용 블록(free block)을 찾고, 그 블럭에 대해서 할당을 진행하고 나면, 가용블럭의 크기가 크면 내부 단편화가 일어날 것입니다.
그래서 place에 필요한 부분이 수업 자료에선 addblock의 부분입니다.
static void place(void *bp, size_t asize) {
size_t current_size = GET_SIZE(HDRP(bp));
if((current_size - asize) >= (OVERHEAD + DSIZE)) {
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(current_size - asize, 0));
PUT(FTRP(bp), PACK(current_size - asize, 0));
return;
}
else {
PUT(HDRP(bp), PACK(current_size, 1));
PUT(FTRP(bp), PACK(current_size, 1));
return;
}
}현재의 포인터와 할당하려는 크기가 들어오면, 현재 가용 블록의 크기와 할당하려는 크기을 비교해보고, 남는 블록이 생긴다면 쪼개서 새 가용블록을 남는 부분으로 만들고, 그렇지 않으면 단순 할당하는 방법으로 진행합니다.
위 코드에서 실습의 경우는 place부분을 addblock없이 진행한 경우를 보이라고 합니다. 그럴때는 else문의 부분만 사용하면 됩니다.
그리고 이 place함수를 사용하는 malloc부분은 아래와 같이 naive함수에서 따와서 수정했습니다.
void *malloc (size_t size) {
size_t asize;
size_t extendsize;
char* bp;
if(size == 0) {
return NULL;
}
asize = ALIGN(size + OVERHEAD);
if((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
extendsize = asize;
if((bp = extend_heap(extendsize / WSIZE)) == NULL) {
return NULL;
}
place(bp, asize);
return bp;
}사전에 말했듯이 할당하려는 크기가 0이면 함수 진행을 끝냅니다.
그게 아니라면 할당하려는 블록의 크기를 주소정렬하여 8의 배수로 맞춥니다. 7 -> 8, 13 -> 16
그리고 find_fit함수를 통해서 가용블록을 찾습니다. 그리고 할당합니다. 만약, 블럭이 없다면 heap을 늘려서 할당을 진행합니다.
그 다음은 위에서 언급한 heap사이즈를 늘리는 extend_heap의 함수를 정의합니다.
void *extend_heap(size_t words) {
char *bp;
size_t size;
size = ALIGN(words * WSIZE);
if((long)(bp = mem_sbrk(size)) == -1) {
return NULL;
}
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
return (last_access_ptr = bp);
}확장하는 사이즈는 8의 배수만큼으로 확장했습니다.
그 다음 이렇게 새로 생긴 가용블록에 헤더와 푸터를 지정합니다. 그 다음에는 에필로그 블록을 맨뒤로 옮깁니다. 그리고 마지막으로 탐색한 블럭의 포인터를 새로 생긴 가용블록의 포인터로 지정합니다.
그리고 realloc과 calloc은 naive와 같습니다.
void *realloc(void *oldptr, size_t size) {
if(size == 0) {
free(oldptr);
return 0;
}
if(oldptr == NULL) {
return malloc(size);
}
void *new_ptr = malloc(size);
if(!new_ptr){
return NULL;
}
size_t old_size = GET_SIZE(HDRP(oldptr));
if(size < old_size) {
old_size = size;
}
memcpy(new_ptr, oldptr, old_size);
free(oldptr);
return new_ptr;
}
void *calloc (size_t nmemb, size_t size) {
size_t bytes = nmemb * size;
void *newptr;
newptr = malloc(bytes);
memset(newptr, 0, bytes);
return newptr;
}그 다음은 free와 coalesc를 구현하여 이용률(utilization)을 올려보겠다. 이전에는 free의 구현이 없어서 naive와 똑같은 성능이 나올 것입니다.
void free (void *ptr) {
if(ptr == NULL) {
return;
}
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
last_access_ptr = coalesce(ptr);
}free는 간단하다 헤더와 푸터를 가져와서 alloc부분만 0으로 바꾸어 주면됩니다.
coalesce를 구현 전이라면 last_access_ptr을 ptr로 할당하면 될 것입니다. last_access_ptr = ptr;
static void *coalesce(void *bp) {
size_t current_block_size = GET_SIZE(HDRP(bp));
char *prev_bp = PREV_BLKP(bp);
char *next_bp = NEXT_BLKP(bp);
int prev_alloc = GET_ALLOC(HDRP(prev_bp));
int next_alloc = GET_ALLOC(HDRP(next_bp));
size_t prev_size = GET_SIZE(HDRP(prev_bp));
size_t next_size = GET_SIZE(HDRP(next_bp));
if(prev_alloc && next_alloc) {
return bp;
}
else if(!prev_alloc && next_alloc) {
current_block_size += prev_size;
PUT(HDRP(prev_bp), PACK(current_block_size, 0));
PUT(FTRP(prev_bp), PACK(current_block_size, 0));
return prev_bp;
}
else if(prev_alloc && !next_alloc) {
current_block_size += next_size;
PUT(HDRP(bp), PACK(current_block_size, 0));
PUT(FTRP(bp), PACK(current_block_size, 0));
return bp;
}
else{
current_block_size += prev_size + next_size;
PUT(HDRP(prev_bp), PACK(current_block_size, 0));
PUT(FTRP(prev_bp), PACK(current_block_size, 0));
return prev_bp;
}
}coalesc의 경우는 4가지 경우로 나눕니다. 앞뒤 블럭이 할당인 경우, 앞 블럭이 가용인 경우, 뒷 블럭이 가용인 경우, 앞뒤 블럭이 가용인 경우로 나뉩니다. 각각의 경우에 따라서 free하려는 블럭과 결합시켜주면됩니다.
이러면 implicit의 구현이 끝이납니다.
explicit 구현
이번에는 직접 리스트이다. 직접 리스트는 간접 리스트와 다르게 가용블럭만을 관리하는 방식이다. 처리율이 더 좋습니다.
우선 매크로 부분입니다.
/* 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 ALIGN(p) (((size_t)(p) + (ALIGNMENT - 1)) & ~0x7)
#define HDRSIZE 4
#define FTRSIZE 4
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12)
#define OVERHEAD 8
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? i(x) : (y))
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
#define GET8(p) (*(unsigned long *)(p))
#define PUT8(p, val) (*(unsigned long *)(p) = (unsigned long)(val))
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define HDRP(bp) ((char *)(bp)-WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_FREEP(bp) ((char *)(bp))
#define PREV_FREEP(bp) ((char *)(bp) + DSIZE)
#define NEXT_FREE_BLKP(bp) ((char *)GET8((char *)(bp)))
#define PREV_FREE_BLKP(bp) ((char *)GET8((char *)(bp) + DSIZE))
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE((char *)(bp)-WSIZE))
#define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE((char *)(bp)-DSIZE))간접리스트와 마찬가지로 초기화부분을 보겠습니다.
static char * heap_start;
void *extend_heap(size_t size);
static void *find_fit(size_t asize);
static void *coalesce(void *bp);
static void place(void *bp, size_t asize);
void relinkblock(void *bp);
void linking(void *first, void *second);
int mm_init(void) {
void *bp;
if ((bp = mem_sbrk(2*WSIZE + OVERHEAD)) == NULL) {
return -1;
}
heap_start = NULL;
PUT(bp, 0);
PUT(bp + WSIZE, PACK(OVERHEAD, 1));
PUT(bp + DSIZE, PACK(OVERHEAD, 1));
PUT(bp + WSIZE + OVERHEAD, PACK(0, 1));
return 0;
}여기서 heap_start는 가용블럭의 시작부분입니다. 간접리스트와 마찬가지로 나머지는 똑같이 되어있습니다.
그 다음은 find_fit의 구현을 보겠습니다.
여기서는 가용리스트의 포인터인 heap_start에서부터 best fit을 찾는 방식으로 구현하였습니다.
static void *find_fit(size_t asize) {
void *bp = heap_start;
void *fit = NULL;
size_t fit_size = -1;
while (bp != NULL) {
size_t block_size = GET_SIZE(HDRP(bp));
if (block_size >= asize) { // 할당하려는 블럭이 현재 가용블럭 사이즈보다 작거나 같은가?
if (fit_size == -1) { // 최초할당인지
fit_size = block_size; // 사이즈 갱신
fit = bp; // 포인터 갱신
}
if (fit_size > block_size) { // 이전까지 탐색한 best size보다 작은 경우
fit_size = block_size; // 사이즈 갱신
fit = bp; // 포인터 갱신
}
if (block_size == asize) { // 할당하려는 블록과 가용 블록 크기가 같은 경우
return bp;
}
}
bp = NEXT_FREE_BLKP(bp); // 조건에 맞지 않을 때 탐색 계속
}
return fit;
}NEXT_FREE_BLKP은 포인터의 블럭 안에 있는 링크포인터를 가지고 주소를 찾아서 그 가용블럭으로 이동하는 것입니다.
그래서 포인터가 null이 아니라면 계속 진행합니다.
이번에는 좀 더 까다로워진 place의 구현을 보겠습니다.
아래의 코드에는 블럭 쪼개기(addblock)의 경우가 포함되어있다. 블럭 쪼개기를 하기전의 구현이라면, next_block_size와 default_size를 비교하는 if문의 코드를 주석처리하면 됩니다.
static void place(void *bp, size_t asize) {
size_t block_size = GET_SIZE(HDRP(bp));
size_t next_block_size = block_size - asize;
size_t default_size = 3 * OVERHEAD;
char *prev_block_pointer = PREV_FREE_BLKP(bp);
char *next_block_pointer = NEXT_FREE_BLKP(bp);
if (next_block_size >= default_size) { // 남는 가용블럭 부분이 8의 배수보다 크거나 같은가
PUT(HDRP(bp), PACK(asize, 1)); // 블럭 할당
PUT(FTRP(bp), PACK(asize, 1)); // 블럭 할당
char * tmp = NEXT_BLKP(bp);
PUT8(PREV_FREEP(tmp), NULL); // 블럭 쪼개기 과정 중 링크 포인터 초기화
PUT8(NEXT_FREEP(tmp), NULL); // 블럭 쪼개기 과정 중 링크 포인터 초기화
if (next_block_pointer != NULL) { // 다음 가용 블럭이 있으면
PUT8(NEXT_FREEP(tmp), next_block_pointer); // 쪼개진 블럭의 다음 가용 블럭을 가리키는 포인터를 쪼개지기 전 블록의 다음 가용 블럭으로
PUT8(PREV_FREEP(next_block_pointer), tmp); // 다음 가용 블럭의 이전 가용블럭 포인터를 현재 쪼개진 블럭으로
}
if (prev_block_pointer != NULL) { // 이전 가용 블럭이 있으면
PUT8(NEXT_FREEP(prev_block_pointer), tmp); // 이전 가용 블럭의 다음 가용 블럭을 가리키는 포인터를 쪼개진 블럭으로
PUT8(PREV_FREEP(tmp), prev_block_pointer); // 쪼개진 블럭의 이전 가용 블럭을 이전 가용 블럭으로
}
if (bp == heap_start) { // 기존 블럭 리스트의 제일 처음 블럭이었다면, 블럭 쪼개기 이후 쪼개진 블럭을 제일 처음 블럭으로 만든다.
heap_start = tmp;
}
PUT(HDRP(tmp), PACK(next_block_size, 0)); // 쪼갠 블럭을 가용블럭으로 만든다.
PUT(FTRP(tmp), PACK(next_block_size, 0)); // // 쪼갠 블럭을 가용블럭으로 만든다.
return;
}
// 블럭 쪼개기를 하지 않는 경우
PUT(HDRP(bp), PACK(block_size, 1));
PUT(FTRP(bp), PACK(block_size, 1));
if (prev_block_pointer == NULL && next_block_pointer == NULL) {
heap_start = NULL;
return;
} // 모든 블럭이 할당되어있는 경우
if (prev_block_pointer == NULL && next_block_pointer != NULL) {
PUT8(PREV_FREEP(next_block_pointer), NULL);
heap_start = next_block_pointer;
return;
} // 이전 블럭은 할당(즉, 가용블럭 리스트의 맨앞), 다음 블럭은 가용인 경우. 다음 가용 블럭의 이전 가용 블럭을 가리키는 포인터를 NULL로 만든다.
if (prev_block_pointer != NULL && next_block_pointer == NULL) {
PUT8(NEXT_FREEP(prev_block_pointer), NULL);
return;
} // 이전 블록이 가용 블럭이고, 다음 블럭이 할당 블럭인 경우(즉 가용블럭 리스트의 맨뒤).
PUT8(NEXT_FREEP(prev_block_pointer), next_block_pointer); // 가용블럭 리스트의 중간에 있는 경우
PUT8(PREV_FREEP(next_block_pointer), prev_block_pointer);
}
place를 구현했으니 이제는 malloc을 구현을 보겠습니다.
void *malloc(size_t size) {
if (size <= 0) {
return NULL;
}
size_t asize = MAX(ALIGN(size + OVERHEAD), 3 * OVERHEAD);
void *bp;
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
size_t extend = MAX(asize, CHUNKSIZE);
bp = extend_heap(extend / WSIZE);
if (bp == NULL) {
return NULL;
}
place(bp, asize);
return bp;
}실습자료를 참고하여 asize를 정해주는 코드를 제외하고는 같습니다.
realloc
void *realloc(void *oldptr, size_t size) {
if (size == 0) {
free(oldptr);
return 0;
}
if (oldptr == NULL) {
return malloc(size);
}
void *newptr = malloc(size);
if (newptr == NULL) {
return NULL;
}
size_t oldsize = GET_SIZE(HDRP(oldptr));
if (size < oldsize) {
oldsize = size;
}
memcpy(newptr, oldptr, oldsize);
free(oldptr);
return newptr;
}calloc
void *calloc(size_t nmemb, size_t size) {
size_t bytes = nmemb * size;
void *newptr;
newptr = malloc(bytes);
memset(newptr, 0, bytes);
return newptr;
}
malloc과정에서 마찬가지로 extend heap의 과정이 있습니다.
void * extend_heap(size_t words) {
unsigned size = (words%2) ? (words+1) * WSIZE : words * WSIZE;
char *bp;
if ((long)(bp = mem_sbrk(size)) == NULL) {
return NULL;
}
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
PUT8(PREV_FREEP(bp), NULL);
PUT8(NEXT_FREEP(bp), NULL);
if(heap_start != NULL) {
PUT8(PREV_FREEP(heap_start), bp);
PUT8(NEXT_FREEP(bp), heap_start);
}
heap_start = bp;
return heap_start;
}실습 자료를 참고하여, size를 결정하였습니다. 확장하려는 크기가 홀수라면 짝수로 만들어서 주소 정렬을 해주었습니다.
헤더, 푸터를 정의하고, 에필로그를 뒤로 미루고, 그 다음에는 현재 블럭이 가리키는 포인터를 설정해줘야 합니다.
LIFO방식으로 구현하기 때문에 가용블럭을 맨앞에 붙여 넣을 것입니다. 그래서 heap_start가 있는지 확인하고 있다면 포인터 설정을 갱신해줍니다. 그리고 heap_start도 새로 추가한 가용블럭으로 지정합니다.
여기까지 구현하면 naive와 성능이 같거나 떨어질 것입니다. 왜냐하면 free 함수가 없기 때문입니다.
그래서 이제 성능을 올리기 위해서 free와 coalesce를 구현하였습니다.
void free(void *ptr) {
if (ptr == NULL){
return;
}
size_t current = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(current, 0));
PUT(FTRP(ptr), PACK(current, 0));
/*PUT8(PREV_FREEP(ptr), NULL);
PUT8(NEXT_FREEP(ptr), NULL);
if(heap_start !=NULL) {
PUT8(PREV_FREEP(heap_start), ptr);
PUT8(NEXT_FREEP(ptr), heap_start);
}
heap_start = ptr;
return heap_start;*/
coalesce(ptr);
}free는 coalesce를 구현하기 전과 한 후의 코드를 다르게 하였습니다.
간접 리스트와 비슷한 방식으로 구현하였습니다.
coalesce부분은 설명이 길어서 보고서로 대체하겠습니다.
static void * coalesce(void *bp) {
size_t current = GET_SIZE(HDRP(bp));
char *prev_bp = PREV_BLKP(bp);
size_t prev_size = GET_SIZE(HDRP(prev_bp));
int prev_alloc = GET_ALLOC(HDRP(prev_bp));
char *next_bp = NEXT_BLKP(bp);
size_t next_size = GET_SIZE(HDRP(next_bp));
int next_alloc = GET_ALLOC(HDRP(next_bp));
if (prev_alloc && next_alloc) {
PUT8(PREV_FREEP(bp), NULL);
PUT8(NEXT_FREEP(bp), NULL);
if (heap_start != NULL) {
PUT8(PREV_FREEP(heap_start), bp);
PUT8(NEXT_FREEP(bp), heap_start);
}
heap_start = bp;
return heap_start;
}
else if (!prev_alloc && next_alloc) {
current += prev_size;
relinkblock(prev_bp);
PUT8(PREV_FREEP(prev_bp), NULL);
if (prev_bp != heap_start) {
PUT8(NEXT_FREEP(prev_bp), heap_start);
PUT8(PREV_FREEP(heap_start), prev_bp);
}
PUT(HDRP(prev_bp), PACK(current, 0));
PUT(FTRP(prev_bp), PACK(current, 0));
heap_start = prev_bp;
return heap_start;
}
else if (prev_alloc && !next_alloc) {
current += next_size;
relinkblock(next_bp);
PUT8(PREV_FREEP(bp), NULL);
if (next_bp == heap_start) {
PUT8(NEXT_FREEP(bp), NEXT_FREE_BLKP(next_bp));
if (NEXT_FREE_BLKP(next_bp) != NULL) {
PUT8(PREV_FREEP(NEXT_FREE_BLKP(next_bp)), bp);
}
}
if (next_bp != heap_start) {
PUT8(NEXT_FREEP(bp), heap_start);
PUT8(PREV_FREEP(heap_start), bp);
}
PUT(HDRP(bp), PACK(current, 0));
PUT(FTRP(bp), PACK(current, 0));
heap_start = bp;
return heap_start;
}
else if (!prev_alloc && !next_alloc) {
current += prev_size + next_size;
if (prev_bp != heap_start && next_bp != heap_start) {
relinkblock(prev_bp);
relinkblock(next_bp);
PUT8(PREV_FREEP(prev_bp), NULL);
linking(prev_bp, heap_start);
PUT(HDRP(prev_bp), PACK(current, 0));
PUT(FTRP(prev_bp), PACK(current, 0));
heap_start = prev_bp;
return heap_start;
}
else if (prev_bp == heap_start && next_bp == NEXT_FREE_BLKP(prev_bp)) {
void *right_next = NEXT_FREE_BLKP(next_bp);
PUT8(PREV_FREEP(prev_bp), NULL);
linking(prev_bp, right_next);
PUT(HDRP(prev_bp), PACK(current, 0));
PUT(FTRP(prev_bp), PACK(current, 0));
heap_start = prev_bp;
return heap_start;
}
else if (prev_bp == heap_start && next_bp != NEXT_FREE_BLKP(prev_bp)) {
void *left_next = NEXT_FREE_BLKP(prev_bp);
relinkblock(next_bp);
PUT8(PREV_FREEP(prev_bp), NULL);
linking(prev_bp, left_next);
PUT(HDRP(prev_bp), PACK(current, 0));
PUT(FTRP(prev_bp), PACK(current, 0));
heap_start = prev_bp;
return heap_start;
}
else if (next_bp == heap_start && prev_bp == NEXT_FREE_BLKP(next_bp)) {
void *left_next = NEXT_FREE_BLKP(prev_bp);
PUT8(PREV_FREEP(prev_bp), NULL);
linking(prev_bp, left_next);
PUT(HDRP(prev_bp), PACK(current, 0));
PUT(FTRP(prev_bp), PACK(current, 0));
heap_start = prev_bp;
return heap_start;
}
else if (next_bp == heap_start && prev_bp != NEXT_FREE_BLKP(next_bp)) {
relinkblock(prev_bp);
PUT8(PREV_FREEP(prev_bp), NULL);
linking(prev_bp, NEXT_FREE_BLKP(next_bp));
PUT(HDRP(prev_bp), PACK(current, 0));
PUT(FTRP(prev_bp), PACK(current, 0));
heap_start = prev_bp;
return heap_start;
}
return NULL;
}
return NULL;
}
void relinkblock(void *bp) {
char *prev_bp = PREV_FREE_BLKP(bp);
char *next_bp = NEXT_FREE_BLKP(bp);
if ((prev_bp) == NULL) {
return;
}
PUT8(NEXT_FREEP(prev_bp), next_bp);
if (next_bp != NULL) {
PUT8(PREV_FREEP(next_bp), prev_bp);
}
}
void linking(void * a, void * b) {
PUT8(NEXT_FREEP(a), b);
if (b != NULL) {
PUT8(PREV_FREEP(b), a);
}
}728x90