1*0Sstevel@tonic-gate /*
2*0Sstevel@tonic-gate * CDDL HEADER START
3*0Sstevel@tonic-gate *
4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
7*0Sstevel@tonic-gate * with the License.
8*0Sstevel@tonic-gate *
9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
11*0Sstevel@tonic-gate * See the License for the specific language governing permissions
12*0Sstevel@tonic-gate * and limitations under the License.
13*0Sstevel@tonic-gate *
14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
19*0Sstevel@tonic-gate *
20*0Sstevel@tonic-gate * CDDL HEADER END
21*0Sstevel@tonic-gate */
22*0Sstevel@tonic-gate /*
23*0Sstevel@tonic-gate * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
24*0Sstevel@tonic-gate * Use is subject to license terms.
25*0Sstevel@tonic-gate */
26*0Sstevel@tonic-gate
27*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI"
28*0Sstevel@tonic-gate
29*0Sstevel@tonic-gate /*
30*0Sstevel@tonic-gate * Routines for manipulating linked lists
31*0Sstevel@tonic-gate */
32*0Sstevel@tonic-gate
33*0Sstevel@tonic-gate #include <stdio.h>
34*0Sstevel@tonic-gate #include <assert.h>
35*0Sstevel@tonic-gate #include <stdlib.h>
36*0Sstevel@tonic-gate
37*0Sstevel@tonic-gate #include "list.h"
38*0Sstevel@tonic-gate #include "memory.h"
39*0Sstevel@tonic-gate
40*0Sstevel@tonic-gate struct list {
41*0Sstevel@tonic-gate void *l_data;
42*0Sstevel@tonic-gate struct list *l_next;
43*0Sstevel@tonic-gate };
44*0Sstevel@tonic-gate
45*0Sstevel@tonic-gate /* Add an element to a list */
46*0Sstevel@tonic-gate void
list_add(list_t ** list,void * data)47*0Sstevel@tonic-gate list_add(list_t **list, void *data)
48*0Sstevel@tonic-gate {
49*0Sstevel@tonic-gate list_t *le;
50*0Sstevel@tonic-gate
51*0Sstevel@tonic-gate le = xmalloc(sizeof (list_t));
52*0Sstevel@tonic-gate le->l_data = data;
53*0Sstevel@tonic-gate le->l_next = *list;
54*0Sstevel@tonic-gate *list = le;
55*0Sstevel@tonic-gate }
56*0Sstevel@tonic-gate
57*0Sstevel@tonic-gate /* Add an element to a sorted list */
58*0Sstevel@tonic-gate void
slist_add(list_t ** list,void * data,int (* cmp)(void *,void *))59*0Sstevel@tonic-gate slist_add(list_t **list, void *data, int (*cmp)(void *, void *))
60*0Sstevel@tonic-gate {
61*0Sstevel@tonic-gate list_t **nextp;
62*0Sstevel@tonic-gate
63*0Sstevel@tonic-gate for (nextp = list; *nextp; nextp = &((*nextp)->l_next)) {
64*0Sstevel@tonic-gate if (cmp((*nextp)->l_data, data) > 0)
65*0Sstevel@tonic-gate break;
66*0Sstevel@tonic-gate }
67*0Sstevel@tonic-gate
68*0Sstevel@tonic-gate list_add(nextp, data);
69*0Sstevel@tonic-gate }
70*0Sstevel@tonic-gate
71*0Sstevel@tonic-gate /*ARGSUSED2*/
72*0Sstevel@tonic-gate static int
list_defcmp(void * d1,void * d2,void * private)73*0Sstevel@tonic-gate list_defcmp(void *d1, void *d2, void *private)
74*0Sstevel@tonic-gate {
75*0Sstevel@tonic-gate return (d1 != d2);
76*0Sstevel@tonic-gate }
77*0Sstevel@tonic-gate
78*0Sstevel@tonic-gate void *
list_remove(list_t ** list,void * data,int (* cmp)(void *,void *,void *),void * private)79*0Sstevel@tonic-gate list_remove(list_t **list, void *data, int (*cmp)(void *, void *, void *),
80*0Sstevel@tonic-gate void *private)
81*0Sstevel@tonic-gate {
82*0Sstevel@tonic-gate list_t *le, **le2;
83*0Sstevel@tonic-gate void *led;
84*0Sstevel@tonic-gate
85*0Sstevel@tonic-gate if (!cmp)
86*0Sstevel@tonic-gate cmp = list_defcmp;
87*0Sstevel@tonic-gate
88*0Sstevel@tonic-gate for (le = *list, le2 = list; le; le2 = &le->l_next, le = le->l_next) {
89*0Sstevel@tonic-gate if (cmp(le->l_data, data, private) == 0) {
90*0Sstevel@tonic-gate *le2 = le->l_next;
91*0Sstevel@tonic-gate led = le->l_data;
92*0Sstevel@tonic-gate free(le);
93*0Sstevel@tonic-gate return (led);
94*0Sstevel@tonic-gate }
95*0Sstevel@tonic-gate }
96*0Sstevel@tonic-gate
97*0Sstevel@tonic-gate return (NULL);
98*0Sstevel@tonic-gate }
99*0Sstevel@tonic-gate
100*0Sstevel@tonic-gate void
list_free(list_t * list,void (* datafree)(void *,void *),void * private)101*0Sstevel@tonic-gate list_free(list_t *list, void (*datafree)(void *, void *), void *private)
102*0Sstevel@tonic-gate {
103*0Sstevel@tonic-gate list_t *le;
104*0Sstevel@tonic-gate
105*0Sstevel@tonic-gate while (list) {
106*0Sstevel@tonic-gate le = list;
107*0Sstevel@tonic-gate list = list->l_next;
108*0Sstevel@tonic-gate if (le->l_data && datafree)
109*0Sstevel@tonic-gate datafree(le->l_data, private);
110*0Sstevel@tonic-gate free(le);
111*0Sstevel@tonic-gate }
112*0Sstevel@tonic-gate }
113*0Sstevel@tonic-gate
114*0Sstevel@tonic-gate /*
115*0Sstevel@tonic-gate * This iterator is specifically designed to tolerate the deletion of the
116*0Sstevel@tonic-gate * node being iterated over.
117*0Sstevel@tonic-gate */
118*0Sstevel@tonic-gate int
list_iter(list_t * list,int (* func)(void *,void *),void * private)119*0Sstevel@tonic-gate list_iter(list_t *list, int (*func)(void *, void *), void *private)
120*0Sstevel@tonic-gate {
121*0Sstevel@tonic-gate list_t *lnext;
122*0Sstevel@tonic-gate int cumrc = 0;
123*0Sstevel@tonic-gate int cbrc;
124*0Sstevel@tonic-gate
125*0Sstevel@tonic-gate while (list) {
126*0Sstevel@tonic-gate lnext = list->l_next;
127*0Sstevel@tonic-gate if ((cbrc = func(list->l_data, private)) < 0)
128*0Sstevel@tonic-gate return (cbrc);
129*0Sstevel@tonic-gate cumrc += cbrc;
130*0Sstevel@tonic-gate list = lnext;
131*0Sstevel@tonic-gate }
132*0Sstevel@tonic-gate
133*0Sstevel@tonic-gate return (cumrc);
134*0Sstevel@tonic-gate }
135*0Sstevel@tonic-gate
136*0Sstevel@tonic-gate /*ARGSUSED*/
137*0Sstevel@tonic-gate static int
list_count_cb(void * data,void * private)138*0Sstevel@tonic-gate list_count_cb(void *data, void *private)
139*0Sstevel@tonic-gate {
140*0Sstevel@tonic-gate return (1);
141*0Sstevel@tonic-gate }
142*0Sstevel@tonic-gate
143*0Sstevel@tonic-gate int
list_count(list_t * list)144*0Sstevel@tonic-gate list_count(list_t *list)
145*0Sstevel@tonic-gate {
146*0Sstevel@tonic-gate return (list_iter(list, list_count_cb, NULL));
147*0Sstevel@tonic-gate }
148*0Sstevel@tonic-gate
149*0Sstevel@tonic-gate int
list_empty(list_t * list)150*0Sstevel@tonic-gate list_empty(list_t *list)
151*0Sstevel@tonic-gate {
152*0Sstevel@tonic-gate return (list == NULL);
153*0Sstevel@tonic-gate }
154*0Sstevel@tonic-gate
155*0Sstevel@tonic-gate void *
list_find(list_t * list,void * tmpl,int (* cmp)(void *,void *))156*0Sstevel@tonic-gate list_find(list_t *list, void *tmpl, int (*cmp)(void *, void *))
157*0Sstevel@tonic-gate {
158*0Sstevel@tonic-gate for (; list; list = list->l_next) {
159*0Sstevel@tonic-gate if (cmp(list->l_data, tmpl) == 0)
160*0Sstevel@tonic-gate return (list->l_data);
161*0Sstevel@tonic-gate }
162*0Sstevel@tonic-gate
163*0Sstevel@tonic-gate return (NULL);
164*0Sstevel@tonic-gate }
165*0Sstevel@tonic-gate
166*0Sstevel@tonic-gate void *
list_first(list_t * list)167*0Sstevel@tonic-gate list_first(list_t *list)
168*0Sstevel@tonic-gate {
169*0Sstevel@tonic-gate return (list ? list->l_data : NULL);
170*0Sstevel@tonic-gate }
171*0Sstevel@tonic-gate
172*0Sstevel@tonic-gate void
list_concat(list_t ** list1,list_t * list2)173*0Sstevel@tonic-gate list_concat(list_t **list1, list_t *list2)
174*0Sstevel@tonic-gate {
175*0Sstevel@tonic-gate list_t *l, *last;
176*0Sstevel@tonic-gate
177*0Sstevel@tonic-gate for (l = *list1, last = NULL; l; last = l, l = l->l_next)
178*0Sstevel@tonic-gate continue;
179*0Sstevel@tonic-gate
180*0Sstevel@tonic-gate if (last == NULL)
181*0Sstevel@tonic-gate *list1 = list2;
182*0Sstevel@tonic-gate else
183*0Sstevel@tonic-gate last->l_next = list2;
184*0Sstevel@tonic-gate }
185*0Sstevel@tonic-gate
186*0Sstevel@tonic-gate /*
187*0Sstevel@tonic-gate * Merges two sorted lists. Equal nodes (as determined by cmp) are retained.
188*0Sstevel@tonic-gate */
189*0Sstevel@tonic-gate void
slist_merge(list_t ** list1p,list_t * list2,int (* cmp)(void *,void *))190*0Sstevel@tonic-gate slist_merge(list_t **list1p, list_t *list2, int (*cmp)(void *, void *))
191*0Sstevel@tonic-gate {
192*0Sstevel@tonic-gate list_t *list1, *next2;
193*0Sstevel@tonic-gate list_t *last1 = NULL;
194*0Sstevel@tonic-gate
195*0Sstevel@tonic-gate if (*list1p == NULL) {
196*0Sstevel@tonic-gate *list1p = list2;
197*0Sstevel@tonic-gate return;
198*0Sstevel@tonic-gate }
199*0Sstevel@tonic-gate
200*0Sstevel@tonic-gate list1 = *list1p;
201*0Sstevel@tonic-gate while (list2 != NULL) {
202*0Sstevel@tonic-gate if (cmp(list1->l_data, list2->l_data) > 0) {
203*0Sstevel@tonic-gate next2 = list2->l_next;
204*0Sstevel@tonic-gate
205*0Sstevel@tonic-gate if (last1 == NULL) {
206*0Sstevel@tonic-gate /* Insert at beginning */
207*0Sstevel@tonic-gate *list1p = last1 = list2;
208*0Sstevel@tonic-gate list2->l_next = list1;
209*0Sstevel@tonic-gate } else {
210*0Sstevel@tonic-gate list2->l_next = list1;
211*0Sstevel@tonic-gate last1->l_next = list2;
212*0Sstevel@tonic-gate last1 = list2;
213*0Sstevel@tonic-gate }
214*0Sstevel@tonic-gate
215*0Sstevel@tonic-gate list2 = next2;
216*0Sstevel@tonic-gate } else {
217*0Sstevel@tonic-gate
218*0Sstevel@tonic-gate last1 = list1;
219*0Sstevel@tonic-gate list1 = list1->l_next;
220*0Sstevel@tonic-gate
221*0Sstevel@tonic-gate if (list1 == NULL) {
222*0Sstevel@tonic-gate /* Add the rest to the end of list1 */
223*0Sstevel@tonic-gate last1->l_next = list2;
224*0Sstevel@tonic-gate list2 = NULL;
225*0Sstevel@tonic-gate }
226*0Sstevel@tonic-gate }
227*0Sstevel@tonic-gate }
228*0Sstevel@tonic-gate }
229