contrib/bmake/lst.c

   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 }