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
39int max_list_depth;
40
41void
42init_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
54void
55examine_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 */
76void
77print_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 */
94void
95print_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
109unsigned int
110hash(const char *str)
111{
112	unsigned int	i;
113
114	for (i = 0; *str != '\0'; )
115		i += *str++;
116	return (i);
117}
118
119
120static int
121name_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 */
139elem *
140find_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 */
162elem *
163find_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 */
180elem *
181find_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
197pkg_list *
198add_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
244void
245add_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