src/libnetdata/linked-lists.h


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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

// SPDX-License-Identifier: GPL-3.0-or-later

#ifndef NETDATA_LINKED_LISTS_H
#define NETDATA_LINKED_LISTS_H

// ---------------------------------------------------------------------------------------------
// double linked list management
// inspired by https://github.com/troydhanson/uthash/blob/master/src/utlist.h

#define DOUBLE_LINKED_LIST_PREPEND_ITEM_UNSAFE(head, item, prev, next)                         \
    do {                                                                                       \
        (item)->next = (head);                                                                 \
                                                                                               \
        if(likely(head)) {                                                                     \
            (item)->prev = (head)->prev;                                                       \
            (head)->prev = (item);                                                             \
        }                                                                                      \
        else                                                                                   \
            (item)->prev = (item);                                                             \
                                                                                               \
        (head) = (item);                                                                       \
    } while (0)

#define DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(head, item, prev, next)                          \
    do {                                                                                       \
                                                                                               \
        (item)->next = NULL;                                                                   \
                                                                                               \
        if(likely(head)) {                                                                     \
            (item)->prev = (head)->prev;                                                       \
            (head)->prev->next = (item);                                                       \
            (head)->prev = (item);                                                             \
        }                                                                                      \
        else {                                                                                 \
            (item)->prev = (item);                                                             \
            (head) = (item);                                                                   \
        }                                                                                      \
                                                                                               \
    } while (0)

#define DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(head, item, prev, next)                          \
    do {                                                                                       \
        fatal_assert((head) != NULL);                                                          \
        fatal_assert((item)->prev != NULL);                                                    \
                                                                                               \
        if((item)->prev == (item))                                                             \
            /* it is the only item in the list */                                              \
            (head) = NULL;                                                                     \
                                                                                               \
        else if((item) == (head)) {                                                            \
            /* it is the first item */                                                         \
            fatal_assert((item)->next != NULL);                                                \
            (item)->next->prev = (item)->prev;                                                 \
            (head) = (item)->next;                                                             \
        }                                                                                      \
        else {                                                                                 \
            /* it is any other item */                                                         \
            (item)->prev->next = (item)->next;                                                 \
                                                                                               \
            if ((item)->next)                                                                  \
                (item)->next->prev = (item)->prev;                                             \
            else                                                                               \
                (head)->prev = (item)->prev;                                                   \
        }                                                                                      \
                                                                                               \
        (item)->next = NULL;                                                                   \
        (item)->prev = NULL;                                                                   \
    } while (0)

#define DOUBLE_LINKED_LIST_INSERT_ITEM_BEFORE_UNSAFE(head, existing, item, prev, next)         \
    do {                                                                                       \
        if (existing) {                                                                        \
            fatal_assert((head) != NULL);                                                      \
            fatal_assert((item) != NULL);                                                      \
                                                                                               \
            (item)->next = (existing);                                                         \
            (item)->prev = (existing)->prev;                                                   \
            (existing)->prev = (item);                                                         \
                                                                                               \
            if ((head) == (existing))                                                          \
                (head) = (item);                                                               \
            else                                                                               \
                (item)->prev->next = (item);                                                   \
                                                                                               \
        }                                                                                      \
        else                                                                                   \
            DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(head, item, prev, next);                     \
                                                                                               \
    } while (0)

#define DOUBLE_LINKED_LIST_INSERT_ITEM_AFTER_UNSAFE(head, existing, item, prev, next)          \
    do {                                                                                       \
        if (existing) {                                                                        \
            fatal_assert((head) != NULL);                                                      \
            fatal_assert((item) != NULL);                                                      \
                                                                                               \
            (item)->next = (existing)->next;                                                   \
            (item)->prev = (existing);                                                         \
            (existing)->next = (item);                                                         \
                                                                                               \
            if ((item)->next)                                                                  \
                (item)->next->prev = (item);                                                   \
            else                                                                               \
                (head)->prev = (item);                                                         \
        }                                                                                      \
        else                                                                                   \
            DOUBLE_LINKED_LIST_PREPEND_ITEM_UNSAFE(head, item, prev, next);                    \
                                                                                               \
    } while (0)

#define DOUBLE_LINKED_LIST_APPEND_LIST_UNSAFE(head, head2, prev, next)                         \
    do {                                                                                       \
        if (head2) {                                                                           \
            if (head) {                                                                        \
                __typeof(head2) _head2_last_item = (head2)->prev;                              \
                                                                                               \
                (head2)->prev = (head)->prev;                                                  \
                (head)->prev->next = (head2);                                                  \
                                                                                               \
                (head)->prev = _head2_last_item;                                               \
            }                                                                                  \
            else                                                                               \
                (head) = (head2);                                                              \
        }                                                                                      \
    } while (0)

#define DOUBLE_LINKED_LIST_FOREACH_FORWARD(head, var, prev, next)                              \
    for ((var) = (head); (var) ; (var) = (var)->next)

#define DOUBLE_LINKED_LIST_FOREACH_BACKWARD(head, var, prev, next)                             \
    for ((var) = (head) ? (head)->prev : NULL ; (var) ; (var) = ((var) == (head)) ? NULL : (var)->prev)

#endif //NETDATA_LINKED_LISTS_H