3-2. GLib의 자료구조들 (해쉬 테이블 - GHashTable)

본 포스트를 이해하려면 해쉬 테이블에 대한 사전 지식이 필요하다. 만약 해쉬 테이블이 무엇인지 모른다면 먼저 해당 내용들에 대해서 구글링을 해 보자.

http://openbooks.sourceforge.net/books/wga/gtk-gnome-intro.html

해쉬 테이블은 데이터를 Key-Value 쌍으로 관리하기 위한 자료구조이다. 하나의 Key에 하나의 Value만 저장될 수 있다. 아래는 GHashTable로 데이터 삽입, 삭제, 조회, 순회를 하는 간단한 예제이다.

#include <glib.h>
#include <stdio.h>
#include <assert.h>

// typedef void* gpointer;

// HashMap을 순회하면서 호출되는 콜백함수
static void print_film(gpointer key, gpointer value, gpointer user_data) {
    char *film = (char*)key;
    char *country = (char*)value;
    int *index = (int*)user_data;
    printf("[foreach][%d] film: %s, country: %s\n", (*index)++, film, country);
}

int main() {
    GHashTable *films = NULL;

    // 해쉬맵을 생성하는 함수.
    // g_str_hash: 스트링을 해쉬로 만드는 함수
    // g_str_equal: 스트링의 해쉬값을 비교하는 함수
    films = g_hash_table_new(g_str_hash, g_str_equal);
    assert(films);

    g_hash_table_insert(films, "SquidGame", (gpointer)"Korea");
    g_hash_table_insert(films, "Evangelion", (gpointer)"China");
    g_hash_table_insert(films, "Avengers", (gpointer)"U.S.A");

    int index = 0;
    // 해쉬 테이블 내의 값을 순회
    // 콜백 함수를 이용해서 순회된 값을 어떻게 처리할 지 정의할 수 있다.
    g_hash_table_foreach(films, print_film, (gpointer)&index);

    // 해쉬 테이블의 Value를 변경
    g_hash_table_replace(films, "Evangelion", (gpointer)"Japan");

    // 직접 특정 Key에 해당하는 Value를 검색
    const char *film_names[] = {"SquidGame", "Evangelion", "Avengers", "Hell"};
    unsigned int film_name_cnt = sizeof(film_names) / sizeof(film_names[0]);
    for (int i = 0; i < film_name_cnt; i++) {
        char *country = (char*)g_hash_table_lookup(films, film_names[i]);
        printf("[forloop][%d] film: %s, country: %s\n", i, film_names[i], country);
    }

    g_hash_table_destroy(films);

    return 0;
}

결과

$ gcc g_hash.c `pkg-config --cflags --libs glib-2.0`                                                                                                                                                                                                                at 18:32:02
$ ./a.out                                                                                                                                                                                                                                                           at 18:33:17
[foreach][0] film: SquidGame, country: Korea
[foreach][1] film: Avengers, country: U.S.A
[foreach][2] film: Evangelion, country: China
[forloop][0] film: SquidGame, country: Korea
[forloop][1] film: Evangelion, country: Japan
[forloop][2] film: Avengers, country: U.S.A
[forloop][3] film: Hell, country: (null)

다른 언어에서 HashTable을 사용해 봤다면, 대체로 금방 이해할 수 있는 코드이다. 다만 g_hash_table_new에 대해서는 부연 설명이 필요할 것 같다. C언어에서는 템플릿을 지원하지 않는다. 따라서 void 포인터로 전달된 Key 값의 해쉬키를 생성하고, 해쉬키 값을 비교하는 것은 개발자가 명시적으로 지정해 주어야 한다. GLib는 포인터, int, string에 대해서 사전에 정의된 함수를 제공하며, 이 외 타입에 대해서는 개발자가 직접 해슁 함수와 비교함수를 작성해야 한다. GLib에서 제공하는 함수들은 다음과 같다.

HashTable 생성 함수	GHashTable* g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
키 타입	해슁 함수	비교 함수
int	g_int_hash	g_int_equal
string	g_str_hash	g_str_equal
pointer	g_direct_hash	g_direct_equal

 

3.2.1 Key-Value 1:N 해쉬 테이블 사용하기

GLib의 HashTable은 기본적으로는 Key-Value를 1:1 매칭으로만 사용하도록 구현되어 있다. 하지만 앞에서 다룬 GList(https://www.kernelpanic.kr/41)와 결합하면 1:N 매칭의 해쉬 테이블을 사용할 수 있다. 아래는 GHashTable을 GList와 결합하여 사용하는 예제 코드이다.

#include <glib.h>
#include <stdio.h>
#include <assert.h>

// typedef void* gpointer;

static void destroy_value(gpointer data) {
    g_list_free((GList*)data);
    // g_list_free_full 함수를 사용하면 GList 삭제 시 커스텀 free 함수를 지정할 수 있다.
}

// 리스트를 순회하면서 호출되는 콜백함수
static void print_list_film(gpointer data, gpointer user_data) {
    char *film = (char*)data;
    int *index = (int*)user_data;
    printf("[%d] film: %s\n", (*index)++, film);
}

// HashMap을 순회하면서 호출되는 콜백함수
static void print_hash_film(gpointer key, gpointer value, gpointer user_data) {
    char *country = (char*)key;
    GList *films = (GList*)value;
    printf("===[%s]===\n", country);
    g_list_foreach(films, print_list_film, user_data);
}

int main() {
    GHashTable *films = NULL;
    GList *film_names = NULL;

    // 해쉬맵을 생성하는 함수.
    // g_str_hash: 스트링을 해쉬로 만드는 함수
    // g_str_equal: 스트링의 해쉬값을 비교하는 함수
    films = g_hash_table_new_full(g_str_hash, g_str_equal, NULL, destroy_value);
    assert(films);

    // GList를 HashTable의 Value로 전달
    film_names = g_list_append(film_names, "SquidGame");
    g_hash_table_insert(films, "Korea", (gpointer)film_names);
    film_names = NULL;

    film_names = g_list_append(film_names, "Avengers");
    g_hash_table_insert(films, "USA", (gpointer)film_names);
    film_names = NULL;

    film_names = g_hash_table_lookup(films, "Korea");
    film_names = g_list_append(film_names, "ChaChaCha");
    film_names = NULL;

    int index = 0;
    g_hash_table_foreach(films, print_hash_film, (gpointer)&index);

    g_hash_table_destroy(films);

    return 0;
}

결과

$ gcc g_hash_list.c `pkg-config --cflags --libs glib-2.0`                                                                                                                                                                                                           at 22:17:01
$ ./a.out                                                                                                                                                                                                                                                           at 22:17:05
===[Korea]===
[0] film: SquidGame
[1] film: ChaChaCha
===[USA]===
[2] film: Avengers

GHashTable 자체는 1:N 해쉬 테이블을 제공하지 않지만, Value에 직접 데이터를 입력하는 대신 GList에 데이터를 입력해서 전달하면 1:N 해쉬 테이블을 사용할 수 있다. 본 예제에서는 GHashTable을 생성하는 함수로 g_hash_table_new_full이 사용되었다. 이 함수는 해쉬 테이블이 삭제될 때 Key, Value를 어떻게 해제할지를 설정할 수 있다. Valgrind로 메모리 누수 검사를 해 보면 g_hash_table_new를 사용해서 해쉬 테이블을 생성한 경우에는 확실히 누수된 메모리가 48Byte, 아마도 누수된 메모리가 24Byte가 나온다. 물론 위 예제와 같이 g_hash_table_new_full를 사용하면 메모리 누수는 검출되지 않는다.