contrib/bmake/lst.c

   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 }