core/include/list.h File Reference

Unidirectional list. More...

Data Structures

struct  os_list1_s
 structure for linking items in list More...

Defines

#define os_list1_is_empty(list1)   ( (list1)->next == NULL )
 condition for testing if the list is empty
#define os_list1_is_last(list1)   ( (list1)->next == NULL )
 condition for a test if the item is last
#define os_list1_del(prev)   os_list1_del_mark( prev, CFG_LISTDEL_POISON )
 removes item from the list
#define os_list1_content(list_item)   (void*)(list_item)
 conversion from list pointer to pointer of user structure
#define os_list1_item(user_item)   (os_list1_t *)( user_item )
 conversion from user structure pointer to list pointer

Typedefs

typedef struct os_list1_s os_list1_t
 data type for field that allows linking on the list

Functions

static void os_list1_insert (os_list1_t *prev, os_list1_t *item)
 inserts new item into the list
static void os_list1_del_mark (os_list1_t *prev, unsigned short poison_code)
 removes item from the list and marks deletion point.

Detailed Description

Unidirectional list.

Author:
Piotr Romaniuk, (c) ELESOFTROM
Version:
1.1 Nov 8, 2013

This is implementation of unidirectional linked list. The user items that should be able to be added to the list need to have specific structure - it must have list chaining part at the beginning. It can be defined as a structural user type of the item, for example:

 struct my_item_s{
                  os_list1_t        list_chain_field;
                  //... user content of the item 
                  //        (i.e. other fields of the item) ...
 };
Warning:
list_chain_field must be the first field in the structure.

The list source code is not aware of the user contents and its structure. The structure is defined for user convenience. Only the chaining parts are used for list manipulation. Because of that, it is possible to chain items of different size and types.

The chaining part contains a reference (pointer) to next item. If the item is the last the .next field is equal to NULL.

Note:
The item can be only on one list at the time, because it can contain only one chaining part.

Each list is build starting from its head, special structure that consists of only chaining part and have no user contents. List is created and initialized by:

 os_list1_s my_list = {NULL};

The list can be browsed and processed item by item, starting from the head and iterating through .next field until the last one is found. Consider following template:

 os_list1_t *Litem = &list_head;
 while( !os_list1_is_last( Litem ))
 {
    struct my_item_s * m_item = os_list1_content( Litem->next );
    // process m_item 
    // if you need to remove the item from the list
        os_list1_del( prev );
        continue;//must be continue because the item was removed, otherwise one item will be missed
                  
    //if you do not remove the item go to next by following reference:
    prev = prev->next;              
 } 

When you remove the item during list iteration, special care should be taken:
1. You must specify previous list item for deletion.
2. After the item has been deleted you should not continue traversing by .next reference but again check current item (see in above code example).

Warning:
Because of many possible scenarios of usage, provided list implementation is minimal and does not include protection from concurrent access. The user should add the guarding (e.g. critical section, mutex) that will be proper for the application and satisfy his needs.

Define Documentation

#define os_list1_content (   list_item)    (void*)(list_item)

conversion from list pointer to pointer of user structure

It should be used when conversion is required from list item to the user structure (i.e. contents).

Parameters:
[in]list_itemlist item pointer
Returns:
pointer to user structure chained on the list
Note:
It returns (void*), so conversion to user struct pointer is needed hwen the pointer is obtained.
#define os_list1_del (   prev)    os_list1_del_mark( prev, CFG_LISTDEL_POISON )

removes item from the list

if CFG_LISTDEL_WITH_POISON is defined in config.h it also marks .next field with CFG_LISTDEL_POISON. It is helpful in debugging to detect processing the item that has been deleted from list.

Parameters:
[in]prevpointer to previous item in the list
#define os_list1_is_empty (   list1)    ( (list1)->next == NULL )

condition for testing if the list is empty

Parameters:
[in]list1pointer to list head
Returns:
value of logical test "is the list empty?"
#define os_list1_is_last (   list1)    ( (list1)->next == NULL )

condition for a test if the item is last

Parameters:
[in]list1pointer to tested list item
Returns:
value of test "is this element last?"
#define os_list1_item (   user_item)    (os_list1_t *)( user_item )

conversion from user structure pointer to list pointer

Use it when you need pointer of the list item and have pointer to the user structure (i.e. contents).

Parameters:
[in]user_itempointer to user structure
Returns:
pointer to list item contained in user structure

Function Documentation

static void os_list1_del_mark ( os_list1_t prev,
unsigned short  poison_code 
) [inline, static]

removes item from the list and marks deletion point.

Usefull for debugging list issues. In the location where item is deleted it can be marked inside .next field with selected code, specific for that location.
Further, it is easy to determine where the item has been deleted.

Note:
use invalid RAM address as marking code
Parameters:
[in]prevpointer to previous item in the list
[in]poison_codevalue that marks .next field of deleted list item
{
         os_list1_t * nx = prev->next;
         if( nx!=NULL )
         {        
                  prev->next = nx->next;
                  nx->next = (struct os_list1_s*)(os_ptr_int_t)poison_code;
         }
}        
static void os_list1_insert ( os_list1_t prev,
os_list1_t item 
) [inline, static]

inserts new item into the list

Function inserts new item into specified location on the list. If it need to be inserted at the beginning use pointer to list head as first argument.

Parameters:
[in]prevpointer to previous item in the list (may be list head)
[in]itempointer to inserted item
{
         os_list1_t * nx = prev->next; 
         prev->next = item;
         item->next = nx;  
}