1. C언어의 제네릭 자료구조들, 하지만 2% 부족한

오늘날 주로 사용되는 언어들 중에서 C언어의 생산성은 낮은 편이다. C언어가 생산성이 낮은 이유는 여러가지가 있겠다. 개인적으로 생각하는 C언어가 생산성이 낮은 이유들은 다음과 같다.

• 문법적으로 Class를 지원하지 않는다.
• 예외처리방법이 일관되지 않고 귀찮다.
• 포인터 관련 메모리 관리가 어렵다.
• STL과 같은 제네릭 자료구조를 지원하지 않는다.

 

이번 주제를 통해서는 C언어의 생산성을 크게 높일 수 있는 방법 - STL과 같은 제네릭 자료구조 - 를 사용하는 방법에 대해서 다룰 예정이다. 주된 내용은 glib의 자료구조를 사용하는 방법에 대해서 다룰 예정이다. 이번 포스트에서는 준비 운동 느낌으로 C언어에서 (glib를 제외한) 사용 가능한 제네릭 자료구조들과 한계점들에 대해서 살펴보자

 

커널 제네릭 자료구조

리눅스 커널은 linked-list, hash-table, rb-tree 등 다양한 제네릭 자료구조를 제공하고 있다. 커널에서 제공하는 제네릭 자료구조들은 최소한의 메모리를 사용하면서 최대한 적은 인스트럭션으로 동작하도록 설계되어있다. 이렇게만 들으면 그야말로 완벽한 자료구조로 들린다. 그렇다면 왜 리눅스 커널의 제네릭 자료구조들은 범용적으로 널리 사용되지 않을까?
여기에는 크게 두 가지 이유가 있다. 하나는 메모리/성능 최적화를 위해 자료구조의 많은 부분을 사용자로 하여금 구현하게 한다. linked-list의 예로 일반적인 경우와, 커널의 제네릭 자료구조의 차이를 살펴보자. 일반적으로 제네릭 linked-list의 노드는 다음과 같이 작성된다.

struct generic_node {
    /* item에 사용자 자료형이 저장된다. */
    void *item;
    /* prev, next로 노드를 순회한다. */
    struct generic_node *prev, *next;
};

item에는 사용자의 자료형이 저장된다. void 포인터 형으로 선언되어 있기 때문에, 어떤 자료형의 포인터든 저장할 수 있다. 노드간의 이동은 prev, next를 사용해서 다른 노드로 이동한다. 반면 커널의 linked-list는 다음과 같이 작성된다.

/* include/linux/types.h */
/* 리눅스 커널에 정의된 list_head 구조체.
   사용하려는 데이터 구조에 삽입하여 사용한다. */
struct list_head {
    struct list_head *next, *prev;
};

/* list.h */
/* custom_datatype은 사용자가 임의로 만든
   데이터타입 */
struct custom_datatype {
    /* 필요한 임의의 멤버를 소유한다. */
    int custom_intdata;
    char *custom_stringdata;
    
    /* list_head 구조체를 멤버로 가져야 한다. */
    struct list_head list;
};

제네릭 linked-list처럼 노드가 데이터를 소유하는 대신 커스텀 자료형이 list 정보를 가지고 있다. 커널에서는 list_head 구조체의 연결 리스트만을 관리하고, 실제 custom_datatype 자료형에 접근할 때는 container_of 매크로를 사용해서 접근한다. 이 방법을 사용하면 별도로 아이템을 저장하는 노드 구조체가 필요하지 않고, 노드간 이동 시에도 메모리 참조를 덜 하기 때문에 인스트럭션의 개수도 더 적다. 하지만 c커스텀 데이터형에 수정을 가해야 한다는 불편함이 존재한다. 심지어 커널의 RB-tree의 경우에는 사용자로 하여금 insert와 search 등의 함수도 직접 제작하도록 한다. 편하게 개발하려고 제네릭 자료구조를 사용하는 개발자 입장에서는 여간 고역이 아닐 수 없다.
커널의 제네릭 자료구조가 사용되기 어려운 다른 이유는 리눅스 커널의 제네릭 자료구조들은 통일된 스타일의 API가 없다. linked-list와 hash-table. rb-tree 간 삽입 API가 어떻게 생겼는지를 비교해보자.

void list_add(struct list_head * new, struct list_head * head);
hash_add(hashtable, node, key); /* 매크로 */
rb_insert(?, ?) /* 직접 제작해야하는 함수 */

 

커널 스타일 자료구조에 익숙한 개발자가 아니라면, API마다 스타일이 너무 달라서 헷갈릴 수 있다.

커널은 운영체제의 가장 핵심이 되는 부분으로 성능과 최적화에 민감할 수 밖에 없다. 따라서 사용하기에는 불편하더라도 적은 메모리와 인스트럭션을 사용하는 자료구조가 필요하다. 그러나 '개발자의 몸값이 컴퓨터의 HW 업그레이드 비용보다 비싼' 것을 감안한다면 일반적인 개발 분야에는 굳이 약간의 이득을 보려고 개발 생산성을 낮출 필요는 없을 것이다.

 

C 표준 라이브러리의 자료구조

C표준 라이브러리에서도 제네릭 정렬, 검색 알고리즘을 제공한다. 제네릭 정렬로는 퀵소트, 제네릭 서치로는 이진 서치가 제공된다. 각각의 사용 방법은 다음과 같다.

qsort

// qsort의 man page에 있는 예제코드이다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int cmpstringp(const void *p1, const void *p2) {
    /* The actual arguments to this function are "pointers to
       pointers to char", but strcmp(3) arguments are "pointers
       to char", hence the following cast plus dereference. */

    return strcmp(*(const char **) p1, *(const char **) p2);
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s <string>...\n", argv[0]);
        exit(EXIT_FAILURE);
    }

    qsort(&argv[1], argc - 1, sizeof(char *), cmpstringp);

    for (int j = 1; j < argc; j++)
        puts(argv[j]);
    exit(EXIT_SUCCESS);
}

bsearch

// bsearch man page에 있는 예제코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct mi {
    int nr;
    char *name;
} months[] = {
    { 1, "jan" }, { 2, "feb" }, { 3, "mar" }, { 4, "apr" },
    { 5, "may" }, { 6, "jun" }, { 7, "jul" }, { 8, "aug" },
    { 9, "sep" }, {10, "oct" }, {11, "nov" }, {12, "dec" }
};

#define nr_of_months (sizeof(months)/sizeof(months[0]))

static int compmi(const void *m1, const void *m2) {
    const struct mi *mi1 = m1;
    const struct mi *mi2 = m2;
    return strcmp(mi1->name, mi2->name);
}

int main(int argc, char **argv) {
    qsort(months, nr_of_months, sizeof(months[0]), compmi);
    for (int i = 1; i < argc; i++) {
        struct mi key;
        struct mi *res;

        key.name = argv[i];
        res = bsearch(&key, months, nr_of_months,
                sizeof(months[0]), compmi);
        if (res == NULL)
            printf("'%s': unknown month\n", argv[i]);
        else
            printf("%s: month #%d\n", res->name, res->nr);
    }
    exit(EXIT_SUCCESS);
}

C언어에서 간단하게 정렬, 검색이 필요할때 유용하다. 다만 자료구조를 별도로 제공하지는 않기 때문에 사용하기에는 한계가 있다.

 

이번 포스트에서는 C 언어에서 사용되는 제네릭 자료구조들에 대해서 살펴보았다. 리눅스 커널과 C 표준 라이브러리 모두 제네릭 자료구조를 제공하지만 두 라이브러리가 가진 한계에 대해서도 알아보았다. 리눅스 커널이 제공하는 자료구조는 API가 지나치게 복잡하고 문법적 일관성이 떨어진다. 또한 C 표준 라이브러리는 사용되는 용처가 너무 제한적이다.

앞으로의 포스트에서는 C++의 STL처럼 좀 더 보편적으로 사용할 수 있는 glib 자료구조에 대해서 살펴보려 한다.