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 "list.h"
71
72
73 /** ------------------------------------------------------------------------
74 Sets the pointers of the specified list to NULL.
75 --------------------------------------------------------------------- **/
76 #if NeedFunctionPrototypes
77 void zero_list(list_ptr lp)
78 #else
79 void zero_list(lp)
80 list_ptr lp;
81 #endif
82 {
83 lp->next = NULL;
84 lp->ptr.item = NULL;
85 }
86
87
88 /** ------------------------------------------------------------------------
89 Adds item to the list pointed to by lp. Finds the end of the
90 list, then mallocs a new list node onto the end of the list.
91 The item pointer in the new node is set to "item" passed in,
92 and the next pointer in the new node is set to NULL.
93 Returns 1 if successful, 0 if the malloc failed.
94 -------------------------------------------------------------------- **/
95 #if NeedFunctionPrototypes
96 int32_t add_to_list(list_ptr lp, void *item)
97 #else
98 int32_t add_to_list(lp, item)
99 list_ptr lp;
100 void *item;
101 #endif
102 {
103 while (lp->next) {
104 lp = lp->next;
105 }
106
107 lp->next = (list_ptr) malloc(sizeof(list_item));
108 if (lp->next == NULL) {
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;
125
126 lp = (list_ptr) malloc(sizeof(list_item));
127 if (lp) {
128 lp->next = NULL;
129 lp->ptr.item = NULL;
130 }
131
132 return lp;
133 }
134
135
136 /** ------------------------------------------------------------------------
137 Creates a new list head, pointing to the same list as the one
138 passed in. If start_at_curr is TRUE, the new list's first item
139 is the "current" item (as set by calls to first/next_in_list()).
140 If start_at_curr is FALSE, the first item in the new list is the
141 same as the first item in the old list. In either case, the
142 curr pointer in the new list is the same as in the old list.
143 Returns a pointer to the new list head.
144 -------------------------------------------------------------------- **/
145 #if NeedFunctionPrototypes
146 list_ptr dup_list_head(list_ptr lp, int32_t start_at_curr)
147 #else
148 list_ptr dup_list_head(lp, start_at_curr)
149 list_ptr lp;
150 int32_t start_at_curr;
151 #endif
152 {
153 list_ptr new_list;
154
155 if ((new_list = (list_ptr) malloc( sizeof( list_item))) == NULL) {
156
157 return (list_ptr)NULL;
158 }
159 new_list->next = start_at_curr ? lp->ptr.curr : lp->next;
160 new_list->ptr.curr = lp->ptr.curr;
161
162 return new_list;
163 }
164
165
166 /** ------------------------------------------------------------------------
167 Returns the number of items in the list.
168 -------------------------------------------------------------------- **/
169 #if NeedFunctionPrototypes
170 uint32_t list_length(list_ptr lp)
171 #else
172 uint32_t list_length(lp)
173 list_ptr lp;
174 #endif
175 {
176 uint32_t count = 0;
177
178 while (lp->next) {
179 count++;
180 lp = lp->next;
181 }
182
183 return count;
184 }
185
186
187 /** ------------------------------------------------------------------------
188 Scans thru list, looking for a node whose ptr.item is equal to
189 the "item" passed in. "Equal" here means the same address - no
190 attempt is made to match equivalent values stored in different
191 locations. If a match is found, that node is deleted from the
192 list. Storage for the node is freed, but not for the item itself.
193 Returns a pointer to the item, so the caller can free it if it
194 so desires. If a match is not found, returns NULL.
195 -------------------------------------------------------------------- **/
196 #if NeedFunctionPrototypes
197 void *delete_from_list(list_ptr lp, void *item)
198 #else
199 void *delete_from_list(lp, item)
200 list_ptr lp;
201 void *item;
202 #endif
203 {
204 list_ptr new_next;
205
206 while (lp->next) {
207 if (lp->next->ptr.item == item) {
208 new_next = lp->next->next;
209 free (lp->next);
210 lp->next = new_next;
211
212 return item;
213 }
214 lp = lp->next;
215 }
216
217 return NULL;
218 }
219
220
221 /** ------------------------------------------------------------------------
222 Deletes each node in the list *except the head*. This allows
223 the deletion of lists where the head is not malloced or created
224 with new_list(). If free_items is true, each item pointed to
225 from the node is freed, in addition to the node itself.
226 -------------------------------------------------------------------- **/
227 #if NeedFunctionPrototypes
228 void delete_list(list_ptr lp, int32_t free_items)
229 #else
230 void delete_list(lp, free_items)
231 list_ptr lp;
232 int32_t free_items;
233 #endif
234 {
235 list_ptr del_node;
236 void *item;
237
238 while (lp->next) {
239 del_node = lp->next;
240 item = del_node->ptr.item;
241 lp->next = del_node->next;
242 free (del_node);
243 if (free_items) {
244 free( item);
245 }
246 }
247 }
248
249 #if NeedFunctionPrototypes
250 void delete_list_destroying(list_ptr lp, void destructor(void *item))
251 #else
252 void delete_list_destroying(lp, destructor)
253 list_ptr lp;
254 void (*destructor)();
255 #endif
256 {
257 list_ptr del_node;
258 void *item;
259
260 while (lp->next) {
261 del_node = lp->next;
262 item = del_node->ptr.item;
263 lp->next = del_node->next;
264 free( del_node);
265 if (destructor) {
266 destructor( item);
267 }
268 }
269 }
270
271
272 /** ------------------------------------------------------------------------
273 Returns a ptr to the first *item* (not list node) in the list.
274 Sets the list head node's curr ptr to the first node in the list.
275 Returns NULL if the list is empty.
276 -------------------------------------------------------------------- **/
277 #if NeedFunctionPrototypes
278 void * first_in_list(list_ptr lp)
279 #else
280 void * first_in_list(lp)
281 list_ptr lp;
282 #endif
283 {
284 if (! lp) {
285
286 return NULL;
287 }
288 lp->ptr.curr = lp->next;
289
290 return lp->ptr.curr ? lp->ptr.curr->ptr.item : NULL;
291 }
292
293 /** ------------------------------------------------------------------------
294 Returns a ptr to the next *item* (not list node) in the list.
295 Sets the list head node's curr ptr to the next node in the list.
296 first_in_list must have been called prior.
297 Returns NULL if no next item.
298 -------------------------------------------------------------------- **/
299 #if NeedFunctionPrototypes
300 void * next_in_list(list_ptr lp)
301 #else
302 void * next_in_list(lp)
303 list_ptr lp;
304 #endif
305 {
306 if (! lp) {
307
308 return NULL;
309 }
310 if (lp->ptr.curr) {
311 lp->ptr.curr = lp->ptr.curr->next;
312 }
313
314 return lp->ptr.curr ? lp->ptr.curr->ptr.item : NULL;
315 }
316
317 #if NeedFunctionPrototypes
318 int32_t list_is_empty(list_ptr lp)
319 #else
320 int32_t list_is_empty(lp)
321 list_ptr lp;
322 #endif
323 {
324 return (lp == NULL || lp->next == NULL);
325 }