xref: /illumos-gate/usr/src/tools/protocmp/list.c (revision 7c478bd9)
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