1141115Sharti/*- 2141115Sharti * Copyright (c) 1988, 1989, 1990, 1993 3141115Sharti * The Regents of the University of California. All rights reserved. 4141115Sharti * 5141115Sharti * This code is derived from software contributed to Berkeley by 6141115Sharti * Adam de Boor. 7141115Sharti * 8141115Sharti * Redistribution and use in source and binary forms, with or without 9141115Sharti * modification, are permitted provided that the following conditions 10141115Sharti * are met: 11141115Sharti * 1. Redistributions of source code must retain the above copyright 12141115Sharti * notice, this list of conditions and the following disclaimer. 13141115Sharti * 2. Redistributions in binary form must reproduce the above copyright 14141115Sharti * notice, this list of conditions and the following disclaimer in the 15141115Sharti * documentation and/or other materials provided with the distribution. 16141115Sharti * 3. Neither the name of the University nor the names of its contributors 17141115Sharti * may be used to endorse or promote products derived from this software 18141115Sharti * without specific prior written permission. 19141115Sharti * 20141115Sharti * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21141115Sharti * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22141115Sharti * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23141115Sharti * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24141115Sharti * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25141115Sharti * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26141115Sharti * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27141115Sharti * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28141115Sharti * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29141115Sharti * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30141115Sharti * SUCH DAMAGE. 31141115Sharti * 32141115Sharti * $FreeBSD$ 33141115Sharti */ 34141115Sharti 35141115Sharti/*- 36141115Sharti * lst.c -- 37141115Sharti * Routines to maintain a linked list of objects. 38141115Sharti */ 39141115Sharti 40141115Sharti#include <stdio.h> 41141115Sharti#include <stdlib.h> 42141115Sharti 43141115Sharti#include "lst.h" 44141115Sharti#include "util.h" 45141115Sharti 46144470Sharti/** 47144470Sharti * Lst_Append 48141115Sharti * Create a new node and add it to the given list after the given node. 49141115Sharti * 50141115Sharti * Arguments: 51141115Sharti * l affected list 52141115Sharti * ln node after which to append the datum 53141115Sharti * d said datum 54141115Sharti * 55141115Sharti * Side Effects: 56141115Sharti * A new LstNode is created and linked in to the List. The lastPtr 57141115Sharti * field of the List will be altered if ln is the last node in the 58141115Sharti * list. lastPtr and firstPtr will alter if the list was empty and 59141115Sharti * ln was NULL. 60141115Sharti */ 61141115Shartivoid 62141115ShartiLst_Append(Lst *list, LstNode *ln, void *d) 63141115Sharti{ 64144470Sharti LstNode *nLNode; 65141115Sharti 66144470Sharti nLNode = emalloc(sizeof(*nLNode)); 67144470Sharti nLNode->datum = d; 68141115Sharti 69144470Sharti if (ln == NULL) { 70144470Sharti nLNode->nextPtr = nLNode->prevPtr = NULL; 71144470Sharti list->firstPtr = list->lastPtr = nLNode; 72144470Sharti } else { 73144470Sharti nLNode->prevPtr = ln; 74144470Sharti nLNode->nextPtr = ln->nextPtr; 75141115Sharti 76144470Sharti ln->nextPtr = nLNode; 77144470Sharti if (nLNode->nextPtr != NULL) { 78144470Sharti nLNode->nextPtr->prevPtr = nLNode; 79144470Sharti } 80141115Sharti 81144470Sharti if (ln == list->lastPtr) { 82144470Sharti list->lastPtr = nLNode; 83144470Sharti } 84141115Sharti } 85141115Sharti} 86141115Sharti 87144470Sharti/** 88144470Sharti * Lst_Concat 89141115Sharti * Concatenate two lists. New elements are created to hold the data 90141115Sharti * elements, if specified, but the elements themselves are not copied. 91141115Sharti * If the elements should be duplicated to avoid confusion with another 92141115Sharti * list, the Lst_Duplicate function should be called first. 93141115Sharti * 94141115Sharti * Arguments: 95141115Sharti * list1 The list to which list2 is to be appended 96141115Sharti * list2 The list to append to list1 97141115Sharti * flags LST_CONCNEW if LstNode's should be duplicated 98141115Sharti * LST_CONCLINK if should just be relinked 99141115Sharti * 100141115Sharti * Side Effects: 101218909Sbrucec * New elements are created and appended the first list. 102141115Sharti */ 103141115Shartivoid 104141115ShartiLst_Concat(Lst *list1, Lst *list2, int flags) 105141115Sharti{ 106144470Sharti LstNode *ln; /* original LstNode */ 107144470Sharti LstNode *nln; /* new LstNode */ 108144470Sharti LstNode *last; /* the last element in the list. Keeps 109141115Sharti * bookkeeping until the end */ 110141115Sharti 111144470Sharti if (list2->firstPtr == NULL) 112144470Sharti return; 113141115Sharti 114144470Sharti if (flags == LST_CONCLINK) { 115144470Sharti /* 116144470Sharti * Link the first element of the second list to the last 117144470Sharti * element of the first list. If the first list isn't empty, 118144470Sharti * we then link the last element of the list to the first 119144470Sharti * element of the second list. The last element of the second 120144470Sharti * list, if it exists, then becomes the last element of the 121144470Sharti * first list. 122144470Sharti */ 123144470Sharti list2->firstPtr->prevPtr = list1->lastPtr; 124144470Sharti if (list1->lastPtr != NULL) 125144470Sharti list1->lastPtr->nextPtr = list2->firstPtr; 126144470Sharti else 127144470Sharti list1->firstPtr = list2->firstPtr; 128144470Sharti list1->lastPtr = list2->lastPtr; 129141115Sharti 130144470Sharti Lst_Init(list2); 131144470Sharti } else { 132144470Sharti /* 133144470Sharti * The loop simply goes through the entire second list creating 134144470Sharti * new LstNodes and filling in the nextPtr, and prevPtr to fit 135144470Sharti * into list1 and its datum field from the datum field of the 136144470Sharti * corresponding element in list2. The 'last' node follows the 137144470Sharti * last of the new nodes along until the entire list2 has been 138144470Sharti * appended. Only then does the bookkeeping catch up with the 139144470Sharti * changes. During the first iteration of the loop, if 'last' 140144470Sharti * is NULL, the first list must have been empty so the 141144470Sharti * newly-created node is made the first node of the list. 142144470Sharti */ 143144470Sharti for (last = list1->lastPtr, ln = list2->firstPtr; 144144470Sharti ln != NULL; 145144470Sharti ln = ln->nextPtr) { 146144470Sharti nln = emalloc(sizeof(*nln)); 147144470Sharti nln->datum = ln->datum; 148144470Sharti if (last != NULL) { 149144470Sharti last->nextPtr = nln; 150144470Sharti } else { 151144470Sharti list1->firstPtr = nln; 152144470Sharti } 153144470Sharti nln->prevPtr = last; 154144470Sharti last = nln; 155144470Sharti } 156144470Sharti 157144470Sharti /* 158144470Sharti * Finish bookkeeping. The last new element becomes the last 159144470Sharti * element of list one. 160144470Sharti */ 161144470Sharti list1->lastPtr = last; 162144470Sharti last->nextPtr = NULL; 163141115Sharti } 164141115Sharti} 165141115Sharti 166144470Sharti/** 167144470Sharti * Lst_DeQueue 168141115Sharti * Remove and return the datum at the head of the given list. 169141115Sharti * 170141115Sharti * Results: 171141115Sharti * The datum in the node at the head or (ick) NULL if the list 172141115Sharti * is empty. 173141115Sharti * 174141115Sharti * Side Effects: 175141115Sharti * The head node is removed from the list. 176141115Sharti */ 177141115Shartivoid * 178141115ShartiLst_DeQueue(Lst *l) 179141115Sharti{ 180144470Sharti void *rd; 181144470Sharti LstNode *tln; 182141115Sharti 183144470Sharti tln = Lst_First(l); 184144470Sharti if (tln == NULL) { 185144470Sharti return (NULL); 186144470Sharti } 187141115Sharti 188144470Sharti rd = tln->datum; 189144470Sharti Lst_Remove(l, tln); 190144470Sharti return (rd); 191141115Sharti} 192141115Sharti 193144470Sharti/** 194144470Sharti * Lst_Destroy 195141115Sharti * Destroy a list and free all its resources. If the freeProc is 196141115Sharti * given, it is called with the datum from each node in turn before 197141115Sharti * the node is freed. 198141115Sharti * 199141115Sharti * Side Effects: 200141115Sharti * The given list is freed in its entirety. 201141115Sharti */ 202141115Shartivoid 203141115ShartiLst_Destroy(Lst *list, FreeProc *freeProc) 204141115Sharti{ 205144470Sharti LstNode *ln; 206141115Sharti 207144470Sharti if (list->firstPtr == NULL) 208144470Sharti return; 209141115Sharti 210144470Sharti if (freeProc != NOFREE) { 211144470Sharti while ((ln = list->firstPtr) != NULL) { 212144470Sharti list->firstPtr = ln->nextPtr; 213144470Sharti (*freeProc)(ln->datum); 214144470Sharti free(ln); 215144470Sharti } 216144470Sharti } else { 217144470Sharti while ((ln = list->firstPtr) != NULL) { 218144470Sharti list->firstPtr = ln->nextPtr; 219144470Sharti free(ln); 220144470Sharti } 221141115Sharti } 222144470Sharti list->lastPtr = NULL; 223141115Sharti} 224141115Sharti 225144470Sharti/** 226144470Sharti * Lst_Duplicate 227141115Sharti * Duplicate an entire list. If a function to copy a void * is 228141115Sharti * given, the individual client elements will be duplicated as well. 229141115Sharti * 230141115Sharti * Arguments: 231141115Sharti * dst the destination list (initialized) 232141115Sharti * src the list to duplicate 233141115Sharti * copyProc A function to duplicate each void 234141115Sharti */ 235141115Shartivoid 236141115ShartiLst_Duplicate(Lst *dst, Lst *src, DuplicateProc *copyProc) 237141115Sharti{ 238144470Sharti LstNode *ln; 239141115Sharti 240144470Sharti ln = src->firstPtr; 241144470Sharti while (ln != NULL) { 242144470Sharti if (copyProc != NOCOPY) 243144470Sharti Lst_AtEnd(dst, (*copyProc)(ln->datum)); 244144470Sharti else 245144470Sharti Lst_AtEnd(dst, ln->datum); 246144470Sharti ln = ln->nextPtr; 247144470Sharti } 248141115Sharti} 249141115Sharti 250144470Sharti/** 251144470Sharti * Lst_Insert 252141115Sharti * Insert a new node with the given piece of data before the given 253141115Sharti * node in the given list. 254141115Sharti * 255141115Sharti * Parameters: 256141115Sharti * l list to manipulate 257141115Sharti * ln node before which to insert d 258141115Sharti * d datum to be inserted 259141115Sharti * 260141115Sharti * Side Effects: 261141115Sharti * the firstPtr field will be changed if ln is the first node in the 262141115Sharti * list. 263141115Sharti */ 264141115Shartivoid 265141115ShartiLst_Insert(Lst *list, LstNode *ln, void *d) 266141115Sharti{ 267144470Sharti LstNode *nLNode; /* new lnode for d */ 268141115Sharti 269144470Sharti nLNode = emalloc(sizeof(*nLNode)); 270144470Sharti nLNode->datum = d; 271141115Sharti 272144470Sharti if (ln == NULL) { 273144470Sharti nLNode->prevPtr = nLNode->nextPtr = NULL; 274144470Sharti list->firstPtr = list->lastPtr = nLNode; 275144470Sharti } else { 276144470Sharti nLNode->prevPtr = ln->prevPtr; 277144470Sharti nLNode->nextPtr = ln; 278141115Sharti 279144470Sharti if (nLNode->prevPtr != NULL) { 280144470Sharti nLNode->prevPtr->nextPtr = nLNode; 281144470Sharti } 282144470Sharti ln->prevPtr = nLNode; 283141115Sharti 284144470Sharti if (ln == list->firstPtr) { 285144470Sharti list->firstPtr = nLNode; 286144470Sharti } 287141115Sharti } 288141115Sharti} 289141115Sharti 290141115ShartiLstNode * 291141115ShartiLst_Member(Lst *list, void *d) 292141115Sharti{ 293144470Sharti LstNode *lNode; 294141115Sharti 295144470Sharti lNode = list->firstPtr; 296144470Sharti if (lNode == NULL) { 297144470Sharti return (NULL); 298141115Sharti } 299141115Sharti 300144470Sharti do { 301144470Sharti if (lNode->datum == d) { 302144470Sharti return (lNode); 303144470Sharti } 304144470Sharti lNode = lNode->nextPtr; 305144470Sharti } while (lNode != NULL && lNode != list->firstPtr); 306144470Sharti 307144470Sharti return (NULL); 308141115Sharti} 309141115Sharti 310144470Sharti/** 311144470Sharti * Lst_Remove 312141115Sharti * Remove the given node from the given list. 313141115Sharti * 314141115Sharti * Side Effects: 315141115Sharti * The list's firstPtr will be set to NULL if ln is the last 316141115Sharti * node on the list. firsPtr and lastPtr will be altered if ln is 317141115Sharti * either the first or last node, respectively, on the list. 318141115Sharti */ 319141115Shartivoid 320141115ShartiLst_Remove(Lst *list, LstNode *ln) 321141115Sharti{ 322144470Sharti /* 323144470Sharti * unlink it from the list 324144470Sharti */ 325144470Sharti if (ln->nextPtr != NULL) 326144470Sharti /* unlink from the backward chain */ 327144470Sharti ln->nextPtr->prevPtr = ln->prevPtr; 328144470Sharti else 329144470Sharti /* this was the last element */ 330144470Sharti list->lastPtr = ln->prevPtr; 331141115Sharti 332144470Sharti if (ln->prevPtr != NULL) 333144470Sharti /* unlink from the forward chain */ 334144470Sharti ln->prevPtr->nextPtr = ln->nextPtr; 335144470Sharti else 336144470Sharti /* this was the first element */ 337144470Sharti list->firstPtr = ln->nextPtr; 338141115Sharti 339144470Sharti /* 340144470Sharti * note that the datum is unmolested. The caller must free it as 341144470Sharti * necessary and as expected. 342144470Sharti */ 343144470Sharti free(ln); 344141115Sharti} 345