diff options
Diffstat (limited to 'lst.c')
| -rw-r--r-- | lst.c | 522 |
1 files changed, 100 insertions, 422 deletions
@@ -1,4 +1,4 @@ -/* $NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 rillig Exp $ */ +/* $NetBSD: lst.c,v 1.91 2020/10/28 02:43:16 rillig Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -32,9 +32,9 @@ * SUCH DAMAGE. */ -#ifdef HAVE_CONFIG_H -# include "config.h" -#endif +#include "make.h" + +MAKE_RCSID("$NetBSD: lst.c,v 1.91 2020/10/28 02:43:16 rillig Exp $"); #ifdef HAVE_INTTYPES_H #include <inttypes.h> @@ -42,110 +42,34 @@ #include <stdint.h> #endif -#include "make.h" - -#ifndef MAKE_NATIVE -static char rcsid[] = "$NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 rillig Exp $"; -#else -#include <sys/cdefs.h> -#ifndef lint -__RCSID("$NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 rillig Exp $"); -#endif /* not lint */ -#endif - -struct ListNode { - struct ListNode *prev; /* previous element in list */ - struct ListNode *next; /* next in list */ - uint8_t useCount; /* Count of functions using the node. - * node may not be deleted until count - * goes to 0 */ - Boolean deleted; /* List node should be removed when done */ - union { - void *datum; /* datum associated with this element */ - const GNode *gnode; /* alias, just for debugging */ - const char *str; /* alias, just for debugging */ - }; -}; - -typedef enum { - Head, Middle, Tail, Unknown -} Where; - -struct List { - LstNode first; /* first node in list */ - LstNode last; /* last node in list */ - - /* fields for sequential access */ - Boolean isOpen; /* true if list has been Lst_Open'ed */ - Where lastAccess; /* Where in the list the last access was */ - LstNode curr; /* current node, if open. NULL if - * *just* opened */ - LstNode prev; /* Previous node, if open. Used by Lst_Remove */ -}; - -/* Allocate and initialize a list node. - * - * The fields 'prev' and 'next' must be initialized by the caller. - */ -static LstNode -LstNodeNew(void *datum) +static ListNode * +LstNodeNew(ListNode *prev, ListNode *next, void *datum) { - LstNode node = bmake_malloc(sizeof *node); - node->useCount = 0; - node->deleted = FALSE; + ListNode *node = bmake_malloc(sizeof *node); + node->prev = prev; + node->next = next; node->datum = datum; return node; } -static Boolean -LstIsEmpty(Lst list) -{ - return list->first == NULL; -} - /* Create and initialize a new, empty list. */ -Lst -Lst_Init(void) +List * +Lst_New(void) { - Lst list = bmake_malloc(sizeof *list); + List *list = bmake_malloc(sizeof *list); list->first = NULL; list->last = NULL; - list->isOpen = FALSE; - list->lastAccess = Unknown; return list; } -/* Duplicate an entire list, usually by copying the datum pointers. - * If copyProc is given, that function is used to create the new datum from the - * old datum, usually by creating a copy of it. */ -Lst -Lst_Copy(Lst list, LstCopyProc copyProc) -{ - Lst newList; - LstNode node; - - assert(list != NULL); - - newList = Lst_Init(); - - for (node = list->first; node != NULL; node = node->next) { - void *datum = copyProc != NULL ? copyProc(node->datum) : node->datum; - Lst_Append(newList, datum); - } - - return newList; -} - -/* Free a list and all its nodes. The list data itself are not freed though. */ +/* Free a list and all its nodes. The node data are not freed though. */ void -Lst_Free(Lst list) +Lst_Free(List *list) { - LstNode node; - LstNode next; - - assert(list != NULL); + ListNode *node; + ListNode *next; for (node = list->first; node != NULL; node = next) { next = node->next; @@ -158,13 +82,10 @@ Lst_Free(Lst list) /* Destroy a list and free all its resources. The freeProc is called with the * datum from each node in turn before the node is freed. */ void -Lst_Destroy(Lst list, LstFreeProc freeProc) +Lst_Destroy(List *list, LstFreeProc freeProc) { - LstNode node; - LstNode next; - - assert(list != NULL); - assert(freeProc != NULL); + ListNode *node; + ListNode *next; for (node = list->first; node != NULL; node = next) { next = node->next; @@ -179,44 +100,33 @@ Lst_Destroy(Lst list, LstFreeProc freeProc) * Functions to modify a list */ -/* Insert a new node with the given piece of data before the given node in the - * given list. */ +/* Insert a new node with the datum before the given node. */ void -Lst_InsertBefore(Lst list, LstNode node, void *datum) +Lst_InsertBefore(List *list, ListNode *node, void *datum) { - LstNode newNode; + ListNode *newNode; - assert(list != NULL); - assert(!LstIsEmpty(list)); - assert(node != NULL); assert(datum != NULL); - newNode = LstNodeNew(datum); - newNode->prev = node->prev; - newNode->next = node; + newNode = LstNodeNew(node->prev, node, datum); - if (node->prev != NULL) { + if (node->prev != NULL) node->prev->next = newNode; - } node->prev = newNode; - if (node == list->first) { + if (node == list->first) list->first = newNode; - } } /* Add a piece of data at the start of the given list. */ void -Lst_Prepend(Lst list, void *datum) +Lst_Prepend(List *list, void *datum) { - LstNode node; + ListNode *node; - assert(list != NULL); assert(datum != NULL); - node = LstNodeNew(datum); - node->prev = NULL; - node->next = list->first; + node = LstNodeNew(NULL, list->first, datum); if (list->first == NULL) { list->first = node; @@ -229,16 +139,13 @@ Lst_Prepend(Lst list, void *datum) /* Add a piece of data at the end of the given list. */ void -Lst_Append(Lst list, void *datum) +Lst_Append(List *list, void *datum) { - LstNode node; + ListNode *node; - assert(list != NULL); assert(datum != NULL); - node = LstNodeNew(datum); - node->prev = list->last; - node->next = NULL; + node = LstNodeNew(list->last, NULL, datum); if (list->last == NULL) { list->first = node; @@ -252,265 +159,83 @@ Lst_Append(Lst list, void *datum) /* Remove the given node from the given list. * The datum stored in the node must be freed by the caller, if necessary. */ void -Lst_Remove(Lst list, LstNode node) +Lst_Remove(List *list, ListNode *node) { - assert(list != NULL); - assert(node != NULL); - - /* - * unlink it from the list - */ - if (node->next != NULL) { + /* unlink it from its neighbors */ + if (node->next != NULL) node->next->prev = node->prev; - } - if (node->prev != NULL) { + if (node->prev != NULL) node->prev->next = node->next; - } - /* - * if either the first or last of the list point to this node, - * adjust them accordingly - */ - if (list->first == node) { + /* unlink it from the list */ + if (list->first == node) list->first = node->next; - } - if (list->last == node) { + if (list->last == node) list->last = node->prev; - } - - /* - * Sequential access stuff. If the node we're removing is the current - * node in the list, reset the current node to the previous one. If the - * previous one was non-existent (prev == NULL), we set the - * end to be Unknown, since it is. - */ - if (list->isOpen && list->curr == node) { - list->curr = list->prev; - if (list->curr == NULL) { - list->lastAccess = Unknown; - } - } - - /* - * note that the datum is unmolested. The caller must free it as - * necessary and as expected. - */ - if (node->useCount == 0) { - free(node); - } else { - node->deleted = TRUE; - } } /* Replace the datum in the given node with the new datum. */ void -LstNode_Set(LstNode node, void *datum) +LstNode_Set(ListNode *node, void *datum) { - assert(node != NULL); assert(datum != NULL); node->datum = datum; } -/* Replace the datum in the given node to NULL. */ +/* Replace the datum in the given node to NULL. + * Having NULL values in a list is unusual though. */ void -LstNode_SetNull(LstNode node) +LstNode_SetNull(ListNode *node) { - assert(node != NULL); - node->datum = NULL; } - -/* - * Node-specific functions - */ - -/* Return the first node from the given list, or NULL if the list is empty. */ -LstNode -Lst_First(Lst list) -{ - assert(list != NULL); - - return list->first; -} - -/* Return the last node from the given list, or NULL if the list is empty. */ -LstNode -Lst_Last(Lst list) -{ - assert(list != NULL); - - return list->last; -} - -/* Return the successor to the given node on its list, or NULL. */ -LstNode -LstNode_Next(LstNode node) -{ - assert(node != NULL); - - return node->next; -} - -/* Return the predecessor to the given node on its list, or NULL. */ -LstNode -LstNode_Prev(LstNode node) -{ - assert(node != NULL); - return node->prev; -} - -/* Return the datum stored in the given node. */ -void * -LstNode_Datum(LstNode node) -{ - assert(node != NULL); - return node->datum; -} - - /* * Functions for entire lists */ -/* Return TRUE if the given list is empty. */ -Boolean -Lst_IsEmpty(Lst list) -{ - assert(list != NULL); - - return LstIsEmpty(list); -} - -/* Return the first node from the list for which the match function returns - * TRUE, or NULL if none of the nodes matched. */ -LstNode -Lst_Find(Lst list, LstFindProc match, const void *matchArgs) -{ - return Lst_FindFrom(list, Lst_First(list), match, matchArgs); -} - -/* Return the first node from the list, starting at the given node, for which - * the match function returns TRUE, or NULL if none of the nodes matches. - * - * The start node may be NULL, in which case nothing is found. This allows - * for passing Lst_First or LstNode_Next as the start node. */ -LstNode -Lst_FindFrom(Lst list, LstNode node, LstFindProc match, const void *matchArgs) -{ - LstNode tln; - - assert(list != NULL); - assert(match != NULL); - - for (tln = node; tln != NULL; tln = tln->next) { - if (match(tln->datum, matchArgs)) - return tln; - } - - return NULL; -} - /* Return the first node that contains the given datum, or NULL. */ -LstNode -Lst_FindDatum(Lst list, const void *datum) +ListNode * +Lst_FindDatum(List *list, const void *datum) { - LstNode node; + ListNode *node; - assert(list != NULL); assert(datum != NULL); - for (node = list->first; node != NULL; node = node->next) { - if (node->datum == datum) { + for (node = list->first; node != NULL; node = node->next) + if (node->datum == datum) return node; - } - } return NULL; } -/* Apply the given function to each element of the given list. The function - * should return 0 if traversal should continue and non-zero if it should - * abort. */ -int -Lst_ForEach(Lst list, LstActionProc proc, void *procData) -{ - if (LstIsEmpty(list)) - return 0; /* XXX: Document what this value means. */ - return Lst_ForEachFrom(list, Lst_First(list), proc, procData); -} - -/* Apply the given function to each element of the given list, starting from - * the given node. The function should return 0 if traversal should continue, - * and non-zero if it should abort. */ int -Lst_ForEachFrom(Lst list, LstNode node, - LstActionProc proc, void *procData) +Lst_ForEachUntil(List *list, LstActionUntilProc proc, void *procData) { - LstNode tln = node; - LstNode next; - Boolean done; - int result; - - assert(list != NULL); - assert(node != NULL); - assert(proc != NULL); - - do { - /* - * Take care of having the current element deleted out from under - * us. - */ - - next = tln->next; - - /* - * We're done with the traversal if - * - the next node to examine doesn't exist and - * - nothing's been added after the current node (check this - * after proc() has been called). - */ - done = next == NULL; - - tln->useCount++; - result = (*proc)(tln->datum, procData); - tln->useCount--; - - /* - * Now check whether a node has been added. - * Note: this doesn't work if this node was deleted before - * the new node was added. - */ - if (next != tln->next) { - next = tln->next; - done = 0; - } - - if (tln->deleted) { - free((char *)tln); - } - tln = next; - } while (!result && !LstIsEmpty(list) && !done); + ListNode *node; + int result = 0; + for (node = list->first; node != NULL; node = node->next) { + result = proc(node->datum, procData); + if (result != 0) + break; + } return result; } /* Move all nodes from list2 to the end of list1. * List2 is destroyed and freed. */ void -Lst_MoveAll(Lst list1, Lst list2) +Lst_MoveAll(List *list1, List *list2) { - assert(list1 != NULL); - assert(list2 != NULL); - if (list2->first != NULL) { list2->first->prev = list1->last; - if (list1->last != NULL) { + if (list1->last != NULL) list1->last->next = list2->first; - } else { + else list1->first = list2->first; - } + list1->last = list2->last; } free(list2); @@ -518,124 +243,77 @@ Lst_MoveAll(Lst list1, Lst list2) /* Copy the element data from src to the start of dst. */ void -Lst_PrependAll(Lst dst, Lst src) +Lst_PrependAll(List *dst, List *src) { - LstNode node; + ListNode *node; for (node = src->last; node != NULL; node = node->prev) Lst_Prepend(dst, node->datum); } /* Copy the element data from src to the end of dst. */ void -Lst_AppendAll(Lst dst, Lst src) +Lst_AppendAll(List *dst, List *src) { - LstNode node; + ListNode *node; for (node = src->first; node != NULL; node = node->next) Lst_Append(dst, node->datum); } /* - * these functions are for dealing with a list as a table, of sorts. - * An idea of the "current element" is kept and used by all the functions - * between Lst_Open() and Lst_Close(). - * - * The sequential functions access the list in a slightly different way. - * CurPtr points to their idea of the current node in the list and they - * access the list based on it. + * for using the list as a queue */ -/* Open a list for sequential access. A list can still be searched, etc., - * without confusing these functions. */ +/* Add the datum to the tail of the given list. */ void -Lst_Open(Lst list) +Lst_Enqueue(List *list, void *datum) { - assert(list != NULL); - assert(!list->isOpen); - - list->isOpen = TRUE; - list->lastAccess = LstIsEmpty(list) ? Head : Unknown; - list->curr = NULL; + Lst_Append(list, datum); } -/* Return the next node for the given list, or NULL if the end has been - * reached. */ -LstNode -Lst_Next(Lst list) +/* Remove and return the datum at the head of the given list. */ +void * +Lst_Dequeue(List *list) { - LstNode node; - - assert(list != NULL); - assert(list->isOpen); - - list->prev = list->curr; - - if (list->curr == NULL) { - if (list->lastAccess == Unknown) { - /* - * If we're just starting out, lastAccess will be Unknown. - * Then we want to start this thing off in the right - * direction -- at the start with lastAccess being Middle. - */ - list->curr = node = list->first; - list->lastAccess = Middle; - } else { - node = NULL; - list->lastAccess = Tail; - } - } else { - node = list->curr->next; - list->curr = node; - - if (node == list->first || node == NULL) { - /* - * If back at the front, then we've hit the end... - */ - list->lastAccess = Tail; - } else { - /* - * Reset to Middle if gone past first. - */ - list->lastAccess = Middle; - } - } - - return node; + void *datum = list->first->datum; + Lst_Remove(list, list->first); + assert(datum != NULL); /* since NULL would mean end of the list */ + return datum; } -/* Close a list which was opened for sequential access. */ void -Lst_Close(Lst list) +Vector_Init(Vector *v, size_t itemSize) { - assert(list != NULL); - assert(list->isOpen); - - list->isOpen = FALSE; - list->lastAccess = Unknown; + v->len = 0; + v->priv_cap = 10; + v->itemSize = itemSize; + v->items = bmake_malloc(v->priv_cap * v->itemSize); } - -/* - * for using the list as a queue - */ - -/* Add the datum to the tail of the given list. */ -void -Lst_Enqueue(Lst list, void *datum) +/* Add space for a new item to the vector and return a pointer to that space. + * The returned data is valid until the next modifying operation. */ +void * +Vector_Push(Vector *v) { - Lst_Append(list, datum); + if (v->len >= v->priv_cap) { + v->priv_cap *= 2; + v->items = bmake_realloc(v->items, v->priv_cap * v->itemSize); + } + v->len++; + return Vector_Get(v, v->len - 1); } -/* Remove and return the datum at the head of the given list. */ +/* Return the pointer to the last item in the vector. + * The returned data is valid until the next modifying operation. */ void * -Lst_Dequeue(Lst list) +Vector_Pop(Vector *v) { - void *datum; - - assert(list != NULL); - assert(!LstIsEmpty(list)); + assert(v->len > 0); + v->len--; + return Vector_Get(v, v->len); +} - datum = list->first->datum; - Lst_Remove(list, list->first); - assert(datum != NULL); - return datum; +void +Vector_Done(Vector *v) +{ + free(v->items); } |