contrib/bmake/lst.c

   1 /* $NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 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 #ifdef HAVE_CONFIG_H
  36 # include "config.h"
  37 #endif
  38
  39 #ifdef HAVE_INTTYPES_H
  40 #include <inttypes.h>
  41 #elif defined(HAVE_STDINT_H)
  42 #include <stdint.h>
  43 #endif
  44
  45 #include "make.h"
  46
  47 #ifndef MAKE_NATIVE
  48 static char rcsid[] = "$NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 rillig Exp $";
  49 #else
  50 #include <sys/cdefs.h>
  51 #ifndef lint
  52 __RCSID("$NetBSD: lst.c,v 1.60 2020/08/31 05:56:02 rillig Exp $");
  53 #endif /* not lint */
  54 #endif
  55
  56 struct ListNode {
  57     struct ListNode *prev;      /* previous element in list */
  58     struct ListNode *next;      /* next in list */
  59     uint8_t useCount;           /* Count of functions using the node.
  60                                  * node may not be deleted until count
  61                                  * goes to 0 */
  62     Boolean deleted;            /* List node should be removed when done */
  63     union {
  64         void *datum;            /* datum associated with this element */
  65         const GNode *gnode;     /* alias, just for debugging */
  66         const char *str;        /* alias, just for debugging */
  67     };
  68 };
  69
  70 typedef enum {
  71     Head, Middle, Tail, Unknown
  72 } Where;
  73
  74 struct List {
  75     LstNode first;              /* first node in list */
  76     LstNode last;               /* last node in list */
  77
  78     /* fields for sequential access */
  79     Boolean isOpen;             /* true if list has been Lst_Open'ed */
  80     Where lastAccess;           /* Where in the list the last access was */
  81     LstNode curr;               /* current node, if open. NULL if
  82                                  * *just* opened */
  83     LstNode prev;               /* Previous node, if open. Used by Lst_Remove */
  84 };
  85
  86 /* Allocate and initialize a list node.
  87  *
  88  * The fields 'prev' and 'next' must be initialized by the caller.
  89  */
  90 static LstNode
  91 LstNodeNew(void *datum)
  92 {
  93     LstNode node = bmake_malloc(sizeof *node);
  94     node->useCount = 0;
  95     node->deleted = FALSE;
  96     node->datum = datum;
  97     return node;
  98 }
  99
 100 static Boolean
 101 LstIsEmpty(Lst list)
 102 {
 103     return list->first == NULL;
 104 }
 105
 106 /* Create and initialize a new, empty list. */
 107 Lst
 108 Lst_Init(void)
 109 {
 110     Lst list = bmake_malloc(sizeof *list);
 111
 112     list->first = NULL;
 113     list->last = NULL;
 114     list->isOpen = FALSE;
 115     list->lastAccess = Unknown;
 116
 117     return list;
 118 }
 119
 120 /* Duplicate an entire list, usually by copying the datum pointers.
 121  * If copyProc is given, that function is used to create the new datum from the
 122  * old datum, usually by creating a copy of it. */
 123 Lst
 124 Lst_Copy(Lst list, LstCopyProc copyProc)
 125 {
 126     Lst newList;
 127     LstNode node;
 128
 129     assert(list != NULL);
 130
 131     newList = Lst_Init();
 132
 133     for (node = list->first; node != NULL; node = node->next) {
 134         void *datum = copyProc != NULL ? copyProc(node->datum) : node->datum;
 135         Lst_Append(newList, datum);
 136     }
 137
 138     return newList;
 139 }
 140
 141 /* Free a list and all its nodes. The list data itself are not freed though. */
 142 void
 143 Lst_Free(Lst list)
 144 {
 145     LstNode node;
 146     LstNode next;
 147
 148     assert(list != NULL);
 149
 150     for (node = list->first; node != NULL; node = next) {
 151         next = node->next;
 152         free(node);
 153     }
 154
 155     free(list);
 156 }
 157
 158 /* Destroy a list and free all its resources. The freeProc is called with the
 159  * datum from each node in turn before the node is freed. */
 160 void
 161 Lst_Destroy(Lst list, LstFreeProc freeProc)
 162 {
 163     LstNode node;
 164     LstNode next;
 165
 166     assert(list != NULL);
 167     assert(freeProc != NULL);
 168
 169     for (node = list->first; node != NULL; node = next) {
 170         next = node->next;
 171         freeProc(node->datum);
 172         free(node);
 173     }
 174
 175     free(list);
 176 }
 177
 178 /*
 179  * Functions to modify a list
 180  */
 181
 182 /* Insert a new node with the given piece of data before the given node in the
 183  * given list. */
 184 void
 185 Lst_InsertBefore(Lst list, LstNode node, void *datum)
 186 {
 187     LstNode newNode;
 188
 189     assert(list != NULL);
 190     assert(!LstIsEmpty(list));
 191     assert(node != NULL);
 192     assert(datum != NULL);
 193
 194     newNode = LstNodeNew(datum);
 195     newNode->prev = node->prev;
 196     newNode->next = node;
 197
 198     if (node->prev != NULL) {
 199         node->prev->next = newNode;
 200     }
 201     node->prev = newNode;
 202
 203     if (node == list->first) {
 204         list->first = newNode;
 205     }
 206 }
 207
 208 /* Add a piece of data at the start of the given list. */
 209 void
 210 Lst_Prepend(Lst list, void *datum)
 211 {
 212     LstNode node;
 213
 214     assert(list != NULL);
 215     assert(datum != NULL);
 216
 217     node = LstNodeNew(datum);
 218     node->prev = NULL;
 219     node->next = list->first;
 220
 221     if (list->first == NULL) {
 222         list->first = node;
 223         list->last = node;
 224     } else {
 225         list->first->prev = node;
 226         list->first = node;
 227     }
 228 }
 229
 230 /* Add a piece of data at the end of the given list. */
 231 void
 232 Lst_Append(Lst list, void *datum)
 233 {
 234     LstNode node;
 235
 236     assert(list != NULL);
 237     assert(datum != NULL);
 238
 239     node = LstNodeNew(datum);
 240     node->prev = list->last;
 241     node->next = NULL;
 242
 243     if (list->last == NULL) {
 244         list->first = node;
 245         list->last = node;
 246     } else {
 247         list->last->next = node;
 248         list->last = node;
 249     }
 250 }
 251
 252 /* Remove the given node from the given list.
 253  * The datum stored in the node must be freed by the caller, if necessary. */
 254 void
 255 Lst_Remove(Lst list, LstNode node)
 256 {
 257     assert(list != NULL);
 258     assert(node != NULL);
 259
 260     /*
 261      * unlink it from the list
 262      */
 263     if (node->next != NULL) {
 264         node->next->prev = node->prev;
 265     }
 266     if (node->prev != NULL) {
 267         node->prev->next = node->next;
 268     }
 269
 270     /*
 271      * if either the first or last of the list point to this node,
 272      * adjust them accordingly
 273      */
 274     if (list->first == node) {
 275         list->first = node->next;
 276     }
 277     if (list->last == node) {
 278         list->last = node->prev;
 279     }
 280
 281     /*
 282      * Sequential access stuff. If the node we're removing is the current
 283      * node in the list, reset the current node to the previous one. If the
 284      * previous one was non-existent (prev == NULL), we set the
 285      * end to be Unknown, since it is.
 286      */
 287     if (list->isOpen && list->curr == node) {
 288         list->curr = list->prev;
 289         if (list->curr == NULL) {
 290             list->lastAccess = Unknown;
 291         }
 292     }
 293
 294     /*
 295      * note that the datum is unmolested. The caller must free it as
 296      * necessary and as expected.
 297      */
 298     if (node->useCount == 0) {
 299         free(node);
 300     } else {
 301         node->deleted = TRUE;
 302     }
 303 }
 304
 305 /* Replace the datum in the given node with the new datum. */
 306 void
 307 LstNode_Set(LstNode node, void *datum)
 308 {
 309     assert(node != NULL);
 310     assert(datum != NULL);
 311
 312     node->datum = datum;
 313 }
 314
 315 /* Replace the datum in the given node to NULL. */
 316 void
 317 LstNode_SetNull(LstNode node)
 318 {
 319     assert(node != NULL);
 320
 321     node->datum = NULL;
 322 }
 323
 324
 325 /*
 326  * Node-specific functions
 327  */
 328
 329 /* Return the first node from the given list, or NULL if the list is empty. */
 330 LstNode
 331 Lst_First(Lst list)
 332 {
 333     assert(list != NULL);
 334
 335     return list->first;
 336 }
 337
 338 /* Return the last node from the given list, or NULL if the list is empty. */
 339 LstNode
 340 Lst_Last(Lst list)
 341 {
 342     assert(list != NULL);
 343
 344     return list->last;
 345 }
 346
 347 /* Return the successor to the given node on its list, or NULL. */
 348 LstNode
 349 LstNode_Next(LstNode node)
 350 {
 351     assert(node != NULL);
 352
 353     return node->next;
 354 }
 355
 356 /* Return the predecessor to the given node on its list, or NULL. */
 357 LstNode
 358 LstNode_Prev(LstNode node)
 359 {
 360     assert(node != NULL);
 361     return node->prev;
 362 }
 363
 364 /* Return the datum stored in the given node. */
 365 void *
 366 LstNode_Datum(LstNode node)
 367 {
 368     assert(node != NULL);
 369     return node->datum;
 370 }
 371
 372
 373 /*
 374  * Functions for entire lists
 375  */
 376
 377 /* Return TRUE if the given list is empty. */
 378 Boolean
 379 Lst_IsEmpty(Lst list)
 380 {
 381     assert(list != NULL);
 382
 383     return LstIsEmpty(list);
 384 }
 385
 386 /* Return the first node from the list for which the match function returns
 387  * TRUE, or NULL if none of the nodes matched. */
 388 LstNode
 389 Lst_Find(Lst list, LstFindProc match, const void *matchArgs)
 390 {
 391     return Lst_FindFrom(list, Lst_First(list), match, matchArgs);
 392 }
 393
 394 /* Return the first node from the list, starting at the given node, for which
 395  * the match function returns TRUE, or NULL if none of the nodes matches.
 396  *
 397  * The start node may be NULL, in which case nothing is found. This allows
 398  * for passing Lst_First or LstNode_Next as the start node. */
 399 LstNode
 400 Lst_FindFrom(Lst list, LstNode node, LstFindProc match, const void *matchArgs)
 401 {
 402     LstNode tln;
 403
 404     assert(list != NULL);
 405     assert(match != NULL);
 406
 407     for (tln = node; tln != NULL; tln = tln->next) {
 408         if (match(tln->datum, matchArgs))
 409             return tln;
 410     }
 411
 412     return NULL;
 413 }
 414
 415 /* Return the first node that contains the given datum, or NULL. */
 416 LstNode
 417 Lst_FindDatum(Lst list, const void *datum)
 418 {
 419     LstNode node;
 420
 421     assert(list != NULL);
 422     assert(datum != NULL);
 423
 424     for (node = list->first; node != NULL; node = node->next) {
 425         if (node->datum == datum) {
 426             return node;
 427         }
 428     }
 429
 430     return NULL;
 431 }
 432
 433 /* Apply the given function to each element of the given list. The function
 434  * should return 0 if traversal should continue and non-zero if it should
 435  * abort. */
 436 int
 437 Lst_ForEach(Lst list, LstActionProc proc, void *procData)
 438 {
 439     if (LstIsEmpty(list))
 440         return 0;               /* XXX: Document what this value means. */
 441     return Lst_ForEachFrom(list, Lst_First(list), proc, procData);
 442 }
 443
 444 /* Apply the given function to each element of the given list, starting from
 445  * the given node. The function should return 0 if traversal should continue,
 446  * and non-zero if it should abort. */
 447 int
 448 Lst_ForEachFrom(Lst list, LstNode node,
 449                  LstActionProc proc, void *procData)
 450 {
 451     LstNode tln = node;
 452     LstNode next;
 453     Boolean done;
 454     int result;
 455
 456     assert(list != NULL);
 457     assert(node != NULL);
 458     assert(proc != NULL);
 459
 460     do {
 461         /*
 462          * Take care of having the current element deleted out from under
 463          * us.
 464          */
 465
 466         next = tln->next;
 467
 468         /*
 469          * We're done with the traversal if
 470          *  - the next node to examine doesn't exist and
 471          *  - nothing's been added after the current node (check this
 472          *    after proc() has been called).
 473          */
 474         done = next == NULL;
 475
 476         tln->useCount++;
 477         result = (*proc)(tln->datum, procData);
 478         tln->useCount--;
 479
 480         /*
 481          * Now check whether a node has been added.
 482          * Note: this doesn't work if this node was deleted before
 483          *       the new node was added.
 484          */
 485         if (next != tln->next) {
 486             next = tln->next;
 487             done = 0;
 488         }
 489
 490         if (tln->deleted) {
 491             free((char *)tln);
 492         }
 493         tln = next;
 494     } while (!result && !LstIsEmpty(list) && !done);
 495
 496     return result;
 497 }
 498
 499 /* Move all nodes from list2 to the end of list1.
 500  * List2 is destroyed and freed. */
 501 void
 502 Lst_MoveAll(Lst list1, Lst list2)
 503 {
 504     assert(list1 != NULL);
 505     assert(list2 != NULL);
 506
 507     if (list2->first != NULL) {
 508         list2->first->prev = list1->last;
 509         if (list1->last != NULL) {
 510             list1->last->next = list2->first;
 511         } else {
 512             list1->first = list2->first;
 513         }
 514         list1->last = list2->last;
 515     }
 516     free(list2);
 517 }
 518
 519 /* Copy the element data from src to the start of dst. */
 520 void
 521 Lst_PrependAll(Lst dst, Lst src)
 522 {
 523     LstNode node;
 524     for (node = src->last; node != NULL; node = node->prev)
 525         Lst_Prepend(dst, node->datum);
 526 }
 527
 528 /* Copy the element data from src to the end of dst. */
 529 void
 530 Lst_AppendAll(Lst dst, Lst src)
 531 {
 532     LstNode node;
 533     for (node = src->first; node != NULL; node = node->next)
 534         Lst_Append(dst, node->datum);
 535 }
 536
 537 /*
 538  * these functions are for dealing with a list as a table, of sorts.
 539  * An idea of the "current element" is kept and used by all the functions
 540  * between Lst_Open() and Lst_Close().
 541  *
 542  * The sequential functions access the list in a slightly different way.
 543  * CurPtr points to their idea of the current node in the list and they
 544  * access the list based on it.
 545  */
 546
 547 /* Open a list for sequential access. A list can still be searched, etc.,
 548  * without confusing these functions. */
 549 void
 550 Lst_Open(Lst list)
 551 {
 552     assert(list != NULL);
 553     assert(!list->isOpen);
 554
 555     list->isOpen = TRUE;
 556     list->lastAccess = LstIsEmpty(list) ? Head : Unknown;
 557     list->curr = NULL;
 558 }
 559
 560 /* Return the next node for the given list, or NULL if the end has been
 561  * reached. */
 562 LstNode
 563 Lst_Next(Lst list)
 564 {
 565     LstNode node;
 566
 567     assert(list != NULL);
 568     assert(list->isOpen);
 569
 570     list->prev = list->curr;
 571
 572     if (list->curr == NULL) {
 573         if (list->lastAccess == Unknown) {
 574             /*
 575              * If we're just starting out, lastAccess will be Unknown.
 576              * Then we want to start this thing off in the right
 577              * direction -- at the start with lastAccess being Middle.
 578              */
 579             list->curr = node = list->first;
 580             list->lastAccess = Middle;
 581         } else {
 582             node = NULL;
 583             list->lastAccess = Tail;
 584         }
 585     } else {
 586         node = list->curr->next;
 587         list->curr = node;
 588
 589         if (node == list->first || node == NULL) {
 590             /*
 591              * If back at the front, then we've hit the end...
 592              */
 593             list->lastAccess = Tail;
 594         } else {
 595             /*
 596              * Reset to Middle if gone past first.
 597              */
 598             list->lastAccess = Middle;
 599         }
 600     }
 601
 602     return node;
 603 }
 604
 605 /* Close a list which was opened for sequential access. */
 606 void
 607 Lst_Close(Lst list)
 608 {
 609     assert(list != NULL);
 610     assert(list->isOpen);
 611
 612     list->isOpen = FALSE;
 613     list->lastAccess = Unknown;
 614 }
 615
 616
 617 /*
 618  * for using the list as a queue
 619  */
 620
 621 /* Add the datum to the tail of the given list. */
 622 void
 623 Lst_Enqueue(Lst list, void *datum)
 624 {
 625     Lst_Append(list, datum);
 626 }
 627
 628 /* Remove and return the datum at the head of the given list. */
 629 void *
 630 Lst_Dequeue(Lst list)
 631 {
 632     void *datum;
 633
 634     assert(list != NULL);
 635     assert(!LstIsEmpty(list));
 636
 637     datum = list->first->datum;
 638     Lst_Remove(list, list->first);
 639     assert(datum != NULL);
 640     return datum;
 641 }