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

/*
    // check calling thread can yield
    thread_assert_can_yield( this , __FUNCTION__ );

 * xlist.h - Double Circular Linked lists, using extended pointers.
 *
 * Author : Alain Greiner (2016,2017,2018)
 *
 * Copyright (c) UPMC Sorbonne Universites
 *
 * This file is part of ALMOS-MKH.
 *
 * ALMOS-kernel 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-kernel 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-kernel; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#ifndef _XLIST_H_
#define _XLIST_H_

#include <kernel_config.h>
#include <hal_kernel_types.h>
#include <hal_remote.h>
#include <printk.h>

/**** global variables ***/

cxy_t  local_cxy;

/***************************************************************************
 * This structure defines an Extended Double Circular Linked List entry.
 * Note (1) The list root is an extra xlist_entry_t, that is NOT part
 *          of the set of linked elements.
 * Note (2) Do NOT change the fields order in this struct.
 **************************************************************************/

typedef struct xlist_entry_s
{
    xptr_t  next;              // extended pointer on next xlist_entry_t
    xptr_t  pred;              // extended pointer on previous xlist_entry_t
}
xlist_entry_t;

/***************************************************************************
 * This macro returns the offset (in 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 an extended pointer on the structure containing an
 * embedded xlist_entry_t field.
 * @ xlist_xp : extended pointer on the xlist_entry_t field
 * @ type     : type of the structure containing the xlist_entry_t
 * @ member   : name of the xlist_entry_t field
 **************************************************************************/

#define XLIST_ELEMENT( xlist_xp , type , member ) \
    (xlist_xp - OFFSETOF( type , member ))

/***************************************************************************
 * This macro returns an extended pointer on the first element of an 
 * extended double linked list, identified by the extended pointer on 
 * the root xlist_entry_t.
 * WARNING : check list non empty before using this macro.
 * @ root_xp : extended pointer on the root xlist_entry_t 
 * @ type    : type of the linked elements
 * @ member  : name of the xlist_entry_t field
 **************************************************************************/

#define XLIST_FIRST( root_xp , type , member )       \
    ({ xptr_t __first = hal_remote_l64( root_xp );   \
           XLIST_ELEMENT( __first , type , member ); })

/***************************************************************************
 * This macro returns an extended pointer on the last element of an
 * extended double linked list, identified by the extended pointer on 
 * the root xlist_entry_t.
 * WARNING : check list non empty before using this macro.
 * @ root_xp : extended pointer on the root xlist_entry_t
 * @ type    : type of the linked elements
 * @ member  : name of the xlist_entry_t field
 **************************************************************************/

#define XLIST_LAST( root_xp , type , member )                       \
    ({ xptr_t __last = hal_remote_l64( root_xp + sizeof(xptr_t) );  \
           XLIST_ELEMENT( __last , type , member ); })

/***************************************************************************
 * This macro traverses an extended double linked list in forward order.
 * WARNING : the iter variable should NOT be deleted during traversal. 
 * @ root_xp  : extended pointer on the root xlist_entry_t
 * @ iter_xp  : current extended pointer on a xlist_entry_t
 **************************************************************************/

#define XLIST_FOREACH( root_xp , iter_xp )    \
for( (iter_xp) = hal_remote_l64( root_xp ) ;  \
     (iter_xp) != (root_xp) ;                 \
     (iter_xp) = hal_remote_l64( iter_xp ) )

/***************************************************************************
 * This macro traverses an extended double linked list in backward order.
 * WARNING : the iter variable should NOT be deleted during traversal. 
 * @ root_xp  : extended pointer on the root xlist_entry_t
 * @ iter_xp  : current extended pointer on a xlist_entry_t
 **************************************************************************/

#define XLIST_FOREACH_BACKWARD( root_xp , iter_xp )              \
for( (iter_xp) = hal_remote_l64( (root_xp) + sizeof(xptr_t) ) ;  \
     (iter_xp) != (root_xp) ;                                    \
     (iter_xp) = hal_remote_l64( (iter_xp) + sizeof(xptr_t) ) )

/***************************************************************************
 * This function returns an extended pointer on the next xlist_entry_t,
 * from an extended pointer on a reference xlist_entry_t.
 * @ root    : extended pointer on the root xlist_entry_t
 * @ ref     : extended pointer on the reference xlist_entry_t
 **************************************************************************/
static inline xptr_t xlist_next( xptr_t  root,
                                 xptr_t  ref )
{
    // get root->next
    xptr_t root_next = (xptr_t)hal_remote_l64( root );

    // get ref->next
    xptr_t ref_next  = (xptr_t)hal_remote_l64( ref );

    // test if list is empty or ref is the last element  
    if( (root_next == root) || (ref_next == root) )  return XPTR_NULL;
    
        return ref_next;
}

/***************************************************************************
 * This function returns an extended pointer on the previous xlist_entry_t.
 * @ root    : extended pointer on the root xlist_entry_t
 * @ ref     : extended pointer on the reference xlist_entry_t
 **************************************************************************/
static inline xptr_t xlist_pred( xptr_t root,
                                 xptr_t ref )
{
    // get root->next
    xptr_t root_next = (xptr_t)hal_remote_l64( root );

    // get ref->pred
    xptr_t ref_pred  = (xptr_t)hal_remote_l64( ref + sizeof(xptr_t) );

    // test if list is empty or ref is the first element  
    if( (root_next == root) || (ref_pred == root) )  return XPTR_NULL;
    
        return ref_pred;
}

/***************************************************************************
 * This function initialises the root of an extended double linked list.
 * The root can be located in any cluster.
 * @ root_xp   :  extended pointer on the root xlist_entry_t
xixi **************************************************************************/
static inline void xlist_root_init( xptr_t root_xp )
{
    hal_remote_s64( root_xp                  , root_xp );
    hal_remote_s64( root_xp + sizeof(xptr_t) , root_xp );
}

/***************************************************************************
 * This function initialises an entry of an extended double linked list.
 * The entry can be located in any cluster.
 * @ entry_xp  : extended pointer on the xlist_entry_t
 **************************************************************************/
static inline void xlist_entry_init( xptr_t entry_xp )
{
    hal_remote_s64( entry_xp                  , 0 );
    hal_remote_s64( entry_xp + sizeof(xptr_t) , 0 );
}

/***************************************************************************
 * This function inserts a new entry in the first place of an extended  
 * double linked list. Four extended pointers must be modified.
 * The lock protecting the list should have been previously taken.
 * @ root_xp   : extended pointer on the root xlist_entry_t
 * @ entry_xp  : extended pointer on the xlist_entry_t to be inserted
 **************************************************************************/
static inline void xlist_add_first( xptr_t root_xp, 
                                    xptr_t entry_xp )
{
    // get the extended pointer on the first element in list
    xptr_t first_xp = hal_remote_l64( root_xp );

    // update root_xp->next <= entry_xp
    hal_remote_s64( root_xp , entry_xp );

    // update entry_xp->next <= first_xp
    hal_remote_s64( entry_xp , first_xp );

    // update entry_xp->pred <= root_xp 
    hal_remote_s64( entry_xp + sizeof(xptr_t) , root_xp );
    
    // update first_xp->pred <= entry_xp
    hal_remote_s64( first_xp + sizeof(xptr_t) , entry_xp );
}

/***************************************************************************
 * This function inserts a new entry in the last place of an extended  
 * double linked list.  Four extended pointers must be modified.
 * The lock protecting the list should have been previously taken.
 * @ root_xp   : extended pointer on the root xlist_entry_t
 * @ entry_xp  : extended pointer on the xlist_entry_t to be inserted
 **************************************************************************/
static inline void xlist_add_last( xptr_t root_xp, 
                                   xptr_t entry_xp )
{
    // get the extended pointer on the last element in list
    xptr_t last_xp = hal_remote_l64( root_xp + sizeof(xptr_t) );

    // update root_xp->pred <= entry_xp
    hal_remote_s64( root_xp + sizeof(xptr_t) , entry_xp );

    // update entry_xp->pred <= last_xp
    hal_remote_s64( entry_xp + sizeof(xptr_t) , last_xp );

    // update entry_xp->next <= root_xp
    hal_remote_s64( entry_xp , root_xp );
    
    // update last_xp->next <= entry_xp
    hal_remote_s64( last_xp , entry_xp );
}


/***************************************************************************
 * This function returns true if the list is empty.
 * @ root_xp  : extended pointer on the root xlist_entry_t.
 **************************************************************************/
static inline bool_t xlist_is_empty( xptr_t root_xp )
{
    // get the extended pointer root.next value
    xptr_t next = (xptr_t)hal_remote_l64( root_xp );

    return ( root_xp == next );
} 

/***************************************************************************
 * This function removes an entry from an extended  double linked list.
 * Two extended pointers must be modified.
 * The memory allocated to the removed entry is not released.
 * @ xp : extended pointer on the xlist_entry_t to be removed.
 **************************************************************************/
static inline void xlist_unlink( xptr_t xp )
{
    // get a local copy of the xlist_entry_t to be removed
    xlist_entry_t entry;
    hal_remote_memcpy( XPTR( local_cxy , &entry ) ,
                       xp , 
                       sizeof(xlist_entry_t) );

    xptr_t next = entry.next;
    xptr_t pred = entry.pred;

    // update pred.next <= next
    hal_remote_s64( pred , (uint64_t)next );

    // update next.pred <= pred
    hal_remote_s64( next + sizeof(xptr_t) , (uint64_t)pred );
}

/***************************************************************************
 * This function replaces an entry in an extended double linked list.
 * Four extended pointers must be modified.
 * The memory allocated to the removed entry is not released.
 * @ old      : extended pointer on the xlist_entry_t to be removed.
 * @ new      : extended pointer on the xlist_entry_t to be inserted.
 **************************************************************************/
static inline void xlist_replace( xptr_t old,
                                  xptr_t new )
{
    // get a local copy of the xlist_entry_t to be removed
    xlist_entry_t entry;
    hal_remote_memcpy( XPTR( local_cxy , &entry ) , 
                                  old , 
                                  sizeof(xlist_entry_t) );

    xptr_t next = entry.next;
    xptr_t pred = entry.pred;

        // update new.next <= next
    hal_remote_s64( new , (uint64_t)next );

    // update new.pred <= pred
    hal_remote_s64( new + sizeof(xptr_t) , (uint64_t)pred );

        // update pred.next <= new
    hal_remote_s64( pred , (uint64_t)new );

    // update next.pred <= new
    hal_remote_s64( next + sizeof(xptr_t) , (uint64_t)new );
}

/***************************************************************************
 * This debug function displays all entries of an xlist.
 * @ root_xp : extended pointer on the root xlist_entry_t.
 * @ string  : list identifier displayed in header.
 * @ max     : max number of éléments to display.
 **************************************************************************/
static inline void xlist_display( xptr_t  root_xp,
                                  char  * string,
                                  uint32_t max )
{
    cxy_t           root_cxy;
    xlist_entry_t * root_ptr;

    xptr_t          iter_xp;
    cxy_t           iter_cxy;
    xlist_entry_t * iter_ptr;

    xptr_t          next_xp;
    cxy_t           next_cxy;
    xlist_entry_t * next_ptr;

    xptr_t          pred_xp;
    cxy_t           pred_cxy;
    xlist_entry_t * pred_ptr;

    uint32_t        index;

    root_cxy = GET_CXY( root_xp );
    root_ptr = GET_PTR( root_xp );

    next_xp  = hal_remote_l64( XPTR( root_cxy , &root_ptr->next ) );
    next_cxy = GET_CXY( next_xp );
    next_ptr = GET_PTR( next_xp );

    pred_xp  = hal_remote_l64( XPTR( root_cxy , &root_ptr->pred ) );
    pred_cxy = GET_CXY( pred_xp );
    pred_ptr = GET_PTR( pred_xp );

    printk("\n***** root (%x,%x) / next (%x,%x) / pred (%x,%x) / %s *****\n",
    root_cxy, root_ptr, next_cxy, next_ptr, pred_cxy, pred_ptr, string );

    if( xlist_is_empty( root_xp ) == false )
    {
        for( iter_xp = hal_remote_l64( XPTR( root_cxy , &root_ptr->next) ) , index = 0 ;
             (iter_xp != root_xp) && (index < max) ;
             iter_xp = next_xp , index++ )
        {
            iter_cxy = GET_CXY( iter_xp );
            iter_ptr = GET_PTR( iter_xp );

            next_xp  = hal_remote_l64( XPTR( iter_cxy , &iter_ptr->next ) );
            next_cxy = GET_CXY( next_xp );
            next_ptr = GET_PTR( next_xp );

            pred_xp  = hal_remote_l64( XPTR( iter_cxy , &iter_ptr->pred ) );
            pred_cxy = GET_CXY( pred_xp );
            pred_ptr = GET_PTR( pred_xp );

            printk(" - %d : iter (%x,%x) / next (%x,%x) / pred (%x,%x)\n",
            index, iter_cxy, iter_ptr, next_cxy, next_ptr, pred_cxy, pred_ptr );
        }
    }
}  // end xlist_display()

#endif  /* _XLIST_H_ */