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