#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>

#include <string.h>


#define STRING_SIZE 512

#define STRING_LIST_SIZE 256


typedef char String[STRING_SIZE];



void * str_list[STRING_LIST_SIZE];

int idx_new, idx_del;



int str_init(void) {

idx_new = 0, idx_del = STRING_LIST_SIZE;

return 0;

}

int str_new(void) {

if (idx_del == STRING_LIST_SIZE)

return idx_new++;

return (((String **)str_list)[idx_del++] - (String *)str_list) / sizeof(void*);

}

String * str_get(int idx) {

return (String *)str_list[idx];

}

int str_del(int idx) {

if (idx == idx_new-1)

idx_new--;

else

((String **)str_list)[--idx_del] = str_get(idx);

return 0;

}


int main(void) {

int i;

for (int j = 0; j < 1000000; j++) {

for (i = 0; i < 100; i++)

str_new();

for (i = 0; i < 100; i++)

str_del(i);

}


return 0;

}


코드가 좀 더럽긴 한데 일단 목적은 메모리를 미리 할당해놓고 필요한 순간이 생기면 미리 할당된 메모리 블럭의 일부를 가져가는 거임. 그래서 메모리 풀인데 구현방식이 조금 다름. str_list는 void *를 담는 배열이고 왜 그런지는 나중에 설명함. 처음으로 str_new를 호출하면 미리 할당된 메모리 블럭을 반환하는데 포인터가 아니라 인덱스로 반환함. 이 값은 idx_new로 기록되어 있고 중간에 삭제가 이루어지지 않는 한 선형적으로 증가함. 그리고 중간에 삭제가 되는 과정인데 str_del에 인덱스 값을 넣어서 삭제하고 함수 내부에서는 str_list의 뒤쪽부터 포인터를 기록함. 이 포인터는 str_get을 이용해서 얻어낸 값인데 인덱스에 대응하는 포인터 테이블의 주소임. 한번 삭제가 이루어졌다면 str_new에서 흐름이 좀 바뀌는데 idx_del의 값이 STRING_LIST_SIZE보다 줄어들었으므로 제거된(지금은 사용되지 않는 공간) 인덱스를 받아오게 됨. 이 과정에서 타입 변환이 조금 복잡하게 일어나는데 str_list를 String **로 변환하고 idx_del로 참조하면 String에 대한 포인터가 되니까 이 값에 str_list의 주소값을 뺌. 이 값은 두 주소 사이의 거리이기 때문에 인덱스와 1대1 대응이 되지 않기 때문에 포인터의 크기로 나눠주면 몇번째 인덱스가 제거되었는지 알 수 있게 됨. 이 값을 반환하면 다시 재사용 할 수 있음.

메모리 블럭을 미리 할당하는 것은 그렇다 쳐도 블럭이 삭제되었다는 정보를 어디다 기록하는지가 문제인데 버퍼를 새로 만드는 대신 메모리 블럭에 대한 포인터 배열의 마지막부터 중간에 삭제된 메모리 블럭의 주소값을 저장한다는 것이 일반적인 메모리 풀과는 다른 구현이겠지만(여기서는 인덱스 값을 저장) 라이브러리 호출 없이 독자적으로 빠르게 할당과 소멸을 하므로 시간복잡도는 O(1)임.

근데 문제는 포인터 테이블의 유효성 검사인데 단순히 블럭이 사용되고 있으면 NULL이 아니고 사용되고 있지 않다면 NULL인데 그렇다면 삭제가 되어서 뒤쪽에 기록된 인덱스 값들에 대한 검증은 어떻게 하냐고? idx_new가 그런 역할도 동시에 하는게 새로운 블럭 할당은 순차적으로만 이루어지고 이 값을 넘어서 접근하는 인덱스는 전부 유효하지 않은 것으로 판단함.

최악의 경우에 사용되지 않은 메모리 공간이 모두 없어져서 사용되고 있는 공간이 절반, 소멸되어 기록된 공간이 절반씩 포인터 테이블에 저장되어 있다면 어떻게 될까? 이 부분은 아직까지 해결하지 못했음. 그나마 해결방법이라면 미리 준비해둔 메모리 공간이 전부 소진되지 않도록 주의를 기울이는 것인데 좋은 해결방법이 있다면 댓글 달아주길 바람.