source: trunk/kernel/libk/xlist.h @ 8

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

First import

File size: 11.9 KB
Line 
1/*
2 * xlist.h - Double Circular Linked lists, using extended pointers.
3 *
4 * Author : Alain Greiner (2016)
5 *
6 * Copyright (c) UPMC Sorbonne Universites
7 *
8 * This file is part of ALMOS-MKH.
9 *
10 * ALMOS-kernel is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; version 2.0 of the License.
13 *
14 * ALMOS-kernel is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with ALMOS-kernel; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24#ifndef _ALMOS_XLIST_H_
25#define _ALMOS_XLIST_H_
26
27#include <almos_config.h>
28#include <hal_types.h>
29#include <hal_remote.h>
30
31/**** global variables ***/
32
33cxy_t  local_cxy;
34
35/***************************************************************************
36 * This structure defines an Extended Double Circular Linked List entry.
37 * Note (1) The list root is an extra xlist_entry_t, that is NOT part
38 *          of the set of linked elements.
39 * Note (2) Do NOT change the fields order in this struct.
40 **************************************************************************/
41
42typedef struct xlist_entry_s
43{
44    xptr_t  next;              // extended pointer on next xlist_entry_t
45    xptr_t  pred;              // extended pointer on previous xlist_entry_t
46}
47xlist_entry_t;
48
49/***************************************************************************
50 * This macro returns the offset (in bytes) of a field in a structure.
51 * @ type   : structure type
52 * @ member : name of the field
53 **************************************************************************/
54
55#ifndef OFFSETOF
56#define OFFSETOF( type , member ) ((unsigned int) & ((type *)0)->member)
57#endif
58
59/***************************************************************************
60 * This macro returns an extended pointer on the structure containing an
61 * embedded xlist_entry_t field.
62 * @ xlist_xp : extended pointer on the xlist_entry_t field
63 * @ type     : type of the structure containing the xlist_entry_t
64 * @ member   : name of the xlist_entry_t field
65 **************************************************************************/
66
67#define XLIST_ELEMENT( xlist_xp , type , member ) \
68    (xlist_xp - OFFSETOF( type , member ))
69
70/***************************************************************************
71 * This macro returns an extended pointer on the first element of an
72 * extended double linked list, identified by the extended pointer on
73 * the root xlist_entry_t.
74 * @ root_xp : extended pointer on the root xlist_entry_t
75 * @ type    : type of the linked elements
76 * @ member  : name of the xlist_entry_t field
77 **************************************************************************/
78
79#define XLIST_FIRST_ELEMENT( root_xp , type , member ) \
80    ({ xptr_t __first = hal_remote_lwd( root_xp );     \
81           XLIST_ELEMENT( __first , type , member ); })
82
83/***************************************************************************
84 * This macro returns an extended pointer on the last element of an
85 * extended double linked list, identified by the extended pointer on
86 * the root xlist_entry_t.
87 * @ root_xp : extended pointer on the root xlist_entry_t
88 * @ type    : type of the linked elements
89 * @ member  : name of the xlist_entry_t field
90 **************************************************************************/
91
92#define XLIST_LAST_ELEMENT( root_xp , type , member )  \
93    ({ xptr_t __last = hal_remote_lwd( root_xp + 8 );  \
94           XLIST_ELEMENT( __last , type , member ); })
95
96/***************************************************************************
97 * This macro traverses an extended double linked list in forward order.
98 * The iter variable should NOT be deleted during traversal.
99 * @ root_xp  : extended pointer on the root xlist_entry_t
100 * @ iter_xp  : current extended pointer on a xlist_entry_t
101 **************************************************************************/
102
103#define XLIST_FOREACH( root_xp , iter_xp )    \
104for( (iter_xp) = hal_remote_lwd( root_xp ) ;  \
105     (iter_xp) != (root_xp) ;                 \
106     (iter_xp) = hal_remote_lwd( iter_xp ) )
107
108/***************************************************************************
109 * This macro traverses an extended double linked list in backward order.
110 * The iter variable should NOT be deleted during traversal.
111 * @ root_xp  : extended pointer on the root xlist_entry_t
112 * @ iter_xp  : current extended pointer on a xlist_entry_t
113 **************************************************************************/
114
115#define XLIST_FOREACH_BACKWARD( root_xp , iter_xp )  \
116for( (iter_xp) = hal_remote_lwd( (root_xp) + 8 ) ;   \
117     (iter_xp) != (root_xp) ;                        \
118     (iter_xp) = hal_remote_lwd( (iter_xp) + 8 ) )
119
120/***************************************************************************
121 * This function returns an extended pointer on the next xlist_entry_t,
122 * from an extended pointer on a reference xlist_entry_t.
123 * @ root    : extended pointer on the root xlist_entry_t
124 * @ ref     : extended pointer on the reference xlist_entry_t
125 **************************************************************************/
126static inline xptr_t xlist_next( xptr_t  root,
127                                 xptr_t  ref )
128{
129    // get root->next
130    xptr_t root_next = (xptr_t)hal_remote_lwd( root );
131
132    // get ref->next
133    xptr_t ref_next  = (xptr_t)hal_remote_lwd( ref );
134
135    // test if list is empty or ref is the last element 
136    if( (root_next == root) || (ref_next == root) )  return XPTR_NULL;
137   
138        return ref_next;
139}
140
141/***************************************************************************
142 * This function returns an extended pointer on the previous xlist_entry_t.
143 * @ root    : extended pointer on the root xlist_entry_t
144 * @ ref     : extended pointer on the reference xlist_entry_t
145 **************************************************************************/
146static inline xptr_t xlist_pred( xptr_t root,
147                                 xptr_t ref )
148{
149    // get root->next
150    xptr_t root_next = (xptr_t)hal_remote_lwd( root );
151
152    // get ref->pred
153    xptr_t ref_pred  = (xptr_t)hal_remote_lwd( ref + 8 );
154
155    // test if list is empty or ref is the first element 
156    if( (root_next == root) || (ref_pred == root) )  return XPTR_NULL;
157   
158        return ref_pred;
159}
160
161/***************************************************************************
162 * This function initialises the root of an extended double linked list.
163 * The root can be located in any cluster.
164 * @ root_xp   :  extended pointer on the root xlist_entry_t
165 **************************************************************************/
166static inline void xlist_root_init( xptr_t root_xp )
167{
168    hal_remote_swd(  root_xp   , root_xp );
169    hal_remote_swd(  root_xp+8 , root_xp );
170}
171
172/***************************************************************************
173 * This function initialises an entry of an extended double linked list.
174 * The entry can be located in any cluster.
175 * @ entry_xp  : extended pointer on the xlist_entry_t
176 **************************************************************************/
177static inline void xlist_entry_init( xptr_t entry_xp )
178{
179    hal_remote_swd(  entry_xp   , 0 );
180    hal_remote_swd(  entry_xp+8 , 0 );
181}
182
183/***************************************************************************
184 * This function inserts a new entry in the first place of an extended 
185 * double linked list. Four extended pointers must be modified.
186 * The lock protecting the list should have been previously taken.
187 * @ root   : extended pointer on the root xlist_entry_t
188 * @ entry  : extended pointer on the xlist_entry_t to be inserted
189 **************************************************************************/
190static inline void xlist_add_first( xptr_t root, 
191                                    xptr_t entry )
192{
193    // get the extended pointer on the first element in list
194    xptr_t first = (xptr_t)hal_remote_lwd( root );
195
196    // update root.next <= entry
197    hal_remote_swd( root , (uint64_t)entry );
198
199    // update entry.next <= first
200    hal_remote_swd( entry , (uint64_t)first );
201
202    // entry.pred <= root
203    hal_remote_swd( entry + 8 , (uint64_t)root );
204   
205    // first.pred <= new
206    hal_remote_swd( first + 8 , (uint64_t)entry );
207}
208
209/***************************************************************************
210 * This function inserts a new entry in the last place of an extended 
211 * double linked list.  Four extended pointers must be modified.
212 * The lock protecting the list should have been previously taken.
213 * @ root   : extended pointer on the root xlist_entry_t
214 * @ entry  : extended pointer on the xlist_entry_t to be inserted
215 **************************************************************************/
216static inline void xlist_add_last( xptr_t root, 
217                                   xptr_t entry )
218{
219    // get the extended pointer on the last element in list
220    xptr_t last = (xptr_t)hal_remote_lwd( root + 8 );
221
222    // update root.pred <= entry
223    hal_remote_swd( root + 8 , (uint64_t)entry );
224
225    // update entry.pred <= last
226    hal_remote_swd( entry + 8 , (uint64_t)last );
227
228    // entry.next <= root
229    hal_remote_swd( entry , (uint64_t)root );
230   
231    // last.next <= entry
232    hal_remote_swd( last , (uint64_t)entry );
233}
234
235
236/***************************************************************************
237 * This function returns true if the list is empty.
238 * @ root  : extended pointer on the root xlist_entry_t
239 **************************************************************************/
240static inline bool_t xlist_is_empty( xptr_t root )
241{
242    // get the extended pointer root.next value
243    xptr_t next = (xptr_t)hal_remote_lwd( root );
244
245    return ( root == next );
246} 
247
248/***************************************************************************
249 * This function removes an entry from an extended  double linked list.
250 * Two extended pointers must be modified.
251 * The memory allocated to the removed entry is not released.
252 * @ xp : extended pointer on the xlist_entry_t to be removed.
253 **************************************************************************/
254static inline void xlist_unlink( xptr_t xp )
255{
256    // get a local copy of the xlist_entry_t to be removed
257    xlist_entry_t entry;
258    hal_remote_memcpy( XPTR( local_cxy , &entry ) ,
259                                  xp , 
260                                  sizeof(xlist_entry_t) );
261
262    xptr_t next = entry.next;
263    xptr_t pred = entry.pred;
264
265    // update pred.next <= next
266    hal_remote_swd( pred , (uint64_t)next );
267
268    // update next.pred <= pred
269    hal_remote_swd( next + 8 , (uint64_t)pred );
270}
271
272/***************************************************************************
273 * This function replaces an entry in an extended double linked list.
274 * Four extended pointers must be modified.
275 * The memory allocated to the removed entry is not released.
276 * @old      : extended pointer on the xlist_entry_t to be removed.
277 * @new      : extended pointer on the xlist_entry_t to be inserted.
278 **************************************************************************/
279static inline void xlist_replace( xptr_t old,
280                                  xptr_t new )
281{
282    // get a local copy of the xlist_entry_t to be removed
283    xlist_entry_t entry;
284    hal_remote_memcpy( XPTR( local_cxy , &entry ) , 
285                                  old , 
286                                  sizeof(xlist_entry_t) );
287
288    xptr_t next = entry.next;
289    xptr_t pred = entry.pred;
290
291        // update new.next <= next
292    hal_remote_swd( new , (uint64_t)next );
293
294    // update new.pred <= pred
295    hal_remote_swd( new + 8 , (uint64_t)pred );
296
297        // update pred.next <= new
298    hal_remote_swd( pred , (uint64_t)new );
299
300    // update next.pred <= new
301    hal_remote_swd( next + 8 , (uint64_t)new );
302}
303
304#endif  /* _ALMOS_LIST_H_ */
Note: See TracBrowser for help on using the repository browser.