1 /* 2 * Copyright (c) 1999, 2020, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 /** ------------------------------------------------------------------------ 26 This file contains routines for manipulating generic lists. 27 Lists are implemented with a "harness". In other words, each 28 node in the list consists of two pointers, one to the data item 29 and one to the next node in the list. The head of the list is 30 the same struct as each node, but the "item" ptr is used to point 31 to the current member of the list (used by the first_in_list and 32 next_in_list functions). 33 34 This file is available under and governed by the GNU General Public 35 License version 2 only, as published by the Free Software Foundation. 36 However, the following notice accompanied the original version of this 37 file: 38 39 Copyright 1994 Hewlett-Packard Co. 40 Copyright 1996, 1998 The Open Group 41 42 Permission to use, copy, modify, distribute, and sell this software and its 43 documentation for any purpose is hereby granted without fee, provided that 44 the above copyright notice appear in all copies and that both that 45 copyright notice and this permission notice appear in supporting 46 documentation. 47 48 The above copyright notice and this permission notice shall be included 49 in all copies or substantial portions of the Software. 50 51 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 52 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 53 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 54 IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR 55 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 56 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 57 OTHER DEALINGS IN THE SOFTWARE. 58 59 Except as contained in this notice, the name of The Open Group shall 60 not be used in advertising or otherwise to promote the sale, use or 61 other dealings in this Software without prior written authorization 62 from The Open Group. 63 64 ----------------------------------------------------------------------- **/ 65 66 #ifdef HEADLESS 67 #error This file should not be included in headless library 68 #endif 69 70 #include <stdio.h> 71 #include <stdlib.h> 72 73 #include "list.h" 74 75 76 /** ------------------------------------------------------------------------ 77 Sets the pointers of the specified list to NULL. 78 --------------------------------------------------------------------- **/ 79 void zero_list(list_ptr lp) 80 { 81 lp->next = NULL; 82 lp->ptr.item = NULL; 83 } 84 85 86 /** ------------------------------------------------------------------------ 87 Adds item to the list pointed to by lp. Finds the end of the 88 list, then mallocs a new list node onto the end of the list. 89 The item pointer in the new node is set to "item" passed in, 90 and the next pointer in the new node is set to NULL. 91 Returns 1 if successful, 0 if the malloc failed. 92 -------------------------------------------------------------------- **/ 93 int add_to_list(list_ptr lp, void *item) 94 { 95 while (lp->next) { 96 lp = lp->next; 97 } 98 if ((lp->next = (list_ptr) malloc( sizeof( list_item))) == NULL) { 99 100 return 0; 101 } 102 lp->next->ptr.item = item; 103 lp->next->next = NULL; 104 105 return 1; 106 } 107 108 109 /** ------------------------------------------------------------------------ 110 Creates a new list and sets its pointers to NULL. 111 Returns a pointer to the new list. 112 -------------------------------------------------------------------- **/ 113 list_ptr new_list (void) 114 { 115 list_ptr lp; 116 117 if ((lp = (list_ptr) malloc( sizeof( list_item)))) { 118 lp->next = NULL; 119 lp->ptr.item = NULL; 120 } 121 122 return lp; 123 } 124 125 126 /** ------------------------------------------------------------------------ 127 Creates a new list head, pointing to the same list as the one 128 passed in. If start_at_curr is TRUE, the new list's first item 129 is the "current" item (as set by calls to first/next_in_list()). 130 If start_at_curr is FALSE, the first item in the new list is the 131 same as the first item in the old list. In either case, the 132 curr pointer in the new list is the same as in the old list. 133 Returns a pointer to the new list head. 134 -------------------------------------------------------------------- **/ 135 list_ptr dup_list_head(list_ptr lp, int start_at_curr) 136 { 137 list_ptr new_listp; 138 139 if ((new_listp = (list_ptr) malloc( sizeof( list_item))) == NULL) { 140 141 return (list_ptr)NULL; 142 } 143 new_listp->next = start_at_curr ? lp->ptr.curr : lp->next; 144 new_listp->ptr.curr = lp->ptr.curr; 145 146 return new_listp; 147 } 148 149 150 /** ------------------------------------------------------------------------ 151 Returns the number of items in the list. 152 -------------------------------------------------------------------- **/ 153 unsigned int list_length(list_ptr lp) 154 { 155 unsigned int count = 0; 156 157 while (lp->next) { 158 count++; 159 lp = lp->next; 160 } 161 162 return count; 163 } 164 165 166 /** ------------------------------------------------------------------------ 167 Scans thru list, looking for a node whose ptr.item is equal to 168 the "item" passed in. "Equal" here means the same address - no 169 attempt is made to match equivalent values stored in different 170 locations. If a match is found, that node is deleted from the 171 list. Storage for the node is freed, but not for the item itself. 172 Returns a pointer to the item, so the caller can free it if it 173 so desires. If a match is not found, returns NULL. 174 -------------------------------------------------------------------- **/ 175 void *delete_from_list(list_ptr lp, void *item) 176 { 177 list_ptr new_next; 178 179 while (lp->next) { 180 if (lp->next->ptr.item == item) { 181 new_next = lp->next->next; 182 free (lp->next); 183 lp->next = new_next; 184 185 return item; 186 } 187 lp = lp->next; 188 } 189 190 return NULL; 191 } 192 193 194 /** ------------------------------------------------------------------------ 195 Deletes each node in the list *except the head*. This allows 196 the deletion of lists where the head is not malloced or created 197 with new_list(). If free_items is true, each item pointed to 198 from the node is freed, in addition to the node itself. 199 -------------------------------------------------------------------- **/ 200 void delete_list(list_ptr lp, int free_items) 201 { 202 list_ptr del_node; 203 void *item; 204 205 while (lp->next) { 206 del_node = lp->next; 207 item = del_node->ptr.item; 208 lp->next = del_node->next; 209 free (del_node); 210 if (free_items) { 211 free( item); 212 } 213 } 214 } 215 216 void delete_list_destroying(list_ptr lp, void destructor(void *item)) 217 { 218 list_ptr del_node; 219 void *item; 220 221 while (lp->next) { 222 del_node = lp->next; 223 item = del_node->ptr.item; 224 lp->next = del_node->next; 225 free( del_node); 226 if (destructor) { 227 destructor( item); 228 } 229 } 230 } 231 232 233 /** ------------------------------------------------------------------------ 234 Returns a ptr to the first *item* (not list node) in the list. 235 Sets the list head node's curr ptr to the first node in the list. 236 Returns NULL if the list is empty. 237 -------------------------------------------------------------------- **/ 238 void * first_in_list(list_ptr lp) 239 { 240 if (! lp) { 241 242 return NULL; 243 } 244 lp->ptr.curr = lp->next; 245 246 return lp->ptr.curr ? lp->ptr.curr->ptr.item : NULL; 247 } 248 249 /** ------------------------------------------------------------------------ 250 Returns a ptr to the next *item* (not list node) in the list. 251 Sets the list head node's curr ptr to the next node in the list. 252 first_in_list must have been called prior. 253 Returns NULL if no next item. 254 -------------------------------------------------------------------- **/ 255 void * next_in_list(list_ptr lp) 256 { 257 if (! lp) { 258 259 return NULL; 260 } 261 if (lp->ptr.curr) { 262 lp->ptr.curr = lp->ptr.curr->next; 263 } 264 265 return lp->ptr.curr ? lp->ptr.curr->ptr.item : NULL; 266 } 267 268 int list_is_empty(list_ptr lp) 269 { 270 return (lp == NULL || lp->next == NULL); 271 } 272