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

/*
 * list.h - Local double circular linked list, using local pointers.
 *
 * 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 <kernel_config.h>
#include <hal_kernel_types.h>
#include <hal_remote.h>
#include <printk.h>

#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 intptr_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 a 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 * first = root->next;  

        entry->next = first;
        entry->pred = root;
  
        root->next  = entry;
        first->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 * last = root->pred;

        entry->next = root;
        entry->pred = last;
  
        root->pred = entry;
        last->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 * first = hal_remote_lpt( XPTR( cxy , &root->next ) );
        
        hal_remote_spt( XPTR( cxy , &entry->next ) , first );
        hal_remote_spt( XPTR( cxy , &entry->pred ) , root );
  
        hal_remote_spt( XPTR( cxy , &root->next )  , entry );
        hal_remote_spt( XPTR( cxy , &first->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 * last = hal_remote_lpt( XPTR( cxy , &root->pred ) );
        
        hal_remote_spt( XPTR( cxy , &entry->next ) , root );
        hal_remote_spt( XPTR( cxy , &entry->pred ) , last );
  
        hal_remote_spt( XPTR( cxy , &root->pred ) , entry );
        hal_remote_spt( XPTR( cxy , &last->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   : local pointer on the remote 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_ */