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