17c478bdstevel@tonic-gate/*
27c478bdstevel@tonic-gate * CDDL HEADER START
37c478bdstevel@tonic-gate *
47c478bdstevel@tonic-gate * The contents of this file are subject to the terms of the
57c478bdstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
67c478bdstevel@tonic-gate * (the "License").  You may not use this file except in compliance
77c478bdstevel@tonic-gate * with the License.
87c478bdstevel@tonic-gate *
97c478bdstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bdstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
117c478bdstevel@tonic-gate * See the License for the specific language governing permissions
127c478bdstevel@tonic-gate * and limitations under the License.
137c478bdstevel@tonic-gate *
147c478bdstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
157c478bdstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bdstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
177c478bdstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
187c478bdstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bdstevel@tonic-gate *
207c478bdstevel@tonic-gate * CDDL HEADER END
217c478bdstevel@tonic-gate */
227c478bdstevel@tonic-gate/*      Copyright (c) 1984 AT&T */
237c478bdstevel@tonic-gate/*        All Rights Reserved   */
247c478bdstevel@tonic-gate
257c478bdstevel@tonic-gate#pragma ident	"%Z%%M%	%I%	%E% SMI"  /* from S5R2 1.1 */
267c478bdstevel@tonic-gate
277c478bdstevel@tonic-gate/*LINTLIBRARY*/
287c478bdstevel@tonic-gate/*
297c478bdstevel@tonic-gate * Linear search algorithm, generalized from Knuth (6.1) Algorithm Q.
307c478bdstevel@tonic-gate *
317c478bdstevel@tonic-gate * This version no longer has anything to do with Knuth's Algorithm Q,
327c478bdstevel@tonic-gate * which first copies the new element into the table, then looks for it.
337c478bdstevel@tonic-gate * The assumption there was that the cost of checking for the end of the
347c478bdstevel@tonic-gate * table before each comparison outweighed the cost of the comparison, which
357c478bdstevel@tonic-gate * isn't true when an arbitrary comparison function must be called and when the
367c478bdstevel@tonic-gate * copy itself takes a significant number of cycles.
377c478bdstevel@tonic-gate * Actually, it has now reverted to Algorithm S, which is "simpler."
387c478bdstevel@tonic-gate */
397c478bdstevel@tonic-gate
407c478bdstevel@tonic-gatetypedef char *POINTER;
417c478bdstevel@tonic-gateextern POINTER memcpy();
427c478bdstevel@tonic-gate
437c478bdstevel@tonic-gatePOINTER
447c478bdstevel@tonic-gatelfind(key, base, nelp, width, compar)
457c478bdstevel@tonic-gateregister POINTER key;		/* Key to be located */
467c478bdstevel@tonic-gateregister POINTER base;		/* Beginning of table */
477c478bdstevel@tonic-gateunsigned *nelp;			/* Pointer to current table size */
487c478bdstevel@tonic-gateregister unsigned width;	/* Width of an element (bytes) */
497c478bdstevel@tonic-gateint (*compar)();		/* Comparison function */
507c478bdstevel@tonic-gate{
517c478bdstevel@tonic-gate	register POINTER next = base + *nelp * width;	/* End of table */
527c478bdstevel@tonic-gate
537c478bdstevel@tonic-gate	for ( ; base < next; base += width)
547c478bdstevel@tonic-gate		if ((*compar)(key, base) == 0)
557c478bdstevel@tonic-gate			return (base);	/* Key found */
567c478bdstevel@tonic-gate	return (POINTER)0;
577c478bdstevel@tonic-gate}
58