/* * list.h - Double circular linked list * * Authors Ghassan Almaless (2008,2009,2010,2011,2012) * Alain Greiner (2016,2017,2018,2019) * * Copyright (c) UPMC Sorbonne Universites * * This file is part of ALMOS-MKH * * ALMOS-MKH is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by * the Free Software Foundation; version 2.0 of the License. * * ALMOS-MKH is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with ALMOS-MKH; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #ifndef _LIST_H_ #define _LIST_H_ #include #include #include #include #ifndef NULL #define NULL (void *) 0 #endif //////////////////////////////////////////////////////////////////////////// // Double circular linked list functions & macros // // It defines a generic local list, as all elements are in the same cluster. // // There is two sets of access functions, because these local lists can be // accessed by local threads, using local pointers, but they can also be // accessed by remote threads running in any cluster, with specific access // functions using extended pointers. //////////////////////////////////////////////////////////////////////////// /*************************************************************************** * This structure defines a Double Circular Linked List entry. * Note : The list root is an extra list-entry_t, that is NOT part * of the set of linked elements. **************************************************************************/ typedef struct list_entry_s { struct list_entry_s * next; struct list_entry_s * pred; } list_entry_t; /*************************************************************************** * This macro return an uint32_t that is the offset (number of bytes) * of a field in a structure. * @ type : structure type * @ member : name of the field **************************************************************************/ #ifndef OFFSETOF #define OFFSETOF( type , member ) ((intptr_t) & ((type *)0)->member) #endif /*************************************************************************** * This macro returns a pointer on a structure containing a list_entry_t. *************************************************************************** * @ list_ptr : pointer on the list_entry * @ container_type : type of the structure containing the list-entry * @ member_name : name of the list_entry field **************************************************************************/ #define LIST_ELEMENT( list_ptr , container_type , member_name) \ ({const typeof(((container_type*)0)->member_name) *__member_ptr = (list_ptr); \ (container_type *)( (char*)__member_ptr - OFFSETOF( container_type , member_name ));}) //////////////////////////////////////////////////////////////////////////// // These functions and macros mus be called by a thread running // in the local cluster to access the local list. //////////////////////////////////////////////////////////////////////////// /*************************************************************************** * This macro returns t pointer on the first element of a list. *************************************************************************** * @ root : pointer on the list root * @ type : type of the linked elements * @ member : name of the list_entry_t field **************************************************************************/ #define LIST_FIRST( root , type , member ) \ LIST_ELEMENT( (root)->next , type , member ) /*************************************************************************** * This macro returns a pointer on the last element of a list. *************************************************************************** * @ root : pointer on the list root * @ type : type of the linked elements * @ member : name of the list_entry_t field **************************************************************************/ #define LIST_LAST( root , type , member ) \ LIST_ELEMENT( (root)->pred , type , member ) /*************************************************************************** * This macro traverse a rooted double linked list in forward order. * WARNING : Don't use this macro when you want to remove one or several * item(s) from the traversed list. *************************************************************************** * @ root : pointer on the root list_entry * @ iter : pointer on a list_entry **************************************************************************/ #define LIST_FOREACH( root , iter ) \ for( (iter) = (root)->next ; \ (iter) != (root) ; \ (iter) = (iter)->next ) /*************************************************************************** * This macro traverse a rooted double linked list in backward order. * WARNING : same as the forward traversal *************************************************************************** * @ root : pointer on the root list_entry * @ iter : pointer on a list_entry **************************************************************************/ #define LIST_FOREACH_BACKWARD( root , iter ) \ for( (iter) = (root)->pred ; \ (iter) != (root) ; \ (iter) = (iter)->pred ) /*************************************************************************** * This function initializes the root of a rooted double linked list. *************************************************************************** * @ root : pointer on the list root **************************************************************************/ static inline void list_root_init( list_entry_t * root ) { root->next = root; root->pred = root; } /*************************************************************************** * This function initializes an entry of a rooted double linked list. *************************************************************************** * @ entry : pointer on the list-entry to be initialized **************************************************************************/ static inline void list_entry_init( list_entry_t * entry ) { entry->next = NULL; entry->pred = NULL; } /*************************************************************************** * This function must be called by a thread running in local cluster. * It inserts a new entry in first place of a double linked list. *************************************************************************** * @ root : pointer on the list root * @ entry : pointer on the list-entry to be inserted **************************************************************************/ static inline void list_add_first( list_entry_t * root, list_entry_t * entry ) { list_entry_t * next = root->next; entry->next = next; entry->pred = root; root->next = entry; next->pred = entry; } /*************************************************************************** * This function must be called by a thread running in local cluster. * It inserts a new entry in last place of a double linked list. *************************************************************************** * @ root : pointer on the list root * @ entry : pointer on the list-entry to be inserted **************************************************************************/ static inline void list_add_last( list_entry_t * root, list_entry_t * entry ) { list_entry_t * pred = root->pred; entry->next = root; entry->pred = pred; root->pred = entry; pred->next = entry; } /*************************************************************************** * This function must be called by a thread running in local cluster. * It returns true if the list is empty. *************************************************************************** * @ root : pointer on the list root **************************************************************************/ static inline bool_t list_is_empty( list_entry_t * root ) { return ( root == root->next ); } /*************************************************************************** * This function must be called by a thread running in local cluster. * It removes an entry from the list. *************************************************************************** * @ entry : pointer on the entry to be removed. **************************************************************************/ static inline void list_unlink( list_entry_t * entry ) { list_entry_t * pred; list_entry_t * next; pred = entry->pred; next = entry->next; pred->next = next; next->pred = pred; } /*************************************************************************** * This function replace an entry in a rooted double linked list. *************************************************************************** * @current : entry to be removed. * @new : entry to be introduced. **************************************************************************/ static inline void list_replace( list_entry_t * current, list_entry_t * new ) { list_entry_t * pred_entry; list_entry_t * next_entry; pred_entry = current->pred; next_entry = current->next; new->next = next_entry; new->pred = pred_entry; pred_entry->next = new; next_entry->pred = new; } /*************************************************************************** * This debug function displays all entries of a list. * @ root : local pointer on the root list_entry_t. * @ string : list identifier displayed in header. * @ max : max number of éléments to display. **************************************************************************/ static inline void list_display( list_entry_t * root, char * string, uint32_t max ) { list_entry_t * iter; list_entry_t * next; list_entry_t * pred; uint32_t index; next = root->next; pred = root->pred; printk("\n***** root (%x) / next (%x) / pred (%x) / %s *****\n", root, next, pred, string ); if( list_is_empty( root ) == false ) { for( iter = next , index = 0 ; (iter != root) && (index < max) ; iter = next , index++ ) { next = iter->next; pred = iter->pred; printk(" - %d : iter (%x) / next (%x) / pred (%x)\n", index, iter, next, pred ); } } } // end list_display() //////////////////////////////////////////////////////////////////////////// // These functions and macros can be used by any thread running // in any cluster to access a remote local list. //////////////////////////////////////////////////////////////////////////// /*************************************************************************** * This macro can be used by a thread running in any cluster to access * a remote local list. It returns a local pointer on the first element * of the remote list in the remote cluster. *************************************************************************** * @ cxy : remote list cluster identifier * @ root : local pointer on the list root * @ type : type of the linked element * @ member : name of the list_entry_t field **************************************************************************/ #define LIST_REMOTE_FIRST( cxy , root , type , member ) \ LIST_ELEMENT( hal_remote_lpt( XPTR( (cxy) , &(root)->next ) ), \ type , member ) /*************************************************************************** * This macro can be used by a thread running in any cluster to access * a remote local list. It traverse the list in forward order. * WARNING : Don't use this macro when you want to remove one or several * item(s) from the traversed list. *************************************************************************** * @ cxy : remote cluster identifier. * @ root : pointer on the root list_entry. * @ iter : pointer on the current list_entry. **************************************************************************/ #define LIST_REMOTE_FOREACH( cxy , root , iter ) \ for( (iter) = hal_remote_lpt( XPTR( (cxy) , &(root)->next ) ) ; \ (iter) != (root) ; \ (iter) = hal_remote_lpt( XPTR( (cxy) , &(iter)->next ) ) ) /*************************************************************************** * This macro can be used by a thread running in any cluster to access * a remote local list. It traverse the list in backward order. * WARNING : same as the forward traversal *************************************************************************** * @ cxy : remote cluster identifier. * @ root : pointer on the root list_entry. * @ iter : pointer on the current list_entry. **************************************************************************/ #define LIST_REMOTE_FOREACH_BACKWARD( cxy , root , iter ) \ for( (iter) = hal_remote_lpt( XPTR( (cxy) , &(root)->pred ) ) ; \ (iter) != (root) ; \ (iter) = hal_remote_lpt( XPTR( (cxy) , &(iter)->pred ) ) ) /*************************************************************************** * This function can be called by a thread running in any cluster to access * a remote local list. It returns true if the list is empty. *************************************************************************** * @ cxy : remote list cluster identifier * @ root : local pointer on the remote list root **************************************************************************/ static inline bool_t list_remote_is_empty( cxy_t cxy, list_entry_t * root ) { list_entry_t * next = hal_remote_lpt( XPTR( cxy , &root->next ) ); return( root == next ); } /*************************************************************************** * This function can be called by a thread running in any cluster to access * a remote local list. It inserts a new entry in first place of the list. *************************************************************************** * @ cxy : remote list cluster identifier * @ root : local pointer on the remote list root * @ entry : local pointer on the remote entry to be inserted **************************************************************************/ static inline void list_remote_add_first( cxy_t cxy, list_entry_t * root, list_entry_t * entry ) { list_entry_t * next = hal_remote_lpt( XPTR( cxy , &root->next ) ); hal_remote_spt( XPTR( cxy , &entry->next ) , next ); hal_remote_spt( XPTR( cxy , &entry->pred ) , root ); hal_remote_spt( XPTR( cxy , &root->next ) , entry ); hal_remote_spt( XPTR( cxy , &next->pred ) , entry ); } /*************************************************************************** * This function can be called by a thread running in any cluster to access * a remote local list. It inserts a new entry in last place of the list. *************************************************************************** * @ cxy : remote list cluster identifier * @ root : local pointer on the remote list root * @ entry : local pointer on the remote entry to be inserted **************************************************************************/ static inline void list_remote_add_last( cxy_t cxy, list_entry_t * root, list_entry_t * entry ) { list_entry_t * pred = hal_remote_lpt( XPTR( cxy , &root->pred ) ); hal_remote_spt( XPTR( cxy , &entry->next ) , root ); hal_remote_spt( XPTR( cxy , &entry->pred ) , pred ); hal_remote_spt( XPTR( cxy , &root->pred ) , entry ); hal_remote_spt( XPTR( cxy , &pred->next ) , entry ); } /*************************************************************************** * This function can be called by a thread running in any cluster to access * a remote local list. It removes an entry from the list. *************************************************************************** * @ cxy : remote list cluster identifier * @ entry : pointer on the entry to be removed. **************************************************************************/ static inline void list_remote_unlink( cxy_t cxy, list_entry_t * entry ) { list_entry_t * pred; list_entry_t * next; pred = hal_remote_lpt( XPTR( cxy , &entry->pred ) ); next = hal_remote_lpt( XPTR( cxy , &entry->next ) ); hal_remote_spt( XPTR( cxy , &pred->next ) , next ); hal_remote_spt( XPTR( cxy , &next->pred ) , pred ); } #endif /* _LIST_H_ */