iot_linear_containers.h

Go to the documentation of this file.

/*
 * IoT Common V1.1.0
 * Copyright (C) 2019 Amazon.com, Inc. or its affiliates.  All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
 * the Software, and to permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef IOT_LINEAR_CONTAINERS_H_
#define IOT_LINEAR_CONTAINERS_H_

/* The config header is always included first. */
#include "iot_config.h"

/* Standard includes. */
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct IotLink
{
    struct IotLink * pPrevious; 
    struct IotLink * pNext;     
} IotLink_t;

typedef IotLink_t   IotListDouble_t;

typedef IotLink_t   IotDeQueue_t;

/* @[define_linear_containers_initializers] */
#define IOT_LINK_INITIALIZER           { 0 }                
#define IOT_LIST_DOUBLE_INITIALIZER    IOT_LINK_INITIALIZER 
#define IOT_DEQUEUE_INITIALIZER        IOT_LINK_INITIALIZER 
/* @[define_linear_containers_initializers] */

#if IOT_CONTAINERS_ENABLE_ASSERTS == 1
    #ifndef IotContainers_Assert
        #ifdef Iot_DefaultAssert
            #define IotContainers_Assert( expression )    Iot_DefaultAssert( expression )
        #else
            #error "Asserts are enabled for containers, but IotContainers_Assert is not defined"
        #endif
    #endif
#else  /* if IOT_CONTAINERS_ENABLE_ASSERTS == 1 */
    #define IotContainers_Assert( expression )
#endif /* if IOT_CONTAINERS_ENABLE_ASSERTS == 1 */

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

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

/* @[declare_linear_containers_link_islinked] */
static inline bool IotLink_IsLinked( const IotLink_t * const pLink )
/* @[declare_linear_containers_link_islinked] */
{
    bool isLinked = false;

    if( pLink != NULL )
    {
        isLinked = ( pLink->pNext != NULL ) && ( pLink->pPrevious != NULL );
    }

    return isLinked;
}

/* @[declare_linear_containers_list_double_create] */
static inline void IotListDouble_Create( IotListDouble_t * const pList )
/* @[declare_linear_containers_list_double_create] */
{
    /* This function must not be called with a NULL parameter. */
    IotContainers_Assert( pList != NULL );

    /* An empty list is a link pointing to itself. */
    pList->pPrevious = pList;
    pList->pNext = pList;
}

/* @[declare_linear_containers_list_double_count] */
static inline size_t IotListDouble_Count( const IotListDouble_t * const pList )
/* @[declare_linear_containers_list_double_count] */
{
    size_t count = 0;

    if( pList != NULL )
    {
        /* Get the list head. */
        const IotLink_t * pCurrent = pList->pNext;

        /* Iterate through the list to count the elements. */
        while( pCurrent != pList )
        {
            count++;
            pCurrent = pCurrent->pNext;
        }
    }

    return count;
}

/* @[declare_linear_containers_list_double_isempty] */
static inline bool IotListDouble_IsEmpty( const IotListDouble_t * const pList )
/* @[declare_linear_containers_list_double_isempty] */
{
    /* An empty list is NULL link, or a link pointing to itself. */
    return( ( pList == NULL ) || ( pList->pNext == pList ) );
}

/* @[declare_linear_containers_list_double_peekhead] */
static inline IotLink_t * IotListDouble_PeekHead( const IotListDouble_t * const pList )
/* @[declare_linear_containers_list_double_peekhead] */
{
    IotLink_t * pHead = NULL;

    if( pList != NULL )
    {
        if( IotListDouble_IsEmpty( pList ) == false )
        {
            pHead = pList->pNext;
        }
    }

    return pHead;
}

/* @[declare_linear_containers_list_double_peektail] */
static inline IotLink_t * IotListDouble_PeekTail( const IotListDouble_t * const pList )
/* @[declare_linear_containers_list_double_peektail] */
{
    IotLink_t * pTail = NULL;

    if( pList != NULL )
    {
        if( IotListDouble_IsEmpty( pList ) == false )
        {
            pTail = pList->pPrevious;
        }
    }

    return pTail;
}

/* @[declare_linear_containers_list_double_inserthead] */
static inline void IotListDouble_InsertHead( IotListDouble_t * const pList,
                                             IotLink_t * const pLink )
/* @[declare_linear_containers_list_double_inserthead] */
{
    /* This function must not be called with NULL parameters. */
    IotContainers_Assert( pList != NULL );
    IotContainers_Assert( pLink != NULL );

    /* Save current list head. */
    IotLink_t * pHead = pList->pNext;

    /* Place new element before list head. */
    pLink->pNext = pHead;
    pLink->pPrevious = pList;

    /* Assign new list head. */
    pHead->pPrevious = pLink;
    pList->pNext = pLink;
}

/* @[declare_linear_containers_list_double_inserttail] */
static inline void IotListDouble_InsertTail( IotListDouble_t * const pList,
                                             IotLink_t * const pLink )
/* @[declare_linear_containers_list_double_inserttail] */
{
    /* This function must not be called with NULL parameters. */
    IotContainers_Assert( pList != NULL );
    IotContainers_Assert( pLink != NULL );

    /* Save current list tail. */
    IotLink_t * pTail = pList->pPrevious;

    pLink->pNext = pList;
    pLink->pPrevious = pTail;

    pList->pPrevious = pLink;
    pTail->pNext = pLink;
}

/* @[declare_linear_containers_list_double_insertbefore] */
static inline void IotListDouble_InsertBefore( IotLink_t * const pElement,
                                               IotLink_t * const pLink )
/* @[declare_linear_containers_list_double_insertbefore] */
{
    IotListDouble_InsertTail( pElement, pLink );
}

/* @[declare_linear_containers_list_double_insertafter] */
static inline void IotListDouble_InsertAfter( IotLink_t * const pElement,
                                              IotLink_t * const pLink )
/* @[declare_linear_containers_list_double_insertafter] */
{
    IotListDouble_InsertHead( pElement, pLink );
}

/* @[declare_linear_containers_list_double_insertsorted] */
static inline void IotListDouble_InsertSorted( IotListDouble_t * const pList,
                                               IotLink_t * const pLink,
                                               int32_t ( *compare )( const IotLink_t * const pParam1, const IotLink_t * const pParam2 ) )
/* @[declare_linear_containers_list_double_insertsorted] */
{
    /* This function must not be called with NULL parameters. */
    IotContainers_Assert( pList != NULL );
    IotContainers_Assert( pLink != NULL );
    IotContainers_Assert( compare != NULL );

    /* Insert at head for empty list. */
    if( IotListDouble_IsEmpty( pList ) == true )
    {
        IotListDouble_InsertHead( pList, pLink );
    }
    else
    {
        bool inserted = false;
        IotLink_t * pCurrent = pList->pNext;

        /* Iterate through the list to find the correct position. */
        while( pCurrent != pList )
        {
            /* Comparing for '<' preserves the order of insertion. */
            if( compare( pLink, pCurrent ) < 0 )
            {
                IotListDouble_InsertBefore( pCurrent, pLink );
                inserted = true;

                break;
            }

            pCurrent = pCurrent->pNext;
        }

        /* New element is greater than all elements in list. Insert at tail. */
        if( inserted == false )
        {
            IotListDouble_InsertTail( pList, pLink );
        }
    }
}

/* @[declare_linear_containers_list_double_remove] */
static inline void IotListDouble_Remove( IotLink_t * const pLink )
/* @[declare_linear_containers_list_double_remove] */
{
    /* This function must not be called with a NULL parameter. */
    IotContainers_Assert( pLink != NULL );

    /* This function must be called on a linked element. */
    IotContainers_Assert( IotLink_IsLinked( pLink ) == true );

    pLink->pPrevious->pNext = pLink->pNext;
    pLink->pNext->pPrevious = pLink->pPrevious;
    pLink->pPrevious = NULL;
    pLink->pNext = NULL;
}

/* @[declare_linear_containers_list_double_removehead] */
static inline IotLink_t * IotListDouble_RemoveHead( const IotListDouble_t * const pList )
/* @[declare_linear_containers_list_double_removehead] */
{
    IotLink_t * pHead = NULL;

    if( IotListDouble_IsEmpty( pList ) == false )
    {
        pHead = pList->pNext;
        IotListDouble_Remove( pHead );
    }

    return pHead;
}

/* @[declare_linear_containers_list_double_removetail] */
static inline IotLink_t * IotListDouble_RemoveTail( const IotListDouble_t * const pList )
/* @[declare_linear_containers_list_double_removetail] */
{
    IotLink_t * pTail = NULL;

    if( IotListDouble_IsEmpty( pList ) == false )
    {
        pTail = pList->pPrevious;
        IotListDouble_Remove( pTail );
    }

    return pTail;
}

/* @[declare_linear_containers_list_double_removeall] */
static inline void IotListDouble_RemoveAll( const IotListDouble_t * const pList,
                                            void ( *freeElement )( void * pData ),
                                            size_t linkOffset )
/* @[declare_linear_containers_list_double_removeall] */
{
    /* This function must not be called with a NULL pList parameter. */
    IotContainers_Assert( pList != NULL );

    /* Get the list head. */
    IotLink_t * pCurrent = pList->pNext;

    /* Iterate through the list and remove all elements. */
    while( pCurrent != pList )
    {
        /* Save a pointer to the next list element. */
        IotLink_t * pNext = pCurrent->pNext;

        /* Remove and free the current list element. */
        IotListDouble_Remove( pCurrent );

        if( freeElement != NULL )
        {
            freeElement( ( ( uint8_t * ) pCurrent ) - linkOffset );
        }

        /* Move the iterating pointer to the next list element. */
        pCurrent = pNext;
    }
}

/* @[declare_linear_containers_list_double_findfirstmatch] */
static inline IotLink_t * IotListDouble_FindFirstMatch( const IotListDouble_t * const pList,
                                                        const IotLink_t * const pStartPoint,
                                                        bool ( *isMatch )( const IotLink_t * const pOperationLink, void * pCompare ),
                                                        void * pMatch )
/* @[declare_linear_containers_list_double_findfirstmatch] */
{
    /* The const must be cast away to match this function's return value. Nevertheless,
     * this function will respect the const-ness of pStartPoint. */
    /* coverity[misra_c_2012_rule_11_8_violation] */
    IotLink_t * pCurrent = ( IotLink_t * ) pStartPoint, * pMatchedLink = NULL;
    bool matchFound = false;

    /* This function must not be called with a NULL pList parameter. */
    IotContainers_Assert( pList != NULL );

    /* Search starting from list head if no start point is given. */
    if( pStartPoint == NULL )
    {
        pCurrent = pList->pNext;
    }

    /* Iterate through the list to search for matches. */
    while( pCurrent != pList )
    {
        /* Call isMatch if provided. Otherwise, compare pointers. */
        if( isMatch != NULL )
        {
            matchFound = isMatch( pCurrent, pMatch );
        }
        else
        {
            matchFound = ( pCurrent == pMatch );
        }

        if( matchFound == true )
        {
            pMatchedLink = pCurrent;
            break;
        }

        pCurrent = pCurrent->pNext;
    }

    /* Return match if found, else NULL. */
    return pMatchedLink;
}

/* @[declare_linear_containers_list_double_removefirstmatch] */
static inline IotLink_t * IotListDouble_RemoveFirstMatch( const IotListDouble_t * const pList,
                                                          const IotLink_t * const pStartPoint,
                                                          bool ( *isMatch )( const IotLink_t * const pOperationLink, void * pCompare ),
                                                          void * pMatch )
/* @[declare_linear_containers_list_double_removefirstmatch] */
{
    IotLink_t * pMatchedElement = IotListDouble_FindFirstMatch( pList,
                                                                pStartPoint,
                                                                isMatch,
                                                                pMatch );

    if( pMatchedElement != NULL )
    {
        IotListDouble_Remove( pMatchedElement );
    }

    return pMatchedElement;
}

/* @[declare_linear_containers_list_double_removeallmatches] */
static inline 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 )
/* @[declare_linear_containers_list_double_removeallmatches] */
{
    IotLink_t * pMatchedElement = NULL, * pNextElement = NULL;

    /* Search the list for all matching elements. */
    do
    {
        pMatchedElement = IotListDouble_FindFirstMatch( pList,
                                                        pMatchedElement,
                                                        isMatch,
                                                        pMatch );

        if( pMatchedElement != NULL )
        {
            /* Save pointer to next element. */
            pNextElement = pMatchedElement->pNext;

            /* Match found; remove and free. */
            IotListDouble_Remove( pMatchedElement );

            if( freeElement != NULL )
            {
                freeElement( ( ( uint8_t * ) pMatchedElement ) - linkOffset );
            }

            /* Continue search from next element. */
            pMatchedElement = pNextElement;
        }
    } while( pMatchedElement != NULL );
}

/* @[declare_linear_containers_queue_create] */
static inline void IotDeQueue_Create( IotDeQueue_t * const pQueue )
/* @[declare_linear_containers_queue_create] */
{
    IotListDouble_Create( pQueue );
}

/* @[declare_linear_containers_queue_count] */
static inline size_t IotDeQueue_Count( const IotDeQueue_t * const pQueue )
/* @[declare_linear_containers_queue_count] */
{
    return IotListDouble_Count( pQueue );
}

/* @[declare_linear_containers_queue_isempty] */
static inline bool IotDeQueue_IsEmpty( const IotDeQueue_t * const pQueue )
/* @[declare_linear_containers_queue_isempty] */
{
    return IotListDouble_IsEmpty( pQueue );
}

/* @[declare_linear_containers_queue_peekhead] */
static inline IotLink_t * IotDeQueue_PeekHead( const IotDeQueue_t * const pQueue )
/* @[declare_linear_containers_queue_peekhead] */
{
    return IotListDouble_PeekHead( pQueue );
}

/* @[declare_linear_containers_queue_peektail] */
static inline IotLink_t * IotDeQueue_PeekTail( const IotDeQueue_t * const pQueue )
/* @[declare_linear_containers_queue_peektail] */
{
    return IotListDouble_PeekTail( pQueue );
}

/* @[declare_linear_containers_queue_enqueuehead] */
static inline void IotDeQueue_EnqueueHead( IotDeQueue_t * const pQueue,
                                           IotLink_t * const pLink )
/* @[declare_linear_containers_queue_enqueuehead] */
{
    IotListDouble_InsertHead( pQueue, pLink );
}

/* @[declare_linear_containers_queue_dequeuehead] */
static inline IotLink_t * IotDeQueue_DequeueHead( const IotDeQueue_t * const pQueue )
/* @[declare_linear_containers_queue_dequeuehead] */
{
    return IotListDouble_RemoveHead( pQueue );
}

/* @[declare_linear_containers_queue_enqueuetail] */
static inline void IotDeQueue_EnqueueTail( IotDeQueue_t * const pQueue,
                                           IotLink_t * const pLink )
/* @[declare_linear_containers_queue_enqueuetail] */
{
    IotListDouble_InsertTail( pQueue, pLink );
}

/* @[declare_linear_containers_queue_dequeuetail] */
static inline IotLink_t * IotDeQueue_DequeueTail( const IotDeQueue_t * const pQueue )
/* @[declare_linear_containers_queue_dequeuetail] */
{
    return IotListDouble_RemoveTail( pQueue );
}

/* @[declare_linear_containers_queue_remove] */
static inline void IotDeQueue_Remove( IotLink_t * const pLink )
/* @[declare_linear_containers_queue_remove] */
{
    IotListDouble_Remove( pLink );
}

/* @[declare_linear_containers_queue_removeall] */
static inline void IotDeQueue_RemoveAll( const IotDeQueue_t * const pQueue,
                                         void ( * freeElement )( void * pData ),
                                         size_t linkOffset )
/* @[declare_linear_containers_queue_removeall] */
{
    IotListDouble_RemoveAll( pQueue, freeElement, linkOffset );
}

/* @[declare_linear_containers_queue_removeallmatches] */
static inline 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 )
/* @[declare_linear_containers_queue_removeallmatches] */
{
    IotListDouble_RemoveAllMatches( pQueue, isMatch, pMatch, freeElement, linkOffset );
}

#endif /* IOT_LINEAR_CONTAINERS_H_ */