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.  But if the nodes and/or list
  154  * object is shared by multiple threads, then explicit steps must be taken to maintain mutual
  155  * exclusion of access.
  156  *
  157  * <HR>
  158  *
  159  * Copyright (C) Sierra Wireless Inc. Use of this work is subject to license.
  160  */
  161 
  162 
  163  /** @file le_singlyLinkedList.h
  164   *
  165   * Legato @ref c_singlyLinkedList include file.
  166   *
  167   * Copyright (C) Sierra Wireless Inc. Use of this work is subject to license.
  168   */
  169 
  170 #ifndef LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
  171 #define LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
  172 
  173 
  174 //--------------------------------------------------------------------------------------------------
  175 /**
  176  * This link object must be included in each user node.  The node's link object is used to add the
  177  * node to a list.  A node may have multiple link objects which would allow the node to be part of
  178  * multiple lists simultaneously.  This link object must be initialized by assigning
  179  * LE_SLS_LINK_INIT to it.
  180  *
  181  * @warning The user MUST NOT access the contents of this structure directly.
  182  */
  183 //--------------------------------------------------------------------------------------------------
  184 typedef struct le_sls_Link
  185 {
  186     struct le_sls_Link* nextPtr;       ///< Next link pointer.
  187 }
  188 le_sls_Link_t;
  189 
  190 
  191 //--------------------------------------------------------------------------------------------------
  192 /**
  193  * This is the list object.  Create this list object and initialize it by assigning
  194  * LE_SLS_LIST_INIT to it.
  195  *
  196  * @warning DON'T access the contents of this structure directly.
  197  */
  198 //--------------------------------------------------------------------------------------------------
  199 typedef struct
  200 {
  201     le_sls_Link_t* tailLinkPtr;        ///< Tail link pointer.
  202 }
  203 le_sls_List_t;
  204 
  205 
  206 //--------------------------------------------------------------------------------------------------
  207 /**
  208  * When a list is created, it must be initialized by assigning this macro to the list before the list
  209  * can be used.
  210  */
  211 //--------------------------------------------------------------------------------------------------
  212 #define LE_SLS_LIST_INIT (le_sls_List_t){NULL}
  213 
  214 
  215 //--------------------------------------------------------------------------------------------------
  216 /**
  217  * When a link is created, it must be initialized by assigning this macro to the link before it can
  218  * be used.
  219  */
  220 //--------------------------------------------------------------------------------------------------
  221 #define LE_SLS_LINK_INIT (le_sls_Link_t){NULL}
  222 
  223 
  224 //--------------------------------------------------------------------------------------------------
  225 /**
  226  * Adds a link at the head of the list.
  227  */
  228 //--------------------------------------------------------------------------------------------------
  229 void le_sls_Stack
  230 (
  231     le_sls_List_t* listPtr,            ///< [IN] List to add to.
  232     le_sls_Link_t* newLinkPtr          ///< [IN] New link to add.
  233 );
  234 
  235 
  236 //--------------------------------------------------------------------------------------------------
  237 /**
  238  * Adds a link to the tail of the list.
  239  */
  240 //--------------------------------------------------------------------------------------------------
  241 void le_sls_Queue
  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 after currentLinkPtr.  Ensure that currentLinkPtr is in the list
  251  * otherwise the behaviour of this function is undefined.
  252  */
  253 //--------------------------------------------------------------------------------------------------
  254 void le_sls_AddAfter
  255 (
  256     le_sls_List_t* listPtr,            ///< [IN] List to add to.
  257     le_sls_Link_t* currentLinkPtr,     ///< [IN] New link will be inserted after this link.
  258     le_sls_Link_t* newLinkPtr          ///< [IN] New link to add.
  259 );
  260 
  261 
  262 //--------------------------------------------------------------------------------------------------
  263 /**
  264  * Removes the link found after currentLinkPtr.  The user must ensure that currentLinkPtr is in the
  265  * list otherwise the behaviour of this function is undefined.
  266  *
  267  * @return
  268  *      Pointer to the removed link.
  269  *      NULL if there are no more links in the list after currentLinkPtr.
  270  */
  271 //--------------------------------------------------------------------------------------------------
  272 le_sls_Link_t* le_sls_RemoveAfter
  273 (
  274     le_sls_List_t* listPtr,            ///< [IN] The list to remove from.
  275     le_sls_Link_t* currentLinkPtr      ///< [IN] The link after this one will be removed from the
  276                                        ///<      list.
  277 );
  278 
  279 
  280 //--------------------------------------------------------------------------------------------------
  281 /**
  282  * Removes and returns the link at the head of the list.
  283  *
  284  * @return
  285  *      Removed link.
  286  *      NULL if the link is not available because the list is empty.
  287  */
  288 //--------------------------------------------------------------------------------------------------
  289 le_sls_Link_t* le_sls_Pop
  290 (
  291     le_sls_List_t* listPtr             ///< [IN] List to remove from.
  292 );
  293 
  294 
  295 //--------------------------------------------------------------------------------------------------
  296 /**
  297  * Returns the link at the head of the list without removing it from the list.
  298  *
  299  * @return
  300  *     Pointer to the head link if successful.
  301  *      NULL if the list is empty.
  302  */
  303 //--------------------------------------------------------------------------------------------------
  304 le_sls_Link_t* le_sls_Peek
  305 (
  306     const le_sls_List_t* listPtr            ///< [IN] The list.
  307 );
  308 
  309 
  310 //------------------------------------------------------------------------------------------------------------
  311 /**
  312  * Returns the link at the tail of the list without removing it from the list.
  313  *
  314  * @return
  315  *      A pointer to the tail link if successful.
  316  *      NULL if the list is empty.
  317  */
  318 //------------------------------------------------------------------------------------------------------------
  319 le_sls_Link_t* le_sls_PeekTail
  320 (
  321     const le_sls_List_t* listPtr            ///< [IN] The list.
  322 );
  323 
  324 
  325 //--------------------------------------------------------------------------------------------------
  326 /**
  327  * Returns the link next to currentLinkPtr (i.e., the link beside currentLinkPtr that's closer to the
  328  * tail) without removing it from the list. Ensure currentLinkPtr is in the list
  329  * otherwise the behaviour of this function is undefined.
  330  *
  331  * @return
  332  *      Pointer to the next link if successful.
  333  *      NULL if there is no link next to the currentLinkPtr (currentLinkPtr is at the tail of the
  334  *      list).
  335  */
  336 //--------------------------------------------------------------------------------------------------
  337 le_sls_Link_t* le_sls_PeekNext
  338 (
  339     const le_sls_List_t* listPtr,           ///< [IN] List containing currentLinkPtr.
  340     const le_sls_Link_t* currentLinkPtr     ///< [IN] Get the link that is relative to this link.
  341 );
  342 
  343 
  344 //--------------------------------------------------------------------------------------------------
  345 /**
  346  * Checks if a list is empty.
  347  *
  348  * @return
  349  *      true if empty, false if not empty.
  350  */
  351 //--------------------------------------------------------------------------------------------------
  352 static inline bool le_sls_IsEmpty
  353 (
  354     const le_sls_List_t* listPtr            ///< [IN] The list.
  355 )
  356 //--------------------------------------------------------------------------------------------------
  357 {
  358     return (le_sls_Peek(listPtr) == NULL);
  359 }
  360 
  361 
  362 //--------------------------------------------------------------------------------------------------
  363 /**
  364  * Checks if a link is in the list.
  365  *
  366  * @return
  367  *    - true if the link is in the list.
  368  *    - false if the link is not in the list.
  369  */
  370 //--------------------------------------------------------------------------------------------------
  371 bool le_sls_IsInList
  372 (
  373     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  374     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is in the list.
  375 );
  376 
  377 
  378 //--------------------------------------------------------------------------------------------------
  379 /**
  380  * Checks if a link is at the head of the list (next to be popped).
  381  *
  382  * @return
  383  *    - true if the link is at the head of the list.
  384  *    - false if not.
  385  */
  386 //--------------------------------------------------------------------------------------------------
  387 static inline bool le_sls_IsHead
  388 (
  389     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  390     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is at the head of the list.
  391 )
  392 {
  393     return (le_sls_Peek(listPtr) == linkPtr);
  394 }
  395 
  396 
  397 //--------------------------------------------------------------------------------------------------
  398 /**
  399  * Checks if a link is at the tail of the list (last to be popped).
  400  *
  401  * @return
  402  *    - true if the link is at the tail of the list.
  403  *    - false if not.
  404  */
  405 //--------------------------------------------------------------------------------------------------
  406 static inline bool le_sls_IsTail
  407 (
  408     const le_sls_List_t* listPtr,    ///< [IN] List to check.
  409     const le_sls_Link_t* linkPtr     ///< [IN] Check if this link is at the tail of the list.
  410 )
  411 {
  412     return (le_sls_PeekTail(listPtr) == linkPtr);
  413 }
  414 
  415 
  416 //--------------------------------------------------------------------------------------------------
  417 /**
  418  * Returns the number of links in a list.
  419  *
  420  * @return
  421  *      Number of links.
  422  */
  423 //--------------------------------------------------------------------------------------------------
  424 size_t le_sls_NumLinks
  425 (
  426     const le_sls_List_t* listPtr       ///< [IN] List to count.
  427 );
  428 
  429 
  430 //--------------------------------------------------------------------------------------------------
  431 /**
  432  * Checks if the list is corrupted.
  433  *
  434  * @return
  435  *      true if the list is corrupted.
  436  *      false if the list is not corrupted.
  437  */
  438 //--------------------------------------------------------------------------------------------------
  439 bool le_sls_IsListCorrupted
  440 (
  441     const le_sls_List_t* listPtr    ///< [IN] List to check.
  442 );
  443 
  444 
  445 #endif  // LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
  446 
le_sls_IsHead
static bool le_sls_IsHead(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
Definition: le_singlyLinkedList.h:388
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:353
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:184
le_sls_IsTail
static bool le_sls_IsTail(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
Definition: le_singlyLinkedList.h:407
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:186
le_sls_List_t::tailLinkPtr
le_sls_Link_t * tailLinkPtr
Tail link pointer. 
Definition: le_singlyLinkedList.h:201
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:199
le_sls_Stack
void le_sls_Stack(le_sls_List_t *listPtr, le_sls_Link_t *newLinkPtr)