[PostgreSQL] ilist API

PostgreSQL에서 사용하는 intgrated/inline 리스트 API 분석

---

commit 7c335b7a202 (2022)

• 이전에는 dllist api를 사용했는데 a66ee69add6 commit(2012)에서 ilist api로 대채되었다
• ilist api는 메모리 할당 오버헤드를 줄이고 inline 함수로 성능을 높였다

ilist 요약

• 특정 객체가 리스트를 구성할 것이 이미 결정된 경우에 사용할 수 있다
• List link들은 객체들에 직접적으로 삽입되기 때문에 별도의 메모리 공간 관리가 필요하지 않다
• 주어진 객체들(List link가 삽입된) 중 소수만 하나의 리스트(a list)에 포함될 경우 리스트에 포함되지 않은 객체들의 List link는 낭비된다
• 일반적으로, 이 방법은 별도의 list node들을 할당하지 않기 때문에 메모리를 절약할 수 있다

doubly-linked list

• doubly-linked list에는 두 가지가 있다
• dlist_head - dlist_node들이 연결된 리스트의 head를 가리킨다
  • dlist 접두어가 붙은 함수들로 조작한다
• dclist_head - 리스트의 head를 가리키고 해당 리스트의 node 개수를 나타내는 count 필드를 가진다
  • dclist 접두어가 붙은 함수들로 조작한다
• dlist와 dclist는 node와 iterator type을 공유한다

API의 특징

• doubly-linked list api는 메모리를 할당하지 않는다
  • 외부에서 관리하는 메모리를 사용할 뿐이다
• doubly-linked count list API들은 해당 리스트의 원소 개수를 반환하는 함수를 제공한다는 점을 제외하면 singly linked list와 doubly linked list의 API는 동일하다

빈 리스트

• 모든 리스트(node가 없는 리스트 포함)는 list header를 가진다
• an empty singly-linked list는 header에 NULL pointer가 포함되어 있다
• 두 가지 doubly-linked list에서 비어있는 리스트를 표현하는 방법은 두 가지이다
  1. head의 next 포인터가 NULL을 가리킨다. 이 방법은 편리성 때문에 list를 초기화할 때 주로 사용한다
  2. head의 next와 prev 포인터가 다시 head를 가리킬 수도 있다. dlist의 모든 원소들이 삭제되면 이런 circular state가 된다. 이런 circular dlist를 추천한다. 분기를 타지 않고 실행 할 수 있다 operation이 있어서 실행속도가 빠르기 때문이다

examples

• 데이터베이스에 저장된 테이블들에 대한 정보를 저장하고 싶다면 아래와 같이 list를 사용할 수 있다

#include "lib/ilist.h"

// list header를 포함하는 database 구조체 선언. 
// 여기에 포함된 list header는 리스트의 노드들에 접근하기 위해 사용된다.
typedef struct my_database
{
    char       *datname;
    dlist_head  tables;
// ...
} my_database;

// table을 표현하는 구조체 선언.
// 각 list_node에는 prev/next list link가 저장되어 있다. 
// 이 list_node들은 리스트의 처음에 위치할 수 없다.
typedef struct my_table
{
    char       *tablename;
    dlist_node  list_node;
    perm_t      permissions;
// ...
} my_table;

// database 구조체 생성(list header)
my_database *db = create_database();

// table list에 table을 추가
dlist_push_head(&db->tables, &create_table(db, "a")->list_node);
// ...
dlist_push_head(&db->tables, &create_table(db, "b")->list_node);


// 단순 iterator element와 looping construct.
// `iter.cur`는 `dlist_node`인스턴스를 가리킨다. `dlist_container`를 사용하면 list link를 가지고 있는
객체에 접근이 가능하다.
dlist_iter  iter;
dlist_foreach(iter, &db->tables)
{
    my_table   *tbl = dlist_container(my_table, list_node, iter.cur);
    printf("we have a table: %s in database %s\n", 
            tbl->tablename, db->datname);
}


// 순회와 동시에 해당 원소를 조작할수 있는 iterator element와 looping construct.
// 특정 조건을 만족하는 테이블을 삭제하는 방법은 아래와 같다.
dlist_mutable_iter miter;
dlist_foreach_modify(miter, &db->tables)
{
    my_table   *tbl = dlist_container(my_table, list_node, miter.cur);

    if (!tbl->to_be_deleted)
    continue;       // don't touch this one

    // 특정 table을 리스트에서 제거(unlink)
    dlist_delete(miter.cur);
    // list link API는 메모리 할당에는 관여하지 않기 때문에 list에서 unlik되어도 여전히 해당 원소에는 접근 가능하다
    drop_table(db, tbl);
}

API

• src/include/lib/ilist.h
• slist_head는 왜 typdef slist_head slist_node로 구현하지 않고 필드가 하나짜리인 구조체를 굳이 만든걸까?

/*
 * doubly linked list를 만드는 list link 구조체
 * node 라는 표현보다는 link(고리)라는 표현이 적절한거같다
 */
typedef struct dlist_node dlist_node;
struct dlist_node
{
    dlist_node *prev;
    dlist_node *next;
};

/*
 * Head of a doubly linked list.
 *
 * 비어있지 않은 리스트는 내부적으로 순환 구조(circularly linked)이다.
 * 이런 구조의 장점은 일반적인 리스트 조작 과정에 분기가 필요 없다는 것이다.
 * 빈 리스트는 간단하게 head의 prev와 next를 NULL로 초기화할 수 있다.
 */
typedef struct dlist_head
{
    /*
     * head.next는 리스트의 첫 번째 원소를 가리키거나, 
     * circular empty list라면 &head를 저장한다. 
     * emtpy and not circular list라면 NULL을 저장한다.
     *
     * head.prev는 리스트의 마지막 원소를 가리키거나,
     * circular empty list라면 &head를 저장한다. 
     * emtpy and not circular list라면 NULL을 저장한다.
     */
    dlist_node  head;
} dlist_head;


/*
 * dlist_head와 dclist_head를 위한 iterator type.
 *
 * dlist_foreach(), dlist_reverse_foreach(), dclist 변형에서 상태를 나타내기 
 * 위해 사용한다.
 *
 * 반복(iteration)에서 현재 원소에 접근하고싶을 때에는 cur 필드를 사용하면 된다.
 *
 * 이 iterator를 사용해서 리스트를 변형하는 것은 허용하지 않는다.
 *
 * 참고: dlist_foreach(), dclist_foreach() 매크로에서 인자들을 여러 번 계산하는 것을 막기 위해 추가적인 end 필드를 사용한다.
 */
typedef struct dlist_iter
{
    dlist_node *cur;            /* current element */
    dlist_node *end;            /* last node we'll iterate to */
} dlist_iter;

/*
 * 반복 과정에서 리스트(dclist_head, dlist_head)에 대한 변형을 허용하는 doubly linked list iterator 타입.
 *
 * dlist_foreach_modify(), dclist_foreach_modify()에서 상태를 나타낸다.
 *
 * 리스트에서 현재 원소를 제거하는 것은 허용하지만, 새로운 원소를 추가하거나 인접 노드를 삭제하는것은 허용하지 않는다.
 *
 * 참고: 변형 가능한 순회(iteration)를 위해서는 현재 노드의 다음 노드를 저장해야 하기 때문에 별도의 iterator type이 필요하다.
 */
typedef struct dlist_mutable_iter
{
    dlist_node *cur;            /* current element */
    dlist_node *next;           /* next node we'll iterate to */
    dlist_node *end;            /* last node we'll iterate to */
} dlist_mutable_iter;

/*
 * doubly linked list의 원소 개수를 저장하는 head.
 *
 * 내부적으로 dlist를 사용하고 원소를 추가하거나 삭제할 때마다 count를 업데이트한다.
 */
typedef struct dclist_head
{
    dlist_head  dlist;
    uint32      count;
} dclist_head;

/*
 * singly linked list의 노드(고리).
 *
 * singly linked list를 구성할 객체에 이 구조체를 삽입해서 사용한다.
 */
typedef struct slist_node slist_node;
struct slist_node
{
    slist_node *next;
};

/*
 * singly linked list의 head.
 *
 * 순환적으로 연결되지 않기 때문에 리스트가 비어 있는 경우 head.next에 NULL을 저장한다.
 * head.next에 NULL을 저장한다고 해서 일반적인 리스트 조작(manipulations)에 대해 추가적인 분기를 필요로 하지 않는다.
 */
typedef struct slist_head
{
    slist_node  head;
} slist_head;

/*
 * Singly linked list iterator.
 *
 * slist_foreach()에서 사용하고 'cur' 필드를 통해 현재 원소에 접근한다.
 *
 * iterating 중에 리스트를 변경하는 것을 허용한다. 단, 현재 원소를 삭제하는 것은 예외이다.
 * 현재 노드를 삭제하면 그 이후에 iteration을 계속 진행할 수 있을지 확인해야 한다.
 * 인접 노드를 삭제하거나 추가하는 것도 조심해야 한다. 의도대로 동작하지 않을 수 있다.
 *
 * 참고: 굳이 별도의 구조체를 정의할 필요는 없었지만 일관성을 위해 별도의 구조체를 만들었다.
 */
typedef struct slist_iter
{
    slist_node *cur;
} slist_iter;

/*
 * iteration 과정에서 변경을 허용하는 singly linked list iterator.
 *
 * slist_foreach_modify()에서 사용한다. cur 멤버를 통해 현재 원소에 접근한다. 
 *
 * itration 중에 허용되는 변경은 slist_delete_current함수를 이용해서 현재 원소를 리스트에서 제거하는 것이다.
 * 인접 노드를 삭제하거나 현재 노드의 양 옆에 새로운 노드를 삽입하는 것은 안전하지 않다.
 */
typedef struct slist_mutable_iter
{
    slist_node *cur;            /* current element */
    slist_node *next;           /* next node we'll iterate to */
    slist_node *prev;           /* prev node, for deletions */
} slist_mutable_iter;


/* list node(고리)를 초기화하는 Static initializers */
#define DLIST_STATIC_INIT(name) {{&(name).head, &(name).head}}
#define DCLIST_STATIC_INIT(name) {{{&(name).dlist.head, &(name).dlist.head}}, 0}
#define SLIST_STATIC_INIT(name) {{NULL}}

inline 함수

• 대부분의 함수는 inline으로 정의되어 있고 일부 크기가 큰 함수들은 extern으로 프로토타입만 선언되어 있다
• slist_delete 함수와 디버깅 전용 함수가 extern으로 선언되어 있다

/* inline이 되기엔 너무 큰 함수들 */

/* 주의: 이 함수의 시간복잡도는 O(n)이다. 대신 slist_delete_current() 쓰자 */
extern void slist_delete(slist_head *head, const slist_node *node);

#ifdef ILIST_DEBUG
extern void dlist_member_check(const dlist_head *head, const dlist_node *node);
extern void dlist_check(const dlist_head *head);
extern void slist_check(const slist_head *head);
#else
/* 인자가 사용되지 않는다는 컴파일러의 경고를 없애기 위해 void로 변환한다. */
#define dlist_member_check(head, node) ((void) (head))
#define dlist_check(head)   ((void) (head))
#define slist_check(head)   ((void) (head))
#endif                          /* ILIST_DEBUG */

초기화 함수

/*
 * doubly linked list 초기화 함수. 개별 원소가 아닌 리스트를 초기화한다.
 * 정리를 하지 않았다면 이전 상태는 덮어써진다.
 */
static inline void
dlist_init(dlist_head *head)
{
    head->head.next = head->head.prev = &head->head;
}

/*
 * doubly linked list의 개별 list link를 초기화한다.
 *
 * 이 함수는 dlist_node_is_detached 함수가 필요한 경우에만 필요하다.
 */
static inline void
dlist_node_init(dlist_node *node)
{
    node->next = node->prev = NULL;
}

push

/*
 * 리스트의 맨 앞에 원소를 추가한다
 */
static inline void
dlist_push_head(dlist_head *head, dlist_node *node)
{
    if (head->head.next == NULL)    /* NULL로 초기화된 head인 경우 원형 구조로 바꾼다 */
        dlist_init(head);

    node->next = head->head.next;
    node->prev = &head->head;
    node->next->prev = node;
    head->head.next = node;

    dlist_check(head);
}

/*
 * 리스트의 맨 마지막에 노드를 추가한다.
 */
static inline void
dlist_push_tail(dlist_head *head, dlist_node *node)
{
    if (head->head.next == NULL)    /* NULL로 초기화된 head인 경우 원형 구조로 바꾼다 */
        dlist_init(head);

    node->next = &head->head;
    node->prev = head->head.prev;
    node->prev->next = node;
    head->head.prev = node;

    dlist_check(head);
}

insert

/*
 * after 노드 뒤에 노드 하나를 추가한다. 두 노드는 같은 리스트의 노드이다.
 */
static inline void
dlist_insert_after(dlist_node *after, dlist_node *node)
{
    node->prev = after;
    node->next = after->next;
    after->next = node;
    node->next->prev = node;
}

/*
 * 노드 하나를 before 노드 앞에 추가한다. 두 노드는 같은 리스트의 노드이다.
 */
static inline void
dlist_insert_before(dlist_node *before, dlist_node *node)
{
    node->prev = before->prev;
    node->next = before;
    before->prev = node;
    node->prev->next = node;
}

delete & pop

/*
 * node를 리스트에서 제거한다. 반드시 해당 노드는 리스트에 존재해야 한다.
 */
static inline void
dlist_delete(dlist_node *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

/*
 * dlist_delete 기능 + 제거한 노드의 next, prev를 NULL로 설정
 */
static inline void
dlist_delete_thoroughly(dlist_node *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
    node->next = NULL;
    node->prev = NULL;
}

/*
 * dlist_delete처럼 노드를 리스트에서 제거한다. 단, ILIST_DEBUG 빌드일 경우 
 노드가 진짜 해당 리스트(head)에 포함되는지 확인한다.
 */
static inline void
dlist_delete_from(dlist_head *head, dlist_node *node)
{
    dlist_member_check(head, node);
    dlist_delete(node);
}

/*
 * dlist_delete_from + 제거된 노드의 prev, next를 NULL로 설정
 */
static inline void
dlist_delete_from_thoroughly(dlist_head *head, dlist_node *node)
{
    dlist_member_check(head, node);
    dlist_delete_thoroughly(node);
}

/*
 * 리스트의 맨 처음 노드를 제거하고 반환한다. 
 * 리스트에 노드가 반드시 존재해야 한다.
 */
static inline dlist_node *
dlist_pop_head_node(dlist_head *head)
{
    dlist_node *node;

    Assert(!dlist_is_empty(head));
    node = head->head.next;
    dlist_delete(node);
    return node;
}

references

• src/include/lib/ilist.h
• PostgreSQL github repository
• inline function in C

---