TAILQ 사용법

개요

TAILQ를 사용하면 동적 요소를 갖는 링크드 리스트 기반의 테이블이나 리스트, 큐 등의 자료구조를 쉽게 구현할 수 있습니다.

 

TAILQ를 이용한 정보의 선언이나 초기화, 큐 삽입, 제거 등의 동작은 모두 매크로로 구현되어 있으며 sys/queue.h 파일에 정의되어 있습니다. 매크로 기반으로 구현되어 있기 때문에 플랫폼과 무관하게 어디에든 쉽게 가져다 사용할 수 있습니다.

 

여기서는 TAILQ를 이용하여 FIFO(First In First Out) 및 LIFO(Last In First Out) 방식의 간단한 데이터 큐를 구현하는 방법에 대해 예제 중심으로 다루고자 합니다. 주로 다루는 내용은 다음과 같습니다.

• 데이터 큐 형식 선언
• 데이터 큐 초기화
• 데이터 큐에 데이터 추가
• 데이터 큐에서 특정 데이터 탐색
• 데이터 큐에서 특정 데이터 제거
• 데이터 큐 비우기

 

데이터 큐 형식 선언

TAILQ_ENTRY()와 TAILQ_HEAD() 매크로를 이용하여 데이터 큐 형식과 데이터 큐 내에 저장되는 데이터 요소(엔트리)의 형식을 선언할 수 있습니다.

# data_queue.h

/**
 * 데이터 큐에 저장되는 데이터 엔트리 정보 형식
 */
struct DataQueueEntry
{
  unsigned int id; ///< 데이터를 식별하는 식별자
  void *data; ///< 데이터
  TAILQ_ENTRY(DataQueueEntry) entries; ///< 엔트리간 연결정보
}
TAILQ_HEAD(DataQueueEntryHead, DataQueueEntry); 

/**
 * 데이터 큐 형식
 */
struct DataQueue
{
  unsigned int entry_num; ///< 큐 내 엔트리의 개수
  struct DataQueueEntryHead head; ///< 큐내 엔트리들에 대한 접근 정보
}

 

(struct DataQueueEntry) 먼저, 저장되는 데이터 요소(엔트리)의 형식을 구조체로 선언합니다. 이 때 해당 구조체 내에 TAILQ_ENTRY() 매크로를 이용하여 선언되는 엔트리간 연결정보인 "entries" 변수가 포함되어야 합니다. 이 때 TAILQ_ENTRY() 매크로의 인자는 구조체 이름을 그대로 사용해야 하며, "entries" 변수는 이후 호출되는 TAILQ 관련 매크로들의 "field" 인자로써 전달됩니다. 변수 이름은 다른 것을 사용해도 무방합니다. 그 외에 저장될 데이터에 관련된 변수(예: id, data)들을 필요에 따라 구조체 내에 선언합니다.

 

TAILQ_HEAD(DataQueueEntryHead, DataQueueEntry) 데이터 요소(엔트리)의 형식 선언이 완료되면, TAILQ_HEAD 매크로를 이용하여 엔트리들에 대한 접근정보의 형식을 선언합니다(이 정보를 통해 엔트리들에 접근할 수 있습니다). TAILQ_HEAD() 매크로의 첫번째 인자는 접근정보 구조체의 이름을 지정해 주는 것으로써 자체적으로 결정하여 사용할 수 있습니다. 여기서는 데이터 엔트리 구조체 이름인 DataQueueEntry 뒤에 "Head" 접미어만 추가하였습니다. 두번째 인자는 엔트리 구조체 이름을 그대로 사용해야 합니다.

 

(struct DataQueue) 마지막으로 데이터 엔트리들이 저장되는 데이터 큐의 형식을 구조체로 선언합니다. 큐내 엔트리들에 대한 접근정보를 담고 있는 "head" 변수가 반드시 포함되어야 합니다. 해당 변수의 이름은 원하는대로 정해서 사용할 수 있습니다. entry_num 변수는 큐 내에 저장된 엔트리의 개수를 관리하기 위해 사용되는 변수이며 필수 사항은 아닙니다.

 

 

 

데이터 큐 초기화

TAILQ_INIT() 매크로를 이용하여 데이터 큐를 초기화합니다.

#data_queue.c

struct DataQueue g_data_q; ///< 데이터큐를 전역변수로 선언

/**
 * @brief 데이터큐를 초기화한다.
 */
void InitDataQueue(void)
{
  TAILQ_INIT(&(g_data_q.head));
  g_data_q.entry_num = 0;
}

 

TAILQ_INIT() 매크로의 인자로 데이터큐 형식 구조체 내 head 변수의 포인터가 전달되어야 합니다.

 

데이터 큐에 데이터 추가

데이터 큐에 데이터를 추가할 때 다음 매크로들이 사용될 수 있습니다.

• TAILQ_INSERT_HEAD(): 큐의 제일 앞에 새로운 데이터를 추가합니다.
• TAILQ_INSERT_TAIL(): 큐의 제일 뒤에 새로운 데이터를 추가합니다.
• TAILQ_INSERT_AFTER(): 큐에 저장되어 있는 특정 데이터의 바로 뒤에 새로운 데이터를 추가합니다.
• TAILQ_INSERT_BEFORE(): 큐에 저장되어 있는 특정 데이터의 바로 앞에 새로운 데이터를 추가합니다.

/**
 * @brief 데이터큐 엔트리의 메모리를 할당한다.
 */
struct DataQueueEntry * AllocateDataQueueEntry(void)
{
  return (struct DataQueueEntry *)calloc(1, sizeof(struct DataQueueEntry));
}


/**
 * @brief 데이터큐의 가장 뒤에 새로운 데이터를 저장한다.
 * @param[in] q 데이터큐
 * @param[in] id 데이터 식별자
 * @param[in] data 데이터 
 * @retval 0: 성공
 * @retval -1: 실패
 */
int PushDataQueueEntry_Last(struct DataQueue *q, unsigned int id, void *data)
{
  struct DataQueueEntry *entry = AllocateDataQueueEntry();
  if (entry) {
    entry->id = id;
    entry->data = data;
    TAILQ_INSERT_TAIL(&(q->head), entry, entries);
    return 0;
  }
  return -1;
}


/**
 * @brief 데이터큐의 가장 앞에 새로운 데이터를 저장한다.
 * @param[in] q 데이터큐
 * @param[in] id 데이터 식별자
 * @param[in] data 데이터 
 * @retval 0: 성공
 * @retval -1: 실패
 */
int PushDataQueueEntry_First(struct DataQueue *q, unsigned int id, void *data)
{
  struct DataQueueEntry *entry = AllocateDataQueueEntry();
  if (entry) {
    entry->id = id;
    entry->data = data;
    TAILQ_INSERT_HEAD(&(q->head), entry, entries);
    return 0;
  }
  return -1;
}


/**
 * @brief 데이터큐 내에 이미 저장되어 있는 특정 데이터 바로 뒤에 새로운 데이터를 저장한다.
 * @param[in] q 데이터큐
 * @param[in] data_in_q 데이터큐 내에 저장되어 있는 특정 데이터
 * @param[in] id 데이터 식별자
 * @param[in] data 데이터 
 * @retval 0: 성공
 * @retval -1: 실패
 */
int PushDataQueueEntry_After(struct DataQueue *q, struct DataQueueEntry *data_in_q, unsigned int id, void *data)
{
  struct DataQueueEntry *entry = AllocateDataQueueEntry();
  if (entry) {
    entry->id = id;
    entry->data = data;
    TAILQ_INSERT_AFTER(&(q->head), data_in_q, entry, entries);
    return 0;
  }
  return -1;
}


/**
 * @brief 데이터큐 내에 이미 저장되어 있는 특정 데이터 바로 앞에 새로운 데이터를 저장한다.
 * @param[in] data_in_q 데이터큐 내에 저장되어 있는 특정 데이터
 * @param[in] id 데이터 식별자
 * @param[in] data 데이터 
 * @retval 0: 성공
 * @retval -1: 실패
 */
int PushDataQueueEntry_Before(struct DataQueueEntry *data_in_q, unsigned int id, void *data)
{
  struct DataQueueEntry *entry = AllocateDataQueueEntry();
  if (entry) {
    entry->id = id;
    entry->data = data;
    TAILQ_INSERT_BEFORE(data_in_q, entry, entries);
    return 0;
  }
  return -1;
}

 

AllocateDataQueueEntry() TAILQ는 링크드 리스트 기반의 자료형이므로 데이터큐에 삽입할 데이터 엔트리는 동적으로 할당해야 합니다. 따라서 먼저 calloc() 등의 함수를 사용하여 데이터 엔트리를 생성하여 정보를 저장한 후 각 매크로를 사용하여 데이터큐에 저장합니다.

TAILQ_INSERT_TAIL(), TAILQ_INSERT_HEAD() 매크로의 첫번째 인자로 데이터 큐 구조체 내 "head" 변수에 대한 포인터가 전달되어야 합니다. 두번째 인자는 데이터큐에 저장될 엔트리 포인터가 사용되며, 세번째 인자는 데이터 엔트리 구조체의 "entries" 변수가 전달되어야 합니다.

TAILQ_INSERT_AFTER(), TAILQ_INSERT_BEFORE() 매크로의 경우, 큐에 이미 저장되어 있는 데이터 엔트리에 대한 포인터가 추가로 전달되며, 참고할만한 점은 TAILQ_INSERT_BEFORE() 매크로에는 head 변수가 전달될 필요가 없다는 점입니다.

 

 

 

데이터큐에서 특정 데이터 탐색

데이터큐에서 특정 데이터를 탐색할때 다음 매크로들이 사용될 수 있습니다.

• TAILQ_FIRST(): 데이터큐 내 가장 앞에 있는 데이터를 선택
• TAILQ_LAST(): 데이터 큐 내 가장 뒤에 있는 데이터를 선택
• TAILQ_NEXT(): 데이터 큐에 저장되어 있는 특정 데이터의 바로 뒤에 있는 데이터를 선택
• TAILQ_PREV(): 데이터 큐에 저장되어 있는 특정 데이터의 바로 앞에 있는 데이터를 선택
• TAILQ_FOREACH(): 데이터 큐를 처음부터 끝까지 살펴가며 원하는 데이터를 선택

/**
 * @brief 데이터큐의 가장 앞에 있는 데이터를 선택한다.
 * @param[in] q 데이터큐
 * @return 데이터 엔트리 포인터
 * @retval NULL: 없을 경우
 */ 
struct DataQueueEntry * GetFirstData(struct DataQueue *q)
{
  return TAILQ_FIRST(&(q->head));
}


/**
 * @brief 데이터큐의 가장 뒤에 있는 데이터를 선택한다.
 * @param[in] q 데이터큐
 * @return 데이터 엔트리 포인터
 * @retval NULL: 없을 경우
 */ 
struct DataQueueEntry * GetLastData(struct DataQueue *q)
{
  return TAILQ_LAST(&(q->head), DataQueneEntryHead);
}


/**
 * @brief 데이터큐 내 특정 데이터의 바로 뒤에 있는 데이터를 선택한다.
 * @param[in] data_in_q 데이터큐 내 데이터
 * @return 데이터 엔트리 포인터
 * @retval NULL: 없을 경우
 */ 
struct DataQueueEntry * GetNextData(struct DataQueueEntry *data_in_q)
{
  return TAILQ_NEXT(data_in_q, entries);
}


/**
 * @brief 데이터큐 내 특정 데이터의 바로 앞에 있는 데이터를 선택한다.
 * @param[in] data_in_q 데이터큐 내 데이터
 * @return 데이터 엔트리 포인터
 * @retval NULL: 없을 경우
 */ 
struct DataQueueEntry * GetPreviousData(struct DataQueueEntry *data_in_q)
{
  return TAILQ_PREV(data_in_q, DataQueneEntryHead, entries);
}


/**
 * @brief 데이터큐 내에서 특정 ID를 갖는 데이터를 선택한다.
 * @param[in] q 데이터큐
 * @param[in] id ID
 * @return 데이터 엔트리 포인터
 * @retval NULL: 없을 경우
 *
 * @note 데이터큐의 앞에서부터 순차적으로 탐색한다.
 */ 
struct DataQueueEntry * GetSomeData1(struct DataQueue *q, unsigned int id)
{
  struct DataQueueEntry *entry;
  TAILQ_FOREACH(entry, &(q->head), entries) {
    if (entry->id == id) {
      return entry;
    }
  }
  return NULL;
}


/**
 * @brief 데이터큐 내에서 특정 ID를 갖는 데이터를 선택한다.
 * @param[in] q 데이터큐
 * @param[in] id ID
 * @return 데이터 엔트리 포인터
 * @retval NULL: 없을 경우
 *
 * @note 데이터큐의 뒤에서부터 역순으로 탐색한다.
 */ 
struct DataQueueEntry * GetSomeData2(struct DataQueue *q, unsigned int id)
{
  struct DataQueueEntry *entry;
  TAILQ_FOREACH_REVERSE(entry, &(q->head), DataQueneEntryHead, entries) {
    if (entry->id == id) {
      return entry;
    }
  }
  return NULL;
}

 

TAILQ_FIRST() 매크로에는 데이터큐 구조체의 head 변수가 인자로 전달되며, 데이터큐에 데이터가 존재하지 않을 경우 NULL이 리턴됩니다. 

TAILQ_LAST() 매크로에는 데이터큐 구조체의 head 변수에 더해 엔트리 접근정보 형식이름(TAILQ_HEAD()를 통해 선언했던)인 DataQueueEntryHead가 인자로 사용됩니다. 데이터큐에 데이터가 존재하지 않을 경우 NULL이 리턴됩니다.

TAILQ_NEXT() 매크로에는 기준이 되는 데이터 엔트리와 데이터 엔트리 구조체에 포함된 entries 변수가 사용됩니다. 기준 데이터 엔트리가 데이터큐 내의 마지막 엔트리일 경우 NULL이 리턴됩니다.

TAILQ_PREV() 매크로에는 이에 더해 엔트리 접근정보 형식이름(TAILQ_HEAD()를 통해 선언했던)인 DataQueueEntryHead가 추가로 사용됩니다. 기준 데이터 엔트리가 데이터큐 내의 첫번째 엔트리일 경우 NULL이 리턴됩니다.

TAILQ_FOREACH()는 TAILQ 내의 첫번째 요소부터 시작하여 마지막 요소까지 순차적으로 선택하는 매크로입니다. 즉, for() 문을 대체하는 매크로입니다. 해당 for() 문 내에서 원하는 조건에 맞는 데이터를 찾아 리턴하도록 구현할 수 있습니다.

TAILQ_FOREACH_REVERSE()는 TAILQ 내의 마지막 요소부터 시작하여 역순으로 선택하는 매크로입니다. 이 매크로에도 엔트리 접근정보 형식이름(TAILQ_HEAD()를 통해 선언했던)인 DataQueueEntryHead가 추가로 사용됩니다.

 

여기서 우리는, 역방향 동작을 하는 매크로(TAILQ_LAST(), TAILQ_PREV(), TAILQ_FOREACH_REVERSE())에는 모두 DataQueueEntryHead 인자가 추가로 사용되는 것을 알 수 있습니다. (TAILQ_LAST()는 head로부터의 역방향 동작)

 

 

 

데이터큐에서 특정 데이터 제거

TAILQ_REMOVE() 매크로를 이용하여 데이터큐에서 데이터를 제거할 수 있습니다.

/**
 * @brief 데이터큐에서 특정 엔트리를 제거한다.
 * @param[in] q 데이터큐
 * @param[in] entry 제거할 엔트리
 */
void RemoveData(struct DataQueue *q, struct DataQueueEntry *entry)
{
  TAILQ_REMOVE(&(q->head), entry, entries);
  free(entry);
  q->num--;
}


/**
 * @brief 데이터큐에서 첫번째 엔트리를 제거한다.
 * @param[in] q 데이터큐
 */
void RemoveFirstData(struct DataQueue *q)
{
  struct DataQueueEntry *entry = TAILQ_FIRST(&(q->head));
  if (entry) {
    RemoveData(q, entry);
  }
}

데이터큐 내에 저장된 어떤 데이터 엔트리든지간에 TAILQ_REMOVE() 매크로를 사용하여 해당 엔트리만 제거할 수 있습니다. 위 코드에서는 단순히 첫번째 데이터만 제거하는 예를 제시하였습니다.

 

데이터큐 비우기

TAILQ_FOREACH_SAFE() 매크로를 이용하여 데이터큐를 비울 수 있습니다.

/**
 * @brief TAILQ_FOREACH_SAFE()를 이용하여 데이터큐를 비운다.
 * @param[in] q 데이터큐
 */
void FlushDataQueue(struct DataQueue *q)
{
  struct DataQueueEntry *entry, *tmp;
  TAILQ_FOREACH_SAFE(entry, &(q->head), entries, tmp) {
    TAILQ_REMOVE(&(q->head), entry, entries);
    free(entry);
  }
  q->num = 0;
}

 

여기서는 tmp라는 엔트리 포인터 변수가 추가로 사용되는데, for() 문 내에서 free(entry)에 의해 entry가 삭제되어 다음 엔트리로의 이동이 불가능하기 때문에 이를 해결하기 위해 임시로 저장하는 용도로 사용되는 것입니다.

 

마무리

본 글에서는 TAILQ 매크로를 사용하는 방법에 대해 알아 보았습니다. 여기서 설명된 기본 매크로들을 활용하면 다양한 형태의 큐, 테이블, 리스트 등의 자료구조를 구현할 수 있습니다.

sys/queue.h 파일에는 TAILQ 외에도 STAILQ, LIST, SLIST 등에 대한 매크로들이 선언되어 있는데 유사한 방식으로 사용할 수 있습니다.

---

파트너스 활동을 통해 일정액의 수수료를 제공받을 수 있음