객체 안에 링크를 넣는 침입형 연결 리스트, offsetof와 포인터 산술로 Linux식 구조 설명

침입형 자료구조는 포인터 역참조가 하나 줄어드는 것 말고도 장점이 있음. C에서는 페이로드별 일반 리스트를 만들려면 매크로 생성이 필요하니 더 매력적이고, 한 객체를 여러 병렬 컬렉션에 연결할 수도 있음. 원소 할당은 호출자가 힙, 스택, 전역 배열, 아레나 등에서 직접 결정함.

그럼 포인터 산술로 페이로드를 찾는 구조에서 객체 하나를 여러 리스트에 어떻게 넣는 건지 궁금함. next 포인터 하나면 리스트 하나에만 묶이는 것 아닌가?

C에서 타입 안전한 매크로 생성 리스트가 C++ 템플릿보다 특별히 더 어색하거나 못하다고 보진 않음. 표준으로 바로 쓸 만한 구현이 없다는 게 문제고, 오래된 BSD 구현도 썩 좋진 않음.

C 매크로 시스템은 오래 유지되지 않더라. 그냥 직접 작성하는 편이 for 루프 쓰는 것보다 어렵지 않음.

매크로 생성 없이도 char payload[0] 앞에 리스트 포인터를 숨길 수 있음. glibc malloc도 데이터 옆에 메타데이터를 두고 realloc이나 free 때 복구하는 비슷한 방식을 쓰는데, 리스트에 없는 임의 포인터를 넘기면 UB라는 문제가 있음.

Zig에서는 @fieldParentPointer와 comptime을 쓰면 꽤 편하게 구현됨. 같은 크기의 구조체를 계속 재활용하는 메모리 풀도 유용한데, 리스트 양쪽을 모두 돌려줄 수 있으면 리스트 전체를 freelist 앞에 붙여 재활용할 수 있음.

여러 병렬 컬렉션의 예로는 A*용 침입형 힙을 들 수 있음. Heap이 데이터를 갖고 HashMap이 SearchNodeId를 Heap 인덱스에 매핑하면, 힙 원소가 계속 섞여도 ID로 O(1)에 찾을 수 있음.

이 글은 역사를 잘못 서술한 듯함. 'intrusive'는 C++식 용어이고, C의 보통 연결 리스트는 원래 데이터와 next 포인터를 같은 구조체에 넣는 방식이었음.

오히려 정의를 거꾸로 잡은 것 같음. 침입형 리스트는 다른 자료구조 안에 연결 필드가 들어간 것이고, 스택에 있는 원소를 연결하는 경우가 고전적인 예임. 글도 용어를 지나치게 좁게 쓰거나 틀렸음.

검색해 보니 Stroustrup이 1985년 C++ 책에서 intrusive라는 말을 쓴 듯함. 1950년대부터 기본적인 연결 리스트는 지금 말하는 침입형이었고, 비침입형은 노드와 페이로드를 분리하는 C++식 추상화가 퍼지며 생긴 구분에 가까움. 성능을 신경 쓴다면 수업 밖에서 비침입형을 쓸 이유는 많지 않다고 봄.