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 by assigning this macro to the list before the list
  221  * can be used.
  222  */
  223 //--------------------------------------------------------------------------------------------------
  224 #define LE_SLS_LIST_INIT (le_sls_List_t){NULL}
  225 
  226 
  227 //--------------------------------------------------------------------------------------------------
  228 /**
  229  * When a link is created, it must be initialized by assigning this macro to the link before it can
  230  * be used.
  231  */
  232 //--------------------------------------------------------------------------------------------------
  233 #define LE_SLS_LINK_INIT (le_sls_Link_t){NULL}
  234 
  235 
  236 //--------------------------------------------------------------------------------------------------
  237 /**
  238  * Adds a link at the head of the list.
  239  */
  240 //--------------------------------------------------------------------------------------------------
  241 void le_sls_Stack
  242 (
  243     le_sls_List_t* listPtr,            ///< [IN] List to add to.
  244     le_sls_Link_t* newLinkPtr          ///< [IN] New link to add.
  245 );
  246 
  247 
  248 //--------------------------------------------------------------------------------------------------
  249 /**
  250  * Adds a link to the tail of the list.
  251  */
  252 //--------------------------------------------------------------------------------------------------
  253 void le_sls_Queue
  254 (
  255     le_sls_List_t* listPtr,            ///< [IN] List to add to.
  256     le_sls_Link_t* newLinkPtr          ///< [IN] New link to add.
  257 );
  258 
  259 
  260 //--------------------------------------------------------------------------------------------------
  261 /**
  262  * Adds a link after currentLinkPtr, or to the beginning of the list if currentLinkPtr is NULL.
  263  * Ensure that currentLinkPtr is in the list (or NULL) otherwise the behaviour of this function is
  264  * undefined.
  265  */
  266 //--------------------------------------------------------------------------------------------------
  267 void le_sls_AddAfter
  268 (
  269     le_sls_List_t* listPtr,            ///< [IN] List to add to.
  270     le_sls_Link_t* currentLinkPtr,     ///< [IN] New link will be inserted after this link.
  271     le_sls_Link_t* newLinkPtr          ///< [IN] New link to add.
  272 );
  273 
  274 
  275 //--------------------------------------------------------------------------------------------------
  276 /**
  277  * Removes the link found after currentLinkPtr.  The user must ensure that currentLinkPtr is in the
  278  * list otherwise the behaviour of this function is undefined.
  279  *
  280  * @return
  281  *      Pointer to the removed link.
  282  *      NULL if there are no more links in the list after currentLinkPtr.
  283  */
  284 //--------------------------------------------------------------------------------------------------
  285 le_sls_Link_t* le_sls_RemoveAfter
  286 (
  287     le_sls_List_t* listPtr,            ///< [IN] The list to remove from.
  288     le_sls_Link_t* currentLinkPtr      ///< [IN] The link after this one will be removed from the
  289                                        ///<      list.
  290 );
  291 
  292 
  293 //--------------------------------------------------------------------------------------------------
  294 /**
  295  * Removes and returns the link at the head of the list.
  296  *
  297  * @return
  298  *      Removed link.
  299  *      NULL if the link is not available because the list is empty.
  300  */
  301 //--------------------------------------------------------------------------------------------------
  302 le_sls_Link_t* le_sls_Pop
  303 (
  304     le_sls_List_t* listPtr             ///< [IN] List to remove from.
  305 );
  306 
  307 
  308 //--------------------------------------------------------------------------------------------------
  309 /**
  310  * Returns the link at the head of the list without removing it from the list.
  311  *
  312  * @return
  313  *     Pointer to the head link if successful.
  314  *      NULL if the list is empty.
  315  */
  316 //--------------------------------------------------------------------------------------------------
  317 le_sls_Link_t* le_sls_Peek
  318 (
  319     const le_sls_List_t* listPtr            ///< [IN] The list.
  320 );
  321 
  322 
  323 //------------------------------------------------------------------------------------------------------------
  324 /**
  325  * Returns the link at the tail of the list without removing it from the list.
  326  *
  327  * @return
  328  *      A pointer to the tail link if successful.
  329  *      NULL if the list is empty.
  330  */
  331 //------------------------------------------------------------------------------------------------------------
  332 le_sls_Link_t* le_sls_PeekTail
  333 (
  334     const le_sls_List_t* listPtr            ///< [IN] The list.
  335 );
  336 
  337 
  338 //--------------------------------------------------------------------------------------------------
  339 /**
  340  * Returns the link next to currentLinkPtr (i.e., the link beside currentLinkPtr that's closer to the
  341  * tail) without removing it from the list. Ensure currentLinkPtr is in the list
  342  * otherwise the behaviour of this function is undefined.
  343  *
  344  * @return
  345  *      Pointer to the next link if successful.
  346  *      NULL if there is no link next to the currentLinkPtr (currentLinkPtr is at the tail of the
  347  *      list).
  348  */
  349 //--------------------------------------------------------------------------------------------------
  350 le_sls_Link_t* le_sls_PeekNext
  351 (
  352     const le_sls_List_t* listPtr,           ///< [IN] List containing currentLinkPtr.
  353     const le_sls_Link_t* currentLinkPtr     ///< [IN] Get the link that is relative to this link.
  354 );
  355 
  356 
  357 //--------------------------------------------------------------------------------------------------
  358 /**
  359  * Checks if a list is empty.
  360  *
  361  * @return
  362  *      true if empty, false if not empty.
  363  */
  364 //--------------------------------------------------------------------------------------------------
  365 LE_DECLARE_INLINE bool le_sls_IsEmpty
  366 (
  367     const le_sls_List_t* listPtr            ///< [IN] The list.
  368 )
  369 //--------------------------------------------------------------------------------------------------
  370 {
  371     return (le_sls_Peek(listPtr) == NULL);
  372 }
  373 
  374 
  375 //--------------------------------------------------------------------------------------------------
  376 /**
  377  * Sort a list in ascending order.
  378  */
  379 //--------------------------------------------------------------------------------------------------
  380 void le_sls_Sort
  381 (
  382     le_sls_List_t* listPtr,                 ///< [IN] List to sort
  383     le_sls_LessThanFunc_t comparatorPtr     ///< [IN] Comparator function for sorting
  384 );
  385 
  386 //--------------------------------------------------------------------------------------------------
  387 /**
  388  * Checks if a link is in the list.
  389  *
  390  * @return
  391  *    - true if the link is in the list.
  392  *    - false if the link is not in the list.
  393  */
  394 //--------------------------------------------------------------------------------------------------
  395 bool le_sls_IsInList
  396 (
  397     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  398     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is in the list.
  399 );
  400 
  401 
  402 //--------------------------------------------------------------------------------------------------
  403 /**
  404  * Checks if a link is at the head of the list (next to be popped).
  405  *
  406  * @return
  407  *    - true if the link is at the head of the list.
  408  *    - false if not.
  409  */
  410 //--------------------------------------------------------------------------------------------------
  411 LE_DECLARE_INLINE bool le_sls_IsHead
  412 (
  413     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  414     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is at the head of the list.
  415 )
  416 {
  417     return (le_sls_Peek(listPtr) == linkPtr);
  418 }
  419 
  420 
  421 //--------------------------------------------------------------------------------------------------
  422 /**
  423  * Checks if a link is at the tail of the list (last to be popped).
  424  *
  425  * @return
  426  *    - true if the link is at the tail of the list.
  427  *    - false if not.
  428  */
  429 //--------------------------------------------------------------------------------------------------
  430 LE_DECLARE_INLINE bool le_sls_IsTail
  431 (
  432     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  433     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is at the tail of the list.
  434 )
  435 {
  436     return (le_sls_PeekTail(listPtr) == linkPtr);
  437 }
  438 
  439 
  440 //--------------------------------------------------------------------------------------------------
  441 /**
  442  * Returns the number of links in a list.
  443  *
  444  * @return
  445  *      Number of links.
  446  */
  447 //--------------------------------------------------------------------------------------------------
  448 size_t le_sls_NumLinks
  449 (
  450     const le_sls_List_t* listPtr       ///< [IN] List to count.
  451 );
  452 
  453 
  454 //--------------------------------------------------------------------------------------------------
  455 /**
  456  * Checks if the list is corrupted.
  457  *
  458  * @return
  459  *      true if the list is corrupted.
  460  *      false if the list is not corrupted.
  461  */
  462 //--------------------------------------------------------------------------------------------------
  463 bool le_sls_IsListCorrupted
  464 (
  465     const le_sls_List_t* listPtr    ///< [IN] List to check.
  466 );
  467 
  468 //--------------------------------------------------------------------------------------------------
  469 /**
  470  * Simple iteration through a singly linked list
  471  */
  472 //--------------------------------------------------------------------------------------------------
  473 #define LE_SLS_FOREACH(listPtr, iteratorPtr, type, member)              \
  474     for ((iteratorPtr) = CONTAINER_OF(le_sls_Peek(listPtr), type, member); \
  475          &((iteratorPtr)->member);                                      \
  476          (iteratorPtr) = CONTAINER_OF(le_sls_PeekNext((listPtr),&((iteratorPtr)->member)), \
  477                                       type, member))
  478 
  479 
  480 
  481 #endif  // LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
  482 
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:431
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:412
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:366
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:306
le_sls_RemoveAfter
le_sls_Link_t * le_sls_RemoveAfter(le_sls_List_t *listPtr, le_sls_Link_t *currentLinkPtr)