1 /* $NetBSD: lst.c,v 1.91 2020/10/28 02:43: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.91 2020/10/28 02:43:16 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 *node = bmake_malloc(sizeof *node); 49 node->prev = prev; 50 node->next = next; 51 node->datum = datum; 52 return node; 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 *node; 72 ListNode *next; 73 74 for (node = list->first; node != NULL; node = next) { 75 next = node->next; 76 free(node); 77 } 78 79 free(list); 80 } 81 82 /* Destroy a list and free all its resources. The freeProc is called with the 83 * datum from each node in turn before the node is freed. */ 84 void 85 Lst_Destroy(List *list, LstFreeProc freeProc) 86 { 87 ListNode *node; 88 ListNode *next; 89 90 for (node = list->first; node != NULL; node = next) { 91 next = node->next; 92 freeProc(node->datum); 93 free(node); 94 } 95 96 free(list); 97 } 98 99 /* 100 * Functions to modify a list 101 */ 102 103 /* Insert a new node with the datum before the given node. */ 104 void 105 Lst_InsertBefore(List *list, ListNode *node, void *datum) 106 { 107 ListNode *newNode; 108 109 assert(datum != NULL); 110 111 newNode = LstNodeNew(node->prev, node, datum); 112 113 if (node->prev != NULL) 114 node->prev->next = newNode; 115 node->prev = newNode; 116 117 if (node == 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 *node; 126 127 assert(datum != NULL); 128 129 node = LstNodeNew(NULL, list->first, datum); 130 131 if (list->first == NULL) { 132 list->first = node; 133 list->last = node; 134 } else { 135 list->first->prev = node; 136 list->first = node; 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 *node; 145 146 assert(datum != NULL); 147 148 node = LstNodeNew(list->last, NULL, datum); 149 150 if (list->last == NULL) { 151 list->first = node; 152 list->last = node; 153 } else { 154 list->last->next = node; 155 list->last = node; 156 } 157 } 158 159 /* Remove the given node from the given list. 160 * The datum stored in the node must be freed by the caller, if necessary. */ 161 void 162 Lst_Remove(List *list, ListNode *node) 163 { 164 /* unlink it from its neighbors */ 165 if (node->next != NULL) 166 node->next->prev = node->prev; 167 if (node->prev != NULL) 168 node->prev->next = node->next; 169 170 /* unlink it from the list */ 171 if (list->first == node) 172 list->first = node->next; 173 if (list->last == node) 174 list->last = node->prev; 175 } 176 177 /* Replace the datum in the given node with the new datum. */ 178 void 179 LstNode_Set(ListNode *node, void *datum) 180 { 181 assert(datum != NULL); 182 183 node->datum = datum; 184 } 185 186 /* Replace the datum in the given node to NULL. 187 * Having NULL values in a list is unusual though. */ 188 void 189 LstNode_SetNull(ListNode *node) 190 { 191 node->datum = NULL; 192 } 193 194 /* 195 * Functions for entire lists 196 */ 197 198 /* Return the first node that contains the given datum, or NULL. */ 199 ListNode * 200 Lst_FindDatum(List *list, const void *datum) 201 { 202 ListNode *node; 203 204 assert(datum != NULL); 205 206 for (node = list->first; node != NULL; node = node->next) 207 if (node->datum == datum) 208 return node; 209 210 return NULL; 211 } 212 213 int 214 Lst_ForEachUntil(List *list, LstActionUntilProc proc, void *procData) 215 { 216 ListNode *node; 217 int result = 0; 218 219 for (node = list->first; node != NULL; node = node->next) { 220 result = proc(node->datum, procData); 221 if (result != 0) 222 break; 223 } 224 return result; 225 } 226 227 /* Move all nodes from list2 to the end of list1. 228 * List2 is destroyed and freed. */ 229 void 230 Lst_MoveAll(List *list1, List *list2) 231 { 232 if (list2->first != NULL) { 233 list2->first->prev = list1->last; 234 if (list1->last != NULL) 235 list1->last->next = list2->first; 236 else 237 list1->first = list2->first; 238 239 list1->last = list2->last; 240 } 241 free(list2); 242 } 243 244 /* Copy the element data from src to the start of dst. */ 245 void 246 Lst_PrependAll(List *dst, List *src) 247 { 248 ListNode *node; 249 for (node = src->last; node != NULL; node = node->prev) 250 Lst_Prepend(dst, node->datum); 251 } 252 253 /* Copy the element data from src to the end of dst. */ 254 void 255 Lst_AppendAll(List *dst, List *src) 256 { 257 ListNode *node; 258 for (node = src->first; node != NULL; node = node->next) 259 Lst_Append(dst, node->datum); 260 } 261 262 /* 263 * for using the list as a queue 264 */ 265 266 /* Add the datum to the tail of the given list. */ 267 void 268 Lst_Enqueue(List *list, void *datum) 269 { 270 Lst_Append(list, datum); 271 } 272 273 /* Remove and return the datum at the head of the given list. */ 274 void * 275 Lst_Dequeue(List *list) 276 { 277 void *datum = list->first->datum; 278 Lst_Remove(list, list->first); 279 assert(datum != NULL); /* since NULL would mean end of the list */ 280 return datum; 281 } 282 283 void 284 Vector_Init(Vector *v, size_t itemSize) 285 { 286 v->len = 0; 287 v->priv_cap = 10; 288 v->itemSize = itemSize; 289 v->items = bmake_malloc(v->priv_cap * v->itemSize); 290 } 291 292 /* Add space for a new item to the vector and return a pointer to that space. 293 * The returned data is valid until the next modifying operation. */ 294 void * 295 Vector_Push(Vector *v) 296 { 297 if (v->len >= v->priv_cap) { 298 v->priv_cap *= 2; 299 v->items = bmake_realloc(v->items, v->priv_cap * v->itemSize); 300 } 301 v->len++; 302 return Vector_Get(v, v->len - 1); 303 } 304 305 /* Return the pointer to the last item in the vector. 306 * The returned data is valid until the next modifying operation. */ 307 void * 308 Vector_Pop(Vector *v) 309 { 310 assert(v->len > 0); 311 v->len--; 312 return Vector_Get(v, v->len); 313 } 314 315 void 316 Vector_Done(Vector *v) 317 { 318 free(v->items); 319 } 320