C에서 타입 세이프(Generic)한 자료구조 작성법

• 이 글은 C 언어에서 타입 세이프(Generic)한 자료구조를 만드는 새로운 방법을 설명함
• union을 활용해 타입 정보를 자료구조에 연관시키는 기법으로, 링크드 리스트 구현을 예시로 설명함
• 기존 C 제네릭 패턴(매크로, void 포인터, Flexible Array Member)과 차별점과 각 방식의 단점을 비교함
• 컴파일 타임 타입 체크가 가능해서 잘못된 타입 사용을 미리 막을 수 있음
• 새로운 기법은 foo_list와 같이 명확하고 일관된 함수/자료구조 인터페이스를 제공함

서론

• C 언어에서 제네릭 자료구조를 타입 안정성 있게 만드는 방법에 대해 소개함
• 이 기법은 union을 사용해 타입 정보를 컴파일 타임에 자료구조에 연결함
• 지도(Map), 배열, 바이너리 트리 등 모든 자료구조에 적용할 수 있으며, 예시로 기본 링크드 리스트 구현을 통해 설명함
• 많은 개발자들이 C에서 제네릭이 불가능하다고 생각하므로, 단계별로 쉽게 설명을 진행함

전통적인 매크로 기반 제네릭

• C에서 제네릭 자료구조 구현의 전통적 방식은 매크로를 이용하여 구조체와 함수의 이름, 타입을 생성함
• 자료구조 헤더를 여러 타입에 대해 여러 번 include하는 식으로 확장함

예시:

• 타입에 맞는 구조체와 함수명을 생성하기 위해 매크로(예: CONCAT, NODE_TYPE, PREPEND_FUNC) 사용
• 각 타입별로 함수와 구조체가 따로 생성되어, int와 Foo 같은 타입 각각 별도의 자료구조 정의가 나옴

단점:

• 타입 및 함수 정의 위치 파악이 어려움 (매크로로 생성되어 추적이 힘듦)
• 코드 자동완성 기능 활용이 어렵고
• 동일 함수 여러 개 생성으로 바이너리 크기 및 빌드 시간 증가
• 함수 이름에 타입 접두사 필요 (예: Foo_list_prepend)

제네릭 단계 1: void 포인터 방식

• 자료구조의 데이터 타입을 *void 로 두어 타입에 무관하게 만듦
• 링크드 리스트의 data 필드를 void *로 선언
• 타입 체크가 불가능하므로 런타임에 타입 오류가 발생할 수 있음, 컴파일 타임의 안전성 낮음
• 메모리 및 캐시 활용 비효율: 노드와 데이터가 따로 할당되어 불필요한 오버헤드 및 캐시 미스 증가

제네릭 단계 2: 인라인 스토리지(Flexible Array Member)

• Flexible Array Member(유연 배열 멤버) 를 활용, 포인터 저장 대신 데이터 자체를 노드에 함께 저장
• 노드 하나당 한 번의 할당으로 충분하며, 캐시에 데이터와 next 포인터가 인접하게 위치함
• 이 방식은 memcpy와 같은 크기 정보 전달이 필요하나, 일관된 메모리 배치로 성능이 개선됨
• list_alloc_front 함수를 이용하면 memcpy 없이 구조체를 직접 초기화할 수 있음

제네릭 단계 3: 타입 체크 구현

• union의 payload 멤버에 파라미터화된 타입 포인터를 선언하여 컴파일 타임에 자료구조에 타입 정보 추가
• 예) #define List(type) union { ListNode *head; type *payload; }
• 이렇게 하면 typeof(foo_list.payload) 로 해당 리스트의 타입을 얻을 수 있음
• 매크로(list_prepend)에서 함수 타입 캐스팅을 통해, 올바른 타입이어야만 컴파일 가능
• 잘못된 타입 사용 시 컴파일 타임에 에러 발생

에러 예시:

• foo_list에 int를 추가 시, 'incompatible integer to pointer conversion' 컴파일 에러 메시지가 출력됨

typeof 미지원 컴파일러 대응

• C23 이전까지 __typeof__는 표준이 아니므로 일부 컴파일러(예: 구버전 MSVC)에서는 동작하지 않음
• struct 내 payload 멤버 활용 등 우회방법으로 비슷한 효과 가능

파라미터 전달 및 typedef

• 동일한 형태의 List(Foo)도 컴파일러는 서로 다른 타입이라 판단함
• typedef 사용 시, 매개변수 전달 및 대입이 원활해짐

예시:

• typedef List(Foo) ListFoo;
• ListFoo 변수 선언 및 함수 매개변수로 사용 가능

마무리 및 다양한 자료구조 확장

• 이 기법은 여러 타입 파라미터가 필요한 자료구조(예: 해시맵)에도 활용 가능
• union을 통해 key, value 각각의 타입 안전성을 보장 가능
• 더 자세한 실습 및 매크로 구현체는 관련 코드 gist 링크 참고

결론

• 새로운 방식은 기존 방식의 단점(가독성, 빌드 효율성, 유지보수성)을 극복하고, 일관성 있는 함수 명명 체계와 타입 안전성 제공함
• 여러 자료구조 및 복수 타입 파라미터 지원이 용이함
• 컴파일 타임 타입 체크를 통해 제네릭 자료구조 사용의 안전성과 효율성을 동시에 확보함

감사의 말

• 이 글은 Martin Fouilleul의 피드백 및 격려를 받아 완성함