1/* ========================================================================== ** 2 * ubi_sLinkList.c 3 * 4 * Copyright (C) 1997, 1998 by Christopher R. Hertel 5 * 6 * Email: crh@ubiqx.mn.org 7 * -------------------------------------------------------------------------- ** 8 * This module implements a simple singly-linked list. 9 * -------------------------------------------------------------------------- ** 10 * 11 * This library is free software; you can redistribute it and/or 12 * modify it under the terms of the GNU Library General Public 13 * License as published by the Free Software Foundation; either 14 * version 2 of the License, or (at your option) any later version. 15 * 16 * This library is distributed in the hope that it will be useful, 17 * but WITHOUT ANY WARRANTY; without even the implied warranty of 18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 19 * Library General Public License for more details. 20 * 21 * You should have received a copy of the GNU Library General Public 22 * License along with this library; if not, write to the Free 23 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 24 * 25 * -------------------------------------------------------------------------- ** 26 * 27 * Log: ubi_sLinkList.c,v 28 * Revision 0.10 1999/06/19 16:58:06 crh 29 * Renamed the ubi_slRemove() function in ubi_sLinkList to 30 * ubi_slRemoveNext(). I was bothered by the fact that it didn't 31 * match the functionality of the ubi_dlRemove() function in 32 * ubi_dLinkList. The new name is more 'correct'. 33 * 34 * Revision 0.9 1998/07/24 07:30:20 crh 35 * Added the ubi_slNewList() macro. 36 * 37 * Revision 0.8 1998/06/04 21:29:27 crh 38 * Upper-cased defined constants (eg UBI_BINTREE_H) in some header files. 39 * This is more "standard", and is what people expect. Weird, eh? 40 * 41 * Revision 0.7 1998/06/03 18:06:03 crh 42 * Further fiddling with sys_include.h, which has been moved from the .c file 43 * to the .h file. 44 * 45 * Revision 0.6 1998/06/02 01:38:47 crh 46 * Changed include file name from ubi_null.h to sys_include.h to make it 47 * more generic. 48 * 49 * Revision 0.5 1998/05/20 04:38:05 crh 50 * The C file now includes ubi_null.h. See ubi_null.h for more info. 51 * 52 * Revision 0.4 1998/03/10 02:23:20 crh 53 * Combined ubi_StackQueue and ubi_sLinkList into one module. Redesigned 54 * the functions and macros. Not a complete rewrite but close to it. 55 * 56 * Revision 0.3 1998/01/03 01:59:52 crh 57 * Added ubi_slCount() macro. 58 * 59 * Revision 0.2 1997/10/21 03:35:18 crh 60 * Added parameter <After> in function Insert(). Made necessary changes 61 * to macro AddHead() and added macro AddHere(). 62 * 63 * Revision 0.1 1997/10/16 02:53:45 crh 64 * Initial Revision. 65 * 66 * -------------------------------------------------------------------------- ** 67 * This module implements a singly-linked list which may also be used as a 68 * queue or a stack. For a queue, entries are added at the tail and removed 69 * from the head of the list. For a stack, the entries are entered and 70 * removed from the head of the list. A traversal of the list will always 71 * start at the head of the list and proceed toward the tail. This is all 72 * mind-numbingly simple, but I'm surprised by the number of programs out 73 * there which re-implement this a dozen or so times. 74 * 75 * Note: When the list header is initialized, the Tail pointer is set to 76 * point to the Head pointer. This simplifies things a great deal, 77 * except that you can't initialize a stack or queue by simply 78 * zeroing it out. One sure way to initialize the header is to call 79 * ubi_slInit(). Another option would be something like this: 80 * 81 * ubi_slNewList( MyList ); 82 * 83 * Which translates to: 84 * 85 * ubi_slList MyList[1] = { NULL, (ubi_slNodePtr)MyList, 0 }; 86 * 87 * See ubi_slInit(), ubi_slNewList(), and the ubi_slList structure 88 * for more info. 89 * 90 * + Also, note that this module is similar to the ubi_dLinkList 91 * module. There are three key differences: 92 * - This is a singly-linked list, the other is a doubly-linked 93 * list. 94 * - In this module, if the list is empty, the tail pointer will 95 * point back to the head of the list as described above. This 96 * is not done in ubi_dLinkList. 97 * - The ubi_slRemoveNext() function, by necessity, removes the 98 * 'next' node. In ubi_dLinkList, the ubi_dlRemove() function 99 * removes the 'current' node. 100 * 101 * ========================================================================== ** 102 */ 103 104#include "ubi_sLinkList.h" /* Header for *this* module. */ 105 106/* ========================================================================== ** 107 * Functions... 108 */ 109 110ubi_slListPtr ubi_slInitList( ubi_slListPtr ListPtr ) 111 /* ------------------------------------------------------------------------ ** 112 * Initialize a singly-linked list header. 113 * 114 * Input: ListPtr - A pointer to the list structure that is to be 115 * initialized for use. 116 * 117 * Output: A pointer to the initialized list header (i.e., same as 118 * <ListPtr>). 119 * 120 * ------------------------------------------------------------------------ ** 121 */ 122 { 123 ListPtr->Head = NULL; 124 ListPtr->Tail = (ubi_slNodePtr)ListPtr; 125 ListPtr->count = 0; 126 return( ListPtr ); 127 } /* ubi_slInitList */ 128 129ubi_slNodePtr ubi_slInsert( ubi_slListPtr ListPtr, 130 ubi_slNodePtr New, 131 ubi_slNodePtr After ) 132 /* ------------------------------------------------------------------------ ** 133 * Add a node to the list. 134 * 135 * Input: ListPtr - A pointer to the list into which the node is to 136 * be inserted. 137 * New - Pointer to the node that is to be added to the list. 138 * After - Pointer to a list in a node after which the new node 139 * will be inserted. If NULL, then the new node will 140 * be added at the head of the list. 141 * 142 * Output: A pointer to the node that was inserted into the list (i.e., 143 * the same as <New>). 144 * 145 * ------------------------------------------------------------------------ ** 146 */ 147 { 148 After = After ? After : (ubi_slNodePtr)ListPtr; 149 New->Next = After->Next; 150 After->Next = New; 151 if( !(New->Next) ) 152 ListPtr->Tail = New; 153 (ListPtr->count)++; 154 return( New ); 155 } /* ubi_slInsert */ 156 157ubi_slNodePtr ubi_slRemoveNext( ubi_slListPtr ListPtr, ubi_slNodePtr AfterMe ) 158 /* ------------------------------------------------------------------------ ** 159 * Remove the node followng <AfterMe>. If <AfterMe> is NULL, remove from 160 * the head of the list. 161 * 162 * Input: ListPtr - A pointer to the list from which the node is to be 163 * removed. 164 * AfterMe - Pointer to the node preceeding the node to be 165 * removed. 166 * 167 * Output: A pointer to the node that was removed, or NULL if the list is 168 * empty. 169 * 170 * ------------------------------------------------------------------------ ** 171 */ 172 { 173 ubi_slNodePtr DelNode; 174 175 AfterMe = AfterMe ? AfterMe : (ubi_slNodePtr)ListPtr; 176 DelNode = AfterMe->Next; 177 if( DelNode ) 178 { 179 if( !(DelNode->Next) ) 180 ListPtr->Tail = AfterMe; 181 AfterMe->Next = DelNode->Next; 182 (ListPtr->count)--; 183 } 184 return( DelNode ); 185 } /* ubi_slRemoveNext */ 186 187/* ================================ The End ================================= */ 188