이번에 소개할것은 Windows에 존재하는 Singly Linked List 입니다.
이 리스트는 Interlocked 계열을 사용한 리스트로서 멀티 프로세서환경에서 다른 동기화 시스템이 필요없다.
!! 여기까지 들으면 와 ~ 할 정도지만. 단점이. 크리티컬한 단점이 존재한다.
1. singly linked list 는 push 와 pop 만이 존재한다. 리스트의 장점인 중간 삽입, 삭제가 불가능하다.
2. singly linked list 는 Queue 가 아닌 Stack 으로 만들어졌다. (LIFO) 흑흑
그래도 사용할 만한곳을 찾았으니. 그건 안가르쳐주고 나혼자 써먹을거당. (은 아니고. 개발후 공개를 해야지)
관련 API를 알려드리겠습니다.
. 초기화
void InitializeSListHead( PSLIST_HEADER ListHead );
. Push
PSLIST_ENTRY InterlockedPushEntrySList( PSLIST_HEADER ListHead, PSLIST_ENTRY ListEntry );
. Pop
PSLIST_ENTRY InterlockedPopEntrySList( PSLIST_HEADER ListHead );
. Flush
PSLIST_ENTRY InterlockedFlushSList( PSLIST_HEADER ListHead );
. 기타
USHORT QueryDepthSList( PSLIST_HEADER ListHead );
(해당 ListHead 의 원소 개수를 반환해준다. 그런데 왜 하필 USHORT 인가.. 65535개 이상인경우 어떻게 확인하라고. ㅠㅠ)
API 설명은 우리의 친절한 MSDN 님에게 알아들 보시구요. 샘플 소스 코드 나갑니다. (MSDN에도 있습니다. 단, 제 소스랑 다릅니다.)
<소스 코드>
<결과 화면>
설명이 필요한가요? 소스만 봐도 감이 오지 않으신가요? 간단한 설명을 드리자면
1. 하나의 singly linked list 에 연결된 SLIST_HEADER 라는 구조체가 필요합니다
2. 우리가 사용하고자는 자료구조는 SLIST_ENTRY 를 상속받거나 최상단에 포함하고 있어야합니다.
3. InterlockedPopEntrySList 함수는 리스트가 비어있는경우 NULL 을 리턴합니다.
위 세가지만 기억하시면 사용하시는데 그리 불편함 OR 삽질은 하시지 않으실겁니다.
이젠 위 소스 코드에 등장하지 않은 함수에 대해 알아보겠습니다.
<소스 코드>
<결과 화면>
QueryDepthSList 는 위에서 설명이 되어있습니다. 리스트 원소 개수를 알려주는 함수이지요. (리턴되는 타입이 USHORT라서 쉣이지만요.ㅠㅠ)
InterlockedFlushSList 함수를 실행하면 PSINGLE_LIST_ENTRY 변수에 해당 리스트의 헤더 정보가 들어갑니다. 그 후 PSINGLE_LIST_ENTRY Next가 NULL 일때까지 파고들면 모든 원소에 액세스가 가능합니다.
주의할 점은 Flush 이 후 SLIST_HEADER 의 리스트는 아무것도 가지고 있지 않다는점만 기억하시면 됩니다.
