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