source: trunk/sys/dietlibc/include/sys/list.h @ 1

Last change on this file since 1 was 1, checked in by alain, 7 years ago

First import

File size: 6.5 KB
Line 
1/*
2    This file is part of MutekP.
3
4    MutekP is free software; you can redistribute it and/or modify it
5    under the terms of the GNU General Public License as published by
6    the Free Software Foundation; either version 2 of the License, or
7    (at your option) any later version.
8
9    MutekP is distributed in the hope that it will be useful, but
10    WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12    General Public License for more details.
13
14    You should have received a copy of the GNU General Public License
15    along with MutekP; if not, write to the Free Software Foundation,
16    Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17
18    UPMC / LIP6 / SOC (c) 2008
19    Copyright Ghassan Almaless <ghassan.almaless@lip6.fr>
20*/
21
22
23#ifndef _MUTEKP_LIST_H_
24#define _MUTEKP_LIST_H_
25
26#ifndef MUTEKP_LIST_DEBUG
27#define MUTEKP_LIST_DEBUG    1
28#endif
29
30#ifndef NULL
31#define NULL (void *) 0
32#endif
33
34#ifndef offsetof
35#define offsetof(type, member) ((unsigned int) & ((type *)0)->member)
36#endif
37
38#define LIST_ROOT_INITIALIZER(name) { &(name), &(name) }
39
40#define list_container(list_ptr,container_type,member_name)                       \
41  ({const typeof(((container_type*)0)->member_name) *__member_ptr = (list_ptr);   \
42    (container_type *)( (char*)__member_ptr - offsetof(container_type,member_name));})
43
44
45/*
46 * Double circular linked list definition
47 */
48struct list_entry{
49  struct list_entry *next;
50  struct list_entry *pred;
51};
52
53/* Simple circular linked list definition
54 * it's managed as a stack data structure
55 * we still able to use somme functions
56 * and macro from list_entry (Double circular
57 * linked list) see commentes of each one
58 */
59struct slist_entry{
60  struct slist_entry *next;
61};
62
63
64/*
65 * Can be used, and should be used for both
66 * list_entry & slist_entry data structures
67 */
68#define list_element(list_ptr, type, member)     \
69  list_container(list_ptr, type, member)
70
71/*
72 * To be used with list_entry data structure
73 * probebly, it has no sens with slist_entry
74 */
75#define list_first(root_ptr, type, member)       \
76  list_element((root_ptr)->next,type,member)
77
78/*
79 * To be used only with list_entry data structure
80 */
81static inline struct list_entry* list_next(struct list_entry *root, struct list_entry *current)
82{
83  if((root == root->next) || (current->next == root))
84    return NULL;
85 
86  return current->next;
87}
88
89/*
90 * To be used only with list_entry data structure
91 */
92static inline struct list_entry* list_pred(struct list_entry *root, struct list_entry *current)
93{
94  if((root == root->next) || (current->pred == root))
95    return NULL;
96 
97  return current->pred;
98}
99
100
101/*
102 * To be used only with list_entry data structure
103 */
104#define list_last(root_ptr, type, member)        \
105  list_element((root_ptr)->pred,type,member)
106
107
108/*
109 * To be used with list_entry data structure
110 * probebly, it has no sens with slist_entry
111 */
112#define list_foreach_forward(root_ptr, iter)     \
113  struct list_entry *__ptr;                      \
114  for(iter = (root_ptr)->next, __ptr = (struct list_entry *)(iter)->next; iter != (root_ptr); iter = (typeof((iter)))__ptr, __ptr = (struct list_entry *)iter->next)
115
116/*
117 * To be used only with list_entry data structure
118 */
119#define list_foreach_backward(root_ptr, iter)    \
120  struct list_entry *__ptr;                      \
121  for(iter = (root_ptr)->pred, __ptr = iter->pred; iter != (root_ptr); iter = __ptr, __ptr = iter->pred)
122
123/*
124 * Can be used, and should be used for both
125 * list_entry & slist_entry data structures
126 */
127#define list_foreach(root_ptr, iter)             \
128  list_foreach_forward(root_ptr,iter)
129
130/*
131 * To be used only with list_entry data structure
132 */
133static inline void list_root_init(struct list_entry *root)
134{
135  root->next = root;
136  root->pred = root;
137}
138
139
140/*
141 * To be used only with list_entry data structure
142 */
143static inline void list_entry_init(struct list_entry *entry)
144{
145  entry->next = NULL;
146  entry->pred = NULL;
147}
148
149/*
150 * To be used only with list_entry data structure
151 */
152static inline void list_add(struct list_entry *root, struct list_entry *entry)
153{
154  struct list_entry *pred_entry;
155  struct list_entry *next_entry;
156 
157  pred_entry = root;
158  next_entry = root->next;
159
160  entry->next = next_entry;
161  entry->pred = pred_entry;
162 
163  pred_entry->next = entry;
164  next_entry->pred = entry;
165}
166
167/*
168 * To be used with list_entry data structure
169 * probebly, it has no sens with slist_entry
170 */
171#define list_add_first(root, entry) \
172  list_add((root),(entry))
173
174/*
175 * To be used with list_entry data structure
176 * probebly, it has no sens with slist_entry
177 */
178#define list_add_next(root, entry)  \
179  list_add((root),(entry))
180
181/*
182 * To be used only with list_entry data structure
183 */
184#define list_add_last(root, entry)  \
185  list_add((root)->pred,(entry))
186
187/*
188 * To be used only with list_entry data structure
189 */
190#define list_add_pred(root, entry)  \
191  list_add((root)->pred,(entry))
192
193/*
194 * Can be used, and should be used for both
195 * list_entry & slist_entry data structures
196 */
197#define list_empty(root) (root == (root)->next)
198
199/*
200 * To be used only with list_entry data structure
201 */
202static inline void list_unlink(struct list_entry *entry)
203{
204  struct list_entry *pred_entry;
205  struct list_entry *next_entry;
206
207  pred_entry = entry->pred;
208  next_entry = entry->next;
209
210  pred_entry->next = entry->next;
211  next_entry->pred = entry->pred;
212
213#if MUTEKP_LIST_DEBUG
214  entry->next = (struct list_entry *)0xDeeDbeef;
215  entry->pred = (struct list_entry *)0xA5cA5fA5;
216#endif
217}
218
219/*
220 * To be used only with list_entry data structure
221 */
222static inline void list_replace(struct list_entry *current, struct list_entry *new)
223{
224  struct list_entry *pred_entry;
225  struct list_entry *next_entry;
226
227  pred_entry = current->pred;
228  next_entry = current->next;
229
230  new->next = next_entry;
231  new->pred = pred_entry;
232
233  pred_entry->next = new;
234  next_entry->pred = new;
235}
236
237///////////////////////////////////////////////////
238/* Simple circular linked list functions & macro */
239///////////////////////////////////////////////////
240
241#define slist_root_init(root)                   \
242  (root)->next = (root)
243
244
245#define slist_entry_init(entry)                 \
246  (entry)->next = NULL
247
248
249#define list_head(root, type, member)           \
250  list_element((root)->next,type,member)
251
252
253#define list_push(root,entry)                   \
254  do{                                           \
255    (entry)->next = (root)->next;               \
256    (root)->next = entry;                       \
257  }while(0)
258
259
260/* list must have at least one element */
261static inline struct slist_entry* list_pop(struct slist_entry *root)
262{
263  struct slist_entry *entry;
264 
265  entry = root->next;
266  root->next = entry->next;
267
268#if MUTEKP_LIST_DEBUG
269  entry->next = (struct slist_entry *)0xbeefdead;
270#endif
271
272  return entry;
273}
274
275#endif  /* _MUTEKP_LIST_H_ */
Note: See TracBrowser for help on using the repository browser.