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