source: trunk/kernel/libk/list.h

Last change on this file was 656, checked in by alain, 11 months ago

Fix several bugs in the FATFS and in the VFS,
related to the creation of big files requiring
more than 4 Kbytes (one cluster) on device.

File size: 17.1 KB
Line 
1/*
2 * list.h - Local double circular linked list, using local pointers.
3 *
4 * Authors Ghassan Almaless  (2008,2009,2010,2011,2012)
5 *         Alain Greiner     (2016,2017,2018,2019)
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 <hal_remote.h>
31#include <printk.h>
32
33#ifndef NULL
34#define NULL (void *) 0
35#endif
36
37
38////////////////////////////////////////////////////////////////////////////
39//          Double circular linked list functions & macros
40//
41// It defines a generic local list, as all elements are in the same cluster.
42//
43// There is two sets of access functions, because these local lists can be
44// accessed by local threads, using local pointers, but they can also be
45// accessed by remote threads running in any cluster, with specific access
46// functions using extended pointers.
47////////////////////////////////////////////////////////////////////////////
48
49/***************************************************************************
50 * This structure defines a Double Circular Linked List entry.
51 * Note : The list root is an extra list-entry_t, that is NOT part
52 *            of the set of linked elements.
53 **************************************************************************/
54
55typedef struct list_entry_s
56{
57        struct list_entry_s * next;
58        struct list_entry_s * pred;
59}
60list_entry_t;
61
62/***************************************************************************
63 * This macro return an intptr_t that is the offset (number of bytes)
64 * of a field in a structure.
65 ***************************************************************************
66 * @ type   : structure type
67 * @ member : name of the field
68 **************************************************************************/
69
70#ifndef OFFSETOF
71#define OFFSETOF( type , member ) ((intptr_t) & ((type *)0)->member)
72#endif
73
74/***************************************************************************
75 * This macro returns a pointer on a structure containing a list_entry_t.
76 ***************************************************************************
77 * @ list_ptr       : pointer on the list_entry
78 * @ container_type : type of the structure containing the list-entry
79 * @ member_name    : name of the list_entry field
80 **************************************************************************/
81
82#define LIST_ELEMENT( list_ptr , container_type , member_name)          \
83        ({const typeof(((container_type*)0)->member_name) *__member_ptr = (list_ptr); \
84        (container_type *)( (char*)__member_ptr - OFFSETOF( container_type , member_name ));})
85
86
87////////////////////////////////////////////////////////////////////////////
88// These functions and macros mus be called by a thread running
89// in the local cluster to access the local list.
90////////////////////////////////////////////////////////////////////////////
91
92/***************************************************************************
93 * This macro returns a pointer on the first element of a list.
94 ***************************************************************************
95 * @ root     : pointer on the list root
96 * @ type     : type of the linked elements
97 * @ member   : name of the list_entry_t field
98 **************************************************************************/
99
100#define LIST_FIRST( root , type , member )              \
101        LIST_ELEMENT( (root)->next , type , member )
102
103/***************************************************************************
104 * This macro returns a pointer on the last element of a list.
105 ***************************************************************************
106 * @ root     : pointer on the list root
107 * @ type     : type of the linked elements
108 * @ member   : name of the list_entry_t field
109 **************************************************************************/
110
111#define LIST_LAST( root , type , member )               \
112        LIST_ELEMENT( (root)->pred , type , member )
113
114/***************************************************************************
115 * This macro traverse a rooted double linked list in forward order.
116 * WARNING : Don't use this macro when you want to remove one or several
117 * item(s) from the traversed list.     
118 ***************************************************************************
119 * @ root      : pointer on the root list_entry
120 * @ iter      : pointer on a list_entry
121 **************************************************************************/
122
123#define LIST_FOREACH( root , iter ) \
124for( (iter) = (root)->next ;        \
125     (iter) != (root) ;                         \
126     (iter) = (iter)->next )
127       
128/***************************************************************************
129 * This macro traverse a rooted double linked list in backward order.
130 * WARNING : same as the forward traversal
131 ***************************************************************************
132 * @ root      : pointer on the root list_entry
133 * @ iter      : pointer on a list_entry
134 **************************************************************************/
135
136#define LIST_FOREACH_BACKWARD( root , iter )  \
137for( (iter) = (root)->pred ;                  \
138     (iter) != (root) ;                       \
139     (iter) = (iter)->pred )
140
141/***************************************************************************
142 * This function initializes the root of a rooted double linked list.
143 ***************************************************************************
144 * @ root    : pointer on the list root
145 **************************************************************************/
146static inline void list_root_init( list_entry_t * root )
147{
148        root->next = root;
149        root->pred = root;
150}
151
152/***************************************************************************
153 * This function initializes an entry of a rooted double linked list.
154 ***************************************************************************
155 * @ entry   : pointer on the list-entry to be initialized
156 **************************************************************************/
157static inline void list_entry_init( list_entry_t * entry )
158{
159        entry->next = NULL;
160        entry->pred = NULL;
161}
162
163/***************************************************************************
164 * This function must be called by a thread running in local cluster.
165 * It inserts a new entry in first place of a double linked list.
166 ***************************************************************************
167 * @ root    : pointer on the list root
168 * @ entry   : pointer on the list-entry to be inserted
169 **************************************************************************/
170static inline void list_add_first( list_entry_t * root, 
171                                   list_entry_t * entry )
172{
173    list_entry_t * first = root->next; 
174
175        entry->next = first;
176        entry->pred = root;
177 
178        root->next  = entry;
179        first->pred = entry;
180}
181
182/***************************************************************************
183 * This function must be called by a thread running in local cluster.
184 * It inserts a new entry in last place of a double linked list.
185 ***************************************************************************
186 * @ root    : pointer on the list root
187 * @ entry   : pointer on the list-entry to be inserted
188 **************************************************************************/
189static inline void list_add_last( list_entry_t * root,
190                                  list_entry_t * entry )
191{
192    list_entry_t * last = root->pred;
193
194        entry->next = root;
195        entry->pred = last;
196 
197        root->pred = entry;
198        last->next = entry;
199}
200
201/***************************************************************************
202 * This function must be called by a thread running in local cluster.
203 * It returns true if the list is empty.
204 ***************************************************************************
205 * @ root    : pointer on the list root
206 **************************************************************************/
207static inline bool_t list_is_empty( list_entry_t * root )
208{
209    return ( root == root->next );
210}
211
212
213/***************************************************************************
214 * This function must be called by a thread running in local cluster.
215 * It removes an entry from the list.
216 ***************************************************************************
217 * @ entry : pointer on the entry to be removed.
218 **************************************************************************/
219static inline void list_unlink( list_entry_t * entry )
220{
221        list_entry_t * pred;
222    list_entry_t * next;
223
224        pred = entry->pred;
225        next = entry->next;
226
227        pred->next = next;
228        next->pred = pred;
229}
230
231/***************************************************************************
232 * This function replace an entry in a rooted double linked list.
233 ***************************************************************************
234 * @current  : entry to be removed.
235 * @new      : entry to be introduced.
236 **************************************************************************/
237static inline void list_replace( list_entry_t * current,
238                                 list_entry_t * new )
239{
240    list_entry_t * pred_entry;
241    list_entry_t * next_entry;
242
243        pred_entry = current->pred;
244        next_entry = current->next;
245
246        new->next = next_entry;
247        new->pred = pred_entry;
248
249        pred_entry->next = new;
250        next_entry->pred = new;
251}
252
253/***************************************************************************
254 * This debug function displays all entries of a list.
255 * @ root    : local pointer on the root list_entry_t.
256 * @ string  : list identifier displayed in header.
257 * @ max     : max number of éléments to display.
258 **************************************************************************/
259static inline void list_display( list_entry_t * root,
260                                 char         * string,
261                                 uint32_t       max )
262{
263    list_entry_t * iter;
264    list_entry_t * next;
265    list_entry_t * pred;
266    uint32_t       index;
267
268    next = root->next;
269    pred = root->pred;
270
271    printk("\n***** root (%x) / next (%x) / pred (%x) / %s *****\n",
272    root, next, pred, string );
273
274    if( list_is_empty( root ) == false )
275    {
276        for( iter = next , index = 0 ;
277             (iter != root) && (index < max) ;
278             iter = next , index++ )
279        {
280            next = iter->next;
281                        pred = iter->pred;
282
283            printk(" - %d : iter (%x) / next (%x) / pred (%x)\n",
284            index, iter, next, pred );
285        }
286    }
287}  // end list_display()
288
289
290
291////////////////////////////////////////////////////////////////////////////
292// These functions and macros can be used by any thread running
293// in any cluster to access a remote local list.
294////////////////////////////////////////////////////////////////////////////
295
296/***************************************************************************
297 * This macro can be used by a thread running in any cluster to access
298 * a remote local list. It returns a local pointer on the first element
299 * of the remote list in the remote cluster.
300 ***************************************************************************
301 * @ cxy     : remote list cluster identifier
302 * @ root    : local pointer on the list root
303 * @ type    : type of the linked element
304 * @ member  : name of the list_entry_t field
305 **************************************************************************/
306
307#define LIST_REMOTE_FIRST( cxy , root , type , member )                \
308        LIST_ELEMENT( hal_remote_lpt( XPTR( (cxy) , &(root)->next ) ), \
309                  type , member )
310
311/***************************************************************************
312 * This macro can be used by a thread running in any cluster to access
313 * a remote local list. It traverse the list in forward order.
314 * WARNING : Don't use this macro when you want to remove one or several
315 * item(s) from the traversed list.     
316 ***************************************************************************
317 * @ cxy     : remote cluster identifier.
318 * @ root    : pointer on the root list_entry.
319 * @ iter    : pointer on the current list_entry.
320 **************************************************************************/
321
322#define LIST_REMOTE_FOREACH( cxy , root , iter )                 \
323for( (iter) = hal_remote_lpt( XPTR( (cxy) , &(root)->next ) ) ;  \
324     (iter) != (root) ;                                                      \
325     (iter) = hal_remote_lpt( XPTR( (cxy) , &(iter)->next ) ) )
326       
327/***************************************************************************
328 * This macro can be used by a thread running in any cluster to access
329 * a remote local list. It traverse the list in backward order.
330 * WARNING : same as the forward traversal
331 ***************************************************************************
332 * @ cxy       : remote cluster identifier.
333 * @ root      : pointer on the root list_entry.
334 * @ iter      : pointer on the current list_entry.
335 **************************************************************************/
336
337#define LIST_REMOTE_FOREACH_BACKWARD( cxy , root , iter )       \
338for( (iter) = hal_remote_lpt( XPTR( (cxy) , &(root)->pred ) ) ; \
339     (iter) != (root) ;                                         \
340     (iter) = hal_remote_lpt( XPTR( (cxy) , &(iter)->pred ) ) )
341
342/***************************************************************************
343 * This function can be called by a thread running in any cluster to access
344 * a remote local list. It returns true if the list is empty.
345 ***************************************************************************
346 * @ cxy     : remote list cluster identifier
347 * @ root    : local pointer on the remote list root
348 **************************************************************************/
349static inline bool_t list_remote_is_empty( cxy_t          cxy,
350                                           list_entry_t * root )
351{
352    list_entry_t * next = hal_remote_lpt( XPTR( cxy , &root->next ) );
353    return( root == next );
354}
355
356/***************************************************************************
357 * This function can be called by a thread running in any cluster to access
358 * a remote local list. It inserts a new entry in first place of the list.
359 ***************************************************************************
360 * @ cxy     : remote list cluster identifier
361 * @ root    : local pointer on the remote list root
362 * @ entry   : local pointer on the remote entry to be inserted
363 **************************************************************************/
364static inline void list_remote_add_first( cxy_t          cxy,
365                                          list_entry_t * root, 
366                                          list_entry_t * entry )
367{
368    list_entry_t * first = hal_remote_lpt( XPTR( cxy , &root->next ) );
369       
370        hal_remote_spt( XPTR( cxy , &entry->next ) , first );
371        hal_remote_spt( XPTR( cxy , &entry->pred ) , root );
372 
373        hal_remote_spt( XPTR( cxy , &root->next )  , entry );
374        hal_remote_spt( XPTR( cxy , &first->pred ) , entry );
375}
376
377/***************************************************************************
378 * This function can be called by a thread running in any cluster to access
379 * a remote local list. It inserts a new entry in last place of the list.
380 ***************************************************************************
381 * @ cxy     : remote list cluster identifier
382 * @ root    : local pointer on the remote list root
383 * @ entry   : local pointer on the remote entry to be inserted
384 **************************************************************************/
385static inline void list_remote_add_last( cxy_t          cxy,
386                                         list_entry_t * root, 
387                                         list_entry_t * entry )
388{
389    list_entry_t * last = hal_remote_lpt( XPTR( cxy , &root->pred ) );
390       
391        hal_remote_spt( XPTR( cxy , &entry->next ) , root );
392        hal_remote_spt( XPTR( cxy , &entry->pred ) , last );
393 
394        hal_remote_spt( XPTR( cxy , &root->pred ) , entry );
395        hal_remote_spt( XPTR( cxy , &last->next ) , entry );
396}
397
398/***************************************************************************
399 * This function can be called by a thread running in any cluster to access
400 * a remote local list. It removes an entry from the list.
401 ***************************************************************************
402 * @ cxy     : remote list cluster identifier
403 * @ entry   : local pointer on the remote entry to be removed.
404 **************************************************************************/
405static inline void list_remote_unlink( cxy_t          cxy,
406                                       list_entry_t * entry )
407{
408        list_entry_t * pred;
409    list_entry_t * next;
410
411        pred = hal_remote_lpt( XPTR( cxy , &entry->pred ) );
412        next = hal_remote_lpt( XPTR( cxy , &entry->next ) );
413
414        hal_remote_spt( XPTR( cxy , &pred->next ) , next );
415        hal_remote_spt( XPTR( cxy , &next->pred ) , pred );
416}
417
418
419#endif  /* _LIST_H_ */
Note: See TracBrowser for help on using the repository browser.