1 /*
2 * Copyright (c) 1999, 2018, 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 #include <stdio.h>
67 #include <stdlib.h>
68
69 #include "list.h"
70
71
72 /** ------------------------------------------------------------------------
73 Sets the pointers of the specified list to NULL.
74 --------------------------------------------------------------------- **/
75 void zero_list(list_ptr lp)
76 {
77 lp->next = NULL;
78 lp->ptr.item = NULL;
79 }
80
81
82 /** ------------------------------------------------------------------------
83 Adds item to the list pointed to by lp. Finds the end of the
84 list, then mallocs a new list node onto the end of the list.
85 The item pointer in the new node is set to "item" passed in,
86 and the next pointer in the new node is set to NULL.
87 Returns 1 if successful, 0 if the malloc failed.
88 -------------------------------------------------------------------- **/
89 int add_to_list(list_ptr lp, void *item)
90 {
91 while (lp->next) {
92 lp = lp->next;
93 }
94 if ((lp->next = (list_ptr) malloc( sizeof( list_item))) == NULL) {
95
96 return 0;
97 }
98 lp->next->ptr.item = item;
99 lp->next->next = NULL;
100
101 return 1;
102 }
103
104
105 /** ------------------------------------------------------------------------
106 Creates a new list and sets its pointers to NULL.
107 Returns a pointer to the new list.
108 -------------------------------------------------------------------- **/
109 list_ptr new_list (void)
110 {
111 list_ptr lp;
112
113 if ((lp = (list_ptr) malloc( sizeof( list_item)))) {
114 lp->next = NULL;
115 lp->ptr.item = NULL;
116 }
117
118 return lp;
119 }
120
121
122 /** ------------------------------------------------------------------------
123 Creates a new list head, pointing to the same list as the one
124 passed in. If start_at_curr is TRUE, the new list's first item
125 is the "current" item (as set by calls to first/next_in_list()).
126 If start_at_curr is FALSE, the first item in the new list is the
127 same as the first item in the old list. In either case, the
128 curr pointer in the new list is the same as in the old list.
129 Returns a pointer to the new list head.
130 -------------------------------------------------------------------- **/
131 list_ptr dup_list_head(list_ptr lp, int start_at_curr)
132 {
133 list_ptr new_listp;
134
135 if ((new_listp = (list_ptr) malloc( sizeof( list_item))) == NULL) {
136
137 return (list_ptr)NULL;
138 }
139 new_listp->next = start_at_curr ? lp->ptr.curr : lp->next;
140 new_listp->ptr.curr = lp->ptr.curr;
141
142 return new_listp;
143 }
144
145
146 /** ------------------------------------------------------------------------
147 Returns the number of items in the list.
148 -------------------------------------------------------------------- **/
149 unsigned int list_length(list_ptr lp)
150 {
151 unsigned int count = 0;
152
153 while (lp->next) {
154 count++;
155 lp = lp->next;
156 }
157
158 return count;
159 }
160
161
162 /** ------------------------------------------------------------------------
163 Scans thru list, looking for a node whose ptr.item is equal to
164 the "item" passed in. "Equal" here means the same address - no
165 attempt is made to match equivalent values stored in different
166 locations. If a match is found, that node is deleted from the
167 list. Storage for the node is freed, but not for the item itself.
168 Returns a pointer to the item, so the caller can free it if it
169 so desires. If a match is not found, returns NULL.
170 -------------------------------------------------------------------- **/
171 void *delete_from_list(list_ptr lp, void *item)
172 {
173 list_ptr new_next;
174
175 while (lp->next) {
176 if (lp->next->ptr.item == item) {
177 new_next = lp->next->next;
178 free (lp->next);
179 lp->next = new_next;
180
181 return item;
182 }
183 lp = lp->next;
184 }
185
186 return NULL;
187 }
188
189
190 /** ------------------------------------------------------------------------
191 Deletes each node in the list *except the head*. This allows
192 the deletion of lists where the head is not malloced or created
193 with new_list(). If free_items is true, each item pointed to
194 from the node is freed, in addition to the node itself.
195 -------------------------------------------------------------------- **/
196 void delete_list(list_ptr lp, int free_items)
197 {
198 list_ptr del_node;
199 void *item;
200
201 while (lp->next) {
202 del_node = lp->next;
203 item = del_node->ptr.item;
204 lp->next = del_node->next;
205 free (del_node);
206 if (free_items) {
207 free( item);
208 }
209 }
210 }
211
212 void delete_list_destroying(list_ptr lp, void destructor(void *item))
213 {
214 list_ptr del_node;
215 void *item;
216
217 while (lp->next) {
218 del_node = lp->next;
219 item = del_node->ptr.item;
220 lp->next = del_node->next;
221 free( del_node);
222 if (destructor) {
223 destructor( item);
224 }
225 }
226 }
227
228
229 /** ------------------------------------------------------------------------
230 Returns a ptr to the first *item* (not list node) in the list.
231 Sets the list head node's curr ptr to the first node in the list.
232 Returns NULL if the list is empty.
233 -------------------------------------------------------------------- **/
234 void * first_in_list(list_ptr lp)
235 {
236 if (! lp) {
237
238 return NULL;
239 }
240 lp->ptr.curr = lp->next;
241
242 return lp->ptr.curr ? lp->ptr.curr->ptr.item : NULL;
243 }
244
245 /** ------------------------------------------------------------------------
246 Returns a ptr to the next *item* (not list node) in the list.
247 Sets the list head node's curr ptr to the next node in the list.
248 first_in_list must have been called prior.
249 Returns NULL if no next item.
250 -------------------------------------------------------------------- **/
251 void * next_in_list(list_ptr lp)
252 {
253 if (! lp) {
254
255 return NULL;
256 }
257 if (lp->ptr.curr) {
258 lp->ptr.curr = lp->ptr.curr->next;
259 }
260
261 return lp->ptr.curr ? lp->ptr.curr->ptr.item : NULL;
262 }
263
264 int list_is_empty(list_ptr lp)
265 {
266 return (lp == NULL || lp->next == NULL);
267 }
268