oc_list.c

Go to the documentation of this file.

#include <oc_list.h>
#include <oc_math.h>
#include <string.h>
#include <oc_null.h>
#include <oc_stdlib.h>
#include <oc_errors.h>

#define _________________________________________LOCAL_PROTOTYPES_SECTION___________________________________________________________________

static void PushToEmpty( oC_List_t List , oC_List_ElementHandle_t Handle );

#undef  _________________________________________LOCAL_PROTOTYPES_SECTION___________________________________________________________________


#define _________________________________________INTERFACE_SECTION__________________________________________________________________________

//==========================================================================================================================================
//==========================================================================================================================================
oC_List_t List_New( Allocator_t Allocator , AllocationFlags_t Flags )
{
    oC_List_t list = NULL;

    list = kmalloc(sizeof(struct List_t) , Allocator , Flags );

    if(list)
    {
        list->ObjectControl = oC_CountObjectControl(list,oC_ObjectId_List);
        list->Count         = 0;
        list->First         = NULL;
        list->Last          = NULL;
    }

    return list;
}


//==========================================================================================================================================
//==========================================================================================================================================
bool List_IsCorrect( oC_List_t List )
{
    return isram(List) && oC_CheckObjectControl(List,oC_ObjectId_List,List->ObjectControl);
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_Delete( oC_List_t * List , AllocationFlags_t Flags )
{
    bool deleted = false;

    if(List_IsCorrect(*List))
    {
        if(List_Clear(*List))
        {
            (*List)->ObjectControl = 0;

            if(kfree(*List,Flags))
            {
                *List   = NULL;
                deleted = true;
            }
            else
            {
                oC_SaveError("List-delete: cannot release memory" , oC_ErrorCode_ReleaseError);
            }
        }
        else
        {
            oC_SaveError("List-delete: cannot clear the list" , oC_ErrorCode_ReleaseError);
        }
    }


    return deleted;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_DeleteElement( oC_List_ElementHandle_t Element )
{
    bool success = false;

    if(isram(Element))
    {
        success = kfree(Element->Object,AllocationFlags_CanWaitForever) && kfree(Element,AllocationFlags_CanWaitForever);
    }

    return success;
}

//==========================================================================================================================================
//==========================================================================================================================================
oC_List_ElementHandle_t List_NewElement( const void * Object , oC_UInt_t Size , Allocator_t Allocator )
{
    oC_List_ElementHandle_t handle = NULL;

    if(isaddresscorrect(Object))
    {
        handle = kmalloc(sizeof(struct List_ElementHandle_t),Allocator,AllocationFlags_CanWaitForever);

        if(handle)
        {
            handle->Object   = kmalloc(Size, Allocator , AllocationFlags_CanWaitForever);
            memcpy(handle->Object,Object,Size);
            handle->Size     = Size;
            handle->Next     = NULL;
            handle->Previous = NULL;
        }
    }

    return handle;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_Contains( oC_List_t List , void * Object , oC_UInt_t Size )
{
    return List_CountObjects(List,Object,Size) > 0;
}

//==========================================================================================================================================
//==========================================================================================================================================
uint32_t List_Count( oC_List_t List )
{
    uint32_t count = 0;

    if(List_IsCorrect(List))
    {
        count = List->Count;
    }

    return count;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_Clear( oC_List_t List )
{
    bool success = false;

    if(List_IsCorrect(List))
    {
        success = true;
        oC_List_ElementHandle_t element     = List->Last;
        oC_List_ElementHandle_t previous    = element->Previous;

        while(List_DeleteElement(element))
        {
            element     = previous;
            previous    = previous->Previous;
            List->Count--;
        }
    }

    return success;
}

//==========================================================================================================================================
//==========================================================================================================================================
uint32_t List_CountObjects( oC_List_t List , void * Object , oC_UInt_t Size )
{
    uint32_t count = 0;

    if(List_IsCorrect(List) && (Size > 0) && (isaddresscorrect(Object)))
    {
        for(oC_List_ElementHandle_t element = List->First ; element != NULL ; element = element->Next )
        {
            if((Size == element->Size) && (memcmp(Object,element->Object,element->Size) == 0))
            {
               count++;
            }
        }
    }

    return count;
}

//==========================================================================================================================================
//==========================================================================================================================================
int List_IndexOf( oC_List_t List , void * Object , oC_UInt_t Size )
{
    int index = -1;

    if(List_IsCorrect(List) && (Size > 0) && isaddresscorrect(Object))
    {
        int currentIndex = 0;
        for(oC_List_ElementHandle_t element = List->First ; element != NULL ; element = element->Next )
        {
            if((Size == element->Size) && (memcmp(Object,element->Object,element->Size) == 0))
            {
                index = currentIndex;
                break;
            }
            currentIndex++;
        }
    }

    return index;
}

//==========================================================================================================================================
//==========================================================================================================================================
int List_IndexOfElement( oC_List_t List , oC_List_ElementHandle_t ElementHandle )
{
    int index = -1;

    if(List_IsCorrect(List))
    {
        int currentIndex = 0;
        for(oC_List_ElementHandle_t element = List->First ; element != NULL ; element = element->Next )
        {
            if(ElementHandle == element)
            {
                index = currentIndex;
                break;
            }
            currentIndex++;
        }
    }

    return index;
}

//==========================================================================================================================================
//==========================================================================================================================================
oC_List_ElementHandle_t List_ElementHandleOf( oC_List_t List , void * Object , oC_UInt_t Size )
{
    oC_List_ElementHandle_t handle = NULL;

    if(List_IsCorrect(List) && (Size > 0) && isaddresscorrect(Object))
    {
        for(oC_List_ElementHandle_t element = List->First ; element != NULL ; element = element->Next )
        {
            if((Size == element->Size) && (memcmp(Object,element->Object,element->Size) == 0))
            {
                handle = element;
                break;
            }
        }
    }

    return handle;
}

//==========================================================================================================================================
//==========================================================================================================================================
oC_List_ElementHandle_t List_ElementOfIndex( oC_List_t List , int Index )
{
    oC_List_ElementHandle_t handle = NULL;

    if(List_IsCorrect(List) && (Index >= 0))
    {
        int currentIndex = 0;
        for(oC_List_ElementHandle_t element = List->First ; element != NULL ; element = element->Next , currentIndex++ )
        {
            if(currentIndex == Index)
            {
                handle = element;
                break;
            }
        }
    }

    return handle;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_PushBack( oC_List_t List , const void * Object , oC_UInt_t Size , Allocator_t Allocator)
{
    bool pushed = false;

    if(List_IsCorrect(List) && (Size > 0) && isaddresscorrect(Object))
    {
        oC_List_ElementHandle_t element = List_NewElement(Object,Size,Allocator);

        if(element)
        {
            if(List->Last && List->First)
            {
                element->Previous   = List->Last;
                element->Next       = NULL;
                List->Last->Next    = element;
                List->Last          = element;
            }
            else
            {
                PushToEmpty(List,element);
            }

            pushed = true;
            List->Count++;
        }
        else
        {
            oC_SaveError("List - push back element error" , oC_ErrorCode_AllocationError);
        }
    }

    return pushed;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_PushFront( oC_List_t List , const void * Object , oC_UInt_t Size , Allocator_t Allocator)
{
    bool pushed = false;

    if(List_IsCorrect(List) && (Size > 0) && isaddresscorrect(Object))
    {
        oC_List_ElementHandle_t element = List_NewElement(Object,Size,Allocator);

        if(element)
        {
            if(List->Last && List->First)
            {
                element->Next         = List->First;
                element->Previous     = NULL;
                List->First->Previous = element;
                List->First           = element;
            }
            else
            {
                PushToEmpty(List,element);
            }

            pushed = true;
            List->Count++;
        }
        else
        {
            oC_SaveError("List - push front element error" , oC_ErrorCode_AllocationError);
        }
    }

    return pushed;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_InsertAfter( oC_List_t List , void * Object , oC_UInt_t Size , oC_List_ElementHandle_t ElementHandle , Allocator_t Allocator)
{
    bool inserted = false;

    if(List_IsCorrect(List) && (Size > 0) && isaddresscorrect(Object))
    {
        if(List->First == NULL && List->Last == NULL)
        {
            inserted = List_PushFront(List,Object,Size,Allocator);
        }
        else if(isram(ElementHandle)==false)
        {
            oC_SaveError("List-insert-after: ElementHandle is not in ram " , oC_ErrorCode_WrongAddress);
        }
        else if(List->Last == ElementHandle)
        {
            inserted = List_PushBack(List,Object,Size,Allocator);
        }
        else
        {
            oC_List_ElementHandle_t element = List_NewElement(Object,Size,Allocator);

            if(element)
            {
                element->Next       = ElementHandle->Next;
                element->Previous   = ElementHandle;

                ElementHandle->Next->Previous   = element;
                ElementHandle->Next             = element;

                inserted = true;
                List->Count++;
            }
            else
            {
                oC_SaveError("List - insert after element error" , oC_ErrorCode_AllocationError);
            }
        }
    }

    return inserted;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_InsertBefore( oC_List_t List , void * Object , oC_UInt_t Size , oC_List_ElementHandle_t ElementHandle , Allocator_t Allocator)
{
    bool inserted = false;

    if(List_IsCorrect(List) && (Size > 0) && isaddresscorrect(Object))
    {
        if( (List->First == ElementHandle) || (List->First == NULL && List->Last == NULL))
        {
            inserted = List_PushFront(List,Object,Size,Allocator);
        }
        else if(isram(ElementHandle)==false)
        {
            oC_SaveError("List-insert-after: ElementHandle is not in ram " , oC_ErrorCode_WrongAddress);
        }
        else
        {
            oC_List_ElementHandle_t element = List_NewElement(Object,Size,Allocator);

            if(element)
            {
                element->Next       = ElementHandle;
                element->Previous   = ElementHandle->Previous;

                ElementHandle->Previous->Next   = element;
                ElementHandle->Previous         = element;

                inserted = true;
                List->Count++;
            }
            else
            {
                oC_SaveError("List - insert before element error" , oC_ErrorCode_AllocationError);
            }
        }
    }

    return inserted;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_Replace( oC_List_t List , void * Object , oC_UInt_t Size , oC_List_ElementHandle_t ElementHandle , Allocator_t Allocator , AllocationFlags_t Flags )
{
    bool replaced = false;

    if(List_IsCorrect(List) && (Size > 0) && isram(ElementHandle) && isaddresscorrect(Object))
    {
        if( List->First == NULL && List->Last == NULL )
        {
            replaced = false;
        }
        else
        {
            if(!kfree(ElementHandle->Object,Flags))
            {
                oC_SaveError("List replace" , oC_ErrorCode_ReleaseError);
            }

            ElementHandle->Object = kmalloc(Size,Allocator,Flags);

            if(ElementHandle->Object)
            {
                memcpy(ElementHandle->Object,Object,Size);
                ElementHandle->Size = Size;
                replaced            = true;
            }

        }
    }

    return replaced;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_Remove( oC_List_t List , oC_List_ElementHandle_t ElementHandle )
{
    bool removed = false;

    if(List_IsCorrect(List) && isram(ElementHandle) && (List->Count > 0))
    {
        if(ElementHandle == List->First)
        {
            removed = List_PopFront(List);
        }
        else if (ElementHandle == List->Last)
        {
            removed = List_PopBack(List);
        }
        else
        {
            oC_List_ElementHandle_t previous = ElementHandle->Previous;
            oC_List_ElementHandle_t next     = ElementHandle->Next;

            previous->Next = next;
            next->Previous = previous;

            removed = List_DeleteElement(ElementHandle);
        }
    }

    return removed;
}

//==========================================================================================================================================
//==========================================================================================================================================
uint32_t List_RemoveAll( oC_List_t List , void * Object , oC_UInt_t Size )
{
    uint32_t removedCount = 0;

    if(List_IsCorrect(List) && (Size > 0) && isaddresscorrect(Object))
    {
        oC_List_ElementHandle_t handle = List->First;
        oC_List_ElementHandle_t next   = handle->Next;
        while(handle != NULL)
        {
            if(Size == handle->Size && (memcmp(Object,handle->Object,Size) == 0))
            {
                if(List_Remove(List,handle))
                {
                    removedCount++;
                }
            }
            handle = next;
            next   = next->Next;
        }
    }

    return removedCount;
}

//==========================================================================================================================================
//==========================================================================================================================================
void * List_At( oC_List_t List , oC_List_ElementHandle_t ElementHandle , void * outObject , oC_UInt_t Size )
{
    void * Object = NULL;

    if(List_IsCorrect(List) && isram(ElementHandle) && isram(outObject))
    {
        if(Size == ElementHandle->Size)
        {
            Object = outObject;
            memcpy(outObject,ElementHandle->Object,Size);
        }
    }

    return Object;
}

//==========================================================================================================================================
//==========================================================================================================================================
void * List_AtWithDefault( oC_List_t List , void * DefaultObject , oC_UInt_t DefaultSize , oC_List_ElementHandle_t ElementHandle , void * outObject , oC_UInt_t Size )
{
    void * AtObject = DefaultObject;

    if(isram(outObject) && isaddresscorrect(DefaultObject))
    {
        if(Size == DefaultSize)
        {
            memcpy(outObject,DefaultObject,Size);
        }

        if(List_IsCorrect(List) && isram(ElementHandle))
        {
            if(Size == ElementHandle->Size)
            {
                AtObject = outObject;
                memcpy(outObject,ElementHandle->Object,Size);
            }
        }
    }

    return AtObject;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_Move( oC_List_t List , oC_List_ElementHandle_t From , oC_List_ElementHandle_t To , Allocator_t Allocator )
{
    bool moved = false;

//    if(List_IsCorrect(List) && isram(From) && isram(To))
//    {
//        oC_UInt_t size = From->Size;
//        void * object  = List_TakeAt(List,From);
//
//        moved = List_InsertAfter(List,object,size,To,Allocator);
//    }

    return moved;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_PopBack( oC_List_t List )
{
    bool poped = false;

    if(List_IsCorrect(List) && (List->Last != NULL))
    {
        oC_List_ElementHandle_t handle = List->Last;

        List->Last = handle->Previous;

        if(List->Last == NULL)
        {
            List->First = NULL;
        }
        else
        {
            List->Last->Next = NULL;
        }

        poped = List_DeleteElement(handle);
    }

    return poped;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_PopFront( oC_List_t List )
{
    bool poped = false;

    if(List_IsCorrect(List) && (List->Last != NULL))
    {
        oC_List_ElementHandle_t handle = List->First;

        List->First = handle->Next;

        if(List->First == NULL)
        {
            List->Last = NULL;
        }
        else
        {
            List->First->Previous = NULL;
        }

        poped = List_DeleteElement(handle);
    }

    return poped;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_Swap( oC_List_t List , oC_List_ElementHandle_t I , oC_List_ElementHandle_t J )
{
    bool swaped = false;

    if(List_IsCorrect(List) && isram(I) && isram(J))
    {
        void *      object = I->Object;
        oC_UInt_t   size   = I->Size;

        I->Object = J->Object;
        I->Size   = J->Size;

        J->Object = object;
        J->Size   = size;

        swaped = true;
    }

    return swaped;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_TakeAt( oC_List_t List , oC_List_ElementHandle_t ElementHandle , void * outObject , oC_UInt_t Size )
{
    bool result = false;

    if(List_IsCorrect(List) && isram(ElementHandle) && ElementHandle->Size == Size && isram(outObject))
    {
        if(ElementHandle == List->First)
        {
            result = List_TakeFirst(List,outObject,Size);
        }
        else if (ElementHandle == List->Last)
        {
            result = List_TakeLast(List,outObject,Size);
        }
        else
        {
            result = true;

            memcpy(outObject,ElementHandle->Object,Size);

            oC_List_ElementHandle_t previous = ElementHandle->Previous;
            oC_List_ElementHandle_t next     = ElementHandle->Next;

            if(previous)
            {
                previous->Next = next;
            }

            if(next)
            {
                next->Previous = previous;
            }

            if(!List_DeleteElement(ElementHandle))
            {
                oC_SaveError("List , takeAt, delete element" , oC_ErrorCode_ReleaseError);
            }
        }
    }

    return result;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_TakeFirst( oC_List_t List , void * outObject , oC_UInt_t Size )
{
    bool result = false;

    if(List_IsCorrect(List) && List->First != NULL && List->First->Size == Size && isram(outObject))
    {
        oC_List_ElementHandle_t first = List->First;

        result      = true;

        memcpy(outObject,List->First->Object,Size);

        List->First = List->First->Next;

        if(List->Last == first)
        {
            List->Last = List->First;
        }

        if(List->First != NULL)
        {
            List->First->Previous = NULL;
        }

        if(!List_DeleteElement(first))
        {
            oC_SaveError("List , take first, delete element" , oC_ErrorCode_ReleaseError);
        }
    }

    return result;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_TakeLast( oC_List_t List , void * outObject , oC_UInt_t Size )
{
    bool result = false;

    if(List_IsCorrect(List) && List->Last != NULL && isram(outObject))
    {
        oC_List_ElementHandle_t last = List->Last;

        result      = true;

        memcpy(outObject,List->Last->Object,Size);

        List->Last  = List->Last->Previous;

        if(List->First == last)
        {
            List->First = List->Last;
        }

        if(List->Last != NULL)
        {
            List->Last->Next = NULL;
        }

        if(!List_DeleteElement(last))
        {
            oC_SaveError("List , take last, delete element" , oC_ErrorCode_ReleaseError);
        }
    }

    return result;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_Verify( oC_List_t List )
{
    bool correct = false;

    if(List_IsCorrect(List))
    {
       uint32_t count = 0;

       for(oC_List_ElementHandle_t element = List->First ; isram(element) && element != NULL ; element = element->Next )
       {
           count++;
       }

       correct = count == List->Count;
    }

    return correct;
}

//==========================================================================================================================================
//==========================================================================================================================================
bool List_Repair( oC_List_t List , void * SavedListAddress , uint32_t MaximumNumberOfObjects )
{
    bool repaired = false;

    /* Check list pointer first and try to restore it if possible */
    if(List_IsCorrect(List) == false)
    {
        if(isram(SavedListAddress) && List != SavedListAddress)
        {
            List = SavedListAddress;
        }
        if(List_IsCorrect(List) == false && isram(List) && SavedListAddress == List)
        {
            List->ObjectControl = oC_CountObjectControl(SavedListAddress,oC_ObjectId_List);
        }
    }

    /* Now, if we repaired list address, we can try to restore elements inside */
    if(List_IsCorrect(List))
    {
        uint32_t                countFromHead       = 0;
        uint32_t                countFromTail       = 0;
        oC_List_ElementHandle_t lastElementFromHead = NULL;
        oC_List_ElementHandle_t firstElementFromTail= NULL;
        bool                    repairFromHead      = false;
        bool                    repairFromTail      = false;

        for(oC_List_ElementHandle_t element = List->First ; isram(element) && element != NULL ; element = element->Next )
        {
            lastElementFromHead = element;
            countFromHead++;
        }

        for(oC_List_ElementHandle_t element = List->Last; isram(element) && element != NULL ; element = element->Previous )
        {
            firstElementFromTail = element;
            countFromTail++;
        }

        if(List->Count < MaximumNumberOfObjects)
        {
            if( countFromHead == List->Count && isram(lastElementFromHead))
            {
                repairFromHead = true;
            }
            else if( countFromTail == List->Count && isram(lastElementFromHead))
            {
                repairFromTail = true;
            }
            else
            {
                if(countFromHead < MaximumNumberOfObjects)
                {
                    repairFromHead = true;
                }
                if(countFromTail < MaximumNumberOfObjects)
                {
                    repairFromTail = true;
                }
            }
        }
        else
        {
            repairFromHead = true;
            repairFromTail = true;
        }

        if(repairFromHead)
        {
            oC_List_ElementHandle_t previous = NULL;

            countFromHead = 0;

            List->Last = lastElementFromHead;

            for(oC_List_ElementHandle_t element = List->First; isram(element) && element != NULL ; element = element->Next )
            {
                element->Previous = previous;
                previous          = element;
                countFromHead++;
            }
        }

        if(repairFromTail)
        {
            oC_List_ElementHandle_t next = NULL;

            countFromTail = 0;

            List->First = firstElementFromTail;

            for(oC_List_ElementHandle_t element = List->Last; isram(element) && element != NULL ; element = element->Previous )
            {
                element->Next     = next;
                next              = element;
                countFromTail++;
            }
        }

        if(repairFromHead)
        {
            oC_List_ElementHandle_t previous = NULL;

            countFromHead = 0;

            List->Last = lastElementFromHead;

            for(oC_List_ElementHandle_t element = List->First; isram(element) && element != NULL ; element = element->Next )
            {
                element->Previous = previous;
                previous          = element;
                countFromHead++;
            }
        }

        if(countFromHead == countFromTail && countFromHead < MaximumNumberOfObjects)
        {
            List->Count = countFromHead;
            repaired    = true;
        }
    }

    return repaired;
}

#undef  _________________________________________INTERFACE_SECTION__________________________________________________________________________

#define _________________________________________LOCAL_FUNCTIONS_SECTION____________________________________________________________________

//==========================================================================================================================================
//==========================================================================================================================================
static void PushToEmpty( oC_List_t List , oC_List_ElementHandle_t Handle )
{
    List->Last = Handle;
    List->First= Handle;
}

#undef  _________________________________________LOCAL_FUNCTIONS_SECTION____________________________________________________________________