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