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

Last change on this file since 666 was 656, checked in by alain, 4 years 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.