1 /* $NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 rillig Exp $ */
4 * Copyright (c) 1988, 1989, 1990, 1993
5 * The Regents of the University of California. All rights reserved.
7 * This code is derived from software contributed to Berkeley by
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39 #ifdef HAVE_INTTYPES_H
41 #elif defined(HAVE_STDINT_H)
48 static char rcsid[] = "$NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 rillig Exp $";
50 #include <sys/cdefs.h>
52 __RCSID("$NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 rillig Exp $");
57 struct ListNode *prev; /* previous element in list */
58 struct ListNode *next; /* next in list */
59 uint8_t useCount; /* Count of functions using the node.
60 * node may not be deleted until count
62 Boolean deleted; /* List node should be removed when done */
64 void *datum; /* datum associated with this element */
65 const GNode *gnode; /* alias, just for debugging */
66 const char *str; /* alias, just for debugging */
71 Head, Middle, Tail, Unknown
75 LstNode first; /* first node in list */
76 LstNode last; /* last node in list */
78 /* fields for sequential access */
79 Boolean isOpen; /* true if list has been Lst_Open'ed */
80 Where lastAccess; /* Where in the list the last access was */
81 LstNode curr; /* current node, if open. NULL if
83 LstNode prev; /* Previous node, if open. Used by Lst_Remove */
86 /* Allocate and initialize a list node.
88 * The fields 'prev' and 'next' must be initialized by the caller.
91 LstNodeNew(void *datum)
93 LstNode node = bmake_malloc(sizeof *node);
95 node->deleted = FALSE;
103 return list->first == NULL;
106 /* Create and initialize a new, empty list. */
110 Lst list = bmake_malloc(sizeof *list);
114 list->isOpen = FALSE;
115 list->lastAccess = Unknown;
120 /* Duplicate an entire list, usually by copying the datum pointers.
121 * If copyProc is given, that function is used to create the new datum from the
122 * old datum, usually by creating a copy of it. */
124 Lst_Copy(Lst list, LstCopyProc copyProc)
129 assert(list != NULL);
131 newList = Lst_Init();
133 for (node = list->first; node != NULL; node = node->next) {
134 void *datum = copyProc != NULL ? copyProc(node->datum) : node->datum;
135 Lst_Append(newList, datum);
141 /* Free a list and all its nodes. The list data itself are not freed though. */
148 assert(list != NULL);
150 for (node = list->first; node != NULL; node = next) {
158 /* Destroy a list and free all its resources. The freeProc is called with the
159 * datum from each node in turn before the node is freed. */
161 Lst_Destroy(Lst list, LstFreeProc freeProc)
166 assert(list != NULL);
167 assert(freeProc != NULL);
169 for (node = list->first; node != NULL; node = next) {
171 freeProc(node->datum);
179 * Functions to modify a list
182 /* Insert a new node with the given piece of data before the given node in the
185 Lst_InsertBefore(Lst list, LstNode node, void *datum)
189 assert(list != NULL);
190 assert(!LstIsEmpty(list));
191 assert(node != NULL);
192 assert(datum != NULL);
194 newNode = LstNodeNew(datum);
195 newNode->prev = node->prev;
196 newNode->next = node;
198 if (node->prev != NULL) {
199 node->prev->next = newNode;
201 node->prev = newNode;
203 if (node == list->first) {
204 list->first = newNode;
208 /* Add a piece of data at the start of the given list. */
210 Lst_Prepend(Lst list, void *datum)
214 assert(list != NULL);
215 assert(datum != NULL);
217 node = LstNodeNew(datum);
219 node->next = list->first;
221 if (list->first == NULL) {
225 list->first->prev = node;
230 /* Add a piece of data at the end of the given list. */
232 Lst_Append(Lst list, void *datum)
236 assert(list != NULL);
237 assert(datum != NULL);
239 node = LstNodeNew(datum);
240 node->prev = list->last;
243 if (list->last == NULL) {
247 list->last->next = node;
252 /* Remove the given node from the given list.
253 * The datum stored in the node must be freed by the caller, if necessary. */
255 Lst_Remove(Lst list, LstNode node)
257 assert(list != NULL);
258 assert(node != NULL);
261 * unlink it from the list
263 if (node->next != NULL) {
264 node->next->prev = node->prev;
266 if (node->prev != NULL) {
267 node->prev->next = node->next;
271 * if either the first or last of the list point to this node,
272 * adjust them accordingly
274 if (list->first == node) {
275 list->first = node->next;
277 if (list->last == node) {
278 list->last = node->prev;
282 * Sequential access stuff. If the node we're removing is the current
283 * node in the list, reset the current node to the previous one. If the
284 * previous one was non-existent (prev == NULL), we set the
285 * end to be Unknown, since it is.
287 if (list->isOpen && list->curr == node) {
288 list->curr = list->prev;
289 if (list->curr == NULL) {
290 list->lastAccess = Unknown;
295 * note that the datum is unmolested. The caller must free it as
296 * necessary and as expected.
298 if (node->useCount == 0) {
301 node->deleted = TRUE;
305 /* Replace the datum in the given node with the new datum. */
307 LstNode_Set(LstNode node, void *datum)
309 assert(node != NULL);
310 assert(datum != NULL);
315 /* Replace the datum in the given node to NULL. */
317 LstNode_SetNull(LstNode node)
319 assert(node != NULL);
326 * Node-specific functions
329 /* Return the first node from the given list, or NULL if the list is empty. */
333 assert(list != NULL);
338 /* Return the last node from the given list, or NULL if the list is empty. */
342 assert(list != NULL);
347 /* Return the successor to the given node on its list, or NULL. */
349 LstNode_Next(LstNode node)
351 assert(node != NULL);
356 /* Return the predecessor to the given node on its list, or NULL. */
358 LstNode_Prev(LstNode node)
360 assert(node != NULL);
364 /* Return the datum stored in the given node. */
366 LstNode_Datum(LstNode node)
368 assert(node != NULL);
374 * Functions for entire lists
377 /* Return TRUE if the given list is empty. */
379 Lst_IsEmpty(Lst list)
381 assert(list != NULL);
383 return LstIsEmpty(list);
386 /* Return the first node from the list for which the match function returns
387 * TRUE, or NULL if none of the nodes matched. */
389 Lst_Find(Lst list, LstFindProc match, const void *matchArgs)
391 return Lst_FindFrom(list, Lst_First(list), match, matchArgs);
394 /* Return the first node from the list, starting at the given node, for which
395 * the match function returns TRUE, or NULL if none of the nodes matches.
397 * The start node may be NULL, in which case nothing is found. This allows
398 * for passing Lst_First or LstNode_Next as the start node. */
400 Lst_FindFrom(Lst list, LstNode node, LstFindProc match, const void *matchArgs)
404 assert(list != NULL);
405 assert(match != NULL);
407 for (tln = node; tln != NULL; tln = tln->next) {
408 if (match(tln->datum, matchArgs))
415 /* Return the first node that contains the given datum, or NULL. */
417 Lst_FindDatum(Lst list, const void *datum)
421 assert(list != NULL);
422 assert(datum != NULL);
424 for (node = list->first; node != NULL; node = node->next) {
425 if (node->datum == datum) {
433 /* Apply the given function to each element of the given list. The function
434 * should return 0 if traversal should continue and non-zero if it should
437 Lst_ForEach(Lst list, LstActionProc proc, void *procData)
439 if (LstIsEmpty(list))
440 return 0; /* XXX: Document what this value means. */
441 return Lst_ForEachFrom(list, Lst_First(list), proc, procData);
444 /* Apply the given function to each element of the given list, starting from
445 * the given node. The function should return 0 if traversal should continue,
446 * and non-zero if it should abort. */
448 Lst_ForEachFrom(Lst list, LstNode node,
449 LstActionProc proc, void *procData)
456 assert(list != NULL);
457 assert(node != NULL);
458 assert(proc != NULL);
462 * Take care of having the current element deleted out from under
469 * We're done with the traversal if
470 * - the next node to examine doesn't exist and
471 * - nothing's been added after the current node (check this
472 * after proc() has been called).
477 result = (*proc)(tln->datum, procData);
481 * Now check whether a node has been added.
482 * Note: this doesn't work if this node was deleted before
483 * the new node was added.
485 if (next != tln->next) {
494 } while (!result && !LstIsEmpty(list) && !done);
499 /* Move all nodes from list2 to the end of list1.
500 * List2 is destroyed and freed. */
502 Lst_MoveAll(Lst list1, Lst list2)
504 assert(list1 != NULL);
505 assert(list2 != NULL);
507 if (list2->first != NULL) {
508 list2->first->prev = list1->last;
509 if (list1->last != NULL) {
510 list1->last->next = list2->first;
512 list1->first = list2->first;
514 list1->last = list2->last;
519 /* Copy the element data from src to the start of dst. */
521 Lst_PrependAll(Lst dst, Lst src)
524 for (node = src->last; node != NULL; node = node->prev)
525 Lst_Prepend(dst, node->datum);
528 /* Copy the element data from src to the end of dst. */
530 Lst_AppendAll(Lst dst, Lst src)
533 for (node = src->first; node != NULL; node = node->next)
534 Lst_Append(dst, node->datum);
538 * these functions are for dealing with a list as a table, of sorts.
539 * An idea of the "current element" is kept and used by all the functions
540 * between Lst_Open() and Lst_Close().
542 * The sequential functions access the list in a slightly different way.
543 * CurPtr points to their idea of the current node in the list and they
544 * access the list based on it.
547 /* Open a list for sequential access. A list can still be searched, etc.,
548 * without confusing these functions. */
552 assert(list != NULL);
553 assert(!list->isOpen);
556 list->lastAccess = LstIsEmpty(list) ? Head : Unknown;
560 /* Return the next node for the given list, or NULL if the end has been
567 assert(list != NULL);
568 assert(list->isOpen);
570 list->prev = list->curr;
572 if (list->curr == NULL) {
573 if (list->lastAccess == Unknown) {
575 * If we're just starting out, lastAccess will be Unknown.
576 * Then we want to start this thing off in the right
577 * direction -- at the start with lastAccess being Middle.
579 list->curr = node = list->first;
580 list->lastAccess = Middle;
583 list->lastAccess = Tail;
586 node = list->curr->next;
589 if (node == list->first || node == NULL) {
591 * If back at the front, then we've hit the end...
593 list->lastAccess = Tail;
596 * Reset to Middle if gone past first.
598 list->lastAccess = Middle;
605 /* Close a list which was opened for sequential access. */
609 assert(list != NULL);
610 assert(list->isOpen);
612 list->isOpen = FALSE;
613 list->lastAccess = Unknown;
618 * for using the list as a queue
621 /* Add the datum to the tail of the given list. */
623 Lst_Enqueue(Lst list, void *datum)
625 Lst_Append(list, datum);
628 /* Remove and return the datum at the head of the given list. */
630 Lst_Dequeue(Lst list)
634 assert(list != NULL);
635 assert(!LstIsEmpty(list));
637 datum = list->first->datum;
638 Lst_Remove(list, list->first);
639 assert(datum != NULL);