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

Zephyr 3.7.0 · Kernel · Data Structures

Single-linked List

Head·tail pointer와 node당 next pointer 하나로 상수 시간 끝점 연산을 제공하는 allocation-free 연결 리스트입니다.

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

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

Part 1

요약·해설

Slist는 intrusive node를 사용자 구조체에 embed하고, sflist는 정렬로 비는 pointer 하위 bit에 flag를 결합해 추가 SRAM 없이 metadata를 보존합니다.

Slist node

1 next pointer

List

head · tail

Sflist

pointer flags

Part 2

접을 수 있는 영어 원문 전체

영어 원문 전체 펼치기
원문 SHA-256 FFAC34E101924B2DED0445C04A8B6E99D269ADF764EC5A13D6E3DE5A08535D2F 
.. _slist_api:

Single-linked List
==================

Zephyr provides a :c:type:`sys_slist_t` type for storing simple
singly-linked list data (i.e. data where each list element stores a
pointer to the next element, but not the previous one).  This supports
constant-time access to the first (head) and last (tail) elements of
the list, insertion before the head and after the tail of the list and
constant time removal of the head.  Removal of subsequent nodes
requires access to the "previous" pointer and thus can only be
performed in linear time by searching the list.

The :c:type:`sys_slist_t` struct may be instantiated by the user in any
accessible memory.  It should be initialized with either
:c:func:`sys_slist_init` or by static assignment from SYS_SLIST_STATIC_INIT
before use.  Its interior fields are opaque and should not be accessed
by user code.

The end nodes of a list may be retrieved with
:c:func:`sys_slist_peek_head` and :c:func:`sys_slist_peek_tail`, which will
return NULL if the list is empty, otherwise a pointer to a
:c:type:`sys_snode_t` struct.

The :c:type:`sys_snode_t` struct represents the data to be inserted.  In
general, it is expected to be allocated/controlled by the user,
usually embedded within a struct which is to be added to the list.
The container struct pointer may be retrieved from a list node using
:c:macro:`SYS_SLIST_CONTAINER`, passing it the struct name of the
containing struct and the field name of the node.  Internally, the
:c:type:`sys_snode_t` struct contains only a next pointer, which may be
accessed with :c:func:`sys_slist_peek_next`.

Lists may be modified by adding a single node at the head or tail with
:c:func:`sys_slist_prepend` and :c:func:`sys_slist_append`.  They may also
have a node added to an interior point with :c:func:`sys_slist_insert`,
which inserts a new node after an existing one.  Similarly
:c:func:`sys_slist_remove` will remove a node given a pointer to its
predecessor.  These operations are all constant time.

Convenience routines exist for more complicated modifications to a
list.  :c:func:`sys_slist_merge_slist` will append an entire list to an
existing one.  :c:func:`sys_slist_append_list` will append a bounded
subset of an existing list in constant time.  And
:c:func:`sys_slist_find_and_remove` will search a list (in linear time)
for a given node and remove it if present.

Finally the slist implementation provides a set of "for each" macros
that allows for iterating over a list in a natural way without needing
to manually traverse the next pointers.  :c:macro:`SYS_SLIST_FOR_EACH_NODE`
will enumerate every node in a list given a local variable to store
the node pointer.  :c:macro:`SYS_SLIST_FOR_EACH_NODE_SAFE` behaves
similarly, but has a more complicated implementation that requires an
extra scratch variable for storage and allows the user to delete the
iterated node during the iteration.  Each of those macros also exists
in a "container" variant (:c:macro:`SYS_SLIST_FOR_EACH_CONTAINER` and
:c:macro:`SYS_SLIST_FOR_EACH_CONTAINER_SAFE`) which assigns a local
variable of a type that matches the user's container struct and not
the node struct, performing the required offsets internally.  And
:c:macro:`SYS_SLIST_ITERATE_FROM_NODE` exists to allow for enumerating a
node and all its successors only, without inspecting the earlier part
of the list.

Single-linked List Internals
----------------------------

The slist code is designed to be minimal and conventional.
Internally, a :c:type:`sys_slist_t` struct is nothing more than a pair of
"head" and "tail" pointer fields.  And a :c:type:`sys_snode_t` stores only a
single "next" pointer.

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

    An slist containing three elements.

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

    An empty slist

The specific implementation of the list code, however, is done with an
internal "Z_GENLIST" template API which allows for extracting those
fields from arbitrary structures and emits an arbitrarily named set of
functions.  This allows for implementing more complicated
single-linked list variants using the same basic primitives.  The
genlist implementor is responsible for a custom implementation of the
primitive operations only: an "init" step for each struct, and a "get"
and "set" primitives for each of head, tail and next pointers on their
relevant structs.  These inline functions are passed as parameters to
the genlist macro expansion.

Only one such variant, sflist, exists in Zephyr at the moment.


Flagged List
------------

The :c:type:`sys_sflist_t` is implemented using the described genlist
template API.  With the exception of symbol naming ("sflist" instead
of "slist") and the additional API described next, it operates in all
ways identically to the slist API.

It adds the ability to associate exactly two bits of user defined
"flags" with each list node.  These can be accessed and modified with
:c:func:`sys_sfnode_flags_get` and :c:func:`sys_sfnode_flags_set`.
Internally, the flags are stored unioned with the bottom bits of the
next pointer and incur no SRAM storage overhead when compared with the
simpler slist code.


Single-linked List API Reference
--------------------------------

.. doxygengroup:: single-linked-list_apis

Flagged List API Reference
--------------------------------

.. doxygengroup:: flagged-single-linked-list_apis

Part 3

한국어 전문 번역

Zephyr는 단순 singly-linked list data를 저장하는 sys_slist_t 형식을 제공합니다. 각 list element는 다음 element pointer만 저장하고 이전 element pointer는 저장하지 않습니다.

List의 첫 element(head)와 마지막 element(tail)는 상수 시간에 접근할 수 있습니다. Head 앞과 tail 뒤 삽입, head 제거도 상수 시간입니다. 그 뒤 node를 제거하려면 이전 node pointer가 필요하므로, 이를 모르면 list를 선형 검색해야 합니다.

sys_slist_t 구조체는 사용자가 접근할 수 있는 어느 memory에나 둘 수 있습니다. 사용 전에 sys_slist_init() 또는 SYS_SLIST_STATIC_INIT 정적 대입으로 초기화해야 합니다. 내부 field는 opaque이므로 사용자 code가 직접 접근하면 안 됩니다.

sys_slist_peek_head()와 sys_slist_peek_tail()로 양 끝 node를 얻습니다. List가 비었으면 NULL, 아니면 sys_snode_t pointer를 반환합니다.

sys_snode_t는 삽입할 data를 표현하는 intrusive node입니다. 보통 사용자가 소유·할당하는 구조체 안에 이 node를 embed합니다. SYS_SLIST_CONTAINER에 container 구조체 형식과 node field 이름을 넘기면 node에서 container pointer를 되찾을 수 있습니다. Node 내부에는 next pointer 하나만 있고 sys_slist_peek_next()로 접근합니다.

sys_slist_prepend()와 sys_slist_append()는 head 또는 tail에 node 하나를 추가합니다. sys_slist_insert()는 기존 node 다음 내부 위치에 삽입하고, sys_slist_remove()는 predecessor pointer를 받아 node를 제거합니다. 이전 node를 이미 알고 있다면 모두 상수 시간입니다.

sys_slist_merge_slist()는 list 전체를 기존 list 뒤에 붙입니다. sys_slist_append_list()는 기존 list의 head·tail로 경계가 정해진 subset을 상수 시간에 붙입니다. sys_slist_find_and_remove()는 node를 선형 시간에 검색해 있으면 제거합니다.

직접 next pointer를 따라가지 않아도 자연스럽게 순회할 수 있는 for-each macro도 제공합니다. SYS_SLIST_FOR_EACH_NODE는 모든 node를 지역 node pointer에 차례로 넣습니다. SYS_SLIST_FOR_EACH_NODE_SAFE는 scratch variable이 하나 더 필요하지만 순회 중 현재 node를 제거할 수 있습니다.

SYS_SLIST_FOR_EACH_CONTAINER와 SYS_SLIST_FOR_EACH_CONTAINER_SAFE는 raw node 대신 사용자 container 형식의 지역 variable을 설정하고 필요한 offset을 내부에서 계산합니다. SYS_SLIST_ITERATE_FROM_NODE는 list 앞부분을 보지 않고 지정 node와 그 successor만 열거할 때 사용합니다.

Single-linked List 내부 구조

Slist code는 작고 전통적인 구조를 목표로 합니다. 내부에서 sys_slist_t는 head와 tail pointer 두 개뿐이고, sys_snode_t는 next pointer 하나뿐입니다.

세 element를 가진 Zephyr slist 구조
세 element를 가진 slist. List는 head와 tail을 가리키고 각 node는 다음 node 하나만 가리킵니다.
비어 있는 Zephyr slist 구조
비어 있는 slist에서는 head와 tail이 모두 NULL입니다.

실제 list code는 내부 Z_GENLIST template API로 구현됩니다. 이 template은 임의 구조체에서 head·tail·next field를 추출하고 이름을 자유롭게 정한 함수 집합을 생성합니다. 같은 기본 primitive로 더 복잡한 single-linked list 변형을 만들 수 있습니다.

Genlist 구현자는 각 struct의 init, 관련 struct에서 head·tail·next pointer를 읽고 쓰는 primitive만 맞춤 구현합니다. 이 inline function들이 genlist macro expansion의 parameter로 전달됩니다.

현재 Zephyr에서 이 template을 쓰는 변형은 sflist 하나뿐입니다.

Flagged List

sys_sflist_t는 위 genlist template API로 구현합니다. Symbol 이름이 slist 대신 sflist이고 아래 추가 API가 있다는 점을 빼면 slist API와 완전히 같은 방식으로 동작합니다.

각 list node에 사용자가 정의하는 flag bit를 연관할 수 있습니다. 본문 설명은 정확히 2 bit라고 정의하며 sys_sfnode_flags_get()과 sys_sfnode_flags_set()으로 읽고 씁니다. 생성 API의 architecture별 범위는 32-bit에서 0~3, 64-bit에서 0~7이라고 따로 명시합니다.

Flag는 next pointer의 하위 bit와 union해 저장하므로 단순 slist와 비교해 추가 SRAM 없이 metadata를 보존합니다. Node를 제거하거나 다른 sflist로 옮겨도 flag 값은 유지됩니다.

Single-linked List API 참고

single-linked-list_apis는 inline macro와 function으로 singly-linked list를 구현합니다. 이 API는 thread-safe하지 않습니다. 여러 thread가 같은 list를 사용한다면 synchronization primitive로 함수 호출을 보호해야 합니다.

매크로와 정의

SYS_SLIST_FOR_EACH_NODE(__sl, __sn)

List의 각 node를 순회하는 기본 매크로입니다. 이 순회는 안전 변형이 아니므로 순회 중 __sn을 제거하면 안 됩니다. 사용자는 매크로 뒤에 자신의 코드를 감싸는 중괄호를 반드시 추가해야 합니다.

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

매개변수

  • __sl: 순회할 sys_slist_t pointer
  • __sn: 각 node를 가리킬 sys_snode_t pointer
SYS_SLIST_ITERATE_FROM_NODE(__sl, __sn)

List 안의 지정 node에서 시작해 뒤쪽을 순회합니다. 안전 변형이 아니므로 순회 중 __sn을 제거하면 안 됩니다. __sn이 NULL이면 head에서 시작합니다.

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

매개변수

  • __sl: 순회할 sys_slist_t pointer
  • __sn: 시작 node 또는 head에서 시작할 때 NULL인 sys_snode_t pointer
SYS_SLIST_FOR_EACH_NODE_SAFE(__sl, __sn, __sns)

현재 node를 제거해도 loop가 깨지지 않도록 다음 node를 scratch variable에 미리 보관하며 안전하게 순회합니다.

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

매개변수

  • __sl: 순회할 sys_slist_t pointer
  • __sn: 현재 node pointer
  • __sns: 안전 순회를 위한 다음 node scratch pointer
SYS_SLIST_CONTAINER(__ln, __cn, __n)

List node를 포함한 container의 pointer를 구합니다. NULL node에도 안전하게 사용할 수 있습니다.

매개변수

  • __ln: container를 구할 sys_snode_t pointer
  • __cn: container struct type pointer
  • __n: container 안 sys_snode_t field 이름
SYS_SLIST_PEEK_HEAD_CONTAINER(__sl, __cn, __n)

List head node를 포함한 container를 확인하되 제거하지 않습니다.

매개변수

  • __sl: 확인할 sys_slist_t pointer
  • __cn: container struct type pointer
  • __n: container 안 node field 이름
SYS_SLIST_PEEK_TAIL_CONTAINER(__sl, __cn, __n)

List tail node를 포함한 container를 확인하되 제거하지 않습니다.

매개변수

  • __sl: 확인할 sys_slist_t pointer
  • __cn: container struct type pointer
  • __n: container 안 node field 이름
SYS_SLIST_PEEK_NEXT_CONTAINER(__cn, __n)

현재 container 다음에 연결된 node의 container를 확인합니다.

매개변수

  • __cn: 현재 container struct type pointer
  • __n: container 안 node field 이름
SYS_SLIST_FOR_EACH_CONTAINER(__sl, __cn, __n)

Raw node가 아니라 node를 포함한 container pointer로 list를 순회합니다. 안전 변형이 아니므로 순회 중 __cn을 list에서 떼면 안 됩니다.

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

매개변수

  • __sl: 순회할 sys_slist_t pointer
  • __cn: 각 항목을 가리킬 container pointer
  • __n: container 안 node field 이름
SYS_SLIST_FOR_EACH_CONTAINER_SAFE(__sl, __cn, __cns, __n)

현재 container를 list에서 떼어도 loop가 깨지지 않도록 scratch pointer를 사용해 container 단위로 안전하게 순회합니다.

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

매개변수

  • __sl: 순회할 sys_slist_t pointer
  • __cn: 현재 container pointer
  • __cns: 안전 순회용 다음 container pointer
  • __n: container 안 node field 이름
SYS_SLIST_STATIC_INIT(ptr_to_list)

Single-linked list를 compile time에 정적으로 초기화합니다.

매개변수

  • ptr_to_list: 초기화할 list pointer

형식 별칭

typedef struct _snode sys_snode_t

Single-linked list node 구조체 형식입니다.

typedef struct _slist sys_slist_t

Single-linked list 구조체 형식입니다.

함수

static inline void sys_slist_init(sys_slist_t *list)

List를 빈 상태로 초기화합니다.

매개변수

  • list: 초기화할 list pointer
static inline sys_snode_t *sys_slist_peek_head(sys_slist_t *list)

첫 node를 제거하지 않고 확인합니다.

매개변수

  • list: 확인할 list pointer

반환값: 첫 node pointer이며 비었으면 NULL입니다.

static inline sys_snode_t *sys_slist_peek_tail(sys_slist_t *list)

마지막 node를 제거하지 않고 확인합니다.

매개변수

  • list: 확인할 list pointer

반환값: 마지막 node pointer이며 비었으면 NULL입니다.

static inline bool sys_slist_is_empty(sys_slist_t *list)

List가 비었는지 검사합니다.

매개변수

  • list: 검사할 list pointer

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

static inline sys_snode_t *sys_slist_peek_next_no_check(sys_snode_t *node)

현재 node가 NULL이 아님을 이미 알고 있을 때 다음 node를 빠르게 확인합니다.

매개변수

  • node: 현재 node pointer

반환값: 다음 node pointer이며 없으면 NULL입니다.

static inline sys_snode_t *sys_slist_peek_next(sys_snode_t *node)

현재 node 다음 node를 확인합니다.

매개변수

  • node: 현재 node pointer

반환값: 다음 node pointer이며 없으면 NULL입니다.

static inline void sys_slist_prepend(sys_slist_t *list, sys_snode_t *node)

Node를 list head 앞에 추가합니다. 이 API는 thread-safe하지 않습니다. 여러 thread가 같은 list를 사용한다면 synchronization primitive로 함수 호출을 보호해야 합니다.

매개변수

  • list: 변경할 list pointer
  • node: 앞에 추가할 node pointer
static inline void sys_slist_append(sys_slist_t *list, sys_snode_t *node)

Node를 list tail 뒤에 추가합니다. 이 API는 thread-safe하지 않습니다. 여러 thread가 같은 list를 사용한다면 synchronization primitive로 함수 호출을 보호해야 합니다.

매개변수

  • list: 변경할 list pointer
  • node: 뒤에 추가할 node pointer
static inline void sys_slist_append_list(sys_slist_t *list, void *head, void *tail)

첫 field가 next pointer인 NULL 종료 singly-linked node 범위를 list 뒤에 붙입니다. 이 API는 thread-safe하지 않습니다. 여러 thread가 같은 list를 사용한다면 synchronization primitive로 함수 호출을 보호해야 합니다.

매개변수

  • list: 변경할 list pointer
  • head: 붙일 범위의 첫 element pointer
  • tail: 붙일 범위의 마지막 element pointer
static inline void sys_slist_merge_slist(sys_slist_t *list, sys_slist_t *list_to_append)

두 slist를 합쳐 두 번째 list 전체를 첫 번째 list 뒤에 붙입니다. 완료되면 두 번째 list는 비게 됩니다. 이 API는 thread-safe하지 않습니다. 여러 thread가 같은 list를 사용한다면 synchronization primitive로 함수 호출을 보호해야 합니다.

매개변수

  • list: 변경할 첫 번째 list pointer
  • list_to_append: 붙인 뒤 비게 되는 두 번째 list pointer
static inline void sys_slist_insert(sys_slist_t *list, sys_snode_t *prev, sys_snode_t *node)

지정한 이전 node 다음에 새 node를 삽입합니다. 이 API는 thread-safe하지 않습니다. 여러 thread가 같은 list를 사용한다면 synchronization primitive로 함수 호출을 보호해야 합니다.

매개변수

  • list: 변경할 list pointer
  • prev: 이전 node pointer
  • node: 삽입할 node pointer
static inline sys_snode_t *sys_slist_get_not_empty(sys_slist_t *list)

비어 있지 않다고 이미 알고 있는 list에서 첫 node를 가져와 제거합니다. 이 API는 thread-safe하지 않습니다. 여러 thread가 같은 list를 사용한다면 synchronization primitive로 함수 호출을 보호해야 합니다.

매개변수

  • list: 변경할 list pointer

반환값: 기존 첫 node pointer입니다.

static inline sys_snode_t *sys_slist_get(sys_slist_t *list)

List에서 첫 node를 가져와 제거합니다. 이 API는 thread-safe하지 않습니다. 여러 thread가 같은 list를 사용한다면 synchronization primitive로 함수 호출을 보호해야 합니다.

매개변수

  • list: 변경할 list pointer

반환값: 기존 첫 node pointer이며 비었으면 NULL입니다.

static inline void sys_slist_remove(sys_slist_t *list, sys_snode_t *prev_node, sys_snode_t *node)

알고 있는 predecessor를 이용해 node를 제거합니다. Head를 제거할 때 prev_node는 NULL일 수 있습니다. 이 API는 thread-safe하지 않습니다. 여러 thread가 같은 list를 사용한다면 synchronization primitive로 함수 호출을 보호해야 합니다.

매개변수

  • list: 변경할 list pointer
  • prev_node: 이전 node pointer 또는 head 제거 시 NULL
  • node: 제거할 node pointer
static inline bool sys_slist_find_and_remove(sys_slist_t *list, sys_snode_t *node)

List를 검색해 지정 node가 있으면 제거합니다. 검색 때문에 O(n) 시간이 듭니다. 이 API는 thread-safe하지 않습니다. 여러 thread가 같은 list를 사용한다면 synchronization primitive로 함수 호출을 보호해야 합니다.

매개변수

  • list: 변경할 list pointer
  • node: 검색해 제거할 node pointer

반환값: Node를 제거했으면 true입니다.

static inline bool sys_slist_find(sys_slist_t *list, sys_snode_t *node, sys_snode_t **prev)

Node가 singly-linked list에 연결되어 있는지 검색하고 predecessor도 돌려줍니다. 이 API는 thread-safe하지 않습니다. 여러 thread가 같은 list를 사용한다면 synchronization primitive로 함수 호출을 보호해야 합니다.

매개변수

  • list: 검사할 list pointer
  • node: 검색할 node pointer
  • prev: [out] 이전 node pointer를 받을 위치

반환값: 찾았으면 true, 아니면 false입니다.

static inline size_t sys_slist_len(sys_slist_t *list)

주어진 list 길이를 O(n) 시간에 계산합니다.

매개변수

  • list: 검사할 list pointer

반환값: List 크기이며 비었으면 0입니다.

Flagged List API 참고

flagged-single-linked-list_apis는 pointer 하위 bit에 사용자 flag를 저장하는 singly-linked list API입니다. 기본 연산과 동시성 조건은 slist와 같습니다.

매크로와 정의

SYS_SFLIST_FOR_EACH_NODE(__sl, __sn)

Flagged list의 각 node를 순회합니다. 안전 변형이 아니므로 순회 중 __sn을 제거하면 안 됩니다.

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

매개변수

  • __sl: 순회할 sys_sflist_t pointer
  • __sn: 각 node를 가리킬 sys_sfnode_t pointer
SYS_SFLIST_ITERATE_FROM_NODE(__sl, __sn)

Flagged list 안 지정 node에서 시작해 뒤쪽을 순회합니다. __sn이 NULL이면 head에서 시작합니다.

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

매개변수

  • __sl: 순회할 sys_sflist_t pointer
  • __sn: 시작 node 또는 NULL
SYS_SFLIST_FOR_EACH_NODE_SAFE(__sl, __sn, __sns)

현재 flagged node를 제거해도 loop가 깨지지 않게 다음 node를 미리 보관하며 순회합니다.

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

매개변수

  • __sl: 순회할 sys_sflist_t pointer
  • __sn: 현재 node pointer
  • __sns: 다음 node scratch pointer
SYS_SFLIST_CONTAINER(__ln, __cn, __n)

Flagged list node를 포함한 container pointer를 구합니다. NULL node에도 안전합니다.

매개변수

  • __ln: container를 구할 sys_sfnode_t pointer
  • __cn: container struct type pointer
  • __n: container 안 sys_sfnode_t field 이름
SYS_SFLIST_PEEK_HEAD_CONTAINER(__sl, __cn, __n)

Flagged list의 head container를 제거하지 않고 확인합니다.

매개변수

  • __sl: 확인할 sys_sflist_t pointer
  • __cn: container struct type pointer
  • __n: container 안 node field 이름
SYS_SFLIST_PEEK_TAIL_CONTAINER(__sl, __cn, __n)

Flagged list의 tail container를 제거하지 않고 확인합니다.

매개변수

  • __sl: 확인할 sys_sflist_t pointer
  • __cn: container struct type pointer
  • __n: container 안 node field 이름
SYS_SFLIST_PEEK_NEXT_CONTAINER(__cn, __n)

현재 flagged container 다음 container를 확인합니다.

매개변수

  • __cn: 현재 container struct type pointer
  • __n: container 안 node field 이름
SYS_SFLIST_FOR_EACH_CONTAINER(__sl, __cn, __n)

Node가 아니라 container pointer로 flagged list를 순회합니다. 안전 변형이 아니므로 순회 중 __cn을 떼면 안 됩니다.

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

매개변수

  • __sl: 순회할 sys_sflist_t pointer
  • __cn: 현재 container pointer
  • __n: container 안 node field 이름
SYS_SFLIST_FOR_EACH_CONTAINER_SAFE(__sl, __cn, __cns, __n)

현재 container를 떼어도 loop가 깨지지 않도록 flagged list를 안전하게 순회합니다.

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

매개변수

  • __sl: 순회할 sys_sflist_t pointer
  • __cn: 현재 container pointer
  • __cns: 다음 container scratch pointer
  • __n: container 안 node field 이름
SYS_SFLIST_STATIC_INIT(ptr_to_list)

Flagged single-linked list를 compile time에 정적으로 초기화합니다.

매개변수

  • ptr_to_list: 초기화할 list pointer
SYS_SFLIST_FLAGS_MASK

Flagged list node의 next pointer에 결합된 사용자 flag bit를 추출하는 mask입니다.

형식 별칭

typedef struct _sfnode sys_sfnode_t

Flagged single-linked list node 구조체 형식입니다.

typedef struct _sflist sys_sflist_t

Flagged single-linked list 구조체 형식입니다.

함수

static inline void sys_sflist_init(sys_sflist_t *list)

Flagged list를 빈 상태로 초기화합니다.

매개변수

  • list: 초기화할 list pointer
static inline uint8_t sys_sfnode_flags_get(sys_sfnode_t *node)

특정 sfnode에 저장된 flag 값을 읽습니다.

매개변수

  • node: flag를 읽을 node pointer

반환값: 32-bit architecture에서는 0~3, 64-bit architecture에서는 0~7 범위의 값입니다.

static inline sys_sfnode_t *sys_sflist_peek_head(sys_sflist_t *list)

첫 flagged node를 제거하지 않고 확인합니다.

매개변수

  • list: 확인할 list pointer

반환값: 첫 node pointer이며 비었으면 NULL입니다.

static inline sys_sfnode_t *sys_sflist_peek_tail(sys_sflist_t *list)

마지막 flagged node를 제거하지 않고 확인합니다.

매개변수

  • list: 확인할 list pointer

반환값: 마지막 node pointer이며 비었으면 NULL입니다.

static inline void sys_sfnode_init(sys_sfnode_t *node, uint8_t flags)

아직 어떤 list에도 추가하지 않은 sflist node를 초기화하고 최초 flag 값을 설정합니다. 이 값은 node를 list 안에서 옮기거나 제거하거나 다른 sflist로 이식해도 유지됩니다. sys_sfnode_flags_set()보다 아주 조금 빠르므로 미연결 node에만 사용해야 합니다.

매개변수

  • node: 초기화할 node pointer
  • flags: 32-bit architecture에서는 0~3, 64-bit architecture에서는 0~7 범위의 초기 flag 값
static inline void sys_sfnode_flags_set(sys_sfnode_t *node, uint8_t flags)

Sflist node의 flag 값을 설정합니다. 이 값은 node 이동·제거·다른 sflist로의 이식 뒤에도 유지됩니다.

매개변수

  • node: flag를 설정할 node pointer
  • flags: 32-bit architecture에서는 0~3, 64-bit architecture에서는 0~7 범위의 값
static inline bool sys_sflist_is_empty(sys_sflist_t *list)

Flagged list가 비었는지 검사합니다.

매개변수

  • list: 검사할 list pointer

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

static inline sys_sfnode_t *sys_sflist_peek_next_no_check(sys_sfnode_t *node)

현재 node가 NULL이 아님을 이미 알 때 다음 flagged node를 더 빠르게 확인합니다.

매개변수

  • node: 현재 node pointer

반환값: 다음 node pointer이며 없으면 NULL입니다.

static inline sys_sfnode_t *sys_sflist_peek_next(sys_sfnode_t *node)

현재 flagged node의 다음 node를 확인합니다.

매개변수

  • node: 현재 node pointer

반환값: 다음 node pointer이며 없으면 NULL입니다.

static inline void sys_sflist_prepend(sys_sflist_t *list, sys_sfnode_t *node)

Node를 flagged list head 앞에 추가합니다. 이 함수와 다른 sys_sflist_*() 함수는 thread-safe하지 않습니다.

매개변수

  • list: 변경할 list pointer
  • node: 앞에 추가할 node pointer
static inline void sys_sflist_append(sys_sflist_t *list, sys_sfnode_t *node)

Node를 flagged list tail 뒤에 추가합니다. 이 함수와 다른 sys_sflist_*() 함수는 thread-safe하지 않습니다.

매개변수

  • list: 변경할 list pointer
  • node: 뒤에 추가할 node pointer
static inline void sys_sflist_append_list(sys_sflist_t *list, void *head, void *tail)

첫 field가 next pointer인 NULL 종료 singly-linked node 범위를 flagged list 뒤에 붙입니다. 이 함수와 다른 sys_sflist_*() 함수는 thread-safe하지 않습니다.

매개변수

  • list: 변경할 list pointer
  • head: 붙일 범위의 첫 element pointer
  • tail: 붙일 범위의 마지막 element pointer
static inline void sys_sflist_merge_sflist(sys_sflist_t *list, sys_sflist_t *list_to_append)

두 sflist를 합쳐 두 번째 list를 첫 번째 list 뒤에 붙입니다. 완료되면 두 번째 list는 비게 됩니다. 이 함수와 다른 sys_sflist_*() 함수는 thread-safe하지 않습니다.

매개변수

  • list: 변경할 첫 번째 list pointer
  • list_to_append: 붙인 뒤 비게 되는 두 번째 list pointer
static inline void sys_sflist_insert(sys_sflist_t *list, sys_sfnode_t *prev, sys_sfnode_t *node)

지정 predecessor 다음에 flagged node를 삽입합니다. 이 함수와 다른 sys_sflist_*() 함수는 thread-safe하지 않습니다.

매개변수

  • list: 변경할 list pointer
  • prev: 이전 node pointer
  • node: 삽입할 node pointer
static inline sys_sfnode_t *sys_sflist_get_not_empty(sys_sflist_t *list)

비어 있지 않다고 이미 아는 flagged list에서 첫 node를 가져와 제거합니다. 이 함수와 다른 sys_sflist_*() 함수는 thread-safe하지 않습니다.

매개변수

  • list: 변경할 list pointer

반환값: 기존 첫 node pointer입니다.

static inline sys_sfnode_t *sys_sflist_get(sys_sflist_t *list)

Flagged list에서 첫 node를 가져와 제거합니다. 이 함수와 다른 sys_sflist_*() 함수는 thread-safe하지 않습니다.

매개변수

  • list: 변경할 list pointer

반환값: 기존 첫 node pointer이며 비었으면 NULL입니다.

static inline void sys_sflist_remove(sys_sflist_t *list, sys_sfnode_t *prev_node, sys_sfnode_t *node)

알고 있는 predecessor를 이용해 flagged node를 제거합니다. Head 제거 시 prev_node는 NULL일 수 있습니다. 이 함수와 다른 sys_sflist_*() 함수는 thread-safe하지 않습니다.

매개변수

  • list: 변경할 list pointer
  • prev_node: 이전 node 또는 head 제거 시 NULL
  • node: 제거할 node pointer
static inline bool sys_sflist_find_and_remove(sys_sflist_t *list, sys_sfnode_t *node)

Flagged list를 검색해 node가 있으면 제거합니다. 검색 때문에 O(n) 시간이 듭니다. 이 함수와 다른 sys_sflist_*() 함수는 thread-safe하지 않습니다.

매개변수

  • list: 변경할 list pointer
  • node: 검색해 제거할 node pointer

반환값: Node를 제거했으면 true입니다.

static inline size_t sys_sflist_len(sys_sflist_t *list)

Flagged list 길이를 O(n) 시간에 계산합니다.

매개변수

  • list: 검사할 list pointer

반환값: List 크기이며 비었으면 0입니다.

Source

출처

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