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