xref: /haiku/src/libs/zydis/Zycore/List.c (revision 1003e004e6c97eb60657a98928dd334e141c59ee)

/***************************************************************************************************

  Zyan Core Library (Zycore-C)

  Original Author : Florian Bernd

 * 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.

***************************************************************************************************/

#include <Zycore/LibC.h>
#include <Zycore/List.h>

/* ============================================================================================== */
/* Internal macros                                                                                */
/* ============================================================================================== */

/**
 * Returns a pointer to the data of the given `node`.
 *
 * @param   node    A pointer to the `ZyanNodeData` struct.
 *
 * @return  A pointer to the data of the given `node`.
 */
#define ZYCORE_LIST_GET_NODE_DATA(node) \
    ((void*)(node + 1))

/* ============================================================================================== */
/* Internal functions                                                                             */
/* ============================================================================================== */

/* ---------------------------------------------------------------------------------------------- */
/* Helper functions                                                                               */
/* ---------------------------------------------------------------------------------------------- */

/**
 * Allocates memory for a new list node.
 *
 * @param   list    A pointer to the `ZyanList` instance.
 * @param   node    Receives a pointer to the new `ZyanListNode` struct.
 *
 * @return  A zyan status code.
 */
static ZyanStatus ZyanListAllocateNode(ZyanList* list, ZyanListNode** node)
{
    ZYAN_ASSERT(list);
    ZYAN_ASSERT(node);

    const ZyanBool is_dynamic = (list->allocator != ZYAN_NULL);
    if (is_dynamic)
    {
        ZYAN_ASSERT(list->allocator->allocate);
        ZYAN_CHECK(list->allocator->allocate(list->allocator, (void**)node,
            sizeof(ZyanListNode) + list->element_size, 1));
    } else
    {
        if (list->first_unused)
        {
            *node = list->first_unused;
            list->first_unused = (*node)->next;
        } else
        {
            const ZyanUSize size = list->size * (sizeof(ZyanListNode) + list->element_size);
            if (size + (sizeof(ZyanListNode) + list->element_size) > list->capacity)
            {
                return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE;
            }

            *node = (ZyanListNode*)((ZyanU8*)list->buffer + size);
        }
    }

    return ZYAN_STATUS_SUCCESS;
}

/**
 * Frees memory of a node.
 *
 * @param   list    A pointer to the `ZyanList` instance.
 * @param   node    A pointer to the `ZyanListNode` struct.
 *
 * @return  A zyan status code.
 */
static ZyanStatus ZyanListDeallocateNode(ZyanList* list, ZyanListNode* node)
{
    ZYAN_ASSERT(list);
    ZYAN_ASSERT(node);

    const ZyanBool is_dynamic = (list->allocator != ZYAN_NULL);
    if (is_dynamic)
    {
        ZYAN_ASSERT(list->allocator->deallocate);
        ZYAN_CHECK(list->allocator->deallocate(list->allocator, (void*)node,
            sizeof(ZyanListNode) + list->element_size, 1));
    } else
    {
        node->next = list->first_unused;
        list->first_unused = node;
    }

    return ZYAN_STATUS_SUCCESS;
}

/* ---------------------------------------------------------------------------------------------- */

/* ============================================================================================== */
/* Exported functions                                                                             */
/* ============================================================================================== */

/* ---------------------------------------------------------------------------------------------- */
/* Constructor and destructor                                                                     */
/* ---------------------------------------------------------------------------------------------- */

#ifndef ZYAN_NO_LIBC

ZYAN_REQUIRES_LIBC ZyanStatus ZyanListInit(ZyanList* list, ZyanUSize element_size,
    ZyanMemberProcedure destructor)
{
    return ZyanListInitEx(list, element_size, destructor, ZyanAllocatorDefault());
}

#endif // ZYAN_NO_LIBC

ZyanStatus ZyanListInitEx(ZyanList* list, ZyanUSize element_size, ZyanMemberProcedure destructor,
    ZyanAllocator* allocator)
{
    if (!list || !element_size || !allocator)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    list->allocator     = allocator;
    list->size          = 0;
    list->element_size  = element_size;
    list->destructor    = destructor;
    list->head          = ZYAN_NULL;
    list->tail          = ZYAN_NULL;
    list->buffer        = ZYAN_NULL;
    list->capacity      = 0;
    list->first_unused  = ZYAN_NULL;

    return ZYAN_STATUS_SUCCESS;
}

ZyanStatus ZyanListInitCustomBuffer(ZyanList* list, ZyanUSize element_size,
    ZyanMemberProcedure destructor, void* buffer, ZyanUSize capacity)
{
    if (!list || !element_size || !buffer || !capacity)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    list->allocator    = ZYAN_NULL;
    list->size         = 0;
    list->element_size = element_size;
    list->destructor   = destructor;
    list->head         = ZYAN_NULL;
    list->tail         = ZYAN_NULL;
    list->buffer       = buffer;
    list->capacity     = capacity;
    list->first_unused = ZYAN_NULL;

    return ZYAN_STATUS_SUCCESS;
}

ZyanStatus ZyanListDestroy(ZyanList* list)
{
    if (!list)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    ZYAN_ASSERT(list->element_size);

    const ZyanBool is_dynamic = (list->allocator != ZYAN_NULL);
    ZyanListNode* node = (is_dynamic || list->destructor) ? list->head : ZYAN_NULL;
    while (node)
    {
        if (list->destructor)
        {
            list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
        }

        ZyanListNode* const next = node->next;

        if (is_dynamic)
        {
            ZYAN_CHECK(list->allocator->deallocate(list->allocator, node,
                sizeof(ZyanListNode) + list->element_size, 1));
        }

        node = next;
    }

    return ZYAN_STATUS_SUCCESS;
}

/* ---------------------------------------------------------------------------------------------- */
/* Duplication                                                                                    */
/* ---------------------------------------------------------------------------------------------- */



/* ---------------------------------------------------------------------------------------------- */
/* Item access                                                                                    */
/* ---------------------------------------------------------------------------------------------- */

ZyanStatus ZyanListGetHeadNode(const ZyanList* list, const ZyanListNode** node)
{
    if (!list)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    *node = list->head;

    return ZYAN_STATUS_SUCCESS;
}

ZyanStatus ZyanListGetTailNode(const ZyanList* list, const ZyanListNode** node)
{
    if (!list)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    *node = list->tail;

    return ZYAN_STATUS_SUCCESS;
}

ZyanStatus ZyanListGetPrevNode(const ZyanListNode** node)
{
    if (!node || !*node)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    *node = (*node)->prev;

    return ZYAN_STATUS_SUCCESS;
}

ZyanStatus ZyanListGetNextNode(const ZyanListNode** node)
{
    if (!node || !*node)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    *node = (*node)->next;

    return ZYAN_STATUS_SUCCESS;
}

const void* ZyanListGetNodeData(const ZyanListNode* node)
{
    if (!node)
    {
        return ZYAN_NULL;
    }

    return (const void*)ZYCORE_LIST_GET_NODE_DATA(node);
}

ZyanStatus ZyanListGetNodeDataEx(const ZyanListNode* node, const void** value)
{
    if (!node)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    *value = (const void*)ZYCORE_LIST_GET_NODE_DATA(node);

    return ZYAN_STATUS_SUCCESS;
}

void* ZyanListGetNodeDataMutable(const ZyanListNode* node)
{
    if (!node)
    {
        return ZYAN_NULL;
    }

    return ZYCORE_LIST_GET_NODE_DATA(node);
}

ZyanStatus ZyanListGetNodeDataMutableEx(const ZyanListNode* node, void** value)
{
    if (!node)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    *value = ZYCORE_LIST_GET_NODE_DATA(node);

    return ZYAN_STATUS_SUCCESS;
}

ZyanStatus ZyanListSetNodeData(const ZyanList* list, const ZyanListNode* node, const void* value)
{
    if (!list || !node || !value)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    if (list->destructor)
    {
        list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
    }

    ZYAN_ASSERT(list->element_size);
    ZYAN_MEMCPY(ZYCORE_LIST_GET_NODE_DATA(node), value, list->element_size);

    return ZYAN_STATUS_SUCCESS;
}

/* ---------------------------------------------------------------------------------------------- */
/* Insertion                                                                                      */
/* ---------------------------------------------------------------------------------------------- */

ZyanStatus ZyanListPushBack(ZyanList* list, const void* item)
{
    if (!list || !item)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    ZyanListNode* node;
    ZYAN_CHECK(ZyanListAllocateNode(list, &node));
    node->prev = list->tail;
    node->next = ZYAN_NULL;

    ZYAN_MEMCPY(ZYCORE_LIST_GET_NODE_DATA(node), item, list->element_size);

    if (!list->head)
    {
        list->head = node;
        list->tail = node;
    } else
    {
        list->tail->next = node;
        list->tail = node;
    }
    ++list->size;

    return ZYAN_STATUS_SUCCESS;
}

ZyanStatus ZyanListPushFront(ZyanList* list, const void* item)
{
    if (!list || !item)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    ZyanListNode* node;
    ZYAN_CHECK(ZyanListAllocateNode(list, &node));
    node->prev = ZYAN_NULL;
    node->next = list->head;

    ZYAN_MEMCPY(ZYCORE_LIST_GET_NODE_DATA(node), item, list->element_size);

    if (!list->head)
    {
        list->head = node;
        list->tail = node;
    } else
    {
        list->head->prev= node;
        list->head = node;
    }
    ++list->size;

    return ZYAN_STATUS_SUCCESS;
}

ZyanStatus ZyanListEmplaceBack(ZyanList* list, void** item, ZyanMemberFunction constructor)
{
    if (!list || !item)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    ZyanListNode* node;
    ZYAN_CHECK(ZyanListAllocateNode(list, &node));
    node->prev = list->tail;
    node->next = ZYAN_NULL;

    *item = ZYCORE_LIST_GET_NODE_DATA(node);
    if (constructor)
    {
        constructor(*item);
    }

    if (!list->head)
    {
        list->head = node;
        list->tail = node;
    } else
    {
        list->tail->next = node;
        list->tail = node;
    }
    ++list->size;

    return ZYAN_STATUS_SUCCESS;
}

ZyanStatus ZyanListEmplaceFront(ZyanList* list, void** item, ZyanMemberFunction constructor)
{
    if (!list || !item)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    ZyanListNode* node;
    ZYAN_CHECK(ZyanListAllocateNode(list, &node));
    node->prev = ZYAN_NULL;
    node->next = list->head;

    *item = ZYCORE_LIST_GET_NODE_DATA(node);
    if (constructor)
    {
        constructor(*item);
    }

    if (!list->head)
    {
        list->head = node;
        list->tail = node;
    } else
    {
        list->head->prev= node;
        list->head = node;
    }
    ++list->size;

    return ZYAN_STATUS_SUCCESS;
}

/* ---------------------------------------------------------------------------------------------- */
/* Deletion                                                                                       */
/* ---------------------------------------------------------------------------------------------- */

ZyanStatus ZyanListPopBack(ZyanList* list)
{
    if (!list)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }
    if (!list->tail)
    {
        return ZYAN_STATUS_INVALID_OPERATION;
    }

    ZyanListNode* const node = list->tail;

    if (list->destructor)
    {
        list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
    }

    list->tail = node->prev;
    if (list->tail)
    {
        list->tail->next = ZYAN_NULL;
    }
    if (list->head == node)
    {
        list->head = list->tail;
    }
    --list->size;

    return ZyanListDeallocateNode(list, node);
}

ZyanStatus ZyanListPopFront(ZyanList* list)
{
    if (!list)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }
    if (!list->head)
    {
        return ZYAN_STATUS_INVALID_OPERATION;
    }

    ZyanListNode* const node = list->head;

    if (list->destructor)
    {
        list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
    }

    list->head = node->next;
    if (list->head)
    {
        list->head->prev = ZYAN_NULL;
    }
    if (list->tail == node)
    {
        list->tail = list->head;
    }
    --list->size;

    return ZyanListDeallocateNode(list, node);
}

ZyanStatus ZyanListRemove(ZyanList* list, const ZyanListNode* node)
{
    ZYAN_UNUSED(list);
    ZYAN_UNUSED(node);
    return ZYAN_STATUS_SUCCESS;
}

ZyanStatus ZyanListRemoveRange(ZyanList* list, const ZyanListNode* first, const ZyanListNode* last)
{
    ZYAN_UNUSED(list);
    ZYAN_UNUSED(first);
    ZYAN_UNUSED(last);
    return ZYAN_STATUS_SUCCESS;
}

ZyanStatus ZyanListClear(ZyanList* list)
{
    return ZyanListResizeEx(list, 0, ZYAN_NULL);
}

/* ---------------------------------------------------------------------------------------------- */
/* Searching                                                                                      */
/* ---------------------------------------------------------------------------------------------- */



/* ---------------------------------------------------------------------------------------------- */
/* Memory management                                                                              */
/* ---------------------------------------------------------------------------------------------- */

ZyanStatus ZyanListResize(ZyanList* list, ZyanUSize size)
{
    return ZyanListResizeEx(list, size, ZYAN_NULL);
}

ZyanStatus ZyanListResizeEx(ZyanList* list, ZyanUSize size, const void* initializer)
{
    if (!list)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }
    if (size == list->size)
    {
        return ZYAN_STATUS_SUCCESS;
    }

    if (size == 0)
    {
        const ZyanBool is_dynamic = (list->allocator != ZYAN_NULL);
        ZyanListNode* node = (is_dynamic || list->destructor) ? list->head : ZYAN_NULL;
        while (node)
        {
            if (list->destructor)
            {
                list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
            }

            ZyanListNode* const next = node->next;

            if (is_dynamic)
            {
                ZYAN_CHECK(list->allocator->deallocate(list->allocator, node,
                    sizeof(ZyanListNode) + list->element_size, 1));
            }

            node = next;
        }

        list->size = 0;
        list->head = 0;
        list->tail = 0;
        list->first_unused = ZYAN_NULL;

        return ZYAN_STATUS_SUCCESS;
    }

    if (size > list->size)
    {
        ZyanListNode* node;
        for (ZyanUSize i = list->size; i < size; ++i)
        {
            ZYAN_CHECK(ZyanListAllocateNode(list, &node));
            node->prev = list->tail;
            node->next = ZYAN_NULL;

            if (initializer)
            {
                ZYAN_MEMCPY(ZYCORE_LIST_GET_NODE_DATA(node), initializer, list->element_size);
            }

            if (!list->head)
            {
                list->head = node;
                list->tail = node;
            } else
            {
                list->tail->next = node;
                list->tail = node;
            }

            // `ZyanListAllocateNode` needs the list size
            ++list->size;
        }
    } else
    {
        for (ZyanUSize i = size; i < list->size; ++i)
        {
            ZyanListNode* const node = list->tail;

            if (list->destructor)
            {
                list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
            }

            list->tail = node->prev;
            if (list->tail)
            {
                list->tail->next = ZYAN_NULL;
            }

            ZYAN_CHECK(ZyanListDeallocateNode(list, node));
        }

        list->size = size;
    }

    return ZYAN_STATUS_SUCCESS;
}

/* ---------------------------------------------------------------------------------------------- */
/* Information                                                                                    */
/* ---------------------------------------------------------------------------------------------- */

ZyanStatus ZyanListGetSize(const ZyanList* list, ZyanUSize* size)
{
    if (!list)
    {
        return ZYAN_STATUS_INVALID_ARGUMENT;
    }

    *size = list->size;

    return ZYAN_STATUS_SUCCESS;
}

/* ---------------------------------------------------------------------------------------------- */

/* ============================================================================================== */