24.02.17 묵시적 리스트, 백준, C++

24.02.17 묵시적 리스트, 백준, C++

묵시적 리스트 구현

• 모든 할당기는 블록 경계를 구분하고, 할당된 블록과 가용블록을 구분하는 데이터 구조를 필요로 한다.
• 일반적인 방법으로는 추가적으로 1 블록을 사용해 블록 앞에 블록의 크기를 저장하는 방법이 있다.
• 이때 추가적으로 사용되는 1워드를 헤더라고 한다.
• 헤더는 블록 크기와 블록이 할당 되었는지, 혹은 가용상태인지를 인코딩한다.
• 데이터 이후에 사용되지 않은 패딩이 따라올 수도 있는데, 이들의 가변적이다.
  • 외부 단편화를 극복하기 위한 할당기의 전략일 수도, 정렬 요구 사항일수도 있다.
• 특별한 마지막 블록(1/0)이 필요하다. 에필로그 헤더라고 부른다.
  • 마지막 노드를 식별하고 리스트 무결성을 유지하는데 중요한 역할을 한다.
  • 리스트 순회 및 특수 기능 구현에도 활용할 수 있다.

할당할 블록 결정하기

• first fit
  • 처음부터 검색을 시작해서 맨 처음 크기가 맞는 블록을 선택하는 방법이다.
• next fit
  • 이전에 검색이 종료된 위치에서 검색을 시작한다는 점이 다르다
• best fit
  • 리스트를 검색하여 가장 근접한 크기의 블록을 선택하는 방법

가용블록의 분할

• 할당기가 할당할 가용블록을 찾은 후 가용블록의 어느정도를 할당할지에 대해 결정해야 한다.

가용블록 통합하기

• 결합 과정을 통해 가용블록을 통합해서 오류 단편화를 극복한다.

경계태그

• 반환하려는 블록을 현재 블록이라고 할 때 다음 가용블록을 연결하는 것은 쉽고 또한 효율적이다.
• 그러나 이전 가용블록을 연결할 수 있는 방법이 없다. 이전 가용블록을 연결하기 위해 경계태그를 사용한다. 블록 끝에 푸터를 추가한다. 푸터는 헤더를 복사한 것이다ㅣ

묵시적 가용 리스트 장점

• 단순함

묵시적 가용 리스트 단점

• 가용리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용블록 수에 비례한다는 것이다.
• 메모리 사용량은 할당정책에 따라 다르다.

/*
 * 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.
 * 이 순진한 접근 방식에서는 단순히 brk 포인터를 증가시켜 블록을 할당합니다.
 * 블록은 순수한 페이로드입니다.
 * 헤더나 푸터가 없습니다.
 * 블록은 합쳐지거나 재사용되지 않습니다.
 * 재할당은 mm_malloc과 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>
//explicit
#include<sys/mman.h>
#include<errno.h>

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

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "호둘치",
    /* First member's full name */
    "정종문",
    /* First member's email address */
    "whdans4005@naver.com",
    /* Second member's full name (leave blank if none) */
    "백강민, 연선애",
    /* Second member's email address (leave blank if none) */
    "__@naver.com"
    };

/* 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)))

#define WSIZE 4 // 워드 = 헤더 = 풋터 사이즈(bytes)
#define DSIZE 8 // 더블워드 사이즈(bytes)
#define CHUNKSIZE (1<<6) // heap을 이정도 늘린다(bytes)

#define MAX(x, y) ((x) > (y)? (x):(y))
// pack a size and allocated bit into a word 
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p)     (*(unsigned int *)(p)) //p가 가리키는 놈의 값을 가져온다
#define PUT(p,val) (*(unsigned int *)(p) = (val)) //p가 가리키는 포인터에 val을 넣는다
#define GET_SIZE(p)  (GET(p) & ~0x7) // ~0x00000111 -> 0x11111000(얘와 and연산하면 size나옴)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) //헤더+데이터+풋터 -(헤더+풋터)
// Given block ptr bp, compute address of next and previous blocks
// 현재 bp에서 WSIZE를 빼서 header를 가리키게 하고, header에서 get size를 한다.
// 그럼 현재 블록 크기를 return하고(헤더+데이터+풋터), 그걸 현재 bp에 더하면 next_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* coalesce(void* bp);
static void* extend_heap(size_t words);
static void* find_fit(size_t asize);
static void place(void *bp, size_t asize);

static void* heap_listp;

/*
 * mm_init - initialize the malloc package.
 */
// 할당기를 초기화 성공하면 0, 실패하면 -1 리턴
int mm_init(void)
{
    //Create the initial empty heap
    if((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1) 
        return -1;                              // 불러올 수 없으면 -1 return  
    PUT(heap_listp, 0);                         // Alignment padding
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE,1)); // P.H 8(크기)/1(할당됨)
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE,1)); // P.F 8/1
    PUT(heap_listp + (3*WSIZE), PACK(0,1));     // E.H(헤더로만 구성) 0/1
    heap_listp += (2*WSIZE); // 처음에 항상 prolouge 사이를 가리킴
    // 나중에 find_fit 함수에서 find할 때 사용됨
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL) //word가 몇개인지 확인해서 넣으려고
        return -1;
    return 0;
}
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    // Allocate an even number of words to maintain alignment
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1) //size를 불러올 수 없으면
        return NULL;

    // Initialize free block header/footer and the epilogue header
    PUT(HDRP(bp), PACK(size,0)); // Free block header(bp에서 -word로 header자리 가서 에필로그 자리에 넣게 된다.)
    PUT(FTRP(bp), PACK(size,0)); // Free block footer
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0,1)); // New epilogue header

    // Coalesce(연결후 합침) if the previous block was free
    return coalesce(bp);
}
static void* find_fit(size_t asize)
{
    void *bp;

        for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
        {
            if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
                return bp;
        }
        return NULL; // No fit
}

static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));

    if ((csize - asize) >= (2*DSIZE))
    {
        PUT(HDRP(bp), PACK(asize,1));//현재 크기를 헤더에 집어넣고
        PUT(FTRP(bp), PACK(asize,1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize-asize,0));
        PUT(FTRP(bp), PACK(csize-asize,0));
    }
    else
    {
        PUT(HDRP(bp), PACK(csize,1));
        PUT(FTRP(bp), PACK(csize,1));
    }
}
/*
 * 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;

    // Ignore spurious requests - size가 0이면 할당x
    if(size <= 0) // == 대신 <=
        return NULL;

    // Adjust block size to include overhead and alignment reqs.
    if(size <= DSIZE) // size가 8byte보다 작다면,
        asize = 2*DSIZE; // 최소블록조건인 16byte로 맞춤
    else              // size가 8byte보다 크다면
        asize = DSIZE * ((size+(DSIZE)+(DSIZE-1)) / DSIZE);

    //Search the free list for a fit - 적절한 가용(free)블록을 가용리스트에서 검색
    if((bp = find_fit(asize))!=NULL)
    {
        place(bp,asize); //가능하면 초과부분 분할
        return bp;
    }

    //No fit found -> Get more memory and place the block
    extendsize = MAX(asize,CHUNKSIZE);
    if((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    place(bp,asize);
    return bp;
}
/*
 * mm_free - Freeing a block does nothing.
 */
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);    
}
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));

    if (prev_alloc && next_alloc)
        return bp;
    else if(prev_alloc && !next_alloc)
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size,0));
        PUT(FTRP(bp), PACK(size,0));//header가 바뀌었으니까 size도 바뀐다!
    }
    else if(!prev_alloc && next_alloc)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
        bp = PREV_BLKP(bp); //bp를 prev로 옮겨줌
    }
    else
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size,0));
        bp = PREV_BLKP(bp); //bp를 prev로 옮겨줌
    }
    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;

    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    // copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    copySize = GET_SIZE(HDRP(oldptr));
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

백준

1436 영화감독 숌

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int input,check_num = 0;
	cin >> input;
	int num = 666;
	
	while (true)
	{
		if (to_string(num).find("666") != string::npos)
			++check_num;
		if (check_num == input)
			break;
		++num;
	}
	cout << num;
	return 0;
}

• 재희님이 추천해서 풀었던 문제.
• 중간에 약간의 함정이 있다 5666 다음의 666이 들어가는 숫자는 6660인 것. 그리고 숫자는 6661→6662→ … 이렇게 증가한다.
• string.find 함수를 잘 사용한다면 어렵지 않게 풀 수 있는 문제가 아닐까 생각한다.

25206 너의 평점은

#include <bits/stdc++.h>
using namespace std;

constexpr unsigned int Hash(const char* str) 
{
	return str[0] ? static_cast<unsigned int>(str[0]) + 0xEDB8832Full * Hash(str + 1) : 8603;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	char grade[50];
	string subject;
	float my_grade,sum_grade=0,major_GPA=0;
	for (int i = 0; i < 20; ++i)
	{
		cin >> subject >> my_grade >> grade;
		switch (Hash(grade))
		{
		case Hash("A+"):
			sum_grade += my_grade;
			major_GPA += my_grade * 4.5;
			break;
		case Hash("A0"):
			sum_grade += my_grade;
			major_GPA += my_grade * 4.0;
			break;
		case Hash("B+"):
			sum_grade += my_grade;
			major_GPA += my_grade * 3.5;
			break;
		case Hash("B0"):
			sum_grade += my_grade;
			major_GPA += my_grade * 3.0;
			break;
		case Hash("C+"):
			sum_grade += my_grade;
			major_GPA += my_grade * 2.5;
			break;
		case Hash("C0"):
			sum_grade += my_grade;
			major_GPA += my_grade * 2.0;
			break;
		case Hash("D+"):
			sum_grade += my_grade;
			major_GPA += my_grade * 1.5;
			break;
		case Hash("D0"):
			sum_grade += my_grade;
			major_GPA += my_grade * 1.0;
			break;
		case Hash("F"):
			sum_grade += my_grade;
			major_GPA += my_grade * 0.0;
			break;
		case Hash("P"):
			break;
		default:
			break;
		}
	}
	
	cout << major_GPA/sum_grade;
	return 0;
}

• switch 함수와 hash, constexpr 키워드를 사용해서 풀었다.
• TheJungle에게 코드리뷰를 부탁했는데 조금 더 짧게 푸는 코드를 소개시켜줬다.

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	char grade[50];
	string subject;
	float my_grade,sum_grade=0,major_GPA=0;
	string grades[9] = { "A+", "A0", "B+", "B0", "C+", "C0", "D+", "D0", "F" };
	float number[9] = { 4.5, 4.0, 3.5, 3.0, 2.5, 2.0, 1.5, 1.0, 0};
	
	for (int i = 0; i < 20; i++) 
	{
		cin >> subject >> my_grade >> grade;
		for (int idx = 0; idx < 9; idx++) 
		{
			if ("P" == grade)
				continue;
			if (grades[idx] == grade) 
			{
				sum_grade += my_grade;
				major_GPA += my_grade * number[idx];
				continue;
			} 
		}
	}
	cout << major_GPA/sum_grade;
	return 0;
}

• 리스트를 활용해서 하는게 되게 신기했고, 코드도 많이 짧아질 수 있었다.
• 하지만 들어가는것이 많거나 그러면 2중 for문의 문제가 생길 수도 있지 않을까 생각을 해 보았다.

C++

string::find()

• string 클래스의 멤버함수로서, str.find(”찾는 문자”)로 사용한다.
• 반환값은 찾는 문자의 첫 번째 인덱스값을 반환한다.
• 찾는 문자가 없을 경우에 string::npos를 리턴한다.
  • npos는 no position으로 쓰레기값이 나온다.

#include <iostream>
#include <string>

using namespace std;

String str = "Hello World!";

int main() 
{
	if (str.find("Hello") != string::npos) 
	{
    	cout << "찾는 문자가 존재합니다";
		  int index = str.find("Hello");   //해당 문자의 시작 인덱스 반환
	}
}

constexpr

• C++11에 constexpr 이라는 키워드가 추가되었다.
• constexpr은 변수 또는 함수의 값을 컴파일 시점에 도출하여 상수화 시켜주는 아주 강력한 기능이다.
• 컴파일 시점에 상수로 처리되기 때문에 switch case 문에서도 상수로 취급된다.

constexpr을 함수에 사용할 때 제약사항

• constexpr을 사용하는 데 있어서 몇 가지 제약사항이 있다.
  • 반환값이 무조건 Literal Type이어야 한다.
  • virtual로 재정의된 함수가 아니어야 한다.
  • 재귀 함수로 사용될 수 있다.
  • 함수에 constexpr을 붙일 경우 inline을 암시한다.
  • C++11 에서는 함수 본문에 지역변수를 둘 수 없고, 하나의 return 구문만 있어야 했다.
  • 위 제약은 C++14에서 사라졌다.

• 구현 예시
  • 25206 너의 평점은

  #include <bits/stdc++.h>
  using namespace std;
  
  constexpr unsigned int Hash(const char* str) 
  {
  	return str[0] ? static_cast<unsigned int>(str[0]) + 0xEDB8832Full * Hash(str + 1) : 8603;
  }
  
  int main()
  {
  	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  	char grade[50];
  	string subject;
  	float my_grade,sum_grade=0,major_GPA=0;
  	for (int i = 0; i < 20; ++i)
  	{
  		cin >> subject >> my_grade >> grade;
  		switch (Hash(grade))
  		{
  		case Hash("A+"):
  			sum_grade += my_grade;
  			major_GPA += my_grade * 4.5;
  			break;
  		case Hash("A0"):
  			sum_grade += my_grade;
  			major_GPA += my_grade * 4.0;
  			break;
  		case Hash("B+"):
  			sum_grade += my_grade;
  			major_GPA += my_grade * 3.5;
  			break;
  		case Hash("B0"):
  			sum_grade += my_grade;
  			major_GPA += my_grade * 3.0;
  			break;
  		case Hash("C+"):
  			sum_grade += my_grade;
  			major_GPA += my_grade * 2.5;
  			break;
  		case Hash("C0"):
  			sum_grade += my_grade;
  			major_GPA += my_grade * 2.0;
  			break;
  		case Hash("D+"):
  			sum_grade += my_grade;
  			major_GPA += my_grade * 1.5;
  			break;
  		case Hash("D0"):
  			sum_grade += my_grade;
  			major_GPA += my_grade * 1.0;
  			break;
  		case Hash("F"):
  			sum_grade += my_grade;
  			major_GPA += my_grade * 0.0;
  			break;
  		case Hash("P"):
  			break;
  		default:
  			break;
  		}
  	}
  	
  	cout << major_GPA/sum_grade;
  	return 0;
  }