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

Last change on this file since 626 was 612, checked in by alain, 6 years ago

Fix several bugs in vfs.c, fatfs.c, and devfs.c to support
the <.> and <..> directory entries.

File size: 10.4 KB
Line 
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,2017,2018)
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 _LIST_H_
26#define _LIST_H_
27
28#include <kernel_config.h>
29#include <hal_kernel_types.h>
30#include <printk.h>
31
32#ifndef NULL
33#define NULL (void *) 0
34#endif
35
36
37/***************************************************************************
38 * This macro return an uint32_t that is the offset (number of bytes)
39 * of a field in a structure.
40 * @ type   : structure type
41 * @ member : name of the field
42 **************************************************************************/
43
44#ifndef OFFSETOF
45#define OFFSETOF( type , member ) ((intptr_t) & ((type *)0)->member)
46#endif
47
48////////////////////////////////////////////////////////////////////////////
49////////////////////////////////////////////////////////////////////////////
50//          Double circular linked list functions & macros
51////////////////////////////////////////////////////////////////////////////
52////////////////////////////////////////////////////////////////////////////
53
54/***************************************************************************
55 * This structure defines a Double Circular Linked List entry.
56 * Note : The list root is an extra list-entry_t, that is NOT part
57 *            of the set of linked elements.
58 **************************************************************************/
59
60typedef struct list_entry_s
61{
62        struct list_entry_s * next;
63        struct list_entry_s * pred;
64}
65list_entry_t;
66
67/***************************************************************************
68 * This macro returns a pointer on a structure containing a list_entry_t.
69 ***************************************************************************
70 * @ list_ptr       : pointer on the list_entry
71 * @ container_type : type of the structure containing the list-entry
72 * @ member_name    : name of the list_entry field
73 **************************************************************************/
74
75#define LIST_ELEMENT( list_ptr , container_type , member_name)          \
76        ({const typeof(((container_type*)0)->member_name) *__member_ptr = (list_ptr); \
77        (container_type *)( (char*)__member_ptr - OFFSETOF( container_type , member_name ));})
78
79/***************************************************************************
80 * This macro returns t pointer on the first element of a list.
81 ***************************************************************************
82 * @ root     : pointer on the list root
83 * @ type     : type of the linked elements
84 * @ member   : name of the list_entry_t field
85 **************************************************************************/
86
87#define LIST_FIRST( root , type , member )              \
88        LIST_ELEMENT( (root)->next , type , member )
89
90/***************************************************************************
91 * This macro returns a pointer on the last element of a list.
92 ***************************************************************************
93 * @ root     : pointer on the list root
94 * @ type     : type of the linked elements
95 * @ member   : name of the list_entry_t field
96 **************************************************************************/
97
98#define LIST_LAST( root , type , member )               \
99        LIST_ELEMENT( (root)->pred , type , member )
100
101/***************************************************************************
102 * This macro traverse a rooted double linked list in forward order.
103 * WARNING : Don't use 2 LIST_FOREACH in the same function, because the
104 * variable __ptr will be defined twice, wich result in a compilation error.
105 ***************************************************************************
106 * @ root      : pointer on the root list_entry
107 * @ iter      : pointer on a list_entry
108 **************************************************************************/
109
110#define LIST_FOREACH( root , iter ) \
111for( (iter) = (root)->next ;        \
112     (iter) != (root) ;                         \
113     (iter) = (iter)->next )
114       
115/***************************************************************************
116 * This macro traverse a rooted double linked list in backward order.
117 * WARNING : same as the forward traversal
118 ***************************************************************************
119 * @ root      : pointer on the root list_entry
120 * @ iter      : pointer on a list_entry
121 **************************************************************************/
122
123#define LIST_FOREACH_BACKWARD( root , iter )  \
124for( (iter) = (root)->pred ;                  \
125     (iter) != (root) ;                       \
126     (iter) = (iter)->pred )
127
128/***************************************************************************
129 * This function initializes the root of a rooted double linked list.
130 ***************************************************************************
131 * @ root    : pointer on the list root
132 **************************************************************************/
133static inline void list_root_init( list_entry_t * root )
134{
135        root->next = root;
136        root->pred = root;
137}
138
139/***************************************************************************
140 * This function initializes an entry of a rooted double linked list.
141 ***************************************************************************
142 * @ entry   : pointer on the list-entry to be initialized
143 **************************************************************************/
144static inline void list_entry_init( list_entry_t * entry )
145{
146        entry->next = NULL;
147        entry->pred = NULL;
148}
149
150/***************************************************************************
151 * This function inserts a new entry in first place of a double linked list.
152 ***************************************************************************
153 * @ root    : pointer on the list root
154 * @ entry   : pointer on the list-entry to be inserted
155 **************************************************************************/
156static inline void list_add_first( list_entry_t * root, 
157                                   list_entry_t * entry )
158{
159    list_entry_t * pred_entry;
160    list_entry_t * next_entry;
161 
162        pred_entry = root;
163        next_entry = root->next;
164       
165        entry->next = next_entry;
166        entry->pred = pred_entry;
167 
168        pred_entry->next = entry;
169        next_entry->pred = entry;
170}
171
172/***************************************************************************
173 * This function inserts a new entry in last place of a double linked list.
174 ***************************************************************************
175 * @ root    : pointer on the list root
176 * @ entry   : pointer on the list-entry to be inserted
177 **************************************************************************/
178static inline void list_add_last( list_entry_t * root,
179                                  list_entry_t * entry )
180{
181    list_entry_t * pred_entry;
182    list_entry_t * next_entry;
183
184        pred_entry = root->pred;
185        next_entry = root;
186       
187        entry->next = next_entry;
188        entry->pred = pred_entry;
189 
190        pred_entry->next = entry;
191        next_entry->pred = entry;
192}
193
194/***************************************************************************
195 * This function returns true if the list is empty.
196 ***************************************************************************
197 * @ root    : pointer on the list root
198 **************************************************************************/
199static inline bool_t list_is_empty( list_entry_t * root )
200{
201    return ( root == root->next );
202}
203
204/***************************************************************************
205 * This function remove an entry from a rooted double linked list.
206 ***************************************************************************
207 * @ entry : pointer on the entry to be removed.
208 **************************************************************************/
209static inline void list_unlink( list_entry_t * entry )
210{
211        list_entry_t * pred_entry;
212    list_entry_t * next_entry;
213
214        pred_entry = entry->pred;
215        next_entry = entry->next;
216
217        pred_entry->next = entry->next;
218        next_entry->pred = entry->pred;
219}
220
221/***************************************************************************
222 * This function replace an entry in a rooted double linked list.
223 ***************************************************************************
224 * @current  : entry to be removed.
225 * @new      : entry to be introduced.
226 **************************************************************************/
227static inline void list_replace( list_entry_t * current,
228                                 list_entry_t * new )
229{
230    list_entry_t * pred_entry;
231    list_entry_t * next_entry;
232
233        pred_entry = current->pred;
234        next_entry = current->next;
235
236        new->next = next_entry;
237        new->pred = pred_entry;
238
239        pred_entry->next = new;
240        next_entry->pred = new;
241}
242
243/***************************************************************************
244 * This debug function displays all entries of a list.
245 * @ root    : local pointer on the root list_entry_t.
246 * @ string  : list identifier displayed in header.
247 * @ max     : max number of éléments to display.
248 **************************************************************************/
249static inline void list_display( list_entry_t * root,
250                                 char         * string,
251                                 uint32_t       max )
252{
253    list_entry_t * iter;
254    list_entry_t * next;
255    list_entry_t * pred;
256    uint32_t       index;
257
258    next = root->next;
259    pred = root->pred;
260
261    printk("\n***** root (%x) / next (%x) / pred (%x) / %s *****\n",
262    root, next, pred, string );
263
264    if( list_is_empty( root ) == false )
265    {
266        for( iter = next , index = 0 ;
267             (iter != root) && (index < max) ;
268             iter = next , index++ )
269        {
270            next = iter->next;
271                        pred = iter->pred;
272
273            printk(" - %d : iter (%x) / next (%x) / pred (%x)\n",
274            index, iter, next, pred );
275        }
276    }
277}  // end list_display()
278
279
280#endif  /* _LIST_H_ */
Note: See TracBrowser for help on using the repository browser.