1*7c478bd9Sstevel@tonic-gate /*
2*7c478bd9Sstevel@tonic-gate * CDDL HEADER START
3*7c478bd9Sstevel@tonic-gate *
4*7c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*7c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
6*7c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
7*7c478bd9Sstevel@tonic-gate * with the License.
8*7c478bd9Sstevel@tonic-gate *
9*7c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10*7c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
11*7c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
12*7c478bd9Sstevel@tonic-gate * and limitations under the License.
13*7c478bd9Sstevel@tonic-gate *
14*7c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
15*7c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16*7c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
17*7c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
18*7c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
19*7c478bd9Sstevel@tonic-gate *
20*7c478bd9Sstevel@tonic-gate * CDDL HEADER END
21*7c478bd9Sstevel@tonic-gate */
22*7c478bd9Sstevel@tonic-gate /*
23*7c478bd9Sstevel@tonic-gate * Copyright 1993-2003 Sun Microsystems, Inc. All rights reserved.
24*7c478bd9Sstevel@tonic-gate * Use is subject to license terms.
25*7c478bd9Sstevel@tonic-gate */
26*7c478bd9Sstevel@tonic-gate
27*7c478bd9Sstevel@tonic-gate #include <stdio.h>
28*7c478bd9Sstevel@tonic-gate #include <string.h>
29*7c478bd9Sstevel@tonic-gate #include <stdlib.h>
30*7c478bd9Sstevel@tonic-gate #include <sys/param.h>
31*7c478bd9Sstevel@tonic-gate
32*7c478bd9Sstevel@tonic-gate #include "list.h"
33*7c478bd9Sstevel@tonic-gate #include "proto_list.h"
34*7c478bd9Sstevel@tonic-gate
35*7c478bd9Sstevel@tonic-gate /* LINTLIBRARY */
36*7c478bd9Sstevel@tonic-gate
37*7c478bd9Sstevel@tonic-gate int max_list_depth;
38*7c478bd9Sstevel@tonic-gate
39*7c478bd9Sstevel@tonic-gate void
init_list(elem_list * list,int hsize)40*7c478bd9Sstevel@tonic-gate init_list(elem_list *list, int hsize)
41*7c478bd9Sstevel@tonic-gate {
42*7c478bd9Sstevel@tonic-gate int i;
43*7c478bd9Sstevel@tonic-gate
44*7c478bd9Sstevel@tonic-gate list->type = 0;
45*7c478bd9Sstevel@tonic-gate list->list = (elem**)malloc(sizeof (elem *) * hsize);
46*7c478bd9Sstevel@tonic-gate list->num_of_buckets = hsize;
47*7c478bd9Sstevel@tonic-gate for (i = 0; i < list->num_of_buckets; i++)
48*7c478bd9Sstevel@tonic-gate list->list[i] = NULL;
49*7c478bd9Sstevel@tonic-gate }
50*7c478bd9Sstevel@tonic-gate
51*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
52*7c478bd9Sstevel@tonic-gate void
examine_list(elem_list * list)53*7c478bd9Sstevel@tonic-gate examine_list(elem_list *list)
54*7c478bd9Sstevel@tonic-gate {
55*7c478bd9Sstevel@tonic-gate int i;
56*7c478bd9Sstevel@tonic-gate elem *cur;
57*7c478bd9Sstevel@tonic-gate int buck_count;
58*7c478bd9Sstevel@tonic-gate
59*7c478bd9Sstevel@tonic-gate for (i = 0; i < list->num_of_buckets; i++) {
60*7c478bd9Sstevel@tonic-gate buck_count = 0;
61*7c478bd9Sstevel@tonic-gate for (cur = list->list[i]; cur; cur = cur->next)
62*7c478bd9Sstevel@tonic-gate buck_count++;
63*7c478bd9Sstevel@tonic-gate (void) printf("bucket[%4d] contains %5d entries\n",
64*7c478bd9Sstevel@tonic-gate i, buck_count);
65*7c478bd9Sstevel@tonic-gate }
66*7c478bd9Sstevel@tonic-gate }
67*7c478bd9Sstevel@tonic-gate
68*7c478bd9Sstevel@tonic-gate
69*7c478bd9Sstevel@tonic-gate /*
70*7c478bd9Sstevel@tonic-gate * print all elements of a list
71*7c478bd9Sstevel@tonic-gate *
72*7c478bd9Sstevel@tonic-gate * Debugging routine
73*7c478bd9Sstevel@tonic-gate */
74*7c478bd9Sstevel@tonic-gate void
print_list(elem_list * list)75*7c478bd9Sstevel@tonic-gate print_list(elem_list *list)
76*7c478bd9Sstevel@tonic-gate {
77*7c478bd9Sstevel@tonic-gate int i;
78*7c478bd9Sstevel@tonic-gate elem *cur;
79*7c478bd9Sstevel@tonic-gate
80*7c478bd9Sstevel@tonic-gate for (i = 0; i < list->num_of_buckets; i++) {
81*7c478bd9Sstevel@tonic-gate for (cur = list->list[i]; cur; cur = cur->next)
82*7c478bd9Sstevel@tonic-gate print_elem(stdout, cur);
83*7c478bd9Sstevel@tonic-gate }
84*7c478bd9Sstevel@tonic-gate }
85*7c478bd9Sstevel@tonic-gate
86*7c478bd9Sstevel@tonic-gate
87*7c478bd9Sstevel@tonic-gate /*
88*7c478bd9Sstevel@tonic-gate * print all elements of a list of type 'file_type'
89*7c478bd9Sstevel@tonic-gate *
90*7c478bd9Sstevel@tonic-gate * Debugging routine
91*7c478bd9Sstevel@tonic-gate */
92*7c478bd9Sstevel@tonic-gate void
print_type_list(elem_list * list,char file_type)93*7c478bd9Sstevel@tonic-gate print_type_list(elem_list *list, char file_type)
94*7c478bd9Sstevel@tonic-gate {
95*7c478bd9Sstevel@tonic-gate int i;
96*7c478bd9Sstevel@tonic-gate elem *cur;
97*7c478bd9Sstevel@tonic-gate
98*7c478bd9Sstevel@tonic-gate for (i = 0; i < list->num_of_buckets; i++) {
99*7c478bd9Sstevel@tonic-gate for (cur = list->list[i]; cur; cur = cur->next) {
100*7c478bd9Sstevel@tonic-gate if (cur->file_type == file_type)
101*7c478bd9Sstevel@tonic-gate print_elem(stdout, cur);
102*7c478bd9Sstevel@tonic-gate }
103*7c478bd9Sstevel@tonic-gate }
104*7c478bd9Sstevel@tonic-gate }
105*7c478bd9Sstevel@tonic-gate #endif
106*7c478bd9Sstevel@tonic-gate
107*7c478bd9Sstevel@tonic-gate unsigned int
hash(const char * str)108*7c478bd9Sstevel@tonic-gate hash(const char *str)
109*7c478bd9Sstevel@tonic-gate {
110*7c478bd9Sstevel@tonic-gate unsigned int i;
111*7c478bd9Sstevel@tonic-gate
112*7c478bd9Sstevel@tonic-gate for (i = 0; *str != '\0'; )
113*7c478bd9Sstevel@tonic-gate i += *str++;
114*7c478bd9Sstevel@tonic-gate return (i);
115*7c478bd9Sstevel@tonic-gate }
116*7c478bd9Sstevel@tonic-gate
117*7c478bd9Sstevel@tonic-gate
118*7c478bd9Sstevel@tonic-gate static int
name_compare(elem * i,elem * j)119*7c478bd9Sstevel@tonic-gate name_compare(elem *i, elem *j)
120*7c478bd9Sstevel@tonic-gate {
121*7c478bd9Sstevel@tonic-gate int n;
122*7c478bd9Sstevel@tonic-gate
123*7c478bd9Sstevel@tonic-gate if ((n = strncmp(i->name, j->name, MAXNAME)) != 0)
124*7c478bd9Sstevel@tonic-gate return (n);
125*7c478bd9Sstevel@tonic-gate else
126*7c478bd9Sstevel@tonic-gate return (j->arch - i->arch);
127*7c478bd9Sstevel@tonic-gate }
128*7c478bd9Sstevel@tonic-gate
129*7c478bd9Sstevel@tonic-gate
130*7c478bd9Sstevel@tonic-gate /*
131*7c478bd9Sstevel@tonic-gate * find_elem:
132*7c478bd9Sstevel@tonic-gate *
133*7c478bd9Sstevel@tonic-gate * possible values for flag.
134*7c478bd9Sstevel@tonic-gate * flag = FOLLOW_LINK
135*7c478bd9Sstevel@tonic-gate * flag = NO_FOLLOW_LINK
136*7c478bd9Sstevel@tonic-gate */
137*7c478bd9Sstevel@tonic-gate elem *
find_elem(elem_list * list,elem * key,int flag)138*7c478bd9Sstevel@tonic-gate find_elem(elem_list *list, elem *key, int flag)
139*7c478bd9Sstevel@tonic-gate {
140*7c478bd9Sstevel@tonic-gate elem *e;
141*7c478bd9Sstevel@tonic-gate
142*7c478bd9Sstevel@tonic-gate for (e = list->list[hash(key->name) % list->num_of_buckets]; e;
143*7c478bd9Sstevel@tonic-gate e = e->next) {
144*7c478bd9Sstevel@tonic-gate if (!name_compare(e, key))
145*7c478bd9Sstevel@tonic-gate if (e->link_parent && flag == FOLLOW_LINK)
146*7c478bd9Sstevel@tonic-gate return (e->link_parent);
147*7c478bd9Sstevel@tonic-gate else
148*7c478bd9Sstevel@tonic-gate return (e);
149*7c478bd9Sstevel@tonic-gate }
150*7c478bd9Sstevel@tonic-gate
151*7c478bd9Sstevel@tonic-gate return (NULL);
152*7c478bd9Sstevel@tonic-gate }
153*7c478bd9Sstevel@tonic-gate
154*7c478bd9Sstevel@tonic-gate
155*7c478bd9Sstevel@tonic-gate /*
156*7c478bd9Sstevel@tonic-gate * find_elem_isa:
157*7c478bd9Sstevel@tonic-gate *
158*7c478bd9Sstevel@tonic-gate * flags - same as find_elem()
159*7c478bd9Sstevel@tonic-gate */
160*7c478bd9Sstevel@tonic-gate elem *
find_elem_isa(elem_list * list,elem * key,int flag)161*7c478bd9Sstevel@tonic-gate find_elem_isa(elem_list *list, elem *key, int flag)
162*7c478bd9Sstevel@tonic-gate {
163*7c478bd9Sstevel@tonic-gate short orig_arch;
164*7c478bd9Sstevel@tonic-gate elem *e;
165*7c478bd9Sstevel@tonic-gate
166*7c478bd9Sstevel@tonic-gate orig_arch = key->arch;
167*7c478bd9Sstevel@tonic-gate key->arch = P_ISA;
168*7c478bd9Sstevel@tonic-gate e = find_elem(list, key, flag);
169*7c478bd9Sstevel@tonic-gate key->arch = orig_arch;
170*7c478bd9Sstevel@tonic-gate return (e);
171*7c478bd9Sstevel@tonic-gate }
172*7c478bd9Sstevel@tonic-gate
173*7c478bd9Sstevel@tonic-gate /*
174*7c478bd9Sstevel@tonic-gate * find_elem_mach:
175*7c478bd9Sstevel@tonic-gate *
176*7c478bd9Sstevel@tonic-gate * flags - same as find_elem()
177*7c478bd9Sstevel@tonic-gate */
178*7c478bd9Sstevel@tonic-gate elem *
find_elem_mach(elem_list * list,elem * key,int flag)179*7c478bd9Sstevel@tonic-gate find_elem_mach(elem_list *list, elem *key, int flag)
180*7c478bd9Sstevel@tonic-gate {
181*7c478bd9Sstevel@tonic-gate elem *e;
182*7c478bd9Sstevel@tonic-gate
183*7c478bd9Sstevel@tonic-gate for (e = list->list[hash(key->name) % list->num_of_buckets]; e;
184*7c478bd9Sstevel@tonic-gate e = e->next) {
185*7c478bd9Sstevel@tonic-gate if ((e->arch != P_ISA) && (strcmp(key->name, e->name) == 0))
186*7c478bd9Sstevel@tonic-gate if (e->link_parent && flag == FOLLOW_LINK)
187*7c478bd9Sstevel@tonic-gate return (e->link_parent);
188*7c478bd9Sstevel@tonic-gate else
189*7c478bd9Sstevel@tonic-gate return (e);
190*7c478bd9Sstevel@tonic-gate }
191*7c478bd9Sstevel@tonic-gate
192*7c478bd9Sstevel@tonic-gate return (NULL);
193*7c478bd9Sstevel@tonic-gate }
194*7c478bd9Sstevel@tonic-gate
195*7c478bd9Sstevel@tonic-gate pkg_list *
add_pkg(pkg_list * head,const char * pkgname)196*7c478bd9Sstevel@tonic-gate add_pkg(pkg_list *head, const char *pkgname)
197*7c478bd9Sstevel@tonic-gate {
198*7c478bd9Sstevel@tonic-gate pkg_list *cur, *prev = NULL;
199*7c478bd9Sstevel@tonic-gate static pkg_list *new = NULL;
200*7c478bd9Sstevel@tonic-gate
201*7c478bd9Sstevel@tonic-gate if (!new)
202*7c478bd9Sstevel@tonic-gate new = (pkg_list *)malloc(sizeof (pkg_list));
203*7c478bd9Sstevel@tonic-gate
204*7c478bd9Sstevel@tonic-gate (void) strcpy(new->pkg_name, pkgname);
205*7c478bd9Sstevel@tonic-gate
206*7c478bd9Sstevel@tonic-gate for (cur = head; cur; cur = cur->next) {
207*7c478bd9Sstevel@tonic-gate if (strcmp(cur->pkg_name, pkgname) >= 0)
208*7c478bd9Sstevel@tonic-gate break;
209*7c478bd9Sstevel@tonic-gate prev = cur;
210*7c478bd9Sstevel@tonic-gate }
211*7c478bd9Sstevel@tonic-gate
212*7c478bd9Sstevel@tonic-gate if (!head) {
213*7c478bd9Sstevel@tonic-gate new->next = head;
214*7c478bd9Sstevel@tonic-gate head = new;
215*7c478bd9Sstevel@tonic-gate new = NULL;
216*7c478bd9Sstevel@tonic-gate return (head);
217*7c478bd9Sstevel@tonic-gate }
218*7c478bd9Sstevel@tonic-gate
219*7c478bd9Sstevel@tonic-gate if (!cur) {
220*7c478bd9Sstevel@tonic-gate prev->next = new;
221*7c478bd9Sstevel@tonic-gate new->next = NULL;
222*7c478bd9Sstevel@tonic-gate new = NULL;
223*7c478bd9Sstevel@tonic-gate return (head);
224*7c478bd9Sstevel@tonic-gate }
225*7c478bd9Sstevel@tonic-gate
226*7c478bd9Sstevel@tonic-gate if (strcmp(cur->pkg_name, pkgname) == 0) /* a duplicate */
227*7c478bd9Sstevel@tonic-gate return (NULL);
228*7c478bd9Sstevel@tonic-gate
229*7c478bd9Sstevel@tonic-gate if (!prev) {
230*7c478bd9Sstevel@tonic-gate new->next = cur;
231*7c478bd9Sstevel@tonic-gate cur = new;
232*7c478bd9Sstevel@tonic-gate new = NULL;
233*7c478bd9Sstevel@tonic-gate return (cur);
234*7c478bd9Sstevel@tonic-gate }
235*7c478bd9Sstevel@tonic-gate
236*7c478bd9Sstevel@tonic-gate prev->next = new;
237*7c478bd9Sstevel@tonic-gate new->next = cur;
238*7c478bd9Sstevel@tonic-gate new = NULL;
239*7c478bd9Sstevel@tonic-gate return (head);
240*7c478bd9Sstevel@tonic-gate }
241*7c478bd9Sstevel@tonic-gate
242*7c478bd9Sstevel@tonic-gate void
add_elem(elem_list * list,elem * e)243*7c478bd9Sstevel@tonic-gate add_elem(elem_list *list, elem *e)
244*7c478bd9Sstevel@tonic-gate {
245*7c478bd9Sstevel@tonic-gate elem *last = NULL;
246*7c478bd9Sstevel@tonic-gate elem *cur;
247*7c478bd9Sstevel@tonic-gate int bucket;
248*7c478bd9Sstevel@tonic-gate int depth = 0;
249*7c478bd9Sstevel@tonic-gate
250*7c478bd9Sstevel@tonic-gate bucket = hash(e->name) % list->num_of_buckets;
251*7c478bd9Sstevel@tonic-gate if (list->list[bucket]) {
252*7c478bd9Sstevel@tonic-gate for (cur = list->list[bucket]; cur; cur = cur->next) {
253*7c478bd9Sstevel@tonic-gate depth++;
254*7c478bd9Sstevel@tonic-gate if (strcmp(cur->name, e->name) > 0)
255*7c478bd9Sstevel@tonic-gate break;
256*7c478bd9Sstevel@tonic-gate last = cur;
257*7c478bd9Sstevel@tonic-gate }
258*7c478bd9Sstevel@tonic-gate
259*7c478bd9Sstevel@tonic-gate if (last) {
260*7c478bd9Sstevel@tonic-gate if (depth > max_list_depth)
261*7c478bd9Sstevel@tonic-gate max_list_depth = depth;
262*7c478bd9Sstevel@tonic-gate last->next = e;
263*7c478bd9Sstevel@tonic-gate e->next = cur;
264*7c478bd9Sstevel@tonic-gate return;
265*7c478bd9Sstevel@tonic-gate }
266*7c478bd9Sstevel@tonic-gate }
267*7c478bd9Sstevel@tonic-gate
268*7c478bd9Sstevel@tonic-gate /*
269*7c478bd9Sstevel@tonic-gate * insert at head of list
270*7c478bd9Sstevel@tonic-gate */
271*7c478bd9Sstevel@tonic-gate e->next = list->list[bucket];
272*7c478bd9Sstevel@tonic-gate list->list[bucket] = e;
273*7c478bd9Sstevel@tonic-gate if (depth > max_list_depth)
274*7c478bd9Sstevel@tonic-gate max_list_depth = depth;
275*7c478bd9Sstevel@tonic-gate }
276