ludtm/slist.h at main · yskzalloc/ludtm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#ifndef _USER_SPACE_SLIST_H_
#define _USER_SPACE_SLIST_H_

#include <stddef.h> /* offsetof */

/* container_of: 커널 스타일 그대로 */
#define container_of(ptr, type, member) ({                      \
        const typeof(((type *)0)->member) *__mptr = (ptr);      \
        (type *)((char *)__mptr - offsetof(type, member)); })

/* 노드 정의: 단일 연결 리스트 */
struct slist_node {
    struct slist_node *next;
};

/* 리스트 head 정의 (head + tail) */
struct slist_head {
    struct slist_node *first;
    struct slist_node *last;  /* 꼬리 노드 포인터 */
};

/* 초기화 매크로 */
#define SLIST_HEAD_INIT { .first = NULL, .last = NULL }
#define SLIST_HEAD(name) struct slist_head name = SLIST_HEAD_INIT
#define INIT_SLIST_HEAD(ptr) do { (ptr)->first = NULL; (ptr)->last = NULL; } while (0)
#define INIT_SLIST_NODE(ptr) ((ptr)->next = NULL)

/* 리스트가 비었는지 확인 */
static inline int slist_empty(const struct slist_head *h)
{
    return !h->first;
}

/* 머리 삽입: O(1) */
static inline void slist_add_head(struct slist_node *n, struct slist_head *h)
{
    if (!h->first) {
        h->first = n;
        h->last = n;
        n->next = NULL;
    } else {
        n->next = h->first;
        h->first = n;
    }
}

/* 꼬리 삽입: O(1) */
static inline void slist_add_tail(struct slist_node *n, struct slist_head *h)
{
    n->next = NULL;
    if (!h->first) {
        h->first = n;
        h->last = n;
    } else {
        h->last->next = n;
        h->last = n;
    }
}

/* 머리 pop: O(1) */
static inline struct slist_node *slist_pop_head(struct slist_head *h)
{
    struct slist_node *n = h->first;
    if (!n)
        return NULL;

    h->first = n->next;
    if (!h->first)  /* 리스트가 비었으면 tail도 NULL */
        h->last = NULL;
    n->next = NULL;
    return n;
}

/* 특정 노드 뒤 삽입: O(1) */
static inline void slist_add_after(struct slist_node *pos, struct slist_node *n, struct slist_head *h)
{
    n->next = pos->next;
    pos->next = n;
    if (h->last == pos)  /* pos가 마지막이면 tail 업데이트 */
        h->last = n;
}

/* 삭제: head부터 찾아야 함 (O(n)) */
static inline void slist_del(struct slist_node *target, struct slist_head *h)
{
    struct slist_node **pp = &h->first;
    while (*pp) {
        if (*pp == target) {
            *pp = target->next;
            if (h->last == target)  /* tail 삭제 시 업데이트 */
                h->last = (*pp == NULL) ? NULL : h->last;
            target->next = NULL;
            return;
        }
        pp = &(*pp)->next;
    }
}

/* 엔트리 매크로 */
#define slist_entry(ptr, type, member) container_of(ptr, type, member)

/* 순회 매크로 */
#define slist_for_each(pos, head) \
    for (pos = (head)->first; pos; pos = pos->next)

#define slist_for_each_safe(pos, n, head) \
    for (pos = (head)->first; pos && ({ n = pos->next; 1; }); pos = n)

#endif /* _USER_SPACE_SLIST_H_ */