[1] | 1 | /* |
---|
[656] | 2 | * list.h - Local double circular linked list, using local pointers. |
---|
[1] | 3 | * |
---|
| 4 | * Authors Ghassan Almaless (2008,2009,2010,2011,2012) |
---|
[671] | 5 | * Alain Greiner (2016,2017,2018,2019,2020) |
---|
[1] | 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 | |
---|
[610] | 25 | #ifndef _LIST_H_ |
---|
| 26 | #define _LIST_H_ |
---|
[1] | 27 | |
---|
[14] | 28 | #include <kernel_config.h> |
---|
[457] | 29 | #include <hal_kernel_types.h> |
---|
[632] | 30 | #include <hal_remote.h> |
---|
[610] | 31 | #include <printk.h> |
---|
[1] | 32 | |
---|
| 33 | #ifndef NULL |
---|
| 34 | #define NULL (void *) 0 |
---|
| 35 | #endif |
---|
| 36 | |
---|
| 37 | |
---|
| 38 | //////////////////////////////////////////////////////////////////////////// |
---|
[632] | 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. |
---|
[1] | 47 | //////////////////////////////////////////////////////////////////////////// |
---|
| 48 | |
---|
| 49 | /*************************************************************************** |
---|
| 50 | * This structure defines a Double Circular Linked List entry. |
---|
[450] | 51 | * Note : The list root is an extra list-entry_t, that is NOT part |
---|
| 52 | * of the set of linked elements. |
---|
[1] | 53 | **************************************************************************/ |
---|
| 54 | |
---|
| 55 | typedef struct list_entry_s |
---|
| 56 | { |
---|
| 57 | struct list_entry_s * next; |
---|
| 58 | struct list_entry_s * pred; |
---|
| 59 | } |
---|
| 60 | list_entry_t; |
---|
| 61 | |
---|
| 62 | /*************************************************************************** |
---|
[651] | 63 | * This macro return an intptr_t that is the offset (number of bytes) |
---|
[632] | 64 | * of a field in a structure. |
---|
[651] | 65 | *************************************************************************** |
---|
[632] | 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 | /*************************************************************************** |
---|
[1] | 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 | |
---|
[632] | 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 | |
---|
[1] | 92 | /*************************************************************************** |
---|
[656] | 93 | * This macro returns a pointer on the first element of a list. |
---|
[1] | 94 | *************************************************************************** |
---|
[440] | 95 | * @ root : pointer on the list root |
---|
[1] | 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 | /*************************************************************************** |
---|
[612] | 104 | * This macro returns a pointer on the last element of a list. |
---|
[1] | 105 | *************************************************************************** |
---|
[440] | 106 | * @ root : pointer on the list root |
---|
[1] | 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. |
---|
[632] | 116 | * WARNING : Don't use this macro when you want to remove one or several |
---|
| 117 | * item(s) from the traversed list. |
---|
[1] | 118 | *************************************************************************** |
---|
| 119 | * @ root : pointer on the root list_entry |
---|
| 120 | * @ iter : pointer on a list_entry |
---|
| 121 | **************************************************************************/ |
---|
| 122 | |
---|
| 123 | #define LIST_FOREACH( root , iter ) \ |
---|
| 124 | for( (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 ) \ |
---|
| 137 | for( (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 | **************************************************************************/ |
---|
| 146 | static 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 | **************************************************************************/ |
---|
| 157 | static inline void list_entry_init( list_entry_t * entry ) |
---|
| 158 | { |
---|
| 159 | entry->next = NULL; |
---|
| 160 | entry->pred = NULL; |
---|
| 161 | } |
---|
| 162 | |
---|
| 163 | /*************************************************************************** |
---|
[632] | 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. |
---|
[1] | 166 | *************************************************************************** |
---|
| 167 | * @ root : pointer on the list root |
---|
| 168 | * @ entry : pointer on the list-entry to be inserted |
---|
| 169 | **************************************************************************/ |
---|
| 170 | static inline void list_add_first( list_entry_t * root, |
---|
| 171 | list_entry_t * entry ) |
---|
| 172 | { |
---|
[656] | 173 | list_entry_t * first = root->next; |
---|
[632] | 174 | |
---|
[656] | 175 | entry->next = first; |
---|
[632] | 176 | entry->pred = root; |
---|
[1] | 177 | |
---|
[656] | 178 | root->next = entry; |
---|
| 179 | first->pred = entry; |
---|
[1] | 180 | } |
---|
| 181 | |
---|
| 182 | /*************************************************************************** |
---|
[632] | 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. |
---|
[1] | 185 | *************************************************************************** |
---|
| 186 | * @ root : pointer on the list root |
---|
| 187 | * @ entry : pointer on the list-entry to be inserted |
---|
| 188 | **************************************************************************/ |
---|
| 189 | static inline void list_add_last( list_entry_t * root, |
---|
| 190 | list_entry_t * entry ) |
---|
| 191 | { |
---|
[656] | 192 | list_entry_t * last = root->pred; |
---|
[437] | 193 | |
---|
[632] | 194 | entry->next = root; |
---|
[656] | 195 | entry->pred = last; |
---|
[437] | 196 | |
---|
[632] | 197 | root->pred = entry; |
---|
[656] | 198 | last->next = entry; |
---|
[1] | 199 | } |
---|
| 200 | |
---|
| 201 | /*************************************************************************** |
---|
[632] | 202 | * This function must be called by a thread running in local cluster. |
---|
| 203 | * It returns true if the list is empty. |
---|
[1] | 204 | *************************************************************************** |
---|
| 205 | * @ root : pointer on the list root |
---|
| 206 | **************************************************************************/ |
---|
| 207 | static inline bool_t list_is_empty( list_entry_t * root ) |
---|
| 208 | { |
---|
| 209 | return ( root == root->next ); |
---|
| 210 | } |
---|
| 211 | |
---|
[632] | 212 | |
---|
[1] | 213 | /*************************************************************************** |
---|
[632] | 214 | * This function must be called by a thread running in local cluster. |
---|
| 215 | * It removes an entry from the list. |
---|
[1] | 216 | *************************************************************************** |
---|
| 217 | * @ entry : pointer on the entry to be removed. |
---|
| 218 | **************************************************************************/ |
---|
| 219 | static inline void list_unlink( list_entry_t * entry ) |
---|
| 220 | { |
---|
[671] | 221 | list_entry_t * pred = entry->pred; |
---|
| 222 | list_entry_t * next = entry->next; |
---|
[1] | 223 | |
---|
[632] | 224 | pred->next = next; |
---|
| 225 | next->pred = pred; |
---|
[671] | 226 | |
---|
| 227 | entry->next = NULL; |
---|
| 228 | entry->pred = NULL; |
---|
[1] | 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 | **************************************************************************/ |
---|
| 237 | static 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 | |
---|
[610] | 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 | **************************************************************************/ |
---|
| 259 | static 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; |
---|
[1] | 267 | |
---|
[610] | 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 | |
---|
[632] | 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 | |
---|
[635] | 307 | #define LIST_REMOTE_FIRST( cxy , root , type , member ) \ |
---|
| 308 | LIST_ELEMENT( hal_remote_lpt( XPTR( (cxy) , &(root)->next ) ), \ |
---|
| 309 | type , member ) |
---|
[632] | 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 | *************************************************************************** |
---|
[636] | 317 | * @ cxy : remote cluster identifier. |
---|
| 318 | * @ root : pointer on the root list_entry. |
---|
| 319 | * @ iter : pointer on the current list_entry. |
---|
[632] | 320 | **************************************************************************/ |
---|
| 321 | |
---|
[636] | 322 | #define LIST_REMOTE_FOREACH( cxy , root , iter ) \ |
---|
| 323 | for( (iter) = hal_remote_lpt( XPTR( (cxy) , &(root)->next ) ) ; \ |
---|
| 324 | (iter) != (root) ; \ |
---|
| 325 | (iter) = hal_remote_lpt( XPTR( (cxy) , &(iter)->next ) ) ) |
---|
[632] | 326 | |
---|
| 327 | /*************************************************************************** |
---|
[636] | 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 ) \ |
---|
| 338 | for( (iter) = hal_remote_lpt( XPTR( (cxy) , &(root)->pred ) ) ; \ |
---|
| 339 | (iter) != (root) ; \ |
---|
| 340 | (iter) = hal_remote_lpt( XPTR( (cxy) , &(iter)->pred ) ) ) |
---|
| 341 | |
---|
| 342 | /*************************************************************************** |
---|
[632] | 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 | **************************************************************************/ |
---|
| 349 | static 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 | **************************************************************************/ |
---|
| 364 | static inline void list_remote_add_first( cxy_t cxy, |
---|
| 365 | list_entry_t * root, |
---|
| 366 | list_entry_t * entry ) |
---|
| 367 | { |
---|
[656] | 368 | list_entry_t * first = hal_remote_lpt( XPTR( cxy , &root->next ) ); |
---|
[632] | 369 | |
---|
[656] | 370 | hal_remote_spt( XPTR( cxy , &entry->next ) , first ); |
---|
[632] | 371 | hal_remote_spt( XPTR( cxy , &entry->pred ) , root ); |
---|
| 372 | |
---|
[656] | 373 | hal_remote_spt( XPTR( cxy , &root->next ) , entry ); |
---|
| 374 | hal_remote_spt( XPTR( cxy , &first->pred ) , entry ); |
---|
[632] | 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 | **************************************************************************/ |
---|
| 385 | static inline void list_remote_add_last( cxy_t cxy, |
---|
| 386 | list_entry_t * root, |
---|
| 387 | list_entry_t * entry ) |
---|
| 388 | { |
---|
[656] | 389 | list_entry_t * last = hal_remote_lpt( XPTR( cxy , &root->pred ) ); |
---|
[632] | 390 | |
---|
| 391 | hal_remote_spt( XPTR( cxy , &entry->next ) , root ); |
---|
[656] | 392 | hal_remote_spt( XPTR( cxy , &entry->pred ) , last ); |
---|
[632] | 393 | |
---|
| 394 | hal_remote_spt( XPTR( cxy , &root->pred ) , entry ); |
---|
[656] | 395 | hal_remote_spt( XPTR( cxy , &last->next ) , entry ); |
---|
[632] | 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 |
---|
[656] | 403 | * @ entry : local pointer on the remote entry to be removed. |
---|
[632] | 404 | **************************************************************************/ |
---|
| 405 | static inline void list_remote_unlink( cxy_t cxy, |
---|
| 406 | list_entry_t * entry ) |
---|
| 407 | { |
---|
[671] | 408 | list_entry_t * pred = hal_remote_lpt( XPTR( cxy , &entry->pred ) ); |
---|
| 409 | list_entry_t * next = hal_remote_lpt( XPTR( cxy , &entry->next ) ); |
---|
[632] | 410 | |
---|
| 411 | hal_remote_spt( XPTR( cxy , &pred->next ) , next ); |
---|
| 412 | hal_remote_spt( XPTR( cxy , &next->pred ) , pred ); |
---|
[671] | 413 | |
---|
| 414 | hal_remote_spt( XPTR( cxy , &entry->next ) , NULL ); |
---|
| 415 | hal_remote_spt( XPTR( cxy , &entry->pred ) , NULL ); |
---|
[632] | 416 | } |
---|
| 417 | |
---|
| 418 | |
---|
[610] | 419 | #endif /* _LIST_H_ */ |
---|