le_singlyLinkedList.h

    1 /**
    2  * @page c_singlyLinkedList Singly Linked List API
    3  *
    4  * @subpage le_singlyLinkedList.h "API Reference"
    5  *
    6  * <HR>
    7  *
    8  * A singly linked list is a data structure consisting of a group of nodes linked together linearly.
    9  * Each node consists of data elements and a link to the next node.  The main advantage of linked
   10  * lists over simple arrays is that the nodes can be inserted anywhere in the list without
   11  * reallocating the entire array because the nodes in a linked list do not need to be stored
   12  * contiguously in memory.  However, nodes in the list cannot be accessed by index but must be
   13  * accessed by traversing the list.
   14  *
   15  *
   16  * @section sls_createList Creating and Initializing Lists
   17  *
   18  * To create and initialize a linked list, @c create a le_sls_List_t typed list and assign
   19  * LE_SLS_LIST_INIT to it.  The assignment of LE_SLS_LIST_INIT can be done either when the list is
   20  * declared or after it's declared.  The list <b>must</b> be initialized before it can be
   21  * used.
   22  *
   23  * @code
   24  * // Create and initialized the list in the declaration.
   25  * le_sls_List_t MyList = LE_SLS_LIST_INIT;
   26  * @endcode
   27  *
   28  * Or
   29  *
   30  * @code
   31  * // Create list.
   32  * le_sls_List_t MyList;
   33  *
   34  * // Initialize the list.
   35  * MyList = LE_SLS_LIST_INIT;
   36  * @endcode
   37  *
   38  * <b> The elements of le_sls_List_t MUST NOT be accessed directly by the user. </b>
   39  *
   40  *
   41  * @section sls_createNode Creating and Accessing Nodes
   42  *
   43  * Nodes can contain any data in any format and is defined and created by the user.  The only
   44  * requirement for nodes is that it must contain a le_sls_Link_t link member.  The link member must
   45  * be initialized by assigning LE_SLS_LINK_INIT to it before it can be used.  Nodes can then be
   46  * added to the list by passing their links to the add functions (le_sls_Stack(), le_sls_Queue(),
   47  * etc.).  For example:
   48  *
   49  * @code
   50  * // The node may be defined like this.
   51  * typedef struct
   52  * {
   53  *      dataType someUserData;
   54  *      ...
   55  *      le_sls_Link_t myLink;
   56  *
   57  * }
   58  * MyNodeClass_t;
   59  *
   60  * // Create and initialize the list.
   61  * le_sls_List_t MyList = LE_SLS_LIST_INIT;
   62  *
   63  * void foo (void)
   64  * {
   65  *     // Create the node.  Get the memory from a memory pool previously created.
   66  *     MyNodeClass_t* myNodePtr = le_mem_ForceAlloc(MyNodePool);
   67  *
   68  *     // Initialize the node's link.
   69  *     myNodePtr->myLink = LE_SLS_LINK_INIT;
   70  *
   71  *     // Add the node to the head of the list by passing in the node's link.
   72  *     le_sls_Stack(&MyList, &(myNodePtr->myLink));
   73  * }
   74  * @endcode
   75  *
   76  * The links in the nodes are added to the list and not the nodes themselves.  This
   77  * allows a node to be simultaneously part of multiple lists simply by having multiple links and
   78  * adding the links into differently lists.  This also means that nodes in a list can be of
   79  * different types.
   80  *
   81  * Because the links and not the nodes are in the list, the user must have a way to obtain
   82  * the node itself from the link.  This is achieved using the @c CONTAINER_OF macro defined in
   83  * le_basics.h.  This code sample shows using CONTAINER_OF to obtain the node:
   84  *
   85  * @code
   86  * // Assuming mylist has been created and initialized and is not empty.
   87  * le_sls_Link_t* linkPtr = le_sls_Peek(&MyList);
   88  *
   89  * // Now we have the link but we want the node so we can access the user data.
   90  * // We use CONTAINER_OF to get a pointer to the node given the node's link.
   91  * if (linkPtr != NULL)
   92  * {
   93  *     MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
   94  * }
   95  * @endcode
   96  *
   97  * The user is responsible for creating and freeing memory for all nodes, the linked list module
   98  * simply manages the links in the nodes.  The node must first be removed from all lists before its
   99  * memory is freed.
  100  *
  101  * <b>The elements of le_sls_Link_t MUST NOT be accessed directly by the user.</b>
  102  *
  103  *
  104  * @section sls_add Adding Links to a List
  105  *
  106  * To add nodes to a list pass the node's link to one of the following functions:
  107  *
  108  * - le_sls_Stack() - Adds the link to the head of the list.
  109  * - le_sls_Queue() - Adds the link to the tail of the list.
  110  * - le_sls_AddAfter() - Adds the link to a list after another specified link.
  111  *
  112  *
  113  * @section sls_remove Removing Links from a List
  114  *
  115  * To remove nodes from a list, use @c le_sls_Pop() to remove and return the link at the head of
  116  * the list.
  117  *
  118  *
  119  * @section sls_peek Accessing Links in a List
  120  *
  121  * To access a link in a list without removing the link, use one of the following functions:
  122  *
  123  * - @c le_sls_Peek() - Returns the link at the head of the list without removing it.
  124  * - @c le_sls_PeekNext() - Returns the link next to a specified link without removing it.
  125  * - @c le_sls_PeekTail() - Returns the link at the tail of the list without removing it.
  126  *
  127  *
  128  * @section sls_query Querying List Status
  129  *
  130  * The following functions can be used to query a list's current status:
  131  *
  132  * - @c le_sls_IsEmpty() - Checks if a given list is empty or not.
  133  * - @c le_sls_IsInList() - Checks if a specified link is in the list.
  134  * - @c le_sls_IsHead() - Checks if a specified link is at the head of the list.
  135  * - @c le_sls_IsTail() - Checks if a specified link is at the tail of the list.
  136  * - @c le_sls_NumLinks() - Checks the number of links currently in the list.
  137  * - @c le_sls_IsListCorrupted() - Checks if the list is corrupted.
  138  *
  139  *
  140  * @section sls_fifo Queues and Stacks
  141  *
  142  * This implementation of linked lists can easily be used as either queues or stacks.
  143  *
  144  * To use the list as a queue, restrict additions to the list to @c le_sls_Queue() and removals
  145  * from the list to @c le_sls_Pop().
  146  *
  147  * To use the list as a stack, restrict additions to the list to @c le_sls_Stack() and removals
  148  * from the list to @c le_sls_Pop().
  149  *
  150  *
  151  * @section sls_synch Thread Safety and Re-Entrancy
  152  *
  153  * All linked list function calls are re-entrant and thread safe themselves, but if the nodes and/or
  154  * list object are shared by multiple threads, then explicit steps must be taken to maintain mutual
  155  * exclusion of access. If you're accessing the same list from multiple threads, you @e must use a
  156  * @ref c_mutex "mutex" or some other form of thread synchronization to ensure only one thread
  157  * accesses the list at a time.
  158  *
  159  * <HR>
  160  *
  161  * Copyright (C) Sierra Wireless Inc.
  162  */
  163 
  164 
  165 /** @file le_singlyLinkedList.h
  166  *
  167  * Legato @ref c_singlyLinkedList include file.
  168  *
  169  * Copyright (C) Sierra Wireless Inc.
  170  */
  171 
  172 #ifndef LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
  173 #define LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
  174 
  175 
  176 //--------------------------------------------------------------------------------------------------
  177 /**
  178  * This link object must be included in each user node.  The node's link object is used to add the
  179  * node to a list.  A node may have multiple link objects which would allow the node to be part of
  180  * multiple lists simultaneously.  This link object must be initialized by assigning
  181  * LE_SLS_LINK_INIT to it.
  182  *
  183  * @warning The user MUST NOT access the contents of this structure directly.
  184  */
  185 //--------------------------------------------------------------------------------------------------
  186 typedef struct le_sls_Link
  187 {
  188     struct le_sls_Link* nextPtr;       ///< Next link pointer.
  189 }
  190 le_sls_Link_t;
  191 
  192 
  193 //--------------------------------------------------------------------------------------------------
  194 /**
  195  * This is the list object.  Create this list object and initialize it by assigning
  196  * LE_SLS_LIST_INIT to it.
  197  *
  198  * @warning DON'T access the contents of this structure directly.
  199  */
  200 //--------------------------------------------------------------------------------------------------
  201 typedef struct
  202 {
  203     le_sls_Link_t* tailLinkPtr;        ///< Tail link pointer.
  204 }
  205 le_sls_List_t;
  206 
  207 
  208 //--------------------------------------------------------------------------------------------------
  209 /**
  210  * This is a comparator function for sorting a list.
  211  *
  212  * This must return true if @c a goes before @c b in the list.
  213  */
  214 //--------------------------------------------------------------------------------------------------
  215 typedef bool (*le_sls_LessThanFunc_t)(le_sls_Link_t* a, le_sls_Link_t* b);
  216 
  217 
  218 //--------------------------------------------------------------------------------------------------
  219 /**
  220  * When a list is created it must be initialized to this macro in the declaration,
  221  * or have @c LE_SLS_LIST_INIT assigned to it, before being used
  222  */
  223 //--------------------------------------------------------------------------------------------------
  224 #define LE_SLS_LIST_DECL_INIT {NULL}
  225 
  226 //--------------------------------------------------------------------------------------------------
  227 /**
  228  * When a list is created it must be initialized by assigning this macro to the list, or
  229  * initializing to @c LE_SLS_LIST_DECL_INIT in the declaration, before the list can be used.
  230  */
  231 //--------------------------------------------------------------------------------------------------
  232 #define LE_SLS_LIST_INIT (le_sls_List_t)LE_SLS_LIST_DECL_INIT
  233 
  234 
  235 //--------------------------------------------------------------------------------------------------
  236 /**
  237  * When a link is created it must be initialized by assigning this macro to the link before it can
  238  * be used.
  239  */
  240 //--------------------------------------------------------------------------------------------------
  241 #define LE_SLS_LINK_INIT (le_sls_Link_t){NULL}
  242 
  243 
  244 //--------------------------------------------------------------------------------------------------
  245 /**
  246  * Adds a link at the head of the list.
  247  */
  248 //--------------------------------------------------------------------------------------------------
  249 void le_sls_Stack
  250 (
  251     le_sls_List_t* listPtr,            ///< [IN] List to add to.
  252     le_sls_Link_t* newLinkPtr          ///< [IN] New link to add.
  253 );
  254 
  255 
  256 //--------------------------------------------------------------------------------------------------
  257 /**
  258  * Adds a link to the tail of the list.
  259  */
  260 //--------------------------------------------------------------------------------------------------
  261 void le_sls_Queue
  262 (
  263     le_sls_List_t* listPtr,            ///< [IN] List to add to.
  264     le_sls_Link_t* newLinkPtr          ///< [IN] New link to add.
  265 );
  266 
  267 
  268 //--------------------------------------------------------------------------------------------------
  269 /**
  270  * Adds a link after currentLinkPtr, or to the beginning of the list if currentLinkPtr is NULL.
  271  * Ensure that currentLinkPtr is in the list (or NULL) otherwise the behaviour of this function is
  272  * undefined.
  273  */
  274 //--------------------------------------------------------------------------------------------------
  275 void le_sls_AddAfter
  276 (
  277     le_sls_List_t* listPtr,            ///< [IN] List to add to.
  278     le_sls_Link_t* currentLinkPtr,     ///< [IN] New link will be inserted after this link.
  279     le_sls_Link_t* newLinkPtr          ///< [IN] New link to add.
  280 );
  281 
  282 
  283 //--------------------------------------------------------------------------------------------------
  284 /**
  285  * Removes the link found after currentLinkPtr.  The user must ensure that currentLinkPtr is in the
  286  * list otherwise the behaviour of this function is undefined.
  287  *
  288  * @return
  289  *      Pointer to the removed link.
  290  *      NULL if there are no more links in the list after currentLinkPtr.
  291  */
  292 //--------------------------------------------------------------------------------------------------
  293 le_sls_Link_t* le_sls_RemoveAfter
  294 (
  295     le_sls_List_t* listPtr,            ///< [IN] The list to remove from.
  296     le_sls_Link_t* currentLinkPtr      ///< [IN] The link after this one will be removed from the
  297                                        ///<      list.
  298 );
  299 
  300 
  301 //--------------------------------------------------------------------------------------------------
  302 /**
  303  * Removes and returns the link at the head of the list.
  304  *
  305  * @return
  306  *      Removed link.
  307  *      NULL if the link is not available because the list is empty.
  308  */
  309 //--------------------------------------------------------------------------------------------------
  310 le_sls_Link_t* le_sls_Pop
  311 (
  312     le_sls_List_t* listPtr             ///< [IN] List to remove from.
  313 );
  314 
  315 
  316 //--------------------------------------------------------------------------------------------------
  317 /**
  318  * Returns the link at the head of the list without removing it from the list.
  319  *
  320  * @return
  321  *     Pointer to the head link if successful.
  322  *      NULL if the list is empty.
  323  */
  324 //--------------------------------------------------------------------------------------------------
  325 le_sls_Link_t* le_sls_Peek
  326 (
  327     const le_sls_List_t* listPtr            ///< [IN] The list.
  328 );
  329 
  330 
  331 //------------------------------------------------------------------------------------------------------------
  332 /**
  333  * Returns the link at the tail of the list without removing it from the list.
  334  *
  335  * @return
  336  *      A pointer to the tail link if successful.
  337  *      NULL if the list is empty.
  338  */
  339 //------------------------------------------------------------------------------------------------------------
  340 le_sls_Link_t* le_sls_PeekTail
  341 (
  342     const le_sls_List_t* listPtr            ///< [IN] The list.
  343 );
  344 
  345 
  346 //--------------------------------------------------------------------------------------------------
  347 /**
  348  * Returns the link next to currentLinkPtr (i.e., the link beside currentLinkPtr that's closer to the
  349  * tail) without removing it from the list. Ensure currentLinkPtr is in the list
  350  * otherwise the behaviour of this function is undefined.
  351  *
  352  * @return
  353  *      Pointer to the next link if successful.
  354  *      NULL if there is no link next to the currentLinkPtr (currentLinkPtr is at the tail of the
  355  *      list).
  356  */
  357 //--------------------------------------------------------------------------------------------------
  358 le_sls_Link_t* le_sls_PeekNext
  359 (
  360     const le_sls_List_t* listPtr,           ///< [IN] List containing currentLinkPtr.
  361     const le_sls_Link_t* currentLinkPtr     ///< [IN] Get the link that is relative to this link.
  362 );
  363 
  364 
  365 //--------------------------------------------------------------------------------------------------
  366 /**
  367  * Checks if a list is empty.
  368  *
  369  * @return
  370  *      true if empty, false if not empty.
  371  */
  372 //--------------------------------------------------------------------------------------------------
  373 LE_DECLARE_INLINE bool le_sls_IsEmpty
  374 (
  375     const le_sls_List_t* listPtr            ///< [IN] The list.
  376 )
  377 //--------------------------------------------------------------------------------------------------
  378 {
  379     return (le_sls_Peek(listPtr) == NULL);
  380 }
  381 
  382 
  383 //--------------------------------------------------------------------------------------------------
  384 /**
  385  * Sort a list in ascending order.
  386  */
  387 //--------------------------------------------------------------------------------------------------
  388 void le_sls_Sort
  389 (
  390     le_sls_List_t* listPtr,                 ///< [IN] List to sort
  391     le_sls_LessThanFunc_t comparatorPtr     ///< [IN] Comparator function for sorting
  392 );
  393 
  394 //--------------------------------------------------------------------------------------------------
  395 /**
  396  * Checks if a link is in the list.
  397  *
  398  * @return
  399  *    - true if the link is in the list.
  400  *    - false if the link is not in the list.
  401  */
  402 //--------------------------------------------------------------------------------------------------
  403 bool le_sls_IsInList
  404 (
  405     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  406     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is in the list.
  407 );
  408 
  409 
  410 //--------------------------------------------------------------------------------------------------
  411 /**
  412  * Checks if a link is at the head of the list (next to be popped).
  413  *
  414  * @return
  415  *    - true if the link is at the head of the list.
  416  *    - false if not.
  417  */
  418 //--------------------------------------------------------------------------------------------------
  419 LE_DECLARE_INLINE bool le_sls_IsHead
  420 (
  421     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  422     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is at the head of the list.
  423 )
  424 {
  425     return (le_sls_Peek(listPtr) == linkPtr);
  426 }
  427 
  428 
  429 //--------------------------------------------------------------------------------------------------
  430 /**
  431  * Checks if a link is at the tail of the list (last to be popped).
  432  *
  433  * @return
  434  *    - true if the link is at the tail of the list.
  435  *    - false if not.
  436  */
  437 //--------------------------------------------------------------------------------------------------
  438 LE_DECLARE_INLINE bool le_sls_IsTail
  439 (
  440     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  441     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is at the tail of the list.
  442 )
  443 {
  444     return (le_sls_PeekTail(listPtr) == linkPtr);
  445 }
  446 
  447 
  448 //--------------------------------------------------------------------------------------------------
  449 /**
  450  * Returns the number of links in a list.
  451  *
  452  * @return
  453  *      Number of links.
  454  */
  455 //--------------------------------------------------------------------------------------------------
  456 size_t le_sls_NumLinks
  457 (
  458     const le_sls_List_t* listPtr       ///< [IN] List to count.
  459 );
  460 
  461 
  462 //--------------------------------------------------------------------------------------------------
  463 /**
  464  * Checks if the list is corrupted.
  465  *
  466  * @return
  467  *      true if the list is corrupted.
  468  *      false if the list is not corrupted.
  469  */
  470 //--------------------------------------------------------------------------------------------------
  471 bool le_sls_IsListCorrupted
  472 (
  473     const le_sls_List_t* listPtr    ///< [IN] List to check.
  474 );
  475 
  476 //--------------------------------------------------------------------------------------------------
  477 /**
  478  * Simple iteration through a singly linked list
  479  */
  480 //--------------------------------------------------------------------------------------------------
  481 #define LE_SLS_FOREACH(listPtr, iteratorPtr, type, member)              \
  482     for ((iteratorPtr) = CONTAINER_OF(le_sls_Peek(listPtr), type, member); \
  483          &((iteratorPtr)->member);                                      \
  484          (iteratorPtr) = CONTAINER_OF(le_sls_PeekNext((listPtr),&((iteratorPtr)->member)), \
  485                                       type, member))
  486 
  487 
  488 
  489 #endif  // LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
le_sls_NumLinks
size_t le_sls_NumLinks(const le_sls_List_t *listPtr)
le_sls_LessThanFunc_t
bool(* le_sls_LessThanFunc_t)(le_sls_Link_t *a, le_sls_Link_t *b)
Definition: le_singlyLinkedList.h:215
le_sls_Link_t::nextPtr
struct le_sls_Link * nextPtr
Next link pointer. 
Definition: le_singlyLinkedList.h:188
le_sls_Link_t
Definition: le_singlyLinkedList.h:186
le_sls_IsTail
LE_DECLARE_INLINE bool le_sls_IsTail(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
Definition: le_singlyLinkedList.h:439
le_sls_PeekNext
le_sls_Link_t * le_sls_PeekNext(const le_sls_List_t *listPtr, const le_sls_Link_t *currentLinkPtr)
le_sls_PeekTail
le_sls_Link_t * le_sls_PeekTail(const le_sls_List_t *listPtr)
le_sls_IsHead
LE_DECLARE_INLINE bool le_sls_IsHead(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
Definition: le_singlyLinkedList.h:420
le_sls_Peek
le_sls_Link_t * le_sls_Peek(const le_sls_List_t *listPtr)
le_sls_Stack
void le_sls_Stack(le_sls_List_t *listPtr, le_sls_Link_t *newLinkPtr)
le_sls_Queue
void le_sls_Queue(le_sls_List_t *listPtr, le_sls_Link_t *newLinkPtr)
le_sls_Sort
void le_sls_Sort(le_sls_List_t *listPtr, le_sls_LessThanFunc_t comparatorPtr)
le_sls_IsListCorrupted
bool le_sls_IsListCorrupted(const le_sls_List_t *listPtr)
le_sls_IsInList
bool le_sls_IsInList(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
le_sls_IsEmpty
LE_DECLARE_INLINE bool le_sls_IsEmpty(const le_sls_List_t *listPtr)
Definition: le_singlyLinkedList.h:374
le_sls_List_t
Definition: le_singlyLinkedList.h:201
le_sls_Pop
le_sls_Link_t * le_sls_Pop(le_sls_List_t *listPtr)
le_sls_List_t::tailLinkPtr
le_sls_Link_t * tailLinkPtr
Tail link pointer. 
Definition: le_singlyLinkedList.h:203
le_sls_AddAfter
void le_sls_AddAfter(le_sls_List_t *listPtr, le_sls_Link_t *currentLinkPtr, le_sls_Link_t *newLinkPtr)
LE_DECLARE_INLINE
#define LE_DECLARE_INLINE
Definition: le_basics.h:320
le_sls_RemoveAfter
le_sls_Link_t * le_sls_RemoveAfter(le_sls_List_t *listPtr, le_sls_Link_t *currentLinkPtr)