diff options
Diffstat (limited to 'js/src/zydis/Zycore/List.c')
| -rw-r--r-- | js/src/zydis/Zycore/List.c | 673 |
1 files changed, 673 insertions, 0 deletions
diff --git a/js/src/zydis/Zycore/List.c b/js/src/zydis/Zycore/List.c new file mode 100644 index 0000000000..8e4f9f96b2 --- /dev/null +++ b/js/src/zydis/Zycore/List.c @@ -0,0 +1,673 @@ +/*************************************************************************************************** + + 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 "zydis/Zycore/LibC.h" +#include "zydis/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; +} + +/* ---------------------------------------------------------------------------------------------- */ + +/* ============================================================================================== */ |