diff options
Diffstat (limited to '')
-rw-r--r-- | js/src/zydis/Zycore/List.h | 573 |
1 files changed, 573 insertions, 0 deletions
diff --git a/js/src/zydis/Zycore/List.h b/js/src/zydis/Zycore/List.h new file mode 100644 index 0000000000..0de13dc62f --- /dev/null +++ b/js/src/zydis/Zycore/List.h @@ -0,0 +1,573 @@ +/*************************************************************************************************** + + 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. + +***************************************************************************************************/ + +/** + * @file + * Implements a doubly linked list. + */ + +#ifndef ZYCORE_LIST_H +#define ZYCORE_LIST_H + +#include "zydis/Zycore/Allocator.h" +#include "zydis/Zycore/Object.h" +#include "zydis/Zycore/Status.h" +#include "zydis/Zycore/Types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* ============================================================================================== */ +/* Enums and types */ +/* ============================================================================================== */ + +/** + * Defines the `ZyanListNode` struct. + * + * All fields in this struct should be considered as "private". Any changes may lead to unexpected + * behavior. + */ +typedef struct ZyanListNode_ +{ + /** + * A pointer to the previous list node. + */ + struct ZyanListNode_* prev; + /** + * A pointer to the next list node. + */ + struct ZyanListNode_* next; +} ZyanListNode; + +/** + * Defines the `ZyanList` struct. + * + * All fields in this struct should be considered as "private". Any changes may lead to unexpected + * behavior. + */ +typedef struct ZyanList_ +{ + /** + * The memory allocator. + */ + ZyanAllocator* allocator; + /** + * The current number of elements in the list. + */ + ZyanUSize size; + /** + * The size of a single element in bytes. + */ + ZyanUSize element_size; + /** + * The element destructor callback. + */ + ZyanMemberProcedure destructor; + /** + * The head node. + */ + ZyanListNode* head; + /** + * The tail node. + */ + ZyanListNode* tail; + /** + * The data buffer. + * + * Only used for instances created by `ZyanListInitCustomBuffer`. + */ + void* buffer; + /** + * The data buffer capacity (number of bytes). + * + * Only used for instances created by `ZyanListInitCustomBuffer`. + */ + ZyanUSize capacity; + /** + * The first unused node. + * + * When removing a node, the first-unused value is updated to point at the removed node and the + * next node of the removed node will be updated to point at the old first-unused node. + * + * When appending the memory of the first unused-node is recycled to store the new node. The + * value of the first-unused node is then updated to point at the reused nodes next node. + * + * If the first-unused value is `ZYAN_NULL`, any new node will be "allocated" behind the tail + * node (if there is enough space left in the fixed size buffer). + * + * Only used for instances created by `ZyanListInitCustomBuffer`. + */ + ZyanListNode* first_unused; +} ZyanList; + +/* ============================================================================================== */ +/* Macros */ +/* ============================================================================================== */ + +/* ---------------------------------------------------------------------------------------------- */ +/* General */ +/* ---------------------------------------------------------------------------------------------- */ + +/** + * Defines an uninitialized `ZyanList` instance. + */ +#define ZYAN_LIST_INITIALIZER \ + { \ + /* allocator */ ZYAN_NULL, \ + /* size */ 0, \ + /* element_size */ 0, \ + /* head */ ZYAN_NULL, \ + /* destructor */ ZYAN_NULL, \ + /* tail */ ZYAN_NULL, \ + /* buffer */ ZYAN_NULL, \ + /* capacity */ 0, \ + /* first_unused */ ZYAN_NULL \ + } + +/* ---------------------------------------------------------------------------------------------- */ +/* Helper macros */ +/* ---------------------------------------------------------------------------------------------- */ + +/** + * Returns the data value of the given `node`. + * + * @param type The desired value type. + * @param node A pointer to the `ZyanListNode` struct. + * + * @result The data value of the given `node`. + * + * Note that this function is unsafe and might dereference a null-pointer. + */ +#ifdef __cplusplus +#define ZYAN_LIST_GET(type, node) \ + (*reinterpret_cast<const type*>(ZyanListGetNodeData(node))) +#else +#define ZYAN_LIST_GET(type, node) \ + (*(const type*)ZyanListGetNodeData(node)) +#endif + +/* ---------------------------------------------------------------------------------------------- */ + +/* ============================================================================================== */ +/* Exported functions */ +/* ============================================================================================== */ + +/* ---------------------------------------------------------------------------------------------- */ +/* Constructor and destructor */ +/* ---------------------------------------------------------------------------------------------- */ + +#ifndef ZYAN_NO_LIBC + +/** + * Initializes the given `ZyanList` instance. + * + * @param list A pointer to the `ZyanList` instance. + * @param element_size The size of a single element in bytes. + * @param destructor A destructor callback that is invoked every time an item is deleted, or + * `ZYAN_NULL` if not needed. + * + * @return A zyan status code. + * + * The memory for the list elements is dynamically allocated by the default allocator. + * + * Finalization with `ZyanListDestroy` is required for all instances created by this function. + */ +ZYCORE_EXPORT ZYAN_REQUIRES_LIBC ZyanStatus ZyanListInit(ZyanList* list, ZyanUSize element_size, + ZyanMemberProcedure destructor); + +#endif // ZYAN_NO_LIBC + +/** + * Initializes the given `ZyanList` instance and sets a custom `allocator`. + * + * @param list A pointer to the `ZyanList` instance. + * @param element_size The size of a single element in bytes. + * @param destructor A destructor callback that is invoked every time an item is deleted, or + * `ZYAN_NULL` if not needed. + * @param allocator A pointer to a `ZyanAllocator` instance. + * + * @return A zyan status code. + * + * Finalization with `ZyanListDestroy` is required for all instances created by this function. + */ +ZYCORE_EXPORT ZyanStatus ZyanListInitEx(ZyanList* list, ZyanUSize element_size, + ZyanMemberProcedure destructor, ZyanAllocator* allocator); + +/** + * Initializes the given `ZyanList` instance and configures it to use a custom user + * defined buffer with a fixed size. + * + * @param list A pointer to the `ZyanList` instance. + * @param element_size The size of a single element in bytes. + * @param destructor A destructor callback that is invoked every time an item is deleted, or + * `ZYAN_NULL` if not needed. + * @param buffer A pointer to the buffer that is used as storage for the elements. + * @param capacity The maximum capacity (number of bytes) of the buffer including the + * space required for the list-nodes. + * + * @return A zyan status code. + * + * The buffer capacity required to store `n` elements of type `T` is be calculated by: + * `size = n * sizeof(ZyanListNode) + n * sizeof(T)` + * + * Finalization is not required for instances created by this function. + */ +ZYCORE_EXPORT ZyanStatus ZyanListInitCustomBuffer(ZyanList* list, ZyanUSize element_size, + ZyanMemberProcedure destructor, void* buffer, ZyanUSize capacity); + +/** + * Destroys the given `ZyanList` instance. + * + * @param list A pointer to the `ZyanList` instance. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListDestroy(ZyanList* list); + +/* ---------------------------------------------------------------------------------------------- */ +/* Duplication */ +/* ---------------------------------------------------------------------------------------------- */ + +#ifndef ZYAN_NO_LIBC + +/** + * Initializes a new `ZyanList` instance by duplicating an existing list. + * + * @param destination A pointer to the (uninitialized) destination `ZyanList` instance. + * @param source A pointer to the source list. + * + * @return A zyan status code. + * + * The memory for the list is dynamically allocated by the default allocator. + * + * Finalization with `ZyanListDestroy` is required for all instances created by this function. + */ +ZYCORE_EXPORT ZYAN_REQUIRES_LIBC ZyanStatus ZyanListDuplicate(ZyanList* destination, + const ZyanList* source); + +#endif // ZYAN_NO_LIBC + +/** + * Initializes a new `ZyanList` instance by duplicating an existing list and sets a + * custom `allocator`. + * + * @param destination A pointer to the (uninitialized) destination `ZyanList` instance. + * @param source A pointer to the source list. + * @param allocator A pointer to a `ZyanAllocator` instance. + * + * @return A zyan status code. + + * Finalization with `ZyanListDestroy` is required for all instances created by this function. + */ +ZYCORE_EXPORT ZyanStatus ZyanListDuplicateEx(ZyanList* destination, const ZyanList* source, + ZyanAllocator* allocator); + +/** + * Initializes a new `ZyanList` instance by duplicating an existing list and + * configures it to use a custom user defined buffer with a fixed size. + * + * @param destination A pointer to the (uninitialized) destination `ZyanList` instance. + * @param source A pointer to the source list. + * @param buffer A pointer to the buffer that is used as storage for the elements. + * @param capacity The maximum capacity (number of bytes) of the buffer including the + * space required for the list-nodes. + + * This function will fail, if the capacity of the buffer is not sufficient + * to store all elements of the source list. + * + * @return A zyan status code. + * + * The buffer capacity required to store `n` elements of type `T` is be calculated by: + * `size = n * sizeof(ZyanListNode) + n * sizeof(T)` + * + * Finalization is not required for instances created by this function. + */ +ZYCORE_EXPORT ZyanStatus ZyanListDuplicateCustomBuffer(ZyanList* destination, + const ZyanList* source, void* buffer, ZyanUSize capacity); + +/* ---------------------------------------------------------------------------------------------- */ +/* Item access */ +/* ---------------------------------------------------------------------------------------------- */ + +/** + * Returns a pointer to the first `ZyanListNode` struct of the given list. + * + * @param list A pointer to the `ZyanList` instance. + * @param node Receives a pointer to the first `ZyanListNode` struct of the list. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListGetHeadNode(const ZyanList* list, const ZyanListNode** node); + +/** + * Returns a pointer to the last `ZyanListNode` struct of the given list. + * + * @param list A pointer to the `ZyanList` instance. + * @param node Receives a pointer to the last `ZyanListNode` struct of the list. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListGetTailNode(const ZyanList* list, const ZyanListNode** node); + +/** + * Receives a pointer to the previous `ZyanListNode` struct linked to the passed one. + * + * @param node Receives a pointer to the previous `ZyanListNode` struct linked to the passed + * one. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListGetPrevNode(const ZyanListNode** node); + +/** + * Receives a pointer to the next `ZyanListNode` struct linked to the passed one. + * + * @param node Receives a pointer to the next `ZyanListNode` struct linked to the passed one. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListGetNextNode(const ZyanListNode** node); + +/** + * Returns a constant pointer to the data of the given `node`. + * + * @param node A pointer to the `ZyanListNode` struct. + * + * @return A constant pointer to the the data of the given `node` or `ZYAN_NULL`, if an error + * occured. + * + * Take a look at `ZyanListGetNodeDataEx`, if you need a function that returns a zyan status code. + */ +ZYCORE_EXPORT const void* ZyanListGetNodeData(const ZyanListNode* node); + +/** + * Returns a constant pointer to the data of the given `node`.. + * + * @param node A pointer to the `ZyanListNode` struct. + * @param value Receives a constant pointer to the data of the given `node`. + * + * Take a look at `ZyanListGetNodeData`, if you need a function that directly returns a pointer. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListGetNodeDataEx(const ZyanListNode* node, const void** value); + +/** + * Returns a mutable pointer to the data of the given `node`. + * + * @param node A pointer to the `ZyanListNode` struct. + * + * @return A mutable pointer to the the data of the given `node` or `ZYAN_NULL`, if an error + * occured. + * + * Take a look at `ZyanListGetPointerMutableEx` instead, if you need a function that returns a + * zyan status code. + */ +ZYCORE_EXPORT void* ZyanListGetNodeDataMutable(const ZyanListNode* node); + +/** + * Returns a mutable pointer to the data of the given `node`.. + * + * @param node A pointer to the `ZyanListNode` struct. + * @param value Receives a mutable pointer to the data of the given `node`. + * + * Take a look at `ZyanListGetNodeDataMutable`, if you need a function that directly returns a + * pointer. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListGetNodeDataMutableEx(const ZyanListNode* node, void** value); + +/** + * Assigns a new data value to the given `node`. + * + * @param list A pointer to the `ZyanList` instance. + * @param node A pointer to the `ZyanListNode` struct. + * @param value The value to assign. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListSetNodeData(const ZyanList* list, const ZyanListNode* node, + const void* value); + +/* ---------------------------------------------------------------------------------------------- */ +/* Insertion */ +/* ---------------------------------------------------------------------------------------------- */ + +/** + * Adds a new `item` to the end of the list. + * + * @param list A pointer to the `ZyanList` instance. + * @param item A pointer to the item to add. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListPushBack(ZyanList* list, const void* item); + +/** + * Adds a new `item` to the beginning of the list. + * + * @param list A pointer to the `ZyanList` instance. + * @param item A pointer to the item to add. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListPushFront(ZyanList* list, const void* item); + +/** + * Constructs an `item` in-place at the end of the list. + * + * @param list A pointer to the `ZyanList` instance. + * @param item Receives a pointer to the new item. + * @param constructor The constructor callback or `ZYAN_NULL`. The new item will be in + * undefined state, if no constructor was passed. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListEmplaceBack(ZyanList* list, void** item, + ZyanMemberFunction constructor); + +/** + * Constructs an `item` in-place at the beginning of the list. + * + * @param list A pointer to the `ZyanList` instance. + * @param item Receives a pointer to the new item. + * @param constructor The constructor callback or `ZYAN_NULL`. The new item will be in + * undefined state, if no constructor was passed. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListEmplaceFront(ZyanList* list, void** item, + ZyanMemberFunction constructor); + +/* ---------------------------------------------------------------------------------------------- */ +/* Deletion */ +/* ---------------------------------------------------------------------------------------------- */ + +/** + * Removes the last element of the list. + * + * @param list A pointer to the `ZyanList` instance. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListPopBack(ZyanList* list); + +/** + * Removes the firstelement of the list. + * + * @param list A pointer to the `ZyanList` instance. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListPopFront(ZyanList* list); + +/** + * Removes the given `node` from the list. + * + * @param list A pointer to the `ZyanList` instance. + * @param node A pointer to the `ZyanListNode` struct. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListRemove(ZyanList* list, const ZyanListNode* node); + +/** + * Removes multiple nodes from the list. + * + * @param list A pointer to the `ZyanList` instance. + * @param first A pointer to the first node. + * @param last A pointer to the last node. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListRemoveRange(ZyanList* list, const ZyanListNode* first, + const ZyanListNode* last); + +/** + * Erases all elements of the list. + * + * @param list A pointer to the `ZyanList` instance. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListClear(ZyanList* list); + +/* ---------------------------------------------------------------------------------------------- */ +/* Searching */ +/* ---------------------------------------------------------------------------------------------- */ + +// TODO: + +/* ---------------------------------------------------------------------------------------------- */ +/* Memory management */ +/* ---------------------------------------------------------------------------------------------- */ + +/** + * Resizes the given `ZyanList` instance. + * + * @param list A pointer to the `ZyanList` instance. + * @param size The new size of the list. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListResize(ZyanList* list, ZyanUSize size); + +/** + * Resizes the given `ZyanList` instance. + * + * @param list A pointer to the `ZyanList` instance. + * @param size The new size of the list. + * @param initializer A pointer to a value to be used as initializer for new items. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListResizeEx(ZyanList* list, ZyanUSize size, const void* initializer); + +/* ---------------------------------------------------------------------------------------------- */ +/* Information */ +/* ---------------------------------------------------------------------------------------------- */ + +/** + * Returns the current size of the list. + * + * @param list A pointer to the `ZyanList` instance. + * @param size Receives the size of the list. + * + * @return A zyan status code. + */ +ZYCORE_EXPORT ZyanStatus ZyanListGetSize(const ZyanList* list, ZyanUSize* size); + +/* ---------------------------------------------------------------------------------------------- */ + +/* ============================================================================================== */ + +#ifdef __cplusplus +} +#endif + +#endif /* ZYCORE_VECTOR_H */ |