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

/*
 * list.h - Double circular chained lists, inspired from linux
 *
 * Authors Ghassan Almaless  (2008,2009,2010,2011,2012)
 *         Alain Greiner     (2016,2017,2018)
 *
 * 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 <printk.h>

#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 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 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;
}

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


#endif  /* _LIST_H_ */