tor-browser

List.h (21312B)

---

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

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