- C에서도 매크로,
void *, flexible array member, union을 조합하면 타입 안전한 제네릭 자료구조를 만들 수 있으며, 예시는 연결 리스트로 단계별 구현을 보여줌
- 타입별 헤더를 여러 번 include하는 방식은 안전하지만, 매크로 생성 코드 때문에 정의 추적과 코드 완성이 어렵고 바이너리 크기·빌드 시간이 늘어날 수 있음
void * 기반 리스트는 범용성이 있지만 타입 오류를 막지 못하고, 노드와 데이터를 따로 할당하면 노드당 2회 할당과 캐시 미스가 생길 수 있음- flexible array member로 데이터를 노드 안에 저장하고
List(type)을 union으로 감싸면, 런타임 비용 없이 컴파일 타임 타입 정보를 붙일 수 있음
list_prepend 매크로는 삼항 연산자로 전달 값과 payload 타입을 맞춰 컴파일 오류를 유도하며, 반환 포인터 타입에는 __typeof__()를 활용할 수 있음
C 제네릭 구현의 출발점
- 목표는 C에서
List(int), List(Foo)처럼 타입별 리스트를 선언하고, 잘못된 타입을 넣으면 컴파일되지 않게 만드는 것임
- 예시에서는
List(Foo)에 Foo 값을 넣을 수 있지만, list_prepend(&foo_list, 7)처럼 다른 타입을 넣는 코드는 컴파일되지 않음
list_for(item, &foo_list) 내부의 item은 Foo * 타입으로 다룰 수 있음
레벨 0: 제네릭 헤더 방식
- 한 가지 방법은 자료구조를 헤더에 작성하고, 타입 매크로
T를 바꿔가며 #include를 여러 번 수행하는 것임
list.h는 T를 기반으로 FooListNode, Foo_list_prepend 같은 타입과 함수를 매크로로 생성함- 이 방식은 제네릭이고 타입 안전하지만 사용성이 거칠어짐
- 타입과 함수가 매크로로 구성돼 정의 위치를 찾기 어려움
- 코드 완성이 잘 동작하지 않을 수 있음
- 동일한 함수 사본이 타입별로 생겨 바이너리 크기와 빌드 시간이 늘어남
list_prepend() 하나가 아니라 Foo_list_prepend(), int_list_prepend()처럼 타입 접두사가 붙은 함수를 써야 함
- 타입별 코드 생성이 필요한 제네릭 함수에는 이 방식이 더 적합할 수 있음
레벨 1: void * 기반 리스트
ListNode가 void *data를 가지면 여러 타입의 데이터를 담을 수 있음list_prepend(ListNode **head, void *data)는 데이터 포인터를 그대로 저장하므로 구현이 단순함- 문제는 이 구조가 타입 안전하지 않다는 점임
- 노드와 데이터가 별도 할당되면 메모리와 성능 비용도 커짐
- 노드 하나에 두 번 할당이 필요함
data 포인터 자체가 추가 메모리를 사용함- 리스트 순회 시 다음 노드 접근과 데이터 접근에서 각각 캐시 미스가 날 수 있음
- 예시 코드는 익숙함 때문에
malloc을 사용하지만, 실제로는 Arena 사용을 권장하며 관련 자료로 영상과 글을 참고할 수 있음
레벨 2: 노드 내부에 데이터 저장
void *data 대신 Flexible Array Member를 사용하면 데이터를 노드 내부에 둘 수 있음struct ListNode는 ListNode *next와 char data[]를 가지며, 할당 시 sizeof(* node) + data_size만큼 한 번에 확보함list_prepend는 전달받은 데이터와 크기를 받아 memcpy로 node->data에 복사함- 이 방식은
next와 실제 데이터가 메모리상 가까이 배치돼 void * 방식의 할당과 캐시 문제를 줄임
- 대신 호출자가
data_size를 넘겨야 하는 부담이 생김
memcpy를 피하고 싶다면 list_alloc_front가 노드의 데이터 영역 포인터를 반환하게 하고, 호출자가 그 메모리를 직접 초기화할 수 있음data 멤버의 정렬, 패딩, 크기 계산 문제는 별도 주제라 예시에서는 자세히 다루지 않음
레벨 3: union으로 타입 정보 붙이기
- 핵심 기법은
List(type)을 union으로 정의하고, 실제 리스트 헤드와 타입 정보용 포인터를 함께 두는 것임
#define List(type) union { \
ListNode *head; \
type *payload; \
}
payload는 런타임에 쓰이지 않고 컴파일 타임 타입 정보를 제공함union을 사용하므로 payload가 별도 메모리를 소비하지 않음List(Foo) foo_list, List(int) int_list처럼 타입별 리스트를 만들 수 있음
삼항 연산자로 타입 검사하기
list_prepend 매크로는 내부 함수 _list_prepend를 호출하면서 삼항 연산자로 item과 (list)->payload의 타입을 맞춤
#define list_prepend(list, item) \
_list_prepend(&((list)->head), \
(1 ? (item) : (list)->payload), \
sizeof(*(list)->payload))
- 삼항 연산자의 두 후보 타입이 맞지 않으면 컴파일러가 타입 불일치 오류를 냄
- 예를 들어
List(Foo)에 Bar *를 넘기면 Clang은 Foo *와 Bar *의 포인터 타입 불일치를 오류로 표시함
- 같은 매크로가
sizeof(*(list)->payload)로 저장 타입의 크기도 자동 전달함
- 실제 작업은
_list_prepend(ListNode **head, void *data, size_t data_size) 같은제네릭 내부 함수가 맡음
반환 타입에는 __typeof__() 사용
- 제네릭 함수가 내부 데이터 포인터를 반환해야 할 때는
__typeof__()로 void * 반환값을 payload 타입으로 캐스팅할 수 있음
#define list_alloc_front(list) \
(__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload))
__typeof__()는 Clang, GCC, MSVC 19.39 이상에서 지원됨__typeof__()는 C23에서 표준에 포함되기 전까지 선택적 확장이었음- MSVC 19.39 이전처럼
__typeof__()가 없는 컴파일러에서는 삼항 연산자 기반 타입 검사를 사용할 수 있음
- 타입 안전한 반환도
payload를 통한 할당 방식으로 가능하지만, 세부 구현은 생략됨
예전 방식과 정의상 주의점
- 이전 방식은
_list_prepend를 __typeof__((list)->payload)를 포함한 함수 포인터 타입으로 캐스팅해 호출하는 구조였음
- 타입 캐스팅된 함수 포인터 호출은 기술적으로 정의되지 않은 동작이지만, 현대 컴파일러와 현대 플랫폼에서는 실제로 문제가 없다고 다룸
- 현재 방식은 함수 포인터 캐스팅 대신 삼항 연산자 타입 일치로 오류를 유도함
List(Foo)를 인자로 넘길 때의 문제
- C 컴파일러는 동일한 구조를 가진 두
List(Foo) 정의를 같은 타입으로 보지 않을 수 있음
List(Foo) a;
List(Foo) b = a; // error
- 함수 인자로
void my_function(List(Foo) list)를 정의하고 my_function(a)를 호출해도 호환되지 않는 타입 오류가 날 수 있음
- 해결책은
typedef로 타입 이름을 붙이는 것임
typedef List(Foo) ListFoo;
ListFoo a;
ListFoo b = a; // ok
void my_function(ListFoo list);
my_function(a); // ok
- 지역 변수에서는
List(Foo) local_foo_list 형태를 계속 사용할 수 있음
- GCC 15와 2025년 말 Clang에서는 규칙 변경으로 같은 태그 이름을 가진 구조적으로 동일한 타입이 같은 타입으로 취급될 예정임
리스트 밖의 자료구조에도 적용 가능
- 같은 기법은 리스트뿐 아니라 맵, 배열, 이진 트리 같은 여러 자료구조에 적용할 수 있음
- 여러 관련 타입이 필요한 자료구조에도 확장 가능함
- 예를 들어 해시 맵은 내부 구조와 키 타입, 값 타입을
union 안에 함께 둘 수 있음
#define Map(key_type, value_type) union { \
MapInternal map; \
key_type *key; \
value_type *value; \
}
- stb_ds.h도 타입 안전한 제네릭 자료구조의 예지만, 배열과 맵이 C 배열을 사용하기 때문에 일부 타입 오류가 값 전달 시점이 아니라 배열 대입 시점에 잡히는 구조임