🎯 To-do List
⏳ Routine
✅ 알고리즘 스터디 | 2504 괄호의 값
☑️ 기술 면접 준비 | X
🍪 Plan
☑️ c++ 공부하기
☑️ 기술 면접 준비 | (1) 경쟁 조건, 데드락, (2) 뮤텍스, 세마포어, 조건 변수, (3) 멀티프로세스와 멀티쓰레드의 차이
☑️ malloc 구현 후 | CS:APP 6장 읽기, 복습을 위해 이거 보기
📚 Journal
5기 분들이 내일 모레면 다 떠나신다길래 저녁에 가서 이것저것 물어봄.
-
5기는 시작부터 끝날때까지 다들 지각 안 하고 잡담 안 하고 하루종일 코딩만 하고 매일 10명 정도는 1시까지 하는 사람들 있었다고 함. 나도 생활 패턴 바로 잡고 더 열심히 해야 한다.
-
나만무는 실력 좋으면 좋겠지만 일단 방향성, 성격 등 마음 맞는 사람들끼리 해야 한다.
-
기록을 잘 해놓으면 좋다. (트러블 슈팅에 관한 거 남겨두면 좋음)
이외에는 나만무 구현하신 것들 구경하거나 신변잡기.
📦 Malloc
묵시적 1: realloc 함수
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
// 새로 할당할 size에 맞는 가용 블록 찾아서 할당
newptr = mm_malloc(size);
// size가 0이거나 음수이면 NULL 반환
if (newptr == NULL)
return NULL;
// copy할 size를 oldptr에 역참조한 값에서 추출
copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
// 재할당하려는 블록의 크기가 기존 블록의 크기보다 작을 경우,
// 실제로 복사할 크기를 size로 제한
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}어제부터 문제가 되었던 함수.
도대체 어떻게 한거지?? 하면서 5기 분들에게 물어보러 감.
realloc을 바꾸지 않고도 잘 작동했었던 것 같다고 하심.
해당 코드가 있는 블로그 주소를 받아옴.
긁어와서 해봤더니 정상 작동함.
다 똑같은데 뭐가 틀린거지? 했는데 동기가
copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
이 부분이 다르다고 함. 뭔가 이상하다고 생각은 하고 있었다고도 함.
답지 코드는 copySize = GET_SIZE(HDRP(oldptr)); 이거였음.
SIZE_T_SIZE가 8바이트만큼 앞으로 가버려서
현재 블록의 헤더가 아니라 이전 블록의 푸터를 가져와버림.
책에 구현돼있는 코드와
repository에 구현돼있던 기존 코드의 로직이 달라서 생겼던 일.
기존 코드에서 한 줄 고쳤더니 정상 작동했다.
묵시적 가용 리스트 완성 ✅
/*
* mm-naive.c - The fastest, least memory-efficient malloc package.
*
* In this naive approach, a block is allocated by simply incrementing
* the brk pointer. A block is pure payload. There are no headers or
* footers. Blocks are never coalesced or reused. Realloc is
* implemented directly using mm_malloc and mm_free.
*
* NOTE TO STUDENTS: Replace this header comment with your own header
* comment that gives a high level description of your solution.
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/* Basic constants and macros */
#define WSIZE 4 // 워드, 헤더, 푸터 사이즈 (단위: 바이트)
#define DSIZE 8 // 더블 워드 사이즈 (단위: 바이트)
#define CHUNKSIZE (1 << 12) // 힙을 이만큼 늘림 (단위: 바이트)
#define MAX(x, y) ((x) > (y) ? (x) : (y))
/* 하나의 워드에 메모리 블록의 크기와 할당 상태를 함께 저장 */
#define PACK(size, alloc) ((size) | (alloc))
/* 주소 p에 있는 워드를 읽고 쓰기 */
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
/* 주소 p에 있는 워드에서 메모리 블록의 크기와 할당 상태 읽기 */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
/* 주어진 블록 포인터 bp에 대해서, 헤더와 푸터의 주소를 구한다 */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* 주어진 블록 포인터 bp에 대해서, 다음 블록과 이전 블록의 위치를 구한다 */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
/////////////// 전방 선언 /////////////////
static void *extend_heap(size_t words);
void *mm_malloc(size_t size);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static void *coalesce(void *bp);
void *mm_realloc(void *ptr, size_t size);
/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team = {
/* Team name */
"ateam",
/* First member's full name */
"Harry Bovik",
/* First member's email address */
"bovik@cs.cmu.edu",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""};
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
/* 8바이트 정렬을 유지하기 위해 짝수인 워드로만 할당한다 */
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
/* mem_sbrk로 힙의 brk 포인터를 변경 시도. 만약 불가능하면 NULL 반환. */
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
/* 가용 블록 헤더/푸터, 에필로그 푸터를 초기화 */
/* sbrk에서 반환된 포인터 bp는 이전의 에필로그 블록을 가리키고 있음.
sbrk로 heap의 크기가 늘어났으므로, 이전의 에필로그 블록을 가용 블록으로 변환해야 함.
이를 위해 새로운 가용 블록의 헤더와 푸터를 설정하고, 새로운 에필로그 블록을 생성하는 과정. */
PUT(HDRP(bp), PACK(size, 0)); // 가용 블록 헤더
PUT(FTRP(bp), PACK(size, 0)); // 가용 블록 푸터
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 새 에필로그 헤더
// 이전 에필로그 블록이 가용 블록이었다면, 새로운 힙 영역의 가용 블록과 결합함
return coalesce(bp);
}
/*
* mm_init - initialize the malloc package.
*/
static char *heap_listp;
int mm_init(void)
{
// char *heap_listp = NULL;
/* 빈 heap 생성 */
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0); // 정렬 패딩
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 헤더
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 푸터
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // 에필로그 헤더
heap_listp += (2 * WSIZE);
/* CHUNKSIZE 바이트의 가용 블록만큼 heap 영역을 늘림 */
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
return -1;
return 0;
}
/*
* mm_malloc - Allocate a block by incrementing the brk pointer.
* Always allocate a block whose size is a multiple of the alignment.
*/
void *mm_malloc(size_t size)
{
size_t asize; // 조정된 블록 사이즈
size_t extendsize; // 힙이 부족하면 늘려야 하는 양
char *bp;
// 이상한 요청 무시
if (size == 0)
return NULL;
// 넣을 데이터의 사이즈가 더블 워드보다 작으면,
// 할당할 블록의 크기를 강제로 키워준다
if (size <= DSIZE)
asize = 2 * DSIZE;
// 아니라면 8바이트 정렬만 맞춰준다
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
// 알맞는 가용 블록 찾기
if ((bp = find_fit(asize)) != NULL)
{
place(bp, asize);
return bp;
}
// 맞는 가용 블록이 없으면 힙 공간을 추가하고 블록 넣기
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}
static void *find_fit(size_t asize)
{
void *bp = heap_listp;
// 힙의 데이터가 시작되는 영역부터 시작해서 에필로그 블록까지 탐색
while (GET_SIZE(HDRP(bp)) > 0)
{
// 헤더를 봤더니 할당되어 있지 않고, 충분히 크다면
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
return bp; // 할당
bp = NEXT_BLKP(bp);
}
return NULL; // 맞는 블록이 없으면 NULL 반환
}
static void place(void *bp, size_t asize)
{
if ((GET_SIZE(HDRP(bp)) - asize) >= (2 * DSIZE))
{
PUT(bp + asize - DSIZE, PACK(asize, 1)); // 새 푸터에 정보 넣기
PUT(bp + asize - WSIZE, PACK(GET_SIZE(HDRP(bp)) - asize, 0)); // 새 헤더에 정보 넣기
PUT(FTRP(bp), PACK(GET_SIZE(HDRP(bp)) - asize, 0)); // 원래 푸터의 정보 갱신
PUT(HDRP(bp), PACK(asize, 1)); // 원래 헤더의 정보 갱신
}
else
{
PUT(HDRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
PUT(FTRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
}
}
/*
* mm_free - 헤더와 푸터는 그대로지만 가용인지 아닌지 상태만 바꿈
*/
void mm_free(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
서: 리스트에 있는 각 블록의 주소가 그 다음 블록의 주소보다 작도록 정렬한다. 이 경우, 블록을 해제하려면 적절한 이전 블록을 찾기 위해 선형 시간 검색이 필
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
// coalesce - 가용 블록들을 병합시키는 함수
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
// case 1 : 이전과 다음 블록이 모두 할당되어 있다. 병합 불가
if (prev_alloc && next_alloc)
{
return bp;
}
// case 2 : 다음 블록만 가용 블록. 다음 블록과 병합.
else if (prev_alloc && !next_alloc)
{
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0)); // 헤더에 기록된 size를 바꾼다
PUT(FTRP(bp), PACK(size, 0)); // 헤더에 기록된 size가 바뀌었으니 FTRP(bp)의 반환값도 size만큼 커진다
}
// case 3 : 이전 블록만 가용 블록. 이전 블록과 병합.
else if (!prev_alloc && next_alloc)
{
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0)); // 푸터에 기록된 size를 바꾼다
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 가용 블록의 헤더에 기록된 size를 바꾼다
bp = PREV_BLKP(bp);
}
// case 4 : 이전 블록과 다음 블록 모두 가용 블록. 모두 병합.
else
{
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 가용 블록의 헤더에 기록된 size를 바꾼다
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); // (bp에 적힌 size는 아직 바뀌지 않았으니 NEXT_BLKP가 원하는대로 작동)
bp = PREV_BLKP(bp);
}
return bp;
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
// 새로 할당할 size에 맞는 가용 블록 찾아서 할당
newptr = mm_malloc(size);
// size가 0이거나 음수이면 NULL 반환
if (newptr == NULL)
return NULL;
// copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
// 책과 repo 코드의 로직이 달라서 문제가 생긴다. 고쳐줘야 함.
// copy할 size를 oldptr에 역참조한 값에서 추출
copySize = GET_SIZE(HDRP(oldptr));
// 재할당하려는 블록의 크기가 기존 블록의 크기보다 작을 경우,
// 실제로 복사할 크기를 size로 제한
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}명시적 가용 리스트
0 : 준비
이거 만들어야 됨.
할당할 블록에도 pred와 succ이 들어갈 자리는 남겨둬야 한다.
내부 단편화가 일어나더라도 어쩔 수 없음.
안 그러면 payload가 8바이트 미만일 때 다른 가용 리스트 찾아서 헤매야됨.
따라서 연산 비용 올라감.
따라서 할당된 블럭이던 가용 블록이던 최소 블록 크기는 16바이트가 돼야 함.
LIFO가 먼저 나오니까 LIFO로 먼저 구현해보기.
고쳐야 할 함수들
1. extend_heap : 새로 할당되는 가용 블록에 이전 가용 리스트 포인터 추가, 이후 가용 리스트 포인터(NULL) 추가
2. mm_maloc : 최소 할당 사이즈를 3*DSIZE로 바꿔야 함
3. find_fit : 이전/이후 가용 리스트가 적힌 영역을 확인하는 식으로 바꿔야 함
4. place : 가용 블럭에 할당했으니까 가용 리스트에서 삭제해야됨
5. mm_free : 가용 블럭이 생겼으니까 가용 리스트에 추가해야됨
6. coalesce : 가용 블럭 병합할때마다 가용 리스트 편집해야됨
7. mm_realloc : 구현한 함수들을 그대로 사용하므로 딱히 고칠 필요 없을듯
1 : extend_heap
extend_heap이 무조건 큰 값을 늘리는게 아니라서
최소 블록 크기(16바이트)를 충족시키지 못할 가능성 있음.
가능성만 적어두고 일단 포인터를 넣어보자.
PUT(HDRP(bp) + WSIZE, PACK(where???, 0));넣어보려고 했는데 뭘 넣어야할지 모르겠음.
최초 상황에는 이전과 다음 포인터에 NULL 넣으면 되는건데
이미 앞쪽에 가용 블록들이 있을 땐 다음 포인터를 어떻게???
if문 하나 추가해야되나? 함수를 하나 만들어버려서 거기서 포인터들을 찾아주면 되나?
LIFO를 어떻게 할지 한참 생각하고 있었는데
옆 동기가 heap_listp를 이용하면 될 것 같다고 알려줌.
heap_listp를 가장 최근에 free된 블록의 포인터로 바꿔주면 된다고 함.
LIFO 설명이 살짝 알아듣기 힘들었는데,
가장 최근에 사용된 블록들이 아니라 가장 최근에 free된 블록이라고 알아들으면 될듯.
해야될 거 시각화 해봄. (이전과 다음이 bp가 아니라 NULL이어야 할듯)
PUT(HDRP(bp), PACK(size, 0)); // 가용 블록 헤더
PUT(HDRP(bp) + WSIZE, heap_listp); // 이전 가용 블록 포인터 : heap_listp
PUT(HDRP(bp) + WSIZE, NULL); // 다음 가용 블록 포인터 : NULL
PUT(FTRP(bp), PACK(size, 0)); // 가용 블록 푸터
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 새 에필로그 헤더
heap_listp = bp;이정도면 되나?
2 : mm_malloc
if (size <= 2 * DSIZE)
asize = 3 * DSIZE;최소 할당 크기만 바꿔줬다
3 : place
뭔가 이상함. heap_listp로 이전 가용 블럭을 가리키면 안될 것 같음.
쓰려면 쓸 수야 있겠지만, 초기화를 NULL로 따로 해줘야 함. 헷갈림.
첫 가용 블록을 만들 때 주소에 NULL이 들어가야 되기 때문.
따로 선언해주는게 편할듯?
처음부터 다시.
(re) 1 : extend_heap
static char *recent_free = NULL;이걸로 가장 최근에 free된 블록을 관리한다.
/* 가장 최근에 생긴 가용 블록이므로 다음 가용 블록 포인터는 NULL */
PUT(HDRP(bp), PACK(size, 0)); // 가용 블록 헤더
PUT(HDRP(bp) + WSIZE, recent_free); // 이전 가용 블록 포인터 : recent_free
PUT(HDRP(bp) + 2 * WSIZE, NULL); // 다음 가용 블록 포인터
PUT(FTRP(bp), PACK(size, 0)); // 가용 블록 푸터
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 새 에필로그 헤더
recent_free = bp;포인터를 8바이트라고 가정했다가 동기가 4바이트라는 사실을 일깨워주었다. 큰일날뻔.
2 : mm_malloc
// 넣을 데이터의 사이즈가 더블워드보다 작으면
// 할당할 블록의 크기를 강제로 키워준다
if (size <= DSIZE)
asize = 3 * DSIZE;
// 아니라면 8바이트 정렬만 맞춰준다
else
asize = DSIZE * ((size + 3 * DSIZE - 1) / DSIZE);맞는진 모르겠는데 일단 내 머리론 맞다.
나중에 틀리면 답지 코드랑 비교해봐야할듯.
3 : 매크로 정의
/* bp에 대해 pred와 succ가 적힌 곳의 주소를 구한다 */
#define PREP(bp) ((char *)(bp)) // 이거 그냥 그대로라 필요 없긴 한데 의미 드러나게 선언
#define NXTP(bp) ((char *)(bp) + WSIZE)
/* bp에 대해 이전/다음 가용 블록의 주소를 구한다 */
#define PREV_FREE(bp) (void *)(GET(PREP(bp)))
#define NEXT_FREE(bp) (void *)(GET(NXTP(bp)))주소에 가는 건 이미 있던 GET()으로 하면 될듯이라고 생각했는데
옆 동기가 GET()이 반환하는게 unsigned int라고 또 일깨워줌.
그냥 4개 다 선언 함.
4 : find_fit
static void *find_fit(size_t asize)
{
void *bp = recent_free;
// recent_free가 가리키는 블록부터 시작해서 NULL이 될 때까지 탐색
while (bp != NULL)
{
// 헤더를 봤더니 할당되어 있지 않고, 충분히 크다면
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
return bp; // 할당
bp = PREV_FREE(bp); // 이전 블록 계속 탐색
}
return NULL; // 맞는 블록이 없으면 NULL 반환
}5 : place
static void place(void *bp, size_t asize)
{
size_t osize = GET_SIZE(HDRP(bp));
if ((osize - asize) >= (3 * DSIZE))
{
// payload 담은 블록 헤더 푸터 설정
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
// 가용 블록 헤더 푸터 가용리스트 설정
PUT(HDRP(bp), PACK(osize - asize, 0));
PUT(FTRP(bp), PACK(osize - asize, 0));
PUT(PREP(bp), recent_free);
PUT(NXTP(bp), NULL);
recent_free = bp;
// 이전 가용 블록으로 찾아가서
// 현재 가용 블록을 다음 가용 블록으로 만들어야 함
PUT(NXTP(PREV_FREE(bp)), bp);
}
else
{
PUT(HDRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
PUT(FTRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
// 이전 가용 블록으로 찾아가서
// 현재 블록의 다음 가용 블록과 이어줘야 함
PUT(NXTP(PREV_FREE(bp)), NEXT_FREE(bp));
PUT(PREP(NEXT_FREE(bp)), PREV_FREE(bp));
}
}생각해보니 매크로로 하면 안될 것 같음.
PUT(NXTP(PREV_FREE(bp)), NEXT_FREE(bp));
PUT(PREP(NEXT_FREE(bp)), PREV_FREE(bp));이 부분에서 NXTP가 NULL이면 NEXT_FREE가 Segmentation 오류 낼듯.
다음 가용 블록 포인터가 NULL인지 아닌지 판별하는게 여기에서만 쓰이면 모르겠는데
coalesce에서 여러 번 쓰일 예정이라 함수로 안 묶는게 곤란.
매크로는 지우고 PREV_FREE()랑 NEXT_FREE() 함수 선언해야할듯.
6 : PREV_FREE, NEXT_FREE
char *PREV_FREE(char *bp)
{
if (GET(PREP(bp)) == NULL)
return NULL;
return (char *)(GET(PREP(bp)));
}
char *NEXT_FREE(char *bp)
{
if (GET(NXTP(bp)) == NULL)
return NULL;
return (char *)(GET(NXTP(bp)));
}5-2 : place
매크로 만들고 다시 place 봤더니 segmentation 오류가 해결되진 않을 것으로 보임.
PUT(NXTP(PREV_FREE(bp)), NEXT_FREE(bp));
PUT(PREP(NEXT_FREE(bp)), PREV_FREE(bp));PREV_FREE(bp)가 NULL로 반환되면 PUT이 오류 일으킴.
보호 구문 추가해줘야 함.
if (PREV_FREE(bp) != NULL)
PUT(NXTP(PREV_FREE(bp)), NEXT_FREE(bp));
if (NEXT_FREE(bp) != NULL)
PUT(PREP(NEXT_FREE(bp)), PREV_FREE(bp));이정도면 될듯.
7 : mm_free
void mm_free(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(PREP(bp), recent_free);
PUT(NXTP(bp), NULL);
recent_free = bp;
coalesce(bp);
}8 : coalesce
처음엔 싹 다 갈아엎어야하는 줄 알았는데
생각해보니까 의외로 그냥 잇고 이으면 되는 간단한 로직만 추가하면 됨.
좀 귀찮긴 할듯?
else if (prev_alloc && !next_alloc)
{
if (PREV_FREE(bp) != NULL)
PUT(NXTP(PREV_FREE(bp)), NEXT_FREE(bp));
if (NEXT_FREE(bp) != NULL)
PUT(PREP(NEXT_FREE(bp)), PREV_FREE(bp));
bp = NEXT_BLKP(bp);
if (PREV_FREE(bp) != NULL)
PUT(NXTP(PREV_FREE(bp)), NEXT_FREE(bp));
if (NEXT_FREE(bp) != NULL)
PUT(PREP(NEXT_FREE(bp)), PREV_FREE(bp));
bp = PREV_BLKP(bp);
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0)); // 헤더에 기록된 size를 바꾼다
PUT(FTRP(bp), PACK(size, 0)); // 헤더에 기록된 size가 바뀌었으니 FTRP(bp)의 반환값도 size만큼 커진다
}
// case 3 : 이전 블록만 가용 블록. 이전 블록과 병합.
else if (!prev_alloc && next_alloc)
{
if (PREV_FREE(bp) != NULL)
PUT(NXTP(PREV_FREE(bp)), NEXT_FREE(bp));
if (NEXT_FREE(bp) != NULL)
PUT(PREP(NEXT_FREE(bp)), PREV_FREE(bp));
bp = PREV_BLKP(bp);
if (PREV_FREE(bp) != NULL)
PUT(NXTP(PREV_FREE(bp)), NEXT_FREE(bp));
if (NEXT_FREE(bp) != NULL)
PUT(PREP(NEXT_FREE(bp)), PREV_FREE(bp));
bp = NEXT_BLKP(bp);
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0)); // 푸터에 기록된 size를 바꾼다
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 가용 블록의 헤더에 기록된 size를 바꾼다
bp = PREV_BLKP(bp);하다보니까 뭔가 이상함을 느낌. 함수 선언해야할듯?
9 : connect_free_list
// 가용 리스트에서 사라지는 노드의 양 옆 노드를 이어줌
void connect_free_list(char *bp)
{
if (PREV_FREE(bp) != NULL)
PUT(NXTP(PREV_FREE(bp)), NEXT_FREE(bp));
if (NEXT_FREE(bp) != NULL)
PUT(PREP(NEXT_FREE(bp)), PREV_FREE(bp));
}반복되는거 함수로 묶어줌
8-2 : coalesce
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
// case 1 : 이전과 다음 블록이 모두 할당되어 있다. 병합 불가
if (prev_alloc && next_alloc)
{
return bp;
}
// case 2 : 다음 블록만 가용 블록. 다음 블록과 병합.
else if (prev_alloc && !next_alloc)
{
connect_free_list(bp);
bp = NEXT_BLKP(bp);
connect_free_list(bp);
bp = PREV_BLKP(bp);
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0)); // 헤더에 기록된 size를 바꾼다
PUT(FTRP(bp), PACK(size, 0)); // 헤더에 기록된 size가 바뀌었으니 FTRP(bp)의 반환값도 size만큼 커진다
}
// case 3 : 이전 블록만 가용 블록. 이전 블록과 병합.
else if (!prev_alloc && next_alloc)
{
connect_free_list(bp);
bp = PREV_BLKP(bp);
connect_free_list(bp);
bp = NEXT_BLKP(bp);
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0)); // 푸터에 기록된 size를 바꾼다
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 가용 블록의 헤더에 기록된 size를 바꾼다
bp = PREV_BLKP(bp);
}
// case 4 : 이전 블록과 다음 블록 모두 가용 블록. 모두 병합.
else
{
connect_free_list(bp);
bp = NEXT_BLKP(bp);
connect_free_list(bp);
bp = PREV_BLKP(bp);
bp = PREV_BLKP(bp);
connect_free_list(bp);
bp = NEXT_BLKP(bp);
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 가용 블록의 헤더에 기록된 size를 바꾼다
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); // (bp에 적힌 size는 아직 바뀌지 않았으니 NEXT_BLKP가 원하는대로 작동)
bp = PREV_BLKP(bp);
}
return bp;
}다 만들긴 했는데 딱 봐도 오류가 어마어마하게 많이 나올 것 같음.
디버깅은 내일 하고 일단 routine 하자.
10 : NULL 오류
mm.c:99:23: warning: comparison between pointer and integer
99 | if (GET(NXTP(bp)) == NULL)근데 이것만 고치고. NULL이 아니라 다 0으로 바꿔줘야 할듯.
11 : 포인터 삽입 오류
mm.c:110:9: note: in expansion of macro ‘PUT’
110 | PUT(PREP(NEXT_FREE(bp)), PREV_FREE(bp));
| ^~~
mm.c: In function ‘extend_heap’:
mm.c:33:43: warning: assignment to ‘unsigned int’ from ‘char *’ makes integer from pointer without a cast [-Wint-conversion]
33 | #define PUT(p, val) (*(unsigned int *)(p) = (val))
| ^PUT에 아무 생각 없이 포인터를 집어넣었더니 안된다고 오류냄.
일단 내일 하자.
근데 이렇게 (불가피했지만) 실행 테스트도 없이 죽 쓰다보니니까
쾌락없는 책임을 즐기는 느낌이었다.
이제 내일 버그가 곱절로 돌아올테지만.
⚔️ 백준
📌 2504 괄호의 값
문자열 여러 번 순회하면서 합쳐지는 괄호들 계산하는 원시적 로직 생각해봤는데
너무 귀찮을 것 같음.
왜인지 모르겠지만 스택으로만 할 수 있을 것 같아서
천천히 손으로 그려가며 슈도 코드를 작성함.
스택으로 하려니까 불필요하게 복잡한거 같아서
어차피 문자 30개까지밖에 없으니까 순회로 해도 될듯
유효한 괄호열인지 확인하는 과정에서 연산까지 같이 하라는게 문제의 의도인듯?
순회 말고 스택으로 다시 돌아가자.
# 유효한 괄호열인지 확인
for i in range(len(brackets)):
brkt = brackets[i]
# 괄호 연달아 나오면 숫자로 변환
if stack[-1] == '(' and brkt == ')':
stack.pop()
stack.append(2)
continue
elif stack[-1] == '[' and brkt == ']':
stack.pop()
stack.append(3)
continue
# 앞에서 첫번째로 나오는 괄호가 짝이 맞다면
# 안에 있는 숫자 다 더하고 연산
if brkt == ')':
for j in range(len(stack)-1,-1,-1):
if brackets[j] == '(':
sum(brackets[j+1:i])
elif brackets[j] == '[':
break
if brkt == ']':
for j in range(len(stack)-1,-1,-1):
if brackets[j] == ']':
sum(brackets[j+1:i])
for _ in range(i-j): brackets.pop()
elif brackets[j] == '(':
break아 근데 아무리 그래도 이건 좀...
그냥 검사만 하고 문자열 순회하는게 편할듯
-> 갈팡질팡하다 결국 스택이 답이라는걸 깨달았다. 새벽이라 정신이 오락가락했었던듯?
