17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*7257d1b4Sraf * Common Development and Distribution License (the "License").
6*7257d1b4Sraf * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
21*7257d1b4Sraf
227c478bd9Sstevel@tonic-gate /*
23*7257d1b4Sraf * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
247c478bd9Sstevel@tonic-gate * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate */
267c478bd9Sstevel@tonic-gate
277c478bd9Sstevel@tonic-gate /* Copyright (c) 1988 AT&T */
287c478bd9Sstevel@tonic-gate /* All Rights Reserved */
297c478bd9Sstevel@tonic-gate
307c478bd9Sstevel@tonic-gate /*
317c478bd9Sstevel@tonic-gate * Linear search algorithm, generalized from Knuth (6.1) Algorithm Q.
327c478bd9Sstevel@tonic-gate *
337c478bd9Sstevel@tonic-gate * This version no longer has anything to do with Knuth's Algorithm Q,
347c478bd9Sstevel@tonic-gate * which first copies the new element into the table, then looks for it.
357c478bd9Sstevel@tonic-gate * The assumption there was that the cost of checking for the end of the
367c478bd9Sstevel@tonic-gate * table before each comparison outweighed the cost of the comparison, which
377c478bd9Sstevel@tonic-gate * isn't true when an arbitrary comparison function must be called and when the
387c478bd9Sstevel@tonic-gate * copy itself takes a significant number of cycles.
397c478bd9Sstevel@tonic-gate * Actually, it has now reverted to Algorithm S, which is "simpler."
407c478bd9Sstevel@tonic-gate */
417c478bd9Sstevel@tonic-gate
42*7257d1b4Sraf #pragma weak _lfind = lfind
437c478bd9Sstevel@tonic-gate
44*7257d1b4Sraf #include "lint.h"
457c478bd9Sstevel@tonic-gate #include <stdlib.h>
467c478bd9Sstevel@tonic-gate #include <mtlib.h>
477c478bd9Sstevel@tonic-gate #include <sys/types.h>
487c478bd9Sstevel@tonic-gate #include <stdio.h>
497c478bd9Sstevel@tonic-gate #include <thread.h>
507c478bd9Sstevel@tonic-gate #include <synch.h>
517c478bd9Sstevel@tonic-gate #include <search.h>
527c478bd9Sstevel@tonic-gate
537c478bd9Sstevel@tonic-gate void *
lfind(const void * ky,const void * bs,size_t * nelp,size_t width,int (* compar)())547c478bd9Sstevel@tonic-gate lfind(const void *ky, const void *bs, size_t *nelp,
557c478bd9Sstevel@tonic-gate size_t width, int (*compar)())
567c478bd9Sstevel@tonic-gate {
577c478bd9Sstevel@tonic-gate char *key = (char *)ky;
587c478bd9Sstevel@tonic-gate char *base = (char *)bs;
597c478bd9Sstevel@tonic-gate char *next = base + *nelp * width; /* End of table */
607c478bd9Sstevel@tonic-gate
617c478bd9Sstevel@tonic-gate for (; base < next; base += width)
627c478bd9Sstevel@tonic-gate if ((*compar)(key, base) == 0)
637c478bd9Sstevel@tonic-gate return (base); /* Key found */
647c478bd9Sstevel@tonic-gate return (NULL);
657c478bd9Sstevel@tonic-gate }
66