le_singlyLinkedList.h

    1 /**
    2  * @page c_singlyLinkedList Singly Linked List API
    3  *
    4  * @ref 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. Use of this work is subject to license.
  162  */
  163 
  164 
  165  /** @file le_singlyLinkedList.h
  166   *
  167   * Legato @ref c_singlyLinkedList include file.
  168   *
  169   * Copyright (C) Sierra Wireless Inc. Use of this work is subject to license.
  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  * When a list is created, it must be initialized by assigning this macro to the list before the list
  211  * can be used.
  212  */
  213 //--------------------------------------------------------------------------------------------------
  214 #define LE_SLS_LIST_INIT (le_sls_List_t){NULL}
  215 
  216 
  217 //--------------------------------------------------------------------------------------------------
  218 /**
  219  * When a link is created, it must be initialized by assigning this macro to the link before it can
  220  * be used.
  221  */
  222 //--------------------------------------------------------------------------------------------------
  223 #define LE_SLS_LINK_INIT (le_sls_Link_t){NULL}
  224 
  225 
  226 //--------------------------------------------------------------------------------------------------
  227 /**
  228  * Adds a link at the head of the list.
  229  */
  230 //--------------------------------------------------------------------------------------------------
  231 void le_sls_Stack
  232 (
  233     le_sls_List_t* listPtr,            ///< [IN] List to add to.
  234     le_sls_Link_t* newLinkPtr          ///< [IN] New link to add.
  235 );
  236 
  237 
  238 //--------------------------------------------------------------------------------------------------
  239 /**
  240  * Adds a link to the tail of the list.
  241  */
  242 //--------------------------------------------------------------------------------------------------
  243 void le_sls_Queue
  244 (
  245     le_sls_List_t* listPtr,            ///< [IN] List to add to.
  246     le_sls_Link_t* newLinkPtr          ///< [IN] New link to add.
  247 );
  248 
  249 
  250 //--------------------------------------------------------------------------------------------------
  251 /**
  252  * Adds a link after currentLinkPtr.  Ensure that currentLinkPtr is in the list
  253  * otherwise the behaviour of this function is undefined.
  254  */
  255 //--------------------------------------------------------------------------------------------------
  256 void le_sls_AddAfter
  257 (
  258     le_sls_List_t* listPtr,            ///< [IN] List to add to.
  259     le_sls_Link_t* currentLinkPtr,     ///< [IN] New link will be inserted after this link.
  260     le_sls_Link_t* newLinkPtr          ///< [IN] New link to add.
  261 );
  262 
  263 
  264 //--------------------------------------------------------------------------------------------------
  265 /**
  266  * Removes the link found after currentLinkPtr.  The user must ensure that currentLinkPtr is in the
  267  * list otherwise the behaviour of this function is undefined.
  268  *
  269  * @return
  270  *      Pointer to the removed link.
  271  *      NULL if there are no more links in the list after currentLinkPtr.
  272  */
  273 //--------------------------------------------------------------------------------------------------
  274 le_sls_Link_t* le_sls_RemoveAfter
  275 (
  276     le_sls_List_t* listPtr,            ///< [IN] The list to remove from.
  277     le_sls_Link_t* currentLinkPtr      ///< [IN] The link after this one will be removed from the
  278                                        ///<      list.
  279 );
  280 
  281 
  282 //--------------------------------------------------------------------------------------------------
  283 /**
  284  * Removes and returns the link at the head of the list.
  285  *
  286  * @return
  287  *      Removed link.
  288  *      NULL if the link is not available because the list is empty.
  289  */
  290 //--------------------------------------------------------------------------------------------------
  291 le_sls_Link_t* le_sls_Pop
  292 (
  293     le_sls_List_t* listPtr             ///< [IN] List to remove from.
  294 );
  295 
  296 
  297 //--------------------------------------------------------------------------------------------------
  298 /**
  299  * Returns the link at the head of the list without removing it from the list.
  300  *
  301  * @return
  302  *     Pointer to the head link if successful.
  303  *      NULL if the list is empty.
  304  */
  305 //--------------------------------------------------------------------------------------------------
  306 le_sls_Link_t* le_sls_Peek
  307 (
  308     const le_sls_List_t* listPtr            ///< [IN] The list.
  309 );
  310 
  311 
  312 //------------------------------------------------------------------------------------------------------------
  313 /**
  314  * Returns the link at the tail of the list without removing it from the list.
  315  *
  316  * @return
  317  *      A pointer to the tail link if successful.
  318  *      NULL if the list is empty.
  319  */
  320 //------------------------------------------------------------------------------------------------------------
  321 le_sls_Link_t* le_sls_PeekTail
  322 (
  323     const le_sls_List_t* listPtr            ///< [IN] The list.
  324 );
  325 
  326 
  327 //--------------------------------------------------------------------------------------------------
  328 /**
  329  * Returns the link next to currentLinkPtr (i.e., the link beside currentLinkPtr that's closer to the
  330  * tail) without removing it from the list. Ensure currentLinkPtr is in the list
  331  * otherwise the behaviour of this function is undefined.
  332  *
  333  * @return
  334  *      Pointer to the next link if successful.
  335  *      NULL if there is no link next to the currentLinkPtr (currentLinkPtr is at the tail of the
  336  *      list).
  337  */
  338 //--------------------------------------------------------------------------------------------------
  339 le_sls_Link_t* le_sls_PeekNext
  340 (
  341     const le_sls_List_t* listPtr,           ///< [IN] List containing currentLinkPtr.
  342     const le_sls_Link_t* currentLinkPtr     ///< [IN] Get the link that is relative to this link.
  343 );
  344 
  345 
  346 //--------------------------------------------------------------------------------------------------
  347 /**
  348  * Checks if a list is empty.
  349  *
  350  * @return
  351  *      true if empty, false if not empty.
  352  */
  353 //--------------------------------------------------------------------------------------------------
  354 static inline bool le_sls_IsEmpty
  355 (
  356     const le_sls_List_t* listPtr            ///< [IN] The list.
  357 )
  358 //--------------------------------------------------------------------------------------------------
  359 {
  360     return (le_sls_Peek(listPtr) == NULL);
  361 }
  362 
  363 
  364 //--------------------------------------------------------------------------------------------------
  365 /**
  366  * Checks if a link is in the list.
  367  *
  368  * @return
  369  *    - true if the link is in the list.
  370  *    - false if the link is not in the list.
  371  */
  372 //--------------------------------------------------------------------------------------------------
  373 bool le_sls_IsInList
  374 (
  375     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  376     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is in the list.
  377 );
  378 
  379 
  380 //--------------------------------------------------------------------------------------------------
  381 /**
  382  * Checks if a link is at the head of the list (next to be popped).
  383  *
  384  * @return
  385  *    - true if the link is at the head of the list.
  386  *    - false if not.
  387  */
  388 //--------------------------------------------------------------------------------------------------
  389 static inline bool le_sls_IsHead
  390 (
  391     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  392     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is at the head of the list.
  393 )
  394 {
  395     return (le_sls_Peek(listPtr) == linkPtr);
  396 }
  397 
  398 
  399 //--------------------------------------------------------------------------------------------------
  400 /**
  401  * Checks if a link is at the tail of the list (last to be popped).
  402  *
  403  * @return
  404  *    - true if the link is at the tail of the list.
  405  *    - false if not.
  406  */
  407 //--------------------------------------------------------------------------------------------------
  408 static inline bool le_sls_IsTail
  409 (
  410     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  411     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is at the tail of the list.
  412 )
  413 {
  414     return (le_sls_PeekTail(listPtr) == linkPtr);
  415 }
  416 
  417 
  418 //--------------------------------------------------------------------------------------------------
  419 /**
  420  * Returns the number of links in a list.
  421  *
  422  * @return
  423  *      Number of links.
  424  */
  425 //--------------------------------------------------------------------------------------------------
  426 size_t le_sls_NumLinks
  427 (
  428     const le_sls_List_t* listPtr       ///< [IN] List to count.
  429 );
  430 
  431 
  432 //--------------------------------------------------------------------------------------------------
  433 /**
  434  * Checks if the list is corrupted.
  435  *
  436  * @return
  437  *      true if the list is corrupted.
  438  *      false if the list is not corrupted.
  439  */
  440 //--------------------------------------------------------------------------------------------------
  441 bool le_sls_IsListCorrupted
  442 (
  443     const le_sls_List_t* listPtr    ///< [IN] List to check.
  444 );
  445 
  446 
  447 #endif  // LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
  448 
le_sls_IsHead
static bool le_sls_IsHead(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
Definition: le_singlyLinkedList.h:390
le_sls_Queue
void le_sls_Queue(le_sls_List_t *listPtr, le_sls_Link_t *newLinkPtr)
le_sls_IsEmpty
static bool le_sls_IsEmpty(const le_sls_List_t *listPtr)
Definition: le_singlyLinkedList.h:355
le_sls_IsInList
bool le_sls_IsInList(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
le_sls_Link_t
Definition: le_singlyLinkedList.h:186
le_sls_IsTail
static bool le_sls_IsTail(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
Definition: le_singlyLinkedList.h:409
le_sls_RemoveAfter
le_sls_Link_t * le_sls_RemoveAfter(le_sls_List_t *listPtr, le_sls_Link_t *currentLinkPtr)
le_sls_PeekNext
le_sls_Link_t * le_sls_PeekNext(const le_sls_List_t *listPtr, const le_sls_Link_t *currentLinkPtr)
le_sls_Peek
le_sls_Link_t * le_sls_Peek(const le_sls_List_t *listPtr)
le_sls_Pop
le_sls_Link_t * le_sls_Pop(le_sls_List_t *listPtr)
le_sls_AddAfter
void le_sls_AddAfter(le_sls_List_t *listPtr, le_sls_Link_t *currentLinkPtr, le_sls_Link_t *newLinkPtr)
le_sls_IsListCorrupted
bool le_sls_IsListCorrupted(const le_sls_List_t *listPtr)
le_sls_Link_t::nextPtr
struct le_sls_Link * nextPtr
Next link pointer. 
Definition: le_singlyLinkedList.h:188
le_sls_List_t::tailLinkPtr
le_sls_Link_t * tailLinkPtr
Tail link pointer. 
Definition: le_singlyLinkedList.h:203
le_sls_PeekTail
le_sls_Link_t * le_sls_PeekTail(const le_sls_List_t *listPtr)
le_sls_NumLinks
size_t le_sls_NumLinks(const le_sls_List_t *listPtr)
le_sls_List_t
Definition: le_singlyLinkedList.h:201
le_sls_Stack
void le_sls_Stack(le_sls_List_t *listPtr, le_sls_Link_t *newLinkPtr)