OpenSolaris_b135/tools/protocmp/list.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 1993-2003 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#pragma ident	"%Z%%M%	%I%	%E% SMI"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/param.h>

#include "list.h"
#include "proto_list.h"

/* LINTLIBRARY */

int max_list_depth;

void
init_list(elem_list *list, int hsize)
{
	int	i;

	list->type = 0;
	list->list = (elem**)malloc(sizeof (elem *) * hsize);
	list->num_of_buckets = hsize;
	for (i = 0; i < list->num_of_buckets; i++)
		list->list[i] = NULL;
}

#ifdef DEBUG
void
examine_list(elem_list *list)
{
	int	i;
	elem	*cur;
	int	buck_count;

	for (i = 0; i < list->num_of_buckets; i++) {
		buck_count = 0;
		for (cur = list->list[i]; cur; cur = cur->next)
			buck_count++;
		(void) printf("bucket[%4d] contains %5d entries\n",
		    i, buck_count);
	}
}


/*
 * print all elements of a list
 *
 * Debugging routine
 */
void
print_list(elem_list *list)
{
	int	i;
	elem	*cur;

	for (i = 0; i < list->num_of_buckets; i++) {
		for (cur = list->list[i]; cur; cur = cur->next)
			print_elem(stdout, cur);
	}
}


/*
 * print all elements of a list of type 'file_type'
 *
 * Debugging routine
 */
void
print_type_list(elem_list *list, char file_type)
{
	int	i;
	elem	*cur;

	for (i = 0; i < list->num_of_buckets; i++) {
		for (cur = list->list[i]; cur; cur = cur->next) {
			if (cur->file_type == file_type)
				print_elem(stdout, cur);
		}
	}
}
#endif

unsigned int
hash(const char *str)
{
	unsigned int	i;

	for (i = 0; *str != '\0'; )
		i += *str++;
	return (i);
}


static int
name_compare(elem *i, elem *j)
{
	int	n;

	if ((n = strncmp(i->name, j->name, MAXNAME)) != 0)
		return (n);
	else
		return (j->arch - i->arch);
}


/*
 * find_elem:
 *
 * possible values for flag.
 * 			flag = FOLLOW_LINK
 *			flag = NO_FOLLOW_LINK
 */
elem *
find_elem(elem_list *list, elem *key, int flag)
{
	elem	*e;

	for (e = list->list[hash(key->name) % list->num_of_buckets]; e;
	    e = e->next) {
		if (!name_compare(e, key))
			if (e->link_parent && flag == FOLLOW_LINK)
				return (e->link_parent);
			else
				return (e);
	}

	return (NULL);
}


/*
 * find_elem_isa:
 *
 * flags - same as find_elem()
 */
elem *
find_elem_isa(elem_list *list, elem *key, int flag)
{
	short	orig_arch;
	elem	*e;

	orig_arch = key->arch;
	key->arch = P_ISA;
	e = find_elem(list, key, flag);
	key->arch = orig_arch;
	return (e);
}

/*
 * find_elem_mach:
 *
 * flags - same as find_elem()
 */
elem *
find_elem_mach(elem_list *list, elem *key, int flag)
{
	elem	*e;

	for (e = list->list[hash(key->name) % list->num_of_buckets]; e;
	    e = e->next) {
		if ((e->arch != P_ISA) && (strcmp(key->name, e->name) == 0))
			if (e->link_parent && flag == FOLLOW_LINK)
				return (e->link_parent);
			else
				return (e);
	}

	return (NULL);
}

pkg_list *
add_pkg(pkg_list *head, const char *pkgname)
{
	pkg_list	*cur, *prev = NULL;
	static pkg_list	*new = NULL;

	if (!new)
		new = (pkg_list *)malloc(sizeof (pkg_list));

	(void) strcpy(new->pkg_name, pkgname);

	for (cur = head; cur; cur = cur->next) {
		if (strcmp(cur->pkg_name, pkgname) >= 0)
			break;
		prev = cur;
	}

	if (!head) {
		new->next = head;
		head = new;
		new = NULL;
		return (head);
	}

	if (!cur) {
		prev->next = new;
		new->next = NULL;
		new = NULL;
		return (head);
	}

	if (strcmp(cur->pkg_name, pkgname) == 0)	/* a duplicate */
		return (NULL);

	if (!prev) {
		new->next = cur;
		cur = new;
		new = NULL;
		return (cur);
	}

	prev->next = new;
	new->next = cur;
	new = NULL;
	return (head);
}

void
add_elem(elem_list *list, elem *e)
{
	elem	*last = NULL;
	elem	*cur;
	int	bucket;
	int	depth = 0;

	bucket = hash(e->name) % list->num_of_buckets;
	if (list->list[bucket]) {
		for (cur = list->list[bucket]; cur; cur = cur->next) {
			depth++;
			if (strcmp(cur->name, e->name) > 0)
				break;
			last = cur;
		}

		if (last) {
			if (depth > max_list_depth)
				max_list_depth = depth;
			last->next = e;
			e->next = cur;
			return;
		}
	}

	/*
	 * insert at head of list
	 */
	e->next = list->list[bucket];
	list->list[bucket] = e;
	if (depth > max_list_depth)
		max_list_depth = depth;
}