백준 3217번 malloc: C언어 풀이

백준 3217번 malloc 문제의 C 언어 풀이 해설입니다.
연결 리스트와 유사하게 동작하면서도 주소를 통한 빠른 접근이 가능하도록 배열을 이용해 메모리를 구현하는 방법을 소개합니다.
변수명과 할당된 주소를 시간복잡도 O(1)에 찾을 수 있도록 해시 테이블을 구현하여 풀이하였습니다.

전략

메모리 구성

메모리를 연결 리스트와 유사한 배열로 구성한다.

이전 철도 공사 문제 풀이 와 유사한 아이디어이다.
연결 리스트 대신 이전, 다음 원소의 인덱스를 갖는 하나의 구조체를 배열에 넣어주면 배열이 가지는 빠른 접근 속도와 연결 리스트의 연결성, 두마리 토끼를 잡을 수 있다.

여기서는 구조체를 같은 속성을 갖는 메모리의 구간으로 정의했다.

각 구간은 할당 여부(FREE/ALLOCATED), 구간의 크기, 이전 구간의 인덱스로 구성했다.
다음 구간의 인덱스는 구간의 크기를 더하는 것으로 간단히 구할 수 있으므로 저장하지 않는다.

변수 이름 인덱싱

변수의 이름이 항상 소문자 4자리 알파벳으로 구성되어있음을 활용하면 26진법 해시 함수를 작성 가능하다.
이렇게 만든 간단한 해시 테이블을 사용해 변수가 저장된 메모리 주소를 O(1)에 찾을 수 있다.

개별 명령 구현

malloc(size)

메모리를 처음부터 순회하며 적절한 메모리 구간을 찾아야 한다.
구간이 FREE 이면서 구간 크기가 할당할 크기보다 크거나 같은 구간을 찾으면 된다.

남는(FREE) 구간의 크기가 할당할 크기보다 클 경우, 남는 구간이 생긴다.
malloc으로 새로 할당된 구간, 할당되고 남은 FREE 구간 이렇게 둘로 나누어준다.

크기가 같다면 간단히 구간의 할당 상태, FREE를 ALLOCATED로 변경만 해주면 된다.

free(var)

var이 저장된 메모리 구간을 FREE로 바꿔주면 된다.
변수명 var가 있는 주소를 저장하는 해시 테이블이 있으므로, 해당 주소를 찾아 FREE로 바꿔주면 된다.

한 가지 주의할 점은, 구간 앞/뒤에 FREE인 구간이 있는지 확인해야 된다는 점이다.
FREE인 구간이 있다면, 구간을 합쳐줘야 한다.

print(var)

변수 이름과 주소를 저장하는 해시 맵을 만들었으므로, 저장된 값을 출력하기만 하면 된다.

코드

#include <stdio.h>

// 100000 + NULL
#define MEMORY_SIZE 100001
#define MEMORY_NULL 0
#define MEMORY_START 1
#define MEMORY_END 100001

// Operation string buffer
#define MAX_BUFFER_SIZE 30

// 26^4 lower case 4 letter vaiable names
#define VAR_ARRAY_SIZE 456976

enum mem_status
{
    FREE = 0,
    ALLOCATED = 1
};

// Linked list like memory segments
struct mem_segment
{
    enum mem_status status;
    int size;
    int prev;
};

// Parse operation based on 5th char of operation string
// Assumes that all var_names are 4 letter lower case
enum operation_type
{
    OP_MALLOC = '=',   // varn=malloc(size)
    OP_FREE = '(',     // free(varn)
    OP_PRINT = 't'     // print(varn)
};


int index_of_var(const char *var_name);
void operation_malloc(char *buffer, struct mem_segment *memory, int *var_address_lookup);
void operation_free(char *buffer, struct mem_segment *memory, int *var_address_lookup);
void operation_print(char *buffer, int *var_address_lookup);

int main(void)
{
    // Lookup variable's address in O(1), with indexed varname
    int var_address_lookup[VAR_ARRAY_SIZE] = {MEMORY_NULL,};

    // Initialize memory
    struct mem_segment memory[MEMORY_SIZE];
    memory[MEMORY_START].status = FREE;
    memory[MEMORY_START].size = MEMORY_SIZE - 1;
    memory[MEMORY_START].prev = MEMORY_NULL;

    int num_operations;
    scanf("%d\n", &num_operations);

    for (int i = 0; i < num_operations; i++)
    {
        // Read operation
        char buffer[MAX_BUFFER_SIZE];
        fgets(buffer, sizeof(buffer), stdin);

        // Parse operation based on 5th char
        enum operation_type op_type = buffer[4];       
        switch (op_type)
        {
            case OP_MALLOC:
                operation_malloc(buffer, memory, var_address_lookup);
                break;
            case OP_FREE:
                operation_free(buffer, memory, var_address_lookup);
                break;
            case OP_PRINT:
                operation_print(buffer, var_address_lookup);
                break;
        }
    }
}

// Converts 4 letter lower case variable name to an integer, making an index to an array
int index_of_var(const char var_name[])
{
    int res = 0;
    for (int i = 0 ; i < 4; i++)
    {
        res = res * 26 + (var_name[i] - 'a');
    }
    return res;
}

void operation_malloc(char *buffer, struct mem_segment *memory, int *var_address_lookup)
{
    char var_name[5];
    int var_size;
    sscanf(buffer, "%4s=malloc(%d);\n", var_name, &var_size);

    // Default = NULL
    int var_addr = MEMORY_NULL;

    for (int current_addr = MEMORY_START; current_addr != MEMORY_END; current_addr += memory[current_addr].size)
    {
        // Find first free segment with enough size
        if (memory[current_addr].status == FREE && memory[current_addr].size >= var_size)
        {
            // Allocation
            var_addr = current_addr;
            memory[var_addr].status = ALLOCATED;

            // Leftover memory makes current segment into two
            int next = current_addr + memory[current_addr].size;
            int memory_leftover = memory[current_addr].size - var_size;
            if (memory_leftover != 0)
            {
                // Allocated segment
                memory[var_addr].size = var_size;

                // Remaining free segment
                int leftover_segment = var_addr + var_size;
                memory[leftover_segment].status = FREE;
                memory[leftover_segment].size = memory_leftover;
                memory[leftover_segment].prev = var_addr;

                // Link with next segment
                if (next != MEMORY_END)
                {
                    memory[next].prev = leftover_segment;
                }
            }
            break;
        }
    }
    // Record result
    var_address_lookup[index_of_var(var_name)] = var_addr;
}

void operation_free(char *buffer, struct mem_segment *memory, int *var_address_lookup)
{
    char var_name[5];
    sscanf(buffer, "free(%4s);\n", var_name);

    int var_index = index_of_var(var_name);
    int var_addr = var_address_lookup[var_index];

    // If variable is not allocated, skip
    if (var_addr == MEMORY_NULL)
    {
        return;
    }

    // Free memory
    memory[var_addr].status = FREE;
    var_address_lookup[var_index] = MEMORY_NULL;

    int prev = memory[var_addr].prev;
    int next = var_addr + memory[var_addr].size;

    // Check for previous segment, merge segments if it's also free
    if (prev != MEMORY_NULL && memory[prev].status == FREE)
    {
        // Merge sizes
        memory[prev].size += memory[var_addr].size;

        // Delete current segment
        memory[var_addr].prev = MEMORY_NULL;
        memory[var_addr].size = 0;
        var_addr = prev;

        // Link next segment to previous
        if (next != MEMORY_END)
        {
            memory[next].prev = var_addr;
        }
    }

    // Check for next segment, merge segments it it's also free
    if (next != MEMORY_END && memory[next].status == FREE)
    {
        // Merge sizes
        memory[var_addr].size += memory[next].size;

        // Delete next segment
        int next_next = next + memory[next].size;
        memory[next].prev = MEMORY_NULL;
        memory[next].size = 0;

        // Link next next segment to current
        if (next_next != MEMORY_END)
        {
            memory[next_next].prev = var_addr;
        }
    }
}

void operation_print(char *buffer, int *var_address_lookup)
{
    char var_name[5];
    sscanf(buffer, "print(%4s);\n", var_name);
    printf("%d\n", var_address_lookup[index_of_var(var_name)]);
}