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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
/* double linked list, for libreswan
*
* Copyright (C) 2015-2019 Andrew Cagney <cagney@gnu.org>
* Copyright (C) 2019 D. Hugh Redelmeier <hugh@mimosa.com>
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the
* Free Software Foundation; either version 2 of the License, or (at your
* option) any later version. See <https://www.gnu.org/licenses/gpl2.txt>.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* for more details.
*/
#ifndef LIST_ENTRY_H
#define LIST_ENTRY_H
/*
* Description of a list entry, used for logging.
*/
struct list_info {
const char *name;
size_t (*jam)(struct jambuf *buf, const void *data);
ptrdiff_t offset;
};
#define LIST_INFO(STRUCT, FIELD, INFO, JAM) \
\
static size_t jam_##INFO(struct jambuf *buf, const void *data) \
{ \
const struct STRUCT *s = data; \
return JAM(buf, s); \
} \
\
static const struct list_info INFO = { \
.name = #STRUCT " " #FIELD, \
.jam = jam_##INFO, \
.offset = offsetof(struct STRUCT, FIELD), \
}
/*
* Double linked list entry.
*
* Since these are stored directly in the list object there is less
* memory management overhead.
* Each list is represented as a doubly-linked cycle, with a
* distinguished element we call the head. The head is the
* only element with .data == NULL. This acts as a sentinel.
*
* For a list_head.head, before initialization, the list head's .newer and
* .older must be NULL. After initialization .newer points to the oldest
* list_entry (list_head.head, if the list is empty) and .older points
* to the newest. This seems contradictory, but it serves to bend time
* into a cycle.
*
* For a regular list_entry, .newer and .older are NULL when the the entry
* is detached from any list. Otherwise both must be non-NULL.
*
* Currently all elements of a list must have identical .info values.
* This could easily be changed if we needed heterogeneous lists.
*/
enum chrono {
OLD2NEW, NEW2OLD,
};
#define CHRONO_ROOF 2
struct list_entry {
struct list_entry *next[CHRONO_ROOF];
void *data;
const struct list_info *info;
};
void jam_list_entry(struct jambuf *buf, const struct list_entry *entry);
/*
* Double linked list HEAD.
*
* INIT_LIST_HEAD() is intended for static structures. To use it at
* runtime, prefix the macro with (struct list_head).
*/
struct list_head {
struct list_entry head;
};
#define INIT_LIST_HEAD(LIST_HEAD_PTR, LIST_INFO_PTR) \
{ \
.head = { \
.info = (LIST_INFO_PTR), \
.next[NEW2OLD] = &(LIST_HEAD_PTR)->head, \
.next[OLD2NEW] = &(LIST_HEAD_PTR)->head, \
}, \
}
/*
* detached_list_entry: test whether an entry is on any list.
* insert_list_entry: Insert an entry at the front of the list.
* remove_list_entry: remove the entry from anywhere in the list.
* The macros *OLD2NEW() and *NEW2OLD(), below, expose the ordering.
*
* These operations are O(1).
*/
void init_list_entry(const struct list_info *info, void *data, struct list_entry *entry);
#if 0
struct list_entry *data_list_entry(const struct list_info *info, void *data);
void *list_entry_data(const struct list_entry *entry);
#endif
bool detached_list_entry(const struct list_entry *entry);
void insert_list_entry(struct list_head *list,
struct list_entry *entry);
void remove_list_entry(struct list_entry *entry);
/*
* Iterate through all the entries in the list in either old-to-new or
* new-to-old order.
*
* So that the current entry can be deleted, the E##entry pointer is
* always on the next entry.
*
* Since a non-empty list loops back to HEAD, HEAD's .data==NULL acts
* as the sentinel; and DATA is left with that NULL value.
*/
#define FOR_EACH_LIST_ENTRY_(DATA, HEAD, NEXT) \
\
/* entry = either first entry or back at head */ \
for (struct list_entry *entry_ = (HEAD)->head.next[NEXT]; \
entry_ != NULL; entry_ = NULL) \
\
/* DATA = ENTRY->data; ENTRY = ENTRY->NEXT */ \
for (DATA = (typeof(DATA))entry_->data, \
entry_ = entry_->next[NEXT]; \
DATA != NULL; \
DATA = (typeof(DATA))entry_->data, \
entry_ = entry_->next[NEXT])
#define FOR_EACH_LIST_ENTRY_OLD2NEW(DATA, HEAD) \
FOR_EACH_LIST_ENTRY_(DATA, HEAD, OLD2NEW)
#define FOR_EACH_LIST_ENTRY_NEW2OLD(DATA, HEAD) \
FOR_EACH_LIST_ENTRY_(DATA, HEAD, NEW2OLD)
#define NEXT_LIST_ENTRY(LIST, DATA, FIELD, NEXT) \
({ \
struct list_entry *next_; \
if (DATA == NULL) { \
next_ = (LIST)->head.next[NEXT]; \
} else { \
next_ = DATA->FIELD.next[NEXT]; \
} \
(typeof(DATA)) (next_ == NULL ? NULL : next_->data); \
})
#endif
|
