레드-블랙 트리 그리고 C언어

 

출처: Introduction to Algorithms (CLRS)

 

정글 커리큘럼의 4주차 부터는 "탐험 준비" 라는 커리큘럼인데, 아마도 pintos를 향한 첫 걸음이 아닐까 생각한다.

 

4주자는 RB Tree 를 C언어로 구현하는 것이다. 물론, 밑바닥부터 구현하는 것은 아니고 기본적인 코드는 제공된다. 예를 들어, 코드 구현에 필요한 타입 같은 것들이 이미 선언되어 있으며, 함수 원형도 헤더파일에 이미 작성되어 있다. 이러한 empty body의 함수들에 코드를 채워넣는 것이다.

 

그리고, 작성한 코드를 테스트할 수 있는 테스트 코드 또한 포함되어 있다. 이것을 사용해서 테스트를 하는 방식이다.

 

다행히, 나는 C언어에 대한 경험이 있었기 때문에 언어의 장벽에 막히지는 않았다. 한창 C언어를 공부할 당시, 포인터에 대한 내용만 담겨 있는 책을 따로 공부를 했기도 하고, 포인터에 대한 이해 및 C언어의 갖가지 트릭에 관해서는 스스로 꽤 자신한다.

 

사실상 이 책을 본 뒤, 기본 학습서의 포인터에 대한 의문점이 모두 해소되었다. 스스로 만족할 정도로 포인터에 대한 이해가 생긴 것이다. 정말 큰 도움이 되었다. 일본인이 저자이며, 2002년에 출판된 꽤 오래된 책인데도 내용은 너무나 훌륭하다. 이때 오래된 책에 대한 편견이 깨진 것 같다.

 

아래는 당시 책이 절판되어 중고로 어렵게 구한 포인터 관련 책이다.

출처: 중고로 힘들게 구한 C언어 포인터 완전제패

 

말이 나온 김에, 또 한 가지 책이 더 있다.

 

이 책은 C언어 학습서의 심화버전인데, 전웅이라는 분이 저자인 "C언어 펀더멘탈" 이라는 책이다. 책의 내용은 꽤 어려웠던 것 같다. 이 책도 이미 절판된 상태였고 중고로는 정말 말도 안되는 가격으로 팔고 있었기 때문에, 대학교 도서관에서 빌려 제본을 해서 봤던 기억이 있다.

출처: yes24

 

지금 생각해보면 그 당시, 왜 이렇게까지 C언어에 집착했을까란 생각이 든다. 내가 주위 사람들에게 위의 책들을 설파하고 다녔을때는 정말 별종이란 얘기까지 들었다... 아마도 내가 처음으로 배운 프로그래밍 언어가 C언어여서 그랬던 것일까 C언어 만능주의자였던 시절이 있었지...

 

C언어 학습에 있어서, 한 가지 매우 아쉬웠던 점을 꼽으라면, C언어를 좀 더 C언어에 최적화된 환경에서 학습하지 못한 것을 꼽을 수 있을 것 같다.

 

나는 윈도우 환경의 Visual Studio라는 IDE에서 MSVC를 설치한 뒤, C언어를 학습한게 처음으로 접했던 경험이다. 그 당시에는 심지어 내가 무엇을 설치했는지, 어떻게 컴파일되어 작동하는지 조차 이해를 하지 못했다! IDE내의 버튼 클릭으로 환경이 자동으로 셋팅되고, 단축키 입력으로 컴파일 및 실행까지 자동으로 수행되었기 때문이다.

 

만약 리눅스 환경의 gcc를 사용하며 CLI 환경에 처음부터 익숙해졌다면 지금쯤 얼마나 성장해있을까 종종 상상하곤 한다.

 

바로 이곳 정글에서는 내가 학습에 이상적이라고 생각했던 환경(Linux) 내에서 과제를 수행할 수 있었는데, 그 첫걸음이 바로 4주차인 RB Tree 과제이다.

 

이 과정에서 정말 많은 것들을 배웠다고 생각한다. 특히 gdb와 valgrind를 어느정도 사용할 수 있게 된 것이라는 점인데, RB Tree 구현에 앞서 Doubly Linked List, Binary Search Tree 등을 먼저 구현하며 어느정도 감을 익히는 시간을 가졌다. 이때부터 gdb를 활용하면서 디버깅 실력을 키우고 valgrind를 사용하여 메모리 누수를 탐지하는 법을 배운 것이다. 뿐만 아니라, Makefile 의 용도와 사용법 또한 직접 사용해보며 이해도를 높일 수 있었다.

 

RB Tree의 삽입, 삭제, 회전 연산 등 거의 모든 곳에서 포인터 연산이 쓰이는데, C언어 특성상 코드에서 실수가 매우 빈번하게 일어난다. 이런 실수들을 gdb를 통해 정확히 에러가 발생하는 코드 지점을 찾을 수 있다. gdb로도 커버가 안되는 경우도 있다. 잘못된 메모리 참조로 인해 backtrace 가 제대로 출력되지 않는 경우인데, 이 때는 직접 printf 함수 사용과 같은 logging 방식을 사용해야 한다.

 

또한, RB Tree 과제에서 bit에 관련된 지식도 늘었다. Tree의 Node 구조체에서 color에 해당하는 값을 저장하는데 새로운 변수를 사용할 필요가 없다는 것이다. 포인터 변수의 사용하지 않는 bit를 활용하여 해당 값을 저장할 수 있다. 왜냐하면 메모리는 word 단위로 접근하기 때문이다. 만약 word가 8 byte 라면 하위 3개의 bit를 사용할 수 있다.

 

그리고 구조체 내의 left, right child 포인터를 배열로 선언하고, 이를 인덱스로 접근하는 방식으로 하면 좀 더 코드를 간단하게 작성 할 수 있는데, 이는 나중에 이어서 설명하겠다.