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