source: trunk/kernel/libk/list.h @ 385

Last change on this file since 385 was 24, checked in by max@…, 7 years ago

Use intptr_t instead.

File size: 10.5 KB
RevLine 
[1]1/*
2 * list.h - Double circular chained lists, inspired from linux
3 *
4 * Authors Ghassan Almaless  (2008,2009,2010,2011,2012)
5 *         Alain Greiner     (2016)
6 *
7 * Copyright (c) UPMC Sorbonne Universites
8 *
9 * This file is part of ALMOS-MKH     
10 *
11 * ALMOS-MKH is free software; you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; version 2.0 of the License.
14 *
15 * ALMOS-MKH is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18 * General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
22 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 */
24
25#ifndef _ALMOS_LIST_H_
26#define _ALMOS_LIST_H_
27
[14]28#include <kernel_config.h>
[1]29#include <hal_types.h>
30
31#ifndef NULL
32#define NULL (void *) 0
33#endif
34
35
36/***************************************************************************
37 * This macro return an uint32_t that is the offset (number of bytes)
38 * of a field in a structure.
39 * @ type   : structure type
40 * @ member : name of the field
41 **************************************************************************/
42
43#ifndef OFFSETOF
[24]44#define OFFSETOF( type , member ) ((intptr_t) & ((type *)0)->member)
[1]45#endif
46
47////////////////////////////////////////////////////////////////////////////
48////////////////////////////////////////////////////////////////////////////
49//          Double circular linked list functions & macros
50////////////////////////////////////////////////////////////////////////////
51////////////////////////////////////////////////////////////////////////////
52
53/***************************************************************************
54 * This structure defines a Double Circular Linked List entry.
55 * Note : The list root is an extra list-entry_t, that is NOT part of the
56 *        set of linked elements.
57 **************************************************************************/
58
59typedef struct list_entry_s
60{
61        struct list_entry_s * next;
62        struct list_entry_s * pred;
63}
64list_entry_t;
65
66/***************************************************************************
67 * This macro returns a pointer on a structure containing a list_entry_t.
68 ***************************************************************************
69 * @ list_ptr       : pointer on the list_entry
70 * @ container_type : type of the structure containing the list-entry
71 * @ member_name    : name of the list_entry field
72 **************************************************************************/
73
74#define LIST_ELEMENT( list_ptr , container_type , member_name)          \
75        ({const typeof(((container_type*)0)->member_name) *__member_ptr = (list_ptr); \
76        (container_type *)( (char*)__member_ptr - OFFSETOF( container_type , member_name ));})
77
78/***************************************************************************
79 * This macro returns the first element of a rooted double linked list.
80 ***************************************************************************
81 * @ root_ptr : pointer on the list root
82 * @ type     : type of the linked elements
83 * @ member   : name of the list_entry_t field
84 **************************************************************************/
85
86#define LIST_FIRST( root , type , member )              \
87        LIST_ELEMENT( (root)->next , type , member )
88
89/***************************************************************************
90 * This macro returns the last element of a rooted double linked list.
91 ***************************************************************************
92 * @ root_ptr : pointer on the list root
93 * @ type     : type of the linked elements
94 * @ member   : name of the list_entry_t field
95 **************************************************************************/
96
97#define LIST_LAST( root , type , member )               \
98        LIST_ELEMENT( (root)->pred , type , member )
99
100/***************************************************************************
101 * This function returns the pointer on the next list_entry_t.
102 ***************************************************************************
103 * @ root    : pointer on the list root.
104 * @ current : pointer on the current list_entry_t.
105 * @ returns pointer on next entry if success.
106 *   returns NULL if list empty or next is the root.
107 **************************************************************************/
108static inline list_entry_t * list_next( list_entry_t * root,
109                                        list_entry_t * current )
110{
111        if((root == root->next) || (current->next == root)) return NULL;
112 
113        return current->next;
114}
115
116/***************************************************************************
117 * This function returns the pointer on the previous list_entry_t.
118 ***************************************************************************
119 * @ root    : pointer on the list root.
120 * @ current : pointer on the current list_entry.
121 * @ returns pointer on previous entry if success.
122 *   returns NULL if list empty or previous is the root.
123 **************************************************************************/
124static inline list_entry_t * list_pred( list_entry_t * root,
125                                        list_entry_t * current )
126{
127        if((root == root->next) || (current->pred == root))
128                return NULL;
129 
130        return current->pred;
131}
132
133/***************************************************************************
134 * This macro traverse a rooted double linked list in forward order.
135 * WARNING : Don't use 2 LIST_FOREACH in the same function, because the
136 * variable __ptr will be defined twice, wich result in a compilation error.
137 ***************************************************************************
138 * @ root      : pointer on the root list_entry
139 * @ iter      : pointer on a list_entry
140 **************************************************************************/
141
142#define LIST_FOREACH( root , iter ) \
143for( (iter) = (root)->next ;        \
144     (iter) != (root) ;                         \
145     (iter) = (iter)->next )
146       
147/***************************************************************************
148 * This macro traverse a rooted double linked list in backward order.
149 * WARNING : same as the forward traversal
150 ***************************************************************************
151 * @ root      : pointer on the root list_entry
152 * @ iter      : pointer on a list_entry
153 **************************************************************************/
154
155#define LIST_FOREACH_BACKWARD( root , iter )  \
156for( (iter) = (root)->pred ;                  \
157     (iter) != (root) ;                       \
158     (iter) = (iter)->pred )
159
160/***************************************************************************
161 * This function initializes the root of a rooted double linked list.
162 ***************************************************************************
163 * @ root    : pointer on the list root
164 **************************************************************************/
165static inline void list_root_init( list_entry_t * root )
166{
167        root->next = root;
168        root->pred = root;
169}
170
171/***************************************************************************
172 * This function initializes an entry of a rooted double linked list.
173 ***************************************************************************
174 * @ entry   : pointer on the list-entry to be initialized
175 **************************************************************************/
176static inline void list_entry_init( list_entry_t * entry )
177{
178        entry->next = NULL;
179        entry->pred = NULL;
180}
181
182/***************************************************************************
183 * This function inserts a new entry in first place of a double linked list.
184 ***************************************************************************
185 * @ root    : pointer on the list root
186 * @ entry   : pointer on the list-entry to be inserted
187 **************************************************************************/
188static inline void list_add_first( list_entry_t * root, 
189                                   list_entry_t * entry )
190{
191    list_entry_t * pred_entry;
192    list_entry_t * next_entry;
193 
194        pred_entry = root;
195        next_entry = root->next;
196       
197        entry->next = next_entry;
198        entry->pred = pred_entry;
199 
200        pred_entry->next = entry;
201        next_entry->pred = entry;
202}
203
204/***************************************************************************
205 * This function inserts a new entry in last place of a double linked list.
206 ***************************************************************************
207 * @ root    : pointer on the list root
208 * @ entry   : pointer on the list-entry to be inserted
209 **************************************************************************/
210static inline void list_add_last( list_entry_t * root,
211                                  list_entry_t * entry )
212{
213    list_add_first( root->pred , entry );
214}
215
216/***************************************************************************
217 * This function returns true if the list is empty.
218 ***************************************************************************
219 * @ root    : pointer on the list root
220 **************************************************************************/
221static inline bool_t list_is_empty( list_entry_t * root )
222{
223    return ( root == root->next );
224}
225
226/***************************************************************************
227 * This function remove an entry from a rooted double linked list.
228 ***************************************************************************
229 * @ entry : pointer on the entry to be removed.
230 **************************************************************************/
231static inline void list_unlink( list_entry_t * entry )
232{
233        list_entry_t * pred_entry;
234    list_entry_t * next_entry;
235
236        pred_entry = entry->pred;
237        next_entry = entry->next;
238
239        pred_entry->next = entry->next;
240        next_entry->pred = entry->pred;
241}
242
243/***************************************************************************
244 * This function replace an entry in a rooted double linked list.
245 ***************************************************************************
246 * @current  : entry to be removed.
247 * @new      : entry to be introduced.
248 **************************************************************************/
249static inline void list_replace( list_entry_t * current,
250                                 list_entry_t * new )
251{
252    list_entry_t * pred_entry;
253    list_entry_t * next_entry;
254
255        pred_entry = current->pred;
256        next_entry = current->next;
257
258        new->next = next_entry;
259        new->pred = pred_entry;
260
261        pred_entry->next = new;
262        next_entry->pred = new;
263}
264
265
266#endif  /* _ALMOS_LIST_H_ */
Note: See TracBrowser for help on using the repository browser.