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