Commit | Line | Data |
---|---|---|
a00718e7 MD |
1 | /* |
2 | * Copyright (C) 2002 Free Software Foundation, Inc. | |
3 | * (originally part of the GNU C Library) | |
4 | * Contributed by Ulrich Drepper <drepper@redhat.com>, 2002. | |
5 | * | |
6 | * Copyright (C) 2009 Pierre-Marc Fournier | |
7 | * Conversion to RCU list. | |
8 | * Copyright (C) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
9 | * | |
10 | * This library is free software; you can redistribute it and/or | |
11 | * modify it under the terms of the GNU Lesser General Public | |
12 | * License as published by the Free Software Foundation; either | |
13 | * version 2.1 of the License, or (at your option) any later version. | |
14 | * | |
15 | * This library is distributed in the hope that it will be useful, | |
16 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
17 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
18 | * Lesser General Public License for more details. | |
19 | * | |
20 | * You should have received a copy of the GNU Lesser General Public | |
21 | * License along with this library; if not, write to the Free Software | |
22 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
23 | */ | |
7a50dcf7 | 24 | |
34cfb3e3 MD |
25 | #ifndef _CDS_LIST_H |
26 | #define _CDS_LIST_H 1 | |
7a50dcf7 MD |
27 | |
28 | /* The definitions of this file are adopted from those which can be | |
29 | found in the Linux kernel headers to enable people familiar with | |
30 | the latter find their way in these sources as well. */ | |
31 | ||
32 | ||
33 | /* Basic type for the double-link list. */ | |
34cfb3e3 | 34 | struct cds_list_head |
7a50dcf7 | 35 | { |
16aa9ee8 DG |
36 | struct cds_list_head *next; |
37 | struct cds_list_head *prev; | |
34cfb3e3 | 38 | }; |
7a50dcf7 | 39 | |
78654362 | 40 | |
7a50dcf7 | 41 | /* Define a variable with the head and tail of the list. */ |
16aa9ee8 | 42 | #define CDS_LIST_HEAD(name) \ |
34cfb3e3 | 43 | struct cds_list_head name = { &(name), &(name) } |
7a50dcf7 MD |
44 | |
45 | /* Initialize a new list head. */ | |
16aa9ee8 | 46 | #define CDS_INIT_LIST_HEAD(ptr) \ |
7a50dcf7 MD |
47 | (ptr)->next = (ptr)->prev = (ptr) |
48 | ||
16aa9ee8 | 49 | #define CDS_LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } |
7a50dcf7 MD |
50 | |
51 | /* Add new element at the head of the list. */ | |
52 | static inline void | |
34cfb3e3 | 53 | cds_list_add (struct cds_list_head *newp, struct cds_list_head *head) |
7a50dcf7 MD |
54 | { |
55 | head->next->prev = newp; | |
56 | newp->next = head->next; | |
57 | newp->prev = head; | |
58 | head->next = newp; | |
59 | } | |
60 | ||
61 | ||
62 | /* Add new element at the tail of the list. */ | |
63 | static inline void | |
34cfb3e3 | 64 | cds_list_add_tail (struct cds_list_head *newp, struct cds_list_head *head) |
7a50dcf7 MD |
65 | { |
66 | head->prev->next = newp; | |
67 | newp->next = head; | |
68 | newp->prev = head->prev; | |
69 | head->prev = newp; | |
70 | } | |
71 | ||
72 | ||
63ff4873 MD |
73 | /* Remove element from list. */ |
74 | static inline void | |
34cfb3e3 | 75 | __cds_list_del (struct cds_list_head *prev, struct cds_list_head *next) |
63ff4873 MD |
76 | { |
77 | next->prev = prev; | |
78 | prev->next = next; | |
79 | } | |
80 | ||
7a50dcf7 MD |
81 | /* Remove element from list. */ |
82 | static inline void | |
34cfb3e3 | 83 | cds_list_del (struct cds_list_head *elem) |
7a50dcf7 | 84 | { |
16aa9ee8 | 85 | __cds_list_del (elem->prev, elem->next); |
7a50dcf7 MD |
86 | } |
87 | ||
3ec07d9f PM |
88 | /* Remove element from list, initializing the element's list pointers. */ |
89 | static inline void | |
90 | cds_list_del_init (struct cds_list_head *elem) | |
91 | { | |
92 | cds_list_del(elem); | |
93 | CDS_INIT_LIST_HEAD(elem); | |
94 | } | |
95 | ||
ac956d00 MD |
96 | /* delete from list, add to another list as head */ |
97 | static inline void | |
34cfb3e3 | 98 | cds_list_move (struct cds_list_head *elem, struct cds_list_head *head) |
ac956d00 | 99 | { |
16aa9ee8 DG |
100 | __cds_list_del (elem->prev, elem->next); |
101 | cds_list_add (elem, head); | |
ac956d00 | 102 | } |
7a50dcf7 | 103 | |
5db941e8 MD |
104 | /* replace an old entry. |
105 | */ | |
106 | static inline void | |
34cfb3e3 | 107 | cds_list_replace(struct cds_list_head *old, struct cds_list_head *_new) |
5db941e8 MD |
108 | { |
109 | _new->next = old->next; | |
110 | _new->prev = old->prev; | |
111 | _new->prev->next = _new; | |
112 | _new->next->prev = _new; | |
113 | } | |
114 | ||
7a50dcf7 MD |
115 | /* Join two lists. */ |
116 | static inline void | |
34cfb3e3 | 117 | cds_list_splice (struct cds_list_head *add, struct cds_list_head *head) |
7a50dcf7 MD |
118 | { |
119 | /* Do nothing if the list which gets added is empty. */ | |
120 | if (add != add->next) | |
121 | { | |
122 | add->next->prev = head; | |
123 | add->prev->next = head->next; | |
124 | head->next->prev = add->prev; | |
125 | head->next = add->next; | |
126 | } | |
127 | } | |
128 | ||
7a50dcf7 | 129 | /* Get typed element from list at a given position. */ |
16aa9ee8 | 130 | #define cds_list_entry(ptr, type, member) \ |
7a50dcf7 MD |
131 | ((type *) ((char *) (ptr) - (unsigned long) (&((type *) 0)->member))) |
132 | ||
133 | ||
58090b34 | 134 | /* Get first entry from a list. */ |
78654362 MD |
135 | #define cds_list_first_entry(ptr, type, member) \ |
136 | cds_list_entry((ptr)->next, type, member) | |
58090b34 | 137 | |
7a50dcf7 MD |
138 | |
139 | /* Iterate forward over the elements of the list. */ | |
16aa9ee8 | 140 | #define cds_list_for_each(pos, head) \ |
7a50dcf7 MD |
141 | for (pos = (head)->next; pos != (head); pos = pos->next) |
142 | ||
143 | ||
144 | /* Iterate forward over the elements of the list. */ | |
16aa9ee8 | 145 | #define cds_list_for_each_prev(pos, head) \ |
7a50dcf7 MD |
146 | for (pos = (head)->prev; pos != (head); pos = pos->prev) |
147 | ||
148 | ||
149 | /* Iterate backwards over the elements list. The list elements can be | |
150 | removed from the list while doing this. */ | |
16aa9ee8 | 151 | #define cds_list_for_each_prev_safe(pos, p, head) \ |
7a50dcf7 MD |
152 | for (pos = (head)->prev, p = pos->prev; \ |
153 | pos != (head); \ | |
154 | pos = p, p = pos->prev) | |
155 | ||
16aa9ee8 | 156 | #define cds_list_for_each_entry(pos, head, member) \ |
bdffa73a | 157 | for (pos = cds_list_entry((head)->next, __typeof__(*pos), member); \ |
7a50dcf7 | 158 | &pos->member != (head); \ |
bdffa73a | 159 | pos = cds_list_entry(pos->member.next, __typeof__(*pos), member)) |
7a50dcf7 | 160 | |
16aa9ee8 | 161 | #define cds_list_for_each_entry_reverse(pos, head, member) \ |
bdffa73a | 162 | for (pos = cds_list_entry((head)->prev, __typeof__(*pos), member); \ |
7a50dcf7 | 163 | &pos->member != (head); \ |
bdffa73a | 164 | pos = cds_list_entry(pos->member.prev, __typeof__(*pos), member)) |
7a50dcf7 | 165 | |
16aa9ee8 | 166 | #define cds_list_for_each_entry_safe(pos, p, head, member) \ |
bdffa73a MD |
167 | for (pos = cds_list_entry((head)->next, __typeof__(*pos), member), \ |
168 | p = cds_list_entry(pos->member.next, __typeof__(*pos), member); \ | |
7a50dcf7 | 169 | &pos->member != (head); \ |
bdffa73a | 170 | pos = p, p = cds_list_entry(pos->member.next, __typeof__(*pos), member)) |
7a50dcf7 | 171 | |
34cfb3e3 | 172 | static inline int cds_list_empty(struct cds_list_head *head) |
7a50dcf7 MD |
173 | { |
174 | return head == head->next; | |
175 | } | |
176 | ||
34cfb3e3 MD |
177 | static inline void cds_list_replace_init(struct cds_list_head *old, |
178 | struct cds_list_head *_new) | |
7a50dcf7 | 179 | { |
34cfb3e3 | 180 | struct cds_list_head *head = old->next; |
16aa9ee8 DG |
181 | cds_list_del(old); |
182 | cds_list_add_tail(_new, head); | |
183 | CDS_INIT_LIST_HEAD(old); | |
7a50dcf7 MD |
184 | } |
185 | ||
34cfb3e3 | 186 | #endif /* _CDS_LIST_H */ |