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