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
|
/* 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;
void (*jam)(struct jambuf *buf, const void *data);
};
/*
* 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.
*/
struct list_entry {
struct list_entry *older;
struct list_entry *newer;
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;
};
struct list_entry list_entry(const struct list_info *info, void *data);
#define INIT_LIST_HEAD(LIST_HEAD_PTR, LIST_INFO_PTR) \
{ \
.head = { \
.info = (LIST_INFO_PTR), \
.older = &(LIST_HEAD_PTR)->head, \
.newer = &(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).
*/
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_(HEAD, DATA, NEXT) \
\
/* entry = either first entry or back at head */ \
for (struct list_entry *entry_ = (HEAD)->head.NEXT; \
entry_ != NULL; entry_ = NULL) \
\
/* DATA = ENTRY->data; ENTRY = ENTRY->NEXT */ \
for (DATA = (typeof(DATA))entry_->data, \
entry_ = entry_->NEXT; \
DATA != NULL; \
DATA = (typeof(DATA))entry_->data, \
entry_ = entry_->NEXT)
#define FOR_EACH_LIST_ENTRY_OLD2NEW(HEAD, DATA) \
FOR_EACH_LIST_ENTRY_(HEAD, DATA, newer)
#define FOR_EACH_LIST_ENTRY_NEW2OLD(HEAD, DATA) \
FOR_EACH_LIST_ENTRY_(HEAD, DATA, older)
#endif
|
