C에서 사전 구현

ISO C에는 기본 제공 사전 자료형이 없습니다. 대상 환경에서 POSIX hsearch 인터페이스를 제공한다면, 이 인터페이스의 해시 테이블 함수로 키-값 항목을 저장하고 조회할 수 있습니다. 아래 예제는 테이블을 만들고 항목 두 개를 삽입한 다음, 존재하는 키와 존재하지 않는 키를 조회하고 반환된 포인터를 확인한 뒤 테이블을 해제합니다. 이 예제는 가능한 모든 사전 설계가 아니라 그중 한 가지 방법을 보여 줍니다.

POSIX hsearch 루틴으로 C에서 사전 구현하기

hcreate, hsearch, hdestroy는 <search.h>에 선언된 POSIX 루틴이며 ISO C 라이브러리 함수가 아닙니다. 대상 운영 체제와 C 라이브러리에 따라 제공 여부가 다르므로, 예제를 사용하기 전에 환경에서 이 인터페이스를 지원하는지 확인하세요. hcreate 및 hsearch의 POSIX 명세에서 인터페이스와 요구 사항을 확인할 수 있습니다. 제공된 자료에는 특정 플랫폼이나 라이브러리 버전이 명시되어 있지 않습니다.

hcreate와 hsearch로 해시 테이블을 만들고 항목 추가하기

hcreate를 한 번 호출해 요청한 용량의 테이블을 만듭니다. 성공하면 0이 아닌 값을 반환하고, 테이블을 만들 수 없으면 0을 반환합니다. ENTRY에는 char * 형식의 키와 void * 형식의 데이터 포인터가 들어갑니다. ENTRY와 ACTION 값을 hsearch에 전달합니다. ENTER는 삽입을 요청하고 FIND는 조회를 요청합니다. 호출이 성공하면 항목을 가리키는 포인터를 반환하고, 실패하면 NULL을 반환합니다.

다음 예제를 실행합니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

#define _XOPEN_SOURCE 700
#include <search.h>
#include <stdio.h>

int main(void) {
    if (hcreate(4) == 0) {
        fputs("could not create table\n", stderr);
        return 1;
    }

    ENTRY item = {"language", "C"};
    if (hsearch(item, ENTER) == NULL) {
        fputs("could not insert language\n", stderr);
        hdestroy();
        return 1;
    }

    item.key = "standard";
    item.data = "POSIX";
    if (hsearch(item, ENTER) == NULL) {
        fputs("could not insert standard\n", stderr);
        hdestroy();
        return 1;
    }

    ENTRY query = {"language", NULL};
    ENTRY *found = hsearch(query, FIND);
    if (found == NULL) {
        puts("language: not found");
    } else {
        printf("language: %s\n", (char *)found->data);
    }

    query.key = "compiler";
    found = hsearch(query, FIND);
    if (found == NULL) {
        puts("compiler: not found");
    } else {
        printf("compiler: %s\n", (char *)found->data);
    }

    hdestroy();
    return 0;
}

language: C
compiler: not found

키 조회 및 누락된 항목 처리

첫 번째 FIND 호출은 프로그램이 값 C와 함께 삽입한 language를 검색하고, 두 번째 호출은 삽입하지 않은 compiler를 검색합니다. 프로그램은 data를 읽기 전에 각 결과를 확인하므로, 결과가 NULL이면 안전하게 “찾을 수 없음” 경로로 처리합니다. 있어야 하는 키를 조회했는데 NULL이 반환되더라도, 예제는 해당 포인터를 역참조하지 않고 결과를 출력합니다. 애플리케이션에 맞게 메시지나 반환 방식을 조정하세요.

삽입을 완료할 수 없는 경우에도 hsearch는 NULL을 반환하므로, 계속 진행하기 전에 각 ENTER 호출의 결과를 확인해야 합니다. 예제에서는 테이블 생성이나 삽입이 실패하면 stderr에 오류 메시지를 쓰고, 이미 생성한 테이블을 해제한 뒤 실패 상태를 반환합니다. 각 연산 직후에 결과를 확인하면 이후 코드에서 포인터가 유효한지 확인한 다음에만 항목을 읽을 수 있습니다. 바이트 단위로 보존된 출력 예시에 표시되는 compiler: not found 문구는 영어입니다.

테이블 해제 및 한계 이해하기

테이블을 더 이상 사용하지 않을 때 hdestroy를 호출합니다. 이 함수는 테이블을 해제하지만, 항목이 참조하는 동적 할당 키 또는 값 저장 공간의 관리는 호출자 책임입니다. 해당 포인터를 보관하고 직접 소유한 메모리를 별도로 해제하세요. 예제는 문자열 리터럴을 사용하므로 해제할 동적 할당 메모리가 없습니다. 여기서 다루는 POSIX 인터페이스에는 개별 항목을 제거하는 연산이 없습니다. 테이블을 만들 때 충분한 용량을 선택하세요. 요청한 용량은 hcreate에 전달하며, 이 인터페이스는 여기서 설명한 사용 방식으로 테이블 크기를 조정하는 기능을 제공하지 않습니다.