diff options
Diffstat (limited to 'lst.h')
| -rw-r--r-- | lst.h | 128 |
1 files changed, 68 insertions, 60 deletions
@@ -1,4 +1,4 @@ -/* $NetBSD: lst.h,v 1.60 2020/09/02 23:33:13 rillig Exp $ */ +/* $NetBSD: lst.h,v 1.84 2020/10/28 02:43:16 rillig Exp $ */ /* * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. @@ -79,101 +79,109 @@ #define MAKE_LST_H #include <sys/param.h> +#include <stdint.h> #include <stdlib.h> /* A doubly-linked list of pointers. */ -typedef struct List *Lst; +typedef struct List List; /* A single node in the doubly-linked list. */ -typedef struct ListNode *LstNode; +typedef struct ListNode ListNode; + +struct ListNode { + ListNode *prev; /* previous node in list, or NULL */ + ListNode *next; /* next node in list, or NULL */ + union { + void *datum; /* datum associated with this element */ + const struct GNode *priv_gnode; /* alias, just for debugging */ + const char *priv_str; /* alias, just for debugging */ + }; +}; + +struct List { + ListNode *first; /* first node in list */ + ListNode *last; /* last node in list */ +}; -/* Copy a node, usually by allocating a copy of the given object. - * For reference-counted objects, the original object may need to be - * modified, therefore the parameter is not const. */ -typedef void *LstCopyProc(void *); /* Free the datum of a node, called before freeing the node itself. */ typedef void LstFreeProc(void *); -/* Return TRUE if the datum matches the args, for Lst_Find. */ -typedef Boolean LstFindProc(const void *datum, const void *args); -/* An action for Lst_ForEach. */ -typedef int LstActionProc(void *datum, void *args); +/* An action for Lst_ForEachUntil and Lst_ForEachUntilConcurrent. */ +typedef int LstActionUntilProc(void *datum, void *args); /* Create or destroy a list */ /* Create a new list. */ -Lst Lst_Init(void); -/* Duplicate an existing list. */ -Lst Lst_Copy(Lst, LstCopyProc); +List *Lst_New(void); /* Free the list, leaving the node data unmodified. */ -void Lst_Free(Lst); +void Lst_Free(List *); /* Free the list, freeing the node data using the given function. */ -void Lst_Destroy(Lst, LstFreeProc); +void Lst_Destroy(List *, LstFreeProc); /* Get information about a list */ -Boolean Lst_IsEmpty(Lst); -/* Return the first node of the list, or NULL. */ -LstNode Lst_First(Lst); -/* Return the last node of the list, or NULL. */ -LstNode Lst_Last(Lst); -/* Find the first node for which the function returns TRUE, or NULL. */ -LstNode Lst_Find(Lst, LstFindProc, const void *); -/* Find the first node for which the function returns TRUE, or NULL. - * The search starts at the given node, towards the end of the list. */ -LstNode Lst_FindFrom(Lst, LstNode, LstFindProc, const void *); +static inline MAKE_ATTR_UNUSED Boolean +Lst_IsEmpty(List *list) { return list->first == NULL; } + /* Find the first node that contains the given datum, or NULL. */ -LstNode Lst_FindDatum(Lst, const void *); +ListNode *Lst_FindDatum(List *, const void *); /* Modify a list */ /* Insert a datum before the given node. */ -void Lst_InsertBefore(Lst, LstNode, void *); +void Lst_InsertBefore(List *, ListNode *, void *); /* Place a datum at the front of the list. */ -void Lst_Prepend(Lst, void *); +void Lst_Prepend(List *, void *); /* Place a datum at the end of the list. */ -void Lst_Append(Lst, void *); +void Lst_Append(List *, void *); /* Remove the node from the list. */ -void Lst_Remove(Lst, LstNode); -void Lst_PrependAll(Lst, Lst); -void Lst_AppendAll(Lst, Lst); -void Lst_MoveAll(Lst, Lst); +void Lst_Remove(List *, ListNode *); +void Lst_PrependAll(List *, List *); +void Lst_AppendAll(List *, List *); +void Lst_MoveAll(List *, List *); /* Node-specific functions */ -/* Return the successor of the node, or NULL. */ -LstNode LstNode_Next(LstNode); -/* Return the predecessor of the node, or NULL. */ -LstNode LstNode_Prev(LstNode); -/* Return the datum of the node. Usually not NULL. */ -void *LstNode_Datum(LstNode); /* Replace the value of the node. */ -void LstNode_Set(LstNode, void *); +void LstNode_Set(ListNode *, void *); /* Set the value of the node to NULL. Having NULL in a list is unusual. */ -void LstNode_SetNull(LstNode); +void LstNode_SetNull(ListNode *); /* Iterating over a list, using a callback function */ -/* Apply a function to each datum of the list, until the callback function - * returns non-zero. */ -int Lst_ForEach(Lst, LstActionProc, void *); -/* Apply a function to each datum of the list, starting at the node, - * until the callback function returns non-zero. */ -int Lst_ForEachFrom(Lst, LstNode, LstActionProc, void *); - -/* Iterating over a list while keeping track of the current node and possible - * concurrent modifications */ - -/* Start iterating the list. */ -void Lst_Open(Lst); -/* Return the next node, or NULL. */ -LstNode Lst_Next(Lst); -/* Finish iterating the list. */ -void Lst_Close(Lst); +/* Run the action for each datum of the list, until the action returns + * non-zero. + * + * During this iteration, the list must not be modified structurally. */ +int Lst_ForEachUntil(List *, LstActionUntilProc, void *); /* Using the list as a queue */ /* Add a datum at the tail of the queue. */ -void Lst_Enqueue(Lst, void *); +void Lst_Enqueue(List *, void *); /* Remove the head node of the queue and return its datum. */ -void *Lst_Dequeue(Lst); +void *Lst_Dequeue(List *); + +/* A vector is an ordered collection of items, allowing for fast indexed + * access. */ +typedef struct Vector { + void *items; /* memory holding the items */ + size_t itemSize; /* size of a single item in bytes */ + size_t len; /* number of actually usable elements */ + size_t priv_cap; /* capacity */ +} Vector; + +void Vector_Init(Vector *, size_t); + +/* Return the pointer to the given item in the vector. + * The returned data is valid until the next modifying operation. */ +static inline MAKE_ATTR_UNUSED void * +Vector_Get(Vector *v, size_t i) +{ + unsigned char *items = v->items; + return items + i * v->itemSize; +} + +void *Vector_Push(Vector *); +void *Vector_Pop(Vector *); +void Vector_Done(Vector *); #endif /* MAKE_LST_H */ |