kernel/data_structures/dlist.html · kernel/data_structures/dlist.rst 공식 원문 ↗

Zephyr 3.7.0 · Kernel · Data Structures

Double-linked List

목록 구조체 자체를 sentinel node로 사용하는 대칭 ring 설계로 모든 위치의 삽입과 제거를 일정하게 처리합니다.

Official pathkernel/data_structures/dlist.html
Source filekernel/data_structures/dlist.rst
Source versionZephyr 3.7.0
TranslationFull · reviewed

본문 기준: Zephyr 3.7.0 LTS3 · 이후 유지보수 패치는 별도입니다.

Part 1

요약·해설

Node마다 prev·next pointer를 두어 상수 시간 삽입·제거를 제공하며, N개 데이터 node와 목록 sentinel 하나가 N+1 ring을 이룹니다.

Node

prev · next

Mutation

O(1) insert · remove

Shape

N+1 sentinel ring

Part 2

접을 수 있는 영어 원문 전체

영어 원문 전체 펼치기
원문 SHA-256 F9E457B14BD0650B0EC4C0DFD5A2FD9050EC16C26682DF794F8864F7B731786D 
.. _dlist_api:

Double-linked List
==================

Similar to the single-linked list in many respects, Zephyr includes a
double-linked implementation.  This provides the same algorithmic
behavior for all the existing slist operations, but also allows for
constant-time removal and insertion (at all points: before or after
the head, tail or any internal node).  To do this, the list stores two
pointers per node, and thus has somewhat higher runtime code and
memory space needs.

A :c:type:`sys_dlist_t` struct may be instantiated by the user in any
accessible memory.  It must be initialized with :c:func:`sys_dlist_init`
or :c:macro:`SYS_DLIST_STATIC_INIT` before use.  The :c:type:`sys_dnode_t` struct
is expected to be provided by the user for any nodes added to the
list (typically embedded within the struct to be tracked, as described
above).  It must be initialized in zeroed/bss memory or with
:c:func:`sys_dnode_init` before use.

Primitive operations may retrieve the head/tail of a list and the
next/prev pointers of a node with :c:func:`sys_dlist_peek_head`,
:c:func:`sys_dlist_peek_tail`, :c:func:`sys_dlist_peek_next` and
:c:func:`sys_dlist_peek_prev`.  These can all return NULL where
appropriate (i.e. for empty lists, or nodes at the endpoints of the
list).

A dlist can be modified in constant time by removing a node with
:c:func:`sys_dlist_remove`, by adding a node to the head or tail of a list
with :c:func:`sys_dlist_prepend` and :c:func:`sys_dlist_append`, or by
inserting a node before an existing node with :c:func:`sys_dlist_insert`.

As for slist, each node in a dlist can be processed in a natural code
block style using :c:macro:`SYS_DLIST_FOR_EACH_NODE`.  This macro also
exists in a "FROM_NODE" form which allows for iterating from a known
starting point, a "SAFE" variant that allows for removing the node
being inspected within the code block, a "CONTAINER" style that
provides the pointer to a containing struct instead of the raw node,
and a "CONTAINER_SAFE" variant that provides both properties.

Convenience utilities provided by dlist include
:c:func:`sys_dlist_insert_at`, which inserts a node that linearly searches
through a list to find the right insertion point, which is provided by
the user as a C callback function pointer, and
:c:func:`sys_dnode_is_linked`, which will affirmatively return whether or
not a node is currently linked into a dlist or not (via an
implementation that has zero overhead vs. the normal list processing).

Double-linked List Internals
----------------------------

Internally, the dlist implementation is minimal: the :c:type:`sys_dlist_t`
struct contains "head" and "tail" pointer fields, the :c:type:`sys_dnode_t`
contains "prev" and "next" pointers, and no other data is stored.  But
in practice the two structs are internally identical, and the list
struct is inserted as a node into the list itself.  This allows for a
very clean symmetry of operations:

* An empty list has backpointers to itself in the list struct, which
  can be trivially detected.

* The head and tail of the list can be detected by comparing the
  prev/next pointers of a node vs. the list struct address.

* An insertion or deletion never needs to check for the special case
  of inserting at the head or tail.  There are never any NULL pointers
  within the list to be avoided.  Exactly the same operations are run,
  without tests or branches, for all list modification primitives.

Effectively, a dlist of N nodes can be thought of as a "ring" of "N+1"
nodes, where one node represents the list tracking struct.

.. figure:: ../../../../kernel/data_structures/dlist.png
    :align: center
    :alt: dlist example
    :figclass: align-center

    A dlist containing three elements.  Note that the list struct
    appears as a fourth "element" in the list.

.. figure:: ../../../../kernel/data_structures/dlist-single.png
    :align: center
    :alt: single-element dlist example
    :figclass: align-center

    An dlist containing just one element.

.. figure:: ../../../../kernel/data_structures/dlist-empty.png
    :align: center
    :alt: dlist example
    :figclass: align-center

    An empty dlist.


Doubly-linked List API Reference
--------------------------------

.. doxygengroup:: doubly-linked-list_apis

Part 3

한국어 전문 번역

Zephyr의 double-linked list는 single-linked list와 여러 면에서 비슷합니다. 기존 slist 연산과 같은 algorithmic behavior를 제공하면서도 head, tail, 내부 node의 앞이나 뒤 어디서든 상수 시간에 제거·삽입할 수 있습니다. 이를 위해 node마다 pointer 두 개를 저장하므로 runtime code와 메모리가 조금 더 필요합니다.

사용자는 접근 가능한 임의 메모리에 sys_dlist_t 구조체를 만들 수 있습니다. 사용 전에 sys_dlist_init() 또는 SYS_DLIST_STATIC_INIT으로 초기화해야 합니다. 목록에 추가할 각 node의 sys_dnode_t 구조체도 사용자가 제공하며, 보통 추적할 구조체 안에 넣습니다. Node는 zeroed/BSS memory에 있거나 sys_dnode_init()으로 초기화되어야 합니다.

sys_dlist_peek_head(), sys_dlist_peek_tail(), sys_dlist_peek_next(), sys_dlist_peek_prev()로 head·tail과 node의 next·prev pointer를 얻을 수 있습니다. 빈 목록이나 끝점 node처럼 적절한 경우 NULL을 반환할 수 있습니다.

sys_dlist_remove()로 node를 제거하고, sys_dlist_prepend()와 sys_dlist_append()로 head·tail에 node를 추가하며, sys_dlist_insert()로 기존 node 앞에 삽입하는 모든 변경은 상수 시간에 수행됩니다.

SYS_DLIST_FOR_EACH_NODE로 각 node를 자연스러운 code block 형식에서 처리할 수 있습니다. 알려진 시작점부터 순회하는 FROM_NODE, 검사 중인 node를 제거해도 되는 SAFE, raw node 대신 포함 구조체 pointer를 주는 CONTAINER, 두 속성을 함께 주는 CONTAINER_SAFE 변형도 있습니다.

sys_dlist_insert_at()은 사용자가 C callback function pointer로 제공한 삽입 조건에 맞는 위치를 찾기 위해 목록을 선형 검색합니다. sys_dnode_is_linked()는 정상 목록 처리와 비교해 overhead 없이 node가 현재 dlist에 연결되어 있는지 확인합니다.

Double-linked list 내부 구조

sys_dlist_t에는 head와 tail pointer field, sys_dnode_t에는 prev와 next pointer만 있으며 다른 데이터는 저장하지 않습니다. 실제로 두 구조체는 내부적으로 같고 목록 구조체 자체가 node처럼 목록에 들어갑니다. 이 설계는 다음과 같은 대칭성을 만듭니다.

  • 빈 목록은 목록 구조체 안에서 자기 자신을 가리키는 backpointer를 가지므로 쉽게 감지할 수 있습니다.
  • Node의 prev·next pointer를 목록 구조체 주소와 비교하면 head와 tail을 판별할 수 있습니다.
  • 삽입·삭제 시 head나 tail이라는 특수 경우를 검사할 필요가 없습니다. 목록 내부에는 피해야 할 NULL pointer가 없으며 모든 목록 변경 primitive가 검사나 branch 없이 같은 연산을 실행합니다.

Node가 N개인 dlist는 N+1개 node로 구성된 ring으로 생각할 수 있으며, 추가 node 하나가 목록 추적 구조체를 나타냅니다.

목록 구조체와 세 node로 이루어진 double-linked list ring
Element 세 개를 담은 dlist. 목록 구조체가 네 번째 element처럼 나타납니다.
목록 구조체와 node 하나로 이루어진 double-linked list ring
Element 하나만 담은 dlist.
자기 자신을 가리키는 빈 double-linked list
빈 dlist.

Double-linked list API 참고

API group doubly-linked-list_apis은 inline macro와 function으로 구현한 double-linked list API입니다. Thread-safe하지 않으므로 thread 사이에서 목록을 공유하면 함수 호출을 synchronization primitive로 보호해야 합니다. Head와 tail pointer가 목록 자체를 가리키도록 초기화하면 node 추가와 제거가 단순해집니다.

매크로와 정의

SYS_DLIST_FOR_EACH_NODE(__dl, __dn)

목록을 순회하는 기본 primitive입니다. 안전하지 않은 loop이므로 __dn을 제거하면 안 됩니다. 사용자가 loop 본문 중괄호를 추가해야 하며 다른 SYS_DLIST_* macro와 마찬가지로 thread-safe하지 않습니다.

SYS_DLIST_FOR_EACH_NODE(l, n) {
    <user code>
}

매개변수

  • __dl: 순회할 sys_dlist_t pointer
  • __dn: 각 node를 가리킬 sys_dnode_t pointer
SYS_DLIST_ITERATE_FROM_NODE(__dl, __dn)

목록의 특정 node부터 순회합니다. __dn을 제거하면 안 됩니다. __dn이 NULL이면 head부터 시작하며 thread-safe하지 않습니다.

SYS_DLIST_ITERATE_FROM_NODE(l, n) {
    <user code>
}

매개변수

  • __dl: 순회할 sys_dlist_t pointer
  • __dn: 시작 node 또는 head부터 시작할 때 NULL인 sys_dnode_t pointer
SYS_DLIST_FOR_EACH_NODE_SAFE(__dl, __dn, __dns)

목록을 안전하게 순회합니다. 검사 중인 __dn을 제거해도 loop가 깨지지 않습니다. Thread-safe하다는 뜻은 아닙니다.

SYS_DLIST_FOR_EACH_NODE_SAFE(l, n, s) {
    <user code>
}

매개변수

  • __dl: 순회할 sys_dlist_t pointer
  • __dn: 각 node를 가리킬 sys_dnode_t pointer
  • __dns: loop를 안전하게 이어 갈 sys_dnode_t pointer
SYS_DLIST_CONTAINER(__dn, __cn, __n)

목록 node를 포함하는 container를 구합니다. NULL node에도 안전합니다.

매개변수

  • __dn: container를 구할 sys_dnode_t pointer
  • __cn: container 구조체 형식 pointer
  • __n: container 구조체 안의 sys_dnode_t field 이름
SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n)

목록 head를 포함하는 container를 확인합니다.

매개변수

  • __dl: 확인할 sys_dlist_t pointer
  • __cn: container 구조체 형식 pointer
  • __n: container 안의 sys_dnode_t field 이름
SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n)

다음 container를 확인합니다.

매개변수

  • __dl: 확인할 sys_dlist_t pointer
  • __cn: container 구조체 형식 pointer
  • __n: container 안의 sys_dnode_t field 이름
SYS_DLIST_FOR_EACH_CONTAINER(__dl, __cn, __n)

Container 단위로 목록을 순회합니다. 안전하지 않은 loop이므로 __cn을 분리하면 안 됩니다.

SYS_DLIST_FOR_EACH_CONTAINER(l, c, n) {
    <user code>
}

매개변수

  • __dl: 순회할 sys_dlist_t pointer
  • __cn: 각 항목을 가리킬 container 구조체 형식 pointer
  • __n: container 안의 sys_dnode_t field 이름
SYS_DLIST_FOR_EACH_CONTAINER_SAFE(__dl, __cn, __cns, __n)

Container 단위로 안전하게 순회합니다. 검사 중인 __cn을 분리해도 loop가 깨지지 않습니다.

SYS_DLIST_FOR_EACH_CONTAINER_SAFE(l, c, cn, n) {
    <user code>
}

매개변수

  • __dl: 순회할 sys_dlist_t pointer
  • __cn: 각 항목을 가리킬 container 구조체 형식 pointer
  • __cns: loop를 안전하게 이어 갈 container pointer
  • __n: container 안의 sys_dnode_t field 이름
SYS_DLIST_STATIC_INIT(ptr_to_list)

Double-linked list의 정적 initializer입니다.

형식 별칭

typedef struct _dnode sys_dlist_t

Double-linked list 구조체입니다.

typedef struct _dnode sys_dnode_t

Double-linked list node 구조체입니다.

함수

static inline void sys_dlist_init(sys_dlist_t *list)

목록을 빈 상태로 초기화합니다.

매개변수

  • list: double-linked list
static inline void sys_dnode_init(sys_dnode_t *node)

Node를 어떤 목록에도 속하지 않은 상태로 초기화합니다.

매개변수

  • node: 초기화할 node
static inline bool sys_dnode_is_linked(const sys_dnode_t *node)

Node가 어떤 목록의 member인지 확인합니다.

매개변수

  • node: 확인할 node

반환값: 목록에 연결되어 있으면 true, 아니면 false입니다.

static inline bool sys_dlist_is_head(sys_dlist_t *list, sys_dnode_t *node)

Node가 목록 head인지 확인합니다.

매개변수

  • list: 대상 double-linked list
  • node: 확인할 node

반환값: Head이면 true, 아니면 false입니다.

static inline bool sys_dlist_is_tail(sys_dlist_t *list, sys_dnode_t *node)

Node가 목록 tail인지 확인합니다.

매개변수

  • list: 대상 double-linked list
  • node: 확인할 node

반환값: Tail이면 true, 아니면 false입니다.

static inline bool sys_dlist_is_empty(sys_dlist_t *list)

목록이 비었는지 확인합니다.

매개변수

  • list: 대상 double-linked list

반환값: 비었으면 true, 아니면 false입니다.

static inline bool sys_dlist_has_multiple_nodes(sys_dlist_t *list)

Node가 둘 이상인지 확인합니다. 다른 sys_dlist_* 함수와 마찬가지로 thread-safe하지 않습니다.

매개변수

  • list: 대상 double-linked list

반환값: Node가 여러 개면 true, 아니면 false입니다.

static inline sys_dnode_t *sys_dlist_peek_head(sys_dlist_t *list)

목록 head 항목을 얻습니다.

매개변수

  • list: 대상 double-linked list

반환값: Head element pointer이며 빈 목록이면 NULL입니다.

static inline sys_dnode_t *sys_dlist_peek_head_not_empty(sys_dlist_t *list)

목록이 비어 있지 않다는 전제에서 head 항목을 얻습니다.

매개변수

  • list: 대상 double-linked list

반환값: Head element pointer입니다.

static inline sys_dnode_t *sys_dlist_peek_next_no_check(sys_dlist_t *list, sys_dnode_t *node)

Node가 NULL이 아님을 알고 있을 때 다음 항목을 더 빠르게 얻습니다.

매개변수

  • list: 대상 double-linked list
  • node: 다음 element를 찾을 기준 node

반환값: 다음 element pointer이며 node가 tail이면 NULL입니다.

static inline sys_dnode_t *sys_dlist_peek_next(sys_dlist_t *list, sys_dnode_t *node)

목록의 다음 항목을 얻습니다.

매개변수

  • list: 대상 double-linked list
  • node: 다음 element를 찾을 기준 node

반환값: 다음 element pointer입니다. Node가 tail이거나, 빈 목록 head를 읽어 얻은 node가 NULL이면 NULL입니다.

static inline sys_dnode_t *sys_dlist_peek_prev_no_check(sys_dlist_t *list, sys_dnode_t *node)

Node가 NULL이 아님을 알고 있을 때 이전 항목을 더 빠르게 얻습니다.

매개변수

  • list: 대상 double-linked list
  • node: 이전 element를 찾을 기준 node

반환값: 이전 element pointer이며 공식 문서상 node가 tail이면 NULL입니다.

static inline sys_dnode_t *sys_dlist_peek_prev(sys_dlist_t *list, sys_dnode_t *node)

목록의 이전 항목을 얻습니다.

매개변수

  • list: 대상 double-linked list
  • node: 이전 element를 찾을 기준 node

반환값: 이전 element pointer입니다. 공식 문서상 node가 tail이거나, 빈 목록 head를 읽어 얻은 node가 NULL이면 NULL입니다.

static inline sys_dnode_t *sys_dlist_peek_tail(sys_dlist_t *list)

목록 tail 항목을 얻습니다.

매개변수

  • list: 대상 double-linked list

반환값: Tail element pointer이며 빈 목록이면 NULL입니다.

static inline void sys_dlist_append(sys_dlist_t *list, sys_dnode_t *node)

Node를 목록 tail에 추가합니다. Thread-safe하지 않습니다.

매개변수

  • list: 대상 double-linked list
  • node: 추가할 element
static inline void sys_dlist_prepend(sys_dlist_t *list, sys_dnode_t *node)

Node를 목록 head에 추가합니다. Thread-safe하지 않습니다.

매개변수

  • list: 대상 double-linked list
  • node: 추가할 element
static inline void sys_dlist_insert(sys_dnode_t *successor, sys_dnode_t *node)

지정한 successor node 앞에 node를 삽입합니다.

매개변수

  • successor: node를 삽입할 위치의 다음 node
  • node: 삽입할 element
static inline void sys_dlist_insert_at(sys_dlist_t *list, sys_dnode_t *node, int (*cond)(sys_dnode_t *node, void *data), void *data)

외부 조건에 따라 정한 위치에 node를 삽입합니다. cond()는 새 node를 현재 검사 중인 node 앞에 넣어야 하는지 판단합니다. Thread-safe하지 않습니다.

매개변수

  • list: 대상 double-linked list
  • node: 삽입할 element
  • cond: 현재 node가 올바른 삽입 지점인지 결정하는 함수
  • data: cond()에 전달할 매개변수
static inline void sys_dlist_remove(sys_dnode_t *node)

특정 node를 목록에서 제거합니다. 목록은 node를 통해 암시되며 node는 반드시 목록에 속해 있어야 합니다. Thread-safe하지 않습니다.

매개변수

  • node: 제거할 node
static inline sys_dnode_t *sys_dlist_get(sys_dlist_t *list)

목록의 첫 node를 꺼냅니다. Thread-safe하지 않습니다.

매개변수

  • list: 대상 double-linked list

반환값: 첫 node이며 빈 목록이면 NULL입니다.

static inline size_t sys_dlist_len(sys_dlist_t *list)

O(n) 시간에 목록 크기를 계산합니다.

매개변수

  • list: 목록 pointer

반환값: 목록 크기와 같은 정수이며 비었으면 0입니다.

Source

출처

영어 원문에는 문단, 문서 지시문, 표, 코드, 코드 심벌, 경로를 그대로 보존했습니다.