usr/src/tools/protocmp/list.c

   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 }