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

/*
 * xlist.h - Double Circular Linked lists, using extended pointers.
 *
 * Author : Alain Greiner (2016)
 *
 * 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 _ALMOS_XLIST_H_
#define _ALMOS_XLIST_H_

#include <kernel_config.h>
#include <hal_kernel_types.h>
#include <hal_remote.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_ELEMENT( root_xp , type , member ) \
    ({ xptr_t __first = hal_remote_lwd( 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_ELEMENT( root_xp , type , member )  \
    ({ xptr_t __last = hal_remote_lwd( root_xp + 8 );  \
           XLIST_ELEMENT( __last , type , member ); })

/***************************************************************************
 * This macro traverses an extended double linked list in forward order.
 * 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_lwd( root_xp ) ;  \
     (iter_xp) != (root_xp) ;                 \
     (iter_xp) = hal_remote_lwd( iter_xp ) )

/***************************************************************************
 * This macro traverses an extended double linked list in backward order.
 * 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_lwd( (root_xp) + 8 ) ;   \
     (iter_xp) != (root_xp) ;                        \
     (iter_xp) = hal_remote_lwd( (iter_xp) + 8 ) )

/***************************************************************************
 * 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_lwd( root );

    // get ref->next
    xptr_t ref_next  = (xptr_t)hal_remote_lwd( 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_lwd( root );

    // get ref->pred
    xptr_t ref_pred  = (xptr_t)hal_remote_lwd( ref + 8 );

    // 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
 **************************************************************************/
static inline void xlist_root_init( xptr_t root_xp )
{
    hal_remote_swd(  root_xp   , root_xp );
    hal_remote_swd(  root_xp+8 , 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_swd(  entry_xp   , 0 );
    hal_remote_swd(  entry_xp+8 , 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   : extended pointer on the root xlist_entry_t
 * @ entry  : extended pointer on the xlist_entry_t to be inserted
 **************************************************************************/
static inline void xlist_add_first( xptr_t root, 
                                    xptr_t entry )
{
    // get the extended pointer on the first element in list
    xptr_t first = (xptr_t)hal_remote_lwd( root );

    // update root.next <= entry
    hal_remote_swd( root , (uint64_t)entry );

    // update entry.next <= first
    hal_remote_swd( entry , (uint64_t)first );

    // entry.pred <= root 
    hal_remote_swd( entry + 8 , (uint64_t)root );
    
    // first.pred <= new
    hal_remote_swd( first + 8 , (uint64_t)entry );
}

/***************************************************************************
 * 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   : extended pointer on the root xlist_entry_t
 * @ entry  : extended pointer on the xlist_entry_t to be inserted
 **************************************************************************/
static inline void xlist_add_last( xptr_t root, 
                                   xptr_t entry )
{
    // get the extended pointer on the last element in list
    xptr_t last = (xptr_t)hal_remote_lwd( root + 8 );

    // update root.pred <= entry
    hal_remote_swd( root + 8 , (uint64_t)entry );

    // update entry.pred <= last
    hal_remote_swd( entry + 8 , (uint64_t)last );

    // entry.next <= root 
    hal_remote_swd( entry , (uint64_t)root );
    
    // last.next <= entry
    hal_remote_swd( last , (uint64_t)entry );
}


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

    return ( root == 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_swd( pred , (uint64_t)next );

    // update next.pred <= pred
    hal_remote_swd( next + 8 , (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_swd( new , (uint64_t)next );

    // update new.pred <= pred
    hal_remote_swd( new + 8 , (uint64_t)pred );

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

    // update next.pred <= new
    hal_remote_swd( next + 8 , (uint64_t)new );
}

#endif  /* _ALMOS_LIST_H_ */