[자료구조 및 프로그래밍] 6. 메모리 관리 시스템

지난 글에서는 연결리스트를 이용해 스택과 큐를 구현하였다.

이번 글에서는 연결리스트를 이용하는 과정에서 new(), free() 기능을 사용했는데, 이 기능을 직접 구현해본다.

---

사실 직접 구현이라고 해서 나도 처음엔 메모리를 직접 다루는 거창한 걸 기대했는데, 그런건 아니다.

그냥 배열을 이용해서 전체 memory pool 을 세팅해두고, 그 세팅된 pool 내 메모리를 주고 받고 하는 방식이다.

 

메모리 풀은 연결리스트 노드의 데이터 형태로 배열에 세팅해두고, 이를 스택처럼 활용하여 메모리를 주고 받는다.

메모리 풀은 이런 구조로 존재한다.

만약 new 함수로 메모리 공간을 요청하면 top이 가리키는 노드를 제공해준다.

제공을 마친 모습이다.

제공된 메모리는 연결리스트에서 자유롭게 Item 부분에도 값을 할당하고, Link 부분에도 값을 할당했을 것이다.

 

여기에서 또 새로운 값을 요청받았다고 해보자.

이렇게 top 이 가리키는 노드를 또 할당해주고, 할당된 노드들끼리는 알아서 연결관계를 막 생성한다.

 

이번엔 노드를 반환(free)해보자.

노드를 반환하게 되면, 반환된 노드는 새로운 top이 된다.

한번 data1 이 들어있는 노드를 반환해본 결과를 그려보면 아래와 같이 된다.

data1 을 지우고 그런건 구현하기 나름이겠다.

이제 이를 코드로 구현해보자.

 

처음에 배열에 linked list 노드 배열을 선언해주고, 각 노드는 다음 인덱스의 노드를 가리키도록 초기화한다.

배열로 구현되어 있기 때문에, 연결할 배열을 인덱스로 접근하면 된다.

 

이번 글에서는 직접 C언어로 구현을 해본다.

#include <cstdio>

struct node {
    int item;
    struct node * link;
};
const int NODE_SIZE = 5;
struct node node_pool[NODE_SIZE];

int main() {
    for (int i = 0; i < NODE_SIZE-1; i++) {
        node_pool[i].link = node_pool + sizeof(struct node)*(i+1);
    }

    node_pool[NODE_SIZE-1].link = NULL;

    printf("%d\n", sizeof(struct node));
    for (int i = 0; i < NODE_SIZE; i++) {
        printf("%p\n", node_pool[i].link);
    }
    return 0;
}

16바이트씩 순차적으로 메모리 주소가 link 에 저장되었다.

마지막 노드는 Link 가 null 이다.

 

이제 메모리 pool 에서 메모리를 제공하는 new_node() 를 구현해보자.

위와 같이 간단하게 구현된다.

만약 모든 메모리의 할당이 끝났다면 null 을 반환한다.

 

이제 메모리 반환도 구현해보자.

더 간단하게 구현된다.

 

이제 연결리스트에서 메모리 풀을 사용하여 데이터를 삽입하고 생성하는 과정을 살펴보는 것으로 마무리한다.

#include <cstdio>

struct node {
    int item;
    struct node * link;
};

const int NODE_SIZE = 5;
struct node node_pool[NODE_SIZE];
struct node * memory_top = node_pool;

void print_all_memory_pool() {
    for (int i = 0; i < NODE_SIZE; i++) {
        printf("%p %p\n", node_pool+i, (node_pool+i)->link);
    }
}

struct node * new_node() {
    struct node* p = memory_top;
    if (p == NULL) {
        return NULL;
    }
    memory_top = p->link;
    return p;
}

void free_node(struct node* _node) {
    _node->link = memory_top;
    memory_top = _node;
}

void memory_pool_init() {
    for (int i = 0; i < NODE_SIZE-1; i++) {
        node_pool[i].link = &node_pool[i+1];
    }

    node_pool[NODE_SIZE-1].link = NULL;
    print_all_memory_pool();
}

////////////////////////////////////////////////////////

struct node * head = NULL;

void add(int x) {
    struct node* p = new_node();
    if (p == NULL) {
        printf("overflow!\n");
        return;
    }
    p->item = x;
    p->link = head;
    printf("add %d to %p, and next link is %p\n", x, p, p->link);
    head = p;
    printf("added!\n");
}

void remove(int x) {
    struct node* prev_check = NULL;
    struct node* now_check = head;
    while (now_check != NULL) {
        if (now_check->item == x) {
            if (prev_check != NULL) {
                prev_check->link = now_check->link;
            } else {
                prev_check = now_check;
                now_check = now_check->link;
            }
            free_node(now_check);
            printf("delete node has %d\n", x);
            return;
        } else {
            prev_check = now_check;
            now_check = now_check->link;

        }
    }
    printf("no node has %d\n", x);
}

void print_all() {
    struct node * p = head;
    while (p != NULL) {
        printf("%p %d\n",p, p->item);
        p = p->link;
    }
}

int main() {
    memory_pool_init();

    add(1);
    print_all();
    print_all_memory_pool();
    printf("\n");

    add(2);
    print_all();
    add(3);
    print_all();
    add(4);
    print_all();
    add(5);
    print_all();

    printf("overflow\n");
    add(6); // 오류가 나야함.
    print_all();

    remove(1);
    print_all();

    remove(3);
    print_all();

    return 0;
}