1 /* $NetBSD: lst.c,v 1.102 2020/12/30 10:03:16 rillig Exp $ */ 2 3 /* 4 * Copyright (c) 1988, 1989, 1990, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Adam de Boor. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 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. 21 * 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 32 * SUCH DAMAGE. 33 */ 34 35 #include "make.h" 36 37 MAKE_RCSID("$NetBSD: lst.c,v 1.102 2020/12/30 10:03:16 rillig Exp $"); 38 39 static ListNode * 40 LstNodeNew(ListNode *prev, ListNode *next, void *datum) 41 { 42 ListNode *ln = bmake_malloc(sizeof *ln); 43 44 ln->prev = prev; 45 ln->next = next; 46 ln->datum = datum; 47 48 return ln; 49 } 50 51 /* Create and initialize a new, empty list. */ 52 List * 53 Lst_New(void) 54 { 55 List *list = bmake_malloc(sizeof *list); 56 Lst_Init(list); 57 return list; 58 } 59 60 void 61 Lst_Done(List *list) 62 { 63 ListNode *ln, *next; 64 65 for (ln = list->first; ln != NULL; ln = next) { 66 next = ln->next; 67 free(ln); 68 } 69 } 70 71 void 72 Lst_DoneCall(List *list, LstFreeProc freeProc) 73 { 74 ListNode *ln, *next; 75 76 for (ln = list->first; ln != NULL; ln = next) { 77 next = ln->next; 78 freeProc(ln->datum); 79 free(ln); 80 } 81 } 82 83 /* Free a list and all its nodes. The node data are not freed though. */ 84 void 85 Lst_Free(List *list) 86 { 87 88 Lst_Done(list); 89 free(list); 90 } 91 92 /* 93 * Destroy a list and free all its resources. The freeProc is called with the 94 * datum from each node in turn before the node is freed. 95 */ 96 void 97 Lst_Destroy(List *list, LstFreeProc freeProc) 98 { 99 Lst_DoneCall(list, freeProc); 100 free(list); 101 } 102 103 /* Insert a new node with the datum before the given node. */ 104 void 105 Lst_InsertBefore(List *list, ListNode *ln, void *datum) 106 { 107 ListNode *newNode; 108 109 assert(datum != NULL); 110 111 newNode = LstNodeNew(ln->prev, ln, datum); 112 113 if (ln->prev != NULL) 114 ln->prev->next = newNode; 115 ln->prev = newNode; 116 117 if (ln == list->first) 118 list->first = newNode; 119 } 120 121 /* Add a piece of data at the start of the given list. */ 122 void 123 Lst_Prepend(List *list, void *datum) 124 { 125 ListNode *ln; 126 127 assert(datum != NULL); 128 129 ln = LstNodeNew(NULL, list->first, datum); 130 131 if (list->first == NULL) { 132 list->first = ln; 133 list->last = ln; 134 } else { 135 list->first->prev = ln; 136 list->first = ln; 137 } 138 } 139 140 /* Add a piece of data at the end of the given list. */ 141 void 142 Lst_Append(List *list, void *datum) 143 { 144 ListNode *ln; 145 146 assert(datum != NULL); 147 148 ln = LstNodeNew(list->last, NULL, datum); 149 150 if (list->last == NULL) { 151 list->first = ln; 152 list->last = ln; 153 } else { 154 list->last->next = ln; 155 list->last = ln; 156 } 157 } 158 159 /* 160 * Remove the given node from the given list. 161 * The datum stored in the node must be freed by the caller, if necessary. 162 */ 163 void 164 Lst_Remove(List *list, ListNode *ln) 165 { 166 /* unlink it from its neighbors */ 167 if (ln->next != NULL) 168 ln->next->prev = ln->prev; 169 if (ln->prev != NULL) 170 ln->prev->next = ln->next; 171 172 /* unlink it from the list */ 173 if (list->first == ln) 174 list->first = ln->next; 175 if (list->last == ln) 176 list->last = ln->prev; 177 } 178 179 /* Replace the datum in the given node with the new datum. */ 180 void 181 LstNode_Set(ListNode *ln, void *datum) 182 { 183 assert(datum != NULL); 184 185 ln->datum = datum; 186 } 187 188 /* 189 * Replace the datum in the given node with NULL. 190 * Having NULL values in a list is unusual though. 191 */ 192 void 193 LstNode_SetNull(ListNode *ln) 194 { 195 ln->datum = NULL; 196 } 197 198 /* 199 * Return the first node that contains the given datum, or NULL. 200 * 201 * Time complexity: O(length(list)) 202 */ 203 ListNode * 204 Lst_FindDatum(List *list, const void *datum) 205 { 206 ListNode *ln; 207 208 assert(datum != NULL); 209 210 for (ln = list->first; ln != NULL; ln = ln->next) 211 if (ln->datum == datum) 212 return ln; 213 214 return NULL; 215 } 216 217 /* 218 * Move all nodes from src to the end of dst. 219 * The source list becomes empty but is not freed. 220 */ 221 void 222 Lst_MoveAll(List *dst, List *src) 223 { 224 if (src->first != NULL) { 225 src->first->prev = dst->last; 226 if (dst->last != NULL) 227 dst->last->next = src->first; 228 else 229 dst->first = src->first; 230 231 dst->last = src->last; 232 } 233 } 234 235 /* Copy the element data from src to the start of dst. */ 236 void 237 Lst_PrependAll(List *dst, List *src) 238 { 239 ListNode *ln; 240 241 for (ln = src->last; ln != NULL; ln = ln->prev) 242 Lst_Prepend(dst, ln->datum); 243 } 244 245 /* Copy the element data from src to the end of dst. */ 246 void 247 Lst_AppendAll(List *dst, List *src) 248 { 249 ListNode *ln; 250 251 for (ln = src->first; ln != NULL; ln = ln->next) 252 Lst_Append(dst, ln->datum); 253 } 254 255 /* Remove and return the datum at the head of the given list. */ 256 void * 257 Lst_Dequeue(List *list) 258 { 259 void *datum = list->first->datum; 260 Lst_Remove(list, list->first); 261 assert(datum != NULL); /* since NULL would mean end of the list */ 262 return datum; 263 } 264 265 void 266 Vector_Init(Vector *v, size_t itemSize) 267 { 268 v->len = 0; 269 v->cap = 10; 270 v->itemSize = itemSize; 271 v->items = bmake_malloc(v->cap * v->itemSize); 272 } 273 274 /* 275 * Add space for a new item to the vector and return a pointer to that space. 276 * The returned data is valid until the next modifying operation. 277 */ 278 void * 279 Vector_Push(Vector *v) 280 { 281 if (v->len >= v->cap) { 282 v->cap *= 2; 283 v->items = bmake_realloc(v->items, v->cap * v->itemSize); 284 } 285 v->len++; 286 return Vector_Get(v, v->len - 1); 287 } 288 289 /* 290 * Return the pointer to the last item in the vector. 291 * The returned data is valid until the next modifying operation. 292 */ 293 void * 294 Vector_Pop(Vector *v) 295 { 296 assert(v->len > 0); 297 v->len--; 298 return Vector_Get(v, v->len); 299 } 300