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 1993-2003 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 #include <stdio.h>
30 #include <string.h>
31 #include <stdlib.h>
32 #include <sys/param.h>
33
34 #include "list.h"
35 #include "proto_list.h"
36
37 /* LINTLIBRARY */
38
39 int max_list_depth;
40
41 void
init_list(elem_list * list,int hsize)42 init_list(elem_list *list, int hsize)
43 {
44 int i;
45
46 list->type = 0;
47 list->list = (elem**)malloc(sizeof (elem *) * hsize);
48 list->num_of_buckets = hsize;
49 for (i = 0; i < list->num_of_buckets; i++)
50 list->list[i] = NULL;
51 }
52
53 #ifdef DEBUG
54 void
examine_list(elem_list * list)55 examine_list(elem_list *list)
56 {
57 int i;
58 elem *cur;
59 int buck_count;
60
61 for (i = 0; i < list->num_of_buckets; i++) {
62 buck_count = 0;
63 for (cur = list->list[i]; cur; cur = cur->next)
64 buck_count++;
65 (void) printf("bucket[%4d] contains %5d entries\n",
66 i, buck_count);
67 }
68 }
69
70
71 /*
72 * print all elements of a list
73 *
74 * Debugging routine
75 */
76 void
print_list(elem_list * list)77 print_list(elem_list *list)
78 {
79 int i;
80 elem *cur;
81
82 for (i = 0; i < list->num_of_buckets; i++) {
83 for (cur = list->list[i]; cur; cur = cur->next)
84 print_elem(stdout, cur);
85 }
86 }
87
88
89 /*
90 * print all elements of a list of type 'file_type'
91 *
92 * Debugging routine
93 */
94 void
print_type_list(elem_list * list,char file_type)95 print_type_list(elem_list *list, char file_type)
96 {
97 int i;
98 elem *cur;
99
100 for (i = 0; i < list->num_of_buckets; i++) {
101 for (cur = list->list[i]; cur; cur = cur->next) {
102 if (cur->file_type == file_type)
103 print_elem(stdout, cur);
104 }
105 }
106 }
107 #endif
108
109 unsigned int
hash(const char * str)110 hash(const char *str)
111 {
112 unsigned int i;
113
114 for (i = 0; *str != '\0'; )
115 i += *str++;
116 return (i);
117 }
118
119
120 static int
name_compare(elem * i,elem * j)121 name_compare(elem *i, elem *j)
122 {
123 int n;
124
125 if ((n = strncmp(i->name, j->name, MAXNAME)) != 0)
126 return (n);
127 else
128 return (j->arch - i->arch);
129 }
130
131
132 /*
133 * find_elem:
134 *
135 * possible values for flag.
136 * flag = FOLLOW_LINK
137 * flag = NO_FOLLOW_LINK
138 */
139 elem *
find_elem(elem_list * list,elem * key,int flag)140 find_elem(elem_list *list, elem *key, int flag)
141 {
142 elem *e;
143
144 for (e = list->list[hash(key->name) % list->num_of_buckets]; e;
145 e = e->next) {
146 if (!name_compare(e, key))
147 if (e->link_parent && flag == FOLLOW_LINK)
148 return (e->link_parent);
149 else
150 return (e);
151 }
152
153 return (NULL);
154 }
155
156
157 /*
158 * find_elem_isa:
159 *
160 * flags - same as find_elem()
161 */
162 elem *
find_elem_isa(elem_list * list,elem * key,int flag)163 find_elem_isa(elem_list *list, elem *key, int flag)
164 {
165 short orig_arch;
166 elem *e;
167
168 orig_arch = key->arch;
169 key->arch = P_ISA;
170 e = find_elem(list, key, flag);
171 key->arch = orig_arch;
172 return (e);
173 }
174
175 /*
176 * find_elem_mach:
177 *
178 * flags - same as find_elem()
179 */
180 elem *
find_elem_mach(elem_list * list,elem * key,int flag)181 find_elem_mach(elem_list *list, elem *key, int flag)
182 {
183 elem *e;
184
185 for (e = list->list[hash(key->name) % list->num_of_buckets]; e;
186 e = e->next) {
187 if ((e->arch != P_ISA) && (strcmp(key->name, e->name) == 0))
188 if (e->link_parent && flag == FOLLOW_LINK)
189 return (e->link_parent);
190 else
191 return (e);
192 }
193
194 return (NULL);
195 }
196
197 pkg_list *
add_pkg(pkg_list * head,const char * pkgname)198 add_pkg(pkg_list *head, const char *pkgname)
199 {
200 pkg_list *cur, *prev = NULL;
201 static pkg_list *new = NULL;
202
203 if (!new)
204 new = (pkg_list *)malloc(sizeof (pkg_list));
205
206 (void) strcpy(new->pkg_name, pkgname);
207
208 for (cur = head; cur; cur = cur->next) {
209 if (strcmp(cur->pkg_name, pkgname) >= 0)
210 break;
211 prev = cur;
212 }
213
214 if (!head) {
215 new->next = head;
216 head = new;
217 new = NULL;
218 return (head);
219 }
220
221 if (!cur) {
222 prev->next = new;
223 new->next = NULL;
224 new = NULL;
225 return (head);
226 }
227
228 if (strcmp(cur->pkg_name, pkgname) == 0) /* a duplicate */
229 return (NULL);
230
231 if (!prev) {
232 new->next = cur;
233 cur = new;
234 new = NULL;
235 return (cur);
236 }
237
238 prev->next = new;
239 new->next = cur;
240 new = NULL;
241 return (head);
242 }
243
244 void
add_elem(elem_list * list,elem * e)245 add_elem(elem_list *list, elem *e)
246 {
247 elem *last = NULL;
248 elem *cur;
249 int bucket;
250 int depth = 0;
251
252 bucket = hash(e->name) % list->num_of_buckets;
253 if (list->list[bucket]) {
254 for (cur = list->list[bucket]; cur; cur = cur->next) {
255 depth++;
256 if (strcmp(cur->name, e->name) > 0)
257 break;
258 last = cur;
259 }
260
261 if (last) {
262 if (depth > max_list_depth)
263 max_list_depth = depth;
264 last->next = e;
265 e->next = cur;
266 return;
267 }
268 }
269
270 /*
271 * insert at head of list
272 */
273 e->next = list->list[bucket];
274 list->list[bucket] = e;
275 if (depth > max_list_depth)
276 max_list_depth = depth;
277 }
278