AWS IoT Device SDK C: Linear Containers
Linked lists and Queues
Return to main page ↑
iot_linear_containers.h File Reference

Declares and implements doubly-linked lists and queues. More...

#include "iot_config.h"
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

Go to the source code of this file.

Data Structures

struct  IotLink_t
 Link member placed in structs of a list or queue. More...
 

Macros

#define IOT_LINK_INITIALIZER   { 0 }
 Initializer for an IotLink_t.
 
#define IOT_LIST_DOUBLE_INITIALIZER   IOT_LINK_INITIALIZER
 Initializer for an IotListDouble_t.
 
#define IOT_DEQUEUE_INITIALIZER   IOT_LINK_INITIALIZER
 Initializer for an IotDeQueue_t.
 
#define IotContainers_Assert(expression)
 Assertion macro for the linear containers library. More...
 
#define IotLink_Container(type, pLink, linkName)   ( ( type * ) ( void * ) ( ( ( uint8_t * ) ( pLink ) ) - offsetof( type, linkName ) ) )
 Calculates the starting address of a containing struct. More...
 
#define IotContainers_ForEach(pStart, pLink)
 Iterates through all elements of a linear container. More...
 

Typedefs

typedef IotLink_t IotListDouble_t
 Represents a doubly-linked list.
 
typedef IotLink_t IotDeQueue_t
 Represents a queue.
 

Functions

static bool IotLink_IsLinked (const IotLink_t *const pLink)
 Check if an IotLink_t is linked in a list or queue. More...
 
static void IotListDouble_Create (IotListDouble_t *const pList)
 Create a new doubly-linked list. More...
 
static size_t IotListDouble_Count (const IotListDouble_t *const pList)
 Return the number of elements contained in an IotListDouble_t. More...
 
static bool IotListDouble_IsEmpty (const IotListDouble_t *const pList)
 Check if a doubly-linked list is empty. More...
 
static IotLink_tIotListDouble_PeekHead (const IotListDouble_t *const pList)
 Return an IotLink_t representing the first element in a doubly-linked list without removing it. More...
 
static IotLink_tIotListDouble_PeekTail (const IotListDouble_t *const pList)
 Return an IotLink_t representing the last element in a doubly-linked list without removing it. More...
 
static void IotListDouble_InsertHead (IotListDouble_t *const pList, IotLink_t *const pLink)
 Insert an element at the head of a doubly-linked list. More...
 
static void IotListDouble_InsertTail (IotListDouble_t *const pList, IotLink_t *const pLink)
 Insert an element at the tail of a doubly-linked list. More...
 
static void IotListDouble_InsertBefore (IotLink_t *const pElement, IotLink_t *const pLink)
 Insert an element before another element in a doubly-linked list. More...
 
static void IotListDouble_InsertAfter (IotLink_t *const pElement, IotLink_t *const pLink)
 Insert an element after another element in a doubly-linked list. More...
 
static void IotListDouble_InsertSorted (IotListDouble_t *const pList, IotLink_t *const pLink, int32_t(*compare)(const IotLink_t *const pParam1, const IotLink_t *const pParam2))
 Insert an element in a sorted doubly-linked list. More...
 
static void IotListDouble_Remove (IotLink_t *const pLink)
 Remove a single element from a doubly-linked list. More...
 
static IotLink_tIotListDouble_RemoveHead (const IotListDouble_t *const pList)
 Remove the element at the head of a doubly-linked list. More...
 
static IotLink_tIotListDouble_RemoveTail (const IotListDouble_t *const pList)
 Remove the element at the tail of a doubly-linked list. More...
 
static void IotListDouble_RemoveAll (const IotListDouble_t *const pList, void(*freeElement)(void *pData), size_t linkOffset)
 Remove all elements in a doubly-linked list. More...
 
static IotLink_tIotListDouble_FindFirstMatch (const IotListDouble_t *const pList, const IotLink_t *const pStartPoint, bool(*isMatch)(const IotLink_t *const pOperationLink, void *pCompare), void *pMatch)
 Search a doubly-linked list for the first matching element. More...
 
static IotLink_tIotListDouble_RemoveFirstMatch (const IotListDouble_t *const pList, const IotLink_t *const pStartPoint, bool(*isMatch)(const IotLink_t *const pOperationLink, void *pCompare), void *pMatch)
 Search a doubly-linked list for the first matching element and remove it. More...
 
static void IotListDouble_RemoveAllMatches (const IotListDouble_t *const pList, bool(*isMatch)(const IotLink_t *const pOperationLink, void *pCompare), void *pMatch, void(*freeElement)(void *pData), size_t linkOffset)
 Remove all matching elements from a doubly-linked list. More...
 
static void IotDeQueue_Create (IotDeQueue_t *const pQueue)
 Create a new queue. More...
 
static size_t IotDeQueue_Count (const IotDeQueue_t *const pQueue)
 Return the number of elements contained in an IotDeQueue_t. More...
 
static bool IotDeQueue_IsEmpty (const IotDeQueue_t *const pQueue)
 Check if a queue is empty. More...
 
static IotLink_tIotDeQueue_PeekHead (const IotDeQueue_t *const pQueue)
 Return an IotLink_t representing the element at the front of the queue without removing it. More...
 
static IotLink_tIotDeQueue_PeekTail (const IotDeQueue_t *const pQueue)
 Return an IotLink_t representing the element at the back of the queue without removing it. More...
 
static void IotDeQueue_EnqueueHead (IotDeQueue_t *const pQueue, IotLink_t *const pLink)
 Add an element at the head of the queue. More...
 
static IotLink_tIotDeQueue_DequeueHead (const IotDeQueue_t *const pQueue)
 Remove an element at the head of the queue. More...
 
static void IotDeQueue_EnqueueTail (IotDeQueue_t *const pQueue, IotLink_t *const pLink)
 Add an element at the tail of the queue. More...
 
static IotLink_tIotDeQueue_DequeueTail (const IotDeQueue_t *const pQueue)
 Remove an element at the tail of the queue. More...
 
static void IotDeQueue_Remove (IotLink_t *const pLink)
 Remove a single element from a queue. More...
 
static void IotDeQueue_RemoveAll (const IotDeQueue_t *const pQueue, void(*freeElement)(void *pData), size_t linkOffset)
 Remove all elements in a queue. More...
 
static void IotDeQueue_RemoveAllMatches (const IotDeQueue_t *const pQueue, bool(*isMatch)(const IotLink_t *const pOperationLink, void *pCompare), void *pMatch, void(*freeElement)(void *pData), size_t linkOffset)
 Remove all matching elements from a queue. More...
 

Detailed Description

Declares and implements doubly-linked lists and queues.

Macro Definition Documentation

◆ IotContainers_Assert

#define IotContainers_Assert (   expression)

Assertion macro for the linear containers library.

Set IOT_CONTAINERS_ENABLE_ASSERTS to 1 to enable assertions in the linear containers library.

Parameters
[in]expressionExpression to be evaluated.

◆ IotLink_Container

#define IotLink_Container (   type,
  pLink,
  linkName 
)    ( ( type * ) ( void * ) ( ( ( uint8_t * ) ( pLink ) ) - offsetof( type, linkName ) ) )

Calculates the starting address of a containing struct.

Parameters
[in]typeType of the containing struct.
[in]pLinkPointer to a link member.
[in]linkNameName of the IotLink_t in the containing struct.

◆ IotContainers_ForEach

#define IotContainers_ForEach (   pStart,
  pLink 
)
Value:
for( ( pLink ) = ( pStart )->pNext; \
( pLink ) != ( pStart ); \
( pLink ) = ( pLink )->pNext )

Iterates through all elements of a linear container.

Container elements must not be freed or removed while iterating.

Parameters
[in]pStartThe first element to iterate from.
[out]pLinkPointer to a container element.

Function Documentation

◆ IotLink_IsLinked()

static bool IotLink_IsLinked ( const IotLink_t *const  pLink)
inlinestatic

Check if an IotLink_t is linked in a list or queue.

Parameters
[in]pLinkThe link to check.
Returns
true if pCurrent is linked in a list or queue; false otherwise.

◆ IotListDouble_Create()

static void IotListDouble_Create ( IotListDouble_t *const  pList)
inlinestatic

Create a new doubly-linked list.

This function initializes a new doubly-linked list. It must be called on an uninitialized IotListDouble_t before calling any other doubly-linked list function. This function must not be called on an already-initialized IotListDouble_t.

This function will not fail. The function IotListDouble_RemoveAll may be called to destroy a list.

Parameters
[in]pListPointer to the memory that will hold the new doubly-linked list.

◆ IotListDouble_Count()

static size_t IotListDouble_Count ( const IotListDouble_t *const  pList)
inlinestatic

Return the number of elements contained in an IotListDouble_t.

Parameters
[in]pListThe doubly-linked list with the elements to count.
Returns
The number of elements in the doubly-linked list.

◆ IotListDouble_IsEmpty()

static bool IotListDouble_IsEmpty ( const IotListDouble_t *const  pList)
inlinestatic

Check if a doubly-linked list is empty.

Parameters
[in]pListThe doubly-linked list to check.
Returns
true if the list is empty; false otherwise.

◆ IotListDouble_PeekHead()

static IotLink_t* IotListDouble_PeekHead ( const IotListDouble_t *const  pList)
inlinestatic

Return an IotLink_t representing the first element in a doubly-linked list without removing it.

Parameters
[in]pListThe list to peek.
Returns
Pointer to an IotLink_t representing the element at the head of the list; NULL if the list is empty. The macro IotLink_Container may be used to determine the address of the link's container.

◆ IotListDouble_PeekTail()

static IotLink_t* IotListDouble_PeekTail ( const IotListDouble_t *const  pList)
inlinestatic

Return an IotLink_t representing the last element in a doubly-linked list without removing it.

Parameters
[in]pListThe list to peek.
Returns
Pointer to an IotLink_t representing the element at the tail of the list; NULL if the list is empty. The macro IotLink_Container may be used to determine the address of the link's container.

◆ IotListDouble_InsertHead()

static void IotListDouble_InsertHead ( IotListDouble_t *const  pList,
IotLink_t *const  pLink 
)
inlinestatic

Insert an element at the head of a doubly-linked list.

Parameters
[in]pListThe doubly-linked list that will hold the new element.
[in]pLinkPointer to the new element's link member.

◆ IotListDouble_InsertTail()

static void IotListDouble_InsertTail ( IotListDouble_t *const  pList,
IotLink_t *const  pLink 
)
inlinestatic

Insert an element at the tail of a doubly-linked list.

Parameters
[in]pListThe double-linked list that will hold the new element.
[in]pLinkPointer to the new element's link member.

◆ IotListDouble_InsertBefore()

static void IotListDouble_InsertBefore ( IotLink_t *const  pElement,
IotLink_t *const  pLink 
)
inlinestatic

Insert an element before another element in a doubly-linked list.

Parameters
[in]pElementThe new element will be placed before this element.
[in]pLinkPointer to the new element's link member.

◆ IotListDouble_InsertAfter()

static void IotListDouble_InsertAfter ( IotLink_t *const  pElement,
IotLink_t *const  pLink 
)
inlinestatic

Insert an element after another element in a doubly-linked list.

Parameters
[in]pElementThe new element will be placed after this element.
[in]pLinkPointer to the new element's link member.

◆ IotListDouble_InsertSorted()

static void IotListDouble_InsertSorted ( IotListDouble_t *const  pList,
IotLink_t *const  pLink,
int32_t(*)(const IotLink_t *const pParam1, const IotLink_t *const pParam2)  compare 
)
inlinestatic

Insert an element in a sorted doubly-linked list.

Places an element into a list by sorting it into order. The function compare is used to determine where to place the new element.

Parameters
[in]pListThe list that will hold the new element.
[in]pLinkPointer to the new element's link member.
[in]compareDetermines the order of the list. Returns a negative value if its first argument is less than its second argument; returns zero if its first argument is equal to its second argument; returns a positive value if its first argument is greater than its second argument. The parameters to this function are IotLink_t, so the macro IotLink_Container may be used to determine the address of the link's container.

◆ IotListDouble_Remove()

static void IotListDouble_Remove ( IotLink_t *const  pLink)
inlinestatic

Remove a single element from a doubly-linked list.

Parameters
[in]pLinkThe element to remove.

◆ IotListDouble_RemoveHead()

static IotLink_t* IotListDouble_RemoveHead ( const IotListDouble_t *const  pList)
inlinestatic

Remove the element at the head of a doubly-linked list.

Parameters
[in]pListThe doubly-linked list that holds the element to remove.
Returns
Pointer to an IotLink_t representing the removed list head; NULL if the list is empty. The macro IotLink_Container may be used to determine the address of the link's container.

◆ IotListDouble_RemoveTail()

static IotLink_t* IotListDouble_RemoveTail ( const IotListDouble_t *const  pList)
inlinestatic

Remove the element at the tail of a doubly-linked list.

Parameters
[in]pListThe doubly-linked list that holds the element to remove.
Returns
Pointer to an IotLink_t representing the removed list tail; NULL if the list is empty. The macro IotLink_Container may be used to determine the address of the link's container.

◆ IotListDouble_RemoveAll()

static void IotListDouble_RemoveAll ( const IotListDouble_t *const  pList,
void(*)(void *pData)  freeElement,
size_t  linkOffset 
)
inlinestatic

Remove all elements in a doubly-linked list.

Parameters
[in]pListThe list to empty.
[in]freeElementA function to free memory used by each removed list element. Optional; pass NULL to ignore.
[in]linkOffsetOffset in bytes of a link member in its container, used to calculate the pointer to pass to freeElement. This value should be calculated with the C offsetof macro. This parameter is ignored if freeElement is NULL or its value is 0.

◆ IotListDouble_FindFirstMatch()

static IotLink_t* IotListDouble_FindFirstMatch ( const IotListDouble_t *const  pList,
const IotLink_t *const  pStartPoint,
bool(*)(const IotLink_t *const pOperationLink, void *pCompare)  isMatch,
void *  pMatch 
)
inlinestatic

Search a doubly-linked list for the first matching element.

If a match is found, the matching element is not removed from the list. See IotListDouble_RemoveFirstMatch for the function that searches and removes.

Parameters
[in]pListThe doubly-linked list to search.
[in]pStartPointAn element in pList. Only elements between this one and the list tail are checked. Pass NULL to search from the beginning of the list.
[in]isMatchFunction to determine if an element matches. Pass NULL to search using the address pMatch, i.e. element == pMatch.
[in]pMatchIf isMatch is NULL, each element in the list is compared to this address to find a match. Otherwise, it is passed as the second argument to isMatch.
Returns
Pointer to an IotLink_t representing the first matched element; NULL if no match is found. The macro IotLink_Container may be used to determine the address of the link's container.

◆ IotListDouble_RemoveFirstMatch()

static IotLink_t* IotListDouble_RemoveFirstMatch ( const IotListDouble_t *const  pList,
const IotLink_t *const  pStartPoint,
bool(*)(const IotLink_t *const pOperationLink, void *pCompare)  isMatch,
void *  pMatch 
)
inlinestatic

Search a doubly-linked list for the first matching element and remove it.

An IotLink_t may be passed as pList to start searching after the head of a doubly-linked list.

Parameters
[in]pListThe doubly-linked list to search.
[in]pStartPointAn element in pList. Only elements between this one and the list tail are checked. Pass NULL to search from the beginning of the list.
[in]isMatchFunction to determine if an element matches. Pass NULL to search using the address pMatch, i.e. element == pMatch.
[in]pMatchIf isMatch is NULL, each element in the list is compared to this address to find a match. Otherwise, it is passed as the second argument to isMatch.
Returns
Pointer to an IotLink_t representing the matched and removed element; NULL if no match is found. The macro IotLink_Container may be used to determine the address of the link's container.

◆ IotListDouble_RemoveAllMatches()

static void IotListDouble_RemoveAllMatches ( const IotListDouble_t *const  pList,
bool(*)(const IotLink_t *const pOperationLink, void *pCompare)  isMatch,
void *  pMatch,
void(*)(void *pData)  freeElement,
size_t  linkOffset 
)
inlinestatic

Remove all matching elements from a doubly-linked list.

Parameters
[in]pListThe doubly-linked list to search.
[in]isMatchFunction to determine if an element matches. Pass NULL to search using the address pMatch, i.e. element == pMatch.
[in]pMatchIf isMatch is NULL, each element in the list is compared to this address to find a match. Otherwise, it is passed as the second argument to isMatch.
[in]freeElementA function to free memory used by each removed list element. Optional; pass NULL to ignore.
[in]linkOffsetOffset in bytes of a link member in its container, used to calculate the pointer to pass to freeElement. This value should be calculated with the C offsetof macro. This parameter is ignored if freeElement is NULL or its value is 0.

◆ IotDeQueue_Create()

static void IotDeQueue_Create ( IotDeQueue_t *const  pQueue)
inlinestatic

Create a new queue.

This function initializes a new double-ended queue. It must be called on an uninitialized IotDeQueue_t before calling any other queue function. This function must not be called on an already-initialized IotDeQueue_t.

This function will not fail.

Parameters
[in]pQueuePointer to the memory that will hold the new queue.

◆ IotDeQueue_Count()

static size_t IotDeQueue_Count ( const IotDeQueue_t *const  pQueue)
inlinestatic

Return the number of elements contained in an IotDeQueue_t.

Parameters
[in]pQueueThe queue with the elements to count.
Returns
The number of items elements in the queue.

◆ IotDeQueue_IsEmpty()

static bool IotDeQueue_IsEmpty ( const IotDeQueue_t *const  pQueue)
inlinestatic

Check if a queue is empty.

Parameters
[in]pQueueThe queue to check.
Returns
true if the queue is empty; false otherwise.

◆ IotDeQueue_PeekHead()

static IotLink_t* IotDeQueue_PeekHead ( const IotDeQueue_t *const  pQueue)
inlinestatic

Return an IotLink_t representing the element at the front of the queue without removing it.

Parameters
[in]pQueueThe queue to peek.
Returns
Pointer to an IotLink_t representing the element at the head of the queue; NULL if the queue is empty. The macro IotLink_Container may be used to determine the address of the link's container.

◆ IotDeQueue_PeekTail()

static IotLink_t* IotDeQueue_PeekTail ( const IotDeQueue_t *const  pQueue)
inlinestatic

Return an IotLink_t representing the element at the back of the queue without removing it.

Parameters
[in]pQueueThe queue to peek.
Returns
Pointer to an IotLink_t representing the element at the head of the queue; NULL if the queue is empty. The macro IotLink_Container may be used to determine the address of the link's container.

◆ IotDeQueue_EnqueueHead()

static void IotDeQueue_EnqueueHead ( IotDeQueue_t *const  pQueue,
IotLink_t *const  pLink 
)
inlinestatic

Add an element at the head of the queue.

Parameters
[in]pQueueThe queue that will hold the new element.
[in]pLinkPointer to the new element's link member.

◆ IotDeQueue_DequeueHead()

static IotLink_t* IotDeQueue_DequeueHead ( const IotDeQueue_t *const  pQueue)
inlinestatic

Remove an element at the head of the queue.

Parameters
[in]pQueueThe queue that holds the element to remove.
Returns
Pointer to an IotLink_t representing the removed queue element; NULL if the queue is empty. The macro IotLink_Container may be used to determine the address of the link's container.

◆ IotDeQueue_EnqueueTail()

static void IotDeQueue_EnqueueTail ( IotDeQueue_t *const  pQueue,
IotLink_t *const  pLink 
)
inlinestatic

Add an element at the tail of the queue.

Parameters
[in]pQueueThe queue that will hold the new element.
[in]pLinkPointer to the new element's link member.

◆ IotDeQueue_DequeueTail()

static IotLink_t* IotDeQueue_DequeueTail ( const IotDeQueue_t *const  pQueue)
inlinestatic

Remove an element at the tail of the queue.

Parameters
[in]pQueueThe queue that holds the element to remove.
Returns
Pointer to an IotLink_t representing the removed queue element; NULL if the queue is empty. The macro IotLink_Container may be used to determine the address of the link's container.

◆ IotDeQueue_Remove()

static void IotDeQueue_Remove ( IotLink_t *const  pLink)
inlinestatic

Remove a single element from a queue.

Parameters
[in]pLinkThe element to remove.

◆ IotDeQueue_RemoveAll()

static void IotDeQueue_RemoveAll ( const IotDeQueue_t *const  pQueue,
void(*)(void *pData)  freeElement,
size_t  linkOffset 
)
inlinestatic

Remove all elements in a queue.

Parameters
[in]pQueueThe queue to empty.
[in]freeElementA function to free memory used by each removed queue element. Optional; pass NULL to ignore.
[in]linkOffsetOffset in bytes of a link member in its container, used to calculate the pointer to pass to freeElement. This value should be calculated with the C offsetof macro. This parameter is ignored if freeElement is NULL or its value is 0.

◆ IotDeQueue_RemoveAllMatches()

static void IotDeQueue_RemoveAllMatches ( const IotDeQueue_t *const  pQueue,
bool(*)(const IotLink_t *const pOperationLink, void *pCompare)  isMatch,
void *  pMatch,
void(*)(void *pData)  freeElement,
size_t  linkOffset 
)
inlinestatic

Remove all matching elements from a queue.

Parameters
[in]pQueueThe queue to search.
[in]isMatchFunction to determine if an element matches. Pass NULL to search using the address pMatch, i.e. element == pMatch.
[in]pMatchIf isMatch is NULL, each element in the queue is compared to this address to find a match. Otherwise, it is passed as the second argument to isMatch.
[in]freeElementA function to free memory used by each removed queue element. Optional; pass NULL to ignore.
[in]linkOffsetOffset in bytes of a link member in its container, used to calculate the pointer to pass to freeElement. This value should be calculated with the C offsetof macro. This parameter is ignored if freeElement is NULL or its value is 0.