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