contrib/bmake/lst.c

   1 /* $NetBSD: lst.c,v 1.104 2021/02/01 19:39:31 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.104 2021/02/01 19:39:31 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 /* Insert a new node with the datum before the given node. */
  93 void
  94 Lst_InsertBefore(List *list, ListNode *ln, void *datum)
  95 {
  96         ListNode *newNode;
  97
  98         assert(datum != NULL);
  99
 100         newNode = LstNodeNew(ln->prev, ln, datum);
 101
 102         if (ln->prev != NULL)
 103                 ln->prev->next = newNode;
 104         ln->prev = newNode;
 105
 106         if (ln == list->first)
 107                 list->first = newNode;
 108 }
 109
 110 /* Add a piece of data at the start of the given list. */
 111 void
 112 Lst_Prepend(List *list, void *datum)
 113 {
 114         ListNode *ln;
 115
 116         assert(datum != NULL);
 117
 118         ln = LstNodeNew(NULL, list->first, datum);
 119
 120         if (list->first == NULL) {
 121                 list->first = ln;
 122                 list->last = ln;
 123         } else {
 124                 list->first->prev = ln;
 125                 list->first = ln;
 126         }
 127 }
 128
 129 /* Add a piece of data at the end of the given list. */
 130 void
 131 Lst_Append(List *list, void *datum)
 132 {
 133         ListNode *ln;
 134
 135         assert(datum != NULL);
 136
 137         ln = LstNodeNew(list->last, NULL, datum);
 138
 139         if (list->last == NULL) {
 140                 list->first = ln;
 141                 list->last = ln;
 142         } else {
 143                 list->last->next = ln;
 144                 list->last = ln;
 145         }
 146 }
 147
 148 /*
 149  * Remove the given node from the given list.
 150  * The datum stored in the node must be freed by the caller, if necessary.
 151  */
 152 void
 153 Lst_Remove(List *list, ListNode *ln)
 154 {
 155         /* unlink it from its neighbors */
 156         if (ln->next != NULL)
 157                 ln->next->prev = ln->prev;
 158         if (ln->prev != NULL)
 159                 ln->prev->next = ln->next;
 160
 161         /* unlink it from the list */
 162         if (list->first == ln)
 163                 list->first = ln->next;
 164         if (list->last == ln)
 165                 list->last = ln->prev;
 166 }
 167
 168 /* Replace the datum in the given node with the new datum. */
 169 void
 170 LstNode_Set(ListNode *ln, void *datum)
 171 {
 172         assert(datum != NULL);
 173
 174         ln->datum = datum;
 175 }
 176
 177 /*
 178  * Replace the datum in the given node with NULL.
 179  * Having NULL values in a list is unusual though.
 180  */
 181 void
 182 LstNode_SetNull(ListNode *ln)
 183 {
 184         ln->datum = NULL;
 185 }
 186
 187 /*
 188  * Return the first node that contains the given datum, or NULL.
 189  *
 190  * Time complexity: O(length(list))
 191  */
 192 ListNode *
 193 Lst_FindDatum(List *list, const void *datum)
 194 {
 195         ListNode *ln;
 196
 197         assert(datum != NULL);
 198
 199         for (ln = list->first; ln != NULL; ln = ln->next)
 200                 if (ln->datum == datum)
 201                         return ln;
 202
 203         return NULL;
 204 }
 205
 206 /*
 207  * Move all nodes from src to the end of dst.
 208  * The source list becomes empty but is not freed.
 209  */
 210 void
 211 Lst_MoveAll(List *dst, List *src)
 212 {
 213         if (src->first != NULL) {
 214                 src->first->prev = dst->last;
 215                 if (dst->last != NULL)
 216                         dst->last->next = src->first;
 217                 else
 218                         dst->first = src->first;
 219
 220                 dst->last = src->last;
 221         }
 222 }
 223
 224 /* Copy the element data from src to the start of dst. */
 225 void
 226 Lst_PrependAll(List *dst, List *src)
 227 {
 228         ListNode *ln;
 229
 230         for (ln = src->last; ln != NULL; ln = ln->prev)
 231                 Lst_Prepend(dst, ln->datum);
 232 }
 233
 234 /* Copy the element data from src to the end of dst. */
 235 void
 236 Lst_AppendAll(List *dst, List *src)
 237 {
 238         ListNode *ln;
 239
 240         for (ln = src->first; ln != NULL; ln = ln->next)
 241                 Lst_Append(dst, ln->datum);
 242 }
 243
 244 /* Remove and return the datum at the head of the given list. */
 245 void *
 246 Lst_Dequeue(List *list)
 247 {
 248         void *datum = list->first->datum;
 249         Lst_Remove(list, list->first);
 250         assert(datum != NULL);  /* since NULL would mean end of the list */
 251         return datum;
 252 }
 253
 254 void
 255 Vector_Init(Vector *v, size_t itemSize)
 256 {
 257         v->len = 0;
 258         v->cap = 10;
 259         v->itemSize = itemSize;
 260         v->items = bmake_malloc(v->cap * v->itemSize);
 261 }
 262
 263 /*
 264  * Add space for a new item to the vector and return a pointer to that space.
 265  * The returned data is valid until the next modifying operation.
 266  */
 267 void *
 268 Vector_Push(Vector *v)
 269 {
 270         if (v->len >= v->cap) {
 271                 v->cap *= 2;
 272                 v->items = bmake_realloc(v->items, v->cap * v->itemSize);
 273         }
 274         v->len++;
 275         return Vector_Get(v, v->len - 1);
 276 }
 277
 278 /*
 279  * Remove the last item from the vector, return the pointer to it.
 280  * The returned data is valid until the next modifying operation.
 281  */
 282 void *
 283 Vector_Pop(Vector *v)
 284 {
 285         assert(v->len > 0);
 286         v->len--;
 287         return Vector_Get(v, v->len);
 288 }