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 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 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 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 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 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 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 * 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 * 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 * 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 * 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 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