42 과제 get_next_line에 대한 스포일러를 포함하고 있습니다.
아직 get_next_line 과제를 완료하지 않으셨다면, 살포시 뒤로가기 눌러주세요!
get_next_line 프로젝트를 위한 가이드가 아닙니다. 아마도 도움이 안 될 거에요...
get_next_line 돌아보기
get_next_line 과제는 파일 2개, 함수 10개가 최대입니다.
이 10개의 함수만으로 모든 것을 해결하는 것은... 상당히 골치 아픈 일입니다.
다른 프로젝트에서 get_next_line을 사용할 수 있습니다. 물론 전 절대로 안 쓸 거지만,
다른 프로젝트에서도 쓸 것이라면 아무래도 어느 정도는 효율적으로 만드는 게 좋겠죠?
일단 get_next_line에서 시간복잡도를 말아먹기 좋은 부분을 알아보겠습니다.
get_next_line이 뭐 하는 과제더라...
fd에서 한 줄씩 읽어서 리턴하는 get_next_line(fd) 함수를 만들면 됩니다.
단, 전역변수를 사용할 수 없고 static 변수를 딱 한 개 사용할 수 있으며
read(fd, buffer, size) 호출에 사용할 size로 정해진 매크로 상수를 사용해야 합니다.
파일이 끝나거나 오류가 발생하면 NULL을 리턴합니다.
다양한 예외 처리가 아예 불가능하지만 일단 무시하겠습니다.
아마도 어려울 부분
자잘한 예외 처리, 모든 기능을 10개의 함수에 욱여넣기가 사실 제일 어려운 부분이겠지만
내부에서 사용하기 위해 구현해야 할 것이 크게 두 가지가 있습니다.
1.
그 fd에서 읽은 (추후 문자열로 바꿀) 데이터를 임시로 저장해야 합니다.
2.
1번의 그 데이터를 저장할 맵이 필요합니다. (fd를 키로 해서 삽입/삭제, 검색)
우선 만만한 2번부터 보겠습니다.
- 링크드리스트 기반 맵
일단 맵을 OPEN_MAX 길이의 고정 길이 배열로 만드는 건 반칙입니다.
OPEN_MAX는 고정되어 있고, 실제로 OPEN_MAX보다 큰 fd가 있을 수 있습니다.
결국 가변 길이 자료구조를 사용한 맵을 만들어야 하는데, 상당히... 쉽지 않습니다.
가장 만만한 방법이 링크드리스트를 사용한 맵인데, 삽입/삭제/검색이 모두 입니다.
- 임시 문자열 데이터 합치기
사실 맵은 그다지 고민하지 않아도 됩니다. 사실 진짜 문제가 되는 부분은 이 부분입니다.
문자열을 합치는 것은 입니다.
여러 번에 나눠서 read를 호출하기 때문에 문자열을 번 합치게 되는데,
그러면 문자열을 합치는 부분이 총 이 됩니다.
작은 문자열을 여러 번 합치는 것처럼, 긴 문자열을 여러 번 나누는 것도 마찬가지입니다.
해결하기
이 둘만 해결해도 (예외 처리를 제외하면) 꽤 쓸 만한 효율을 되찾을 수 있습니다.
문자열 데이터를 효율적으로 합치기
문자열을 바로 합칠 필요가 없습니다.
나중에 문자열로 만들 수 있는 무언가가 필요한 것입니다.
문자열을 연결한 링크드리스트로 만들면 으로 해결할 수 있는 문제입니다.
typedef struct s_get_next_line_stringbuilder_node
{
struct s_get_next_line_stringbuilder_node *next;
size_t length;
char buffer[];
} t_get_next_line_stringbuilder_node;
typedef struct s_get_next_line_stringbuilder
{
t_get_next_line_stringbuilder_node *head;
t_get_next_line_stringbuilder_node *tail;
size_t total_length;
} t_get_next_line_stringbuilder;
C
복사
문자열을 효율적으로 합칠 수 있는 stringbuilder 예시 일부
만들어야 할 함수가 늘었네요!
1.
stringbuilder에 문자열을 추가하는 함수 (read까지 여기서 처리해야 할지도?)
2.
stringbuilder의 내용대로 문자열을 만들고, 다시 비우는 함수
효율적인 맵 구현?
레드블랙트리는 효율적이라서 정말 널리, 많이 쓰입니다.
…하지만 함수 10개로 모든 것을 해결해야 하는 이 프로젝트에는, 적절하지 않은 듯합니다.
Trie 기반의, 높이가 4(=sizeof(int))인 256(=1 << CHAR_BIT)진 트리로도 충분합니다.
typedef union u_get_next_line_session_map
{
struct s_get_next_line_session_map **child;
t_get_next_line_session *value;
} u_get_next_line_session_map;
// key = (unsigned char *)(&fd);
// value = map[key[0]]->child[key[1]]->child[key[2]]->child[key[3]]->value;
C
복사
Trie 기반 맵 코드 예시 일부와 간단한 설명
코드를 첨부하지는 않지만, 함수 두 개로 맵에 삽입/삭제가 모두 해결됩니다.
처럼 보일 수 있지만 높이와 차수가 모두 상수라 이고, 충분히 빠릅니다.
마치며
함수 10개로 이 기능을 효율적으로 구현하는 건 쉽지 않은 일입니다.
함수 10개에 모든 기능을 넣으면서 가독성까지 고려하는 것은 정말 어렵습니다.
심지어 함수 프로토타입 자체가, 제대로 된 예외 처리는 아예 불가능하게 생겼습니다.
다른 곳에 쓰려면 get_next_line을 열심히 만들기보다는 그냥 따로 만드는 것을 권장합니다.
… 그래도! 효율에 대한 고민은 반드시 한 번쯤은 해 보셨으면 좋겠습니다.
