/* * list.h - Double circular chained lists, inspired from linux * * Authors Ghassan Almaless (2008,2009,2010,2011,2012) * Alain Greiner (2016) * * 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 _ALMOS_LIST_H_ #define _ALMOS_LIST_H_ #include #include #ifndef NULL #define NULL (void *) 0 #endif /*************************************************************************** * 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 //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// // Double circular linked list functions & macros //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// /*************************************************************************** * 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 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 ));}) /*************************************************************************** * This macro returns the first element of a rooted double linked 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 the last element of a rooted double linked 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 2 LIST_FOREACH in the same function, because the * variable __ptr will be defined twice, wich result in a compilation error. *************************************************************************** * @ 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 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 * pred_entry; list_entry_t * next_entry; pred_entry = root; next_entry = root->next; entry->next = next_entry; entry->pred = pred_entry; pred_entry->next = entry; next_entry->pred = entry; } /*************************************************************************** * This function 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_entry; list_entry_t * next_entry; pred_entry = root->pred; next_entry = root; entry->next = next_entry; entry->pred = pred_entry; pred_entry->next = entry; next_entry->pred = entry; } /*************************************************************************** * This function 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 remove an entry from a rooted double linked list. *************************************************************************** * @ entry : pointer on the entry to be removed. **************************************************************************/ static inline void list_unlink( list_entry_t * entry ) { list_entry_t * pred_entry; list_entry_t * next_entry; pred_entry = entry->pred; next_entry = entry->next; pred_entry->next = entry->next; next_entry->pred = entry->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; } #endif /* _ALMOS_LIST_H_ */