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