2N/A/*
2N/A * CDDL HEADER START
2N/A *
2N/A * The contents of this file are subject to the terms of the
2N/A * Common Development and Distribution License (the "License").
2N/A * You may not use this file except in compliance with the License.
2N/A *
2N/A * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
2N/A * or http://www.opensolaris.org/os/licensing.
2N/A * See the License for the specific language governing permissions
2N/A * and limitations under the License.
2N/A *
2N/A * When distributing Covered Code, include this CDDL HEADER in each
2N/A * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
2N/A * If applicable, add the following below this CDDL HEADER, with the
2N/A * fields enclosed by brackets "[]" replaced with your own identifying
2N/A * information: Portions Copyright [yyyy] [name of copyright owner]
2N/A *
2N/A * CDDL HEADER END
2N/A */
2N/A
2N/A/*
2N/A * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
2N/A * Use is subject to license terms.
2N/A */
2N/A
2N/A/* Copyright (c) 1988 AT&T */
2N/A/* All Rights Reserved */
2N/A
2N/A#pragma ident "%Z%%M% %I% %E% SMI"
2N/A
2N/A/*
2N/A * Linear search algorithm, generalized from Knuth (6.1) Algorithm Q.
2N/A *
2N/A * This version no longer has anything to do with Knuth's Algorithm Q,
2N/A * which first copies the new element into the table, then looks for it.
2N/A * The assumption there was that the cost of checking for the end of the
2N/A * table before each comparison outweighed the cost of the comparison, which
2N/A * isn't true when an arbitrary comparison function must be called and when the
2N/A * copy itself takes a significant number of cycles.
2N/A * Actually, it has now reverted to Algorithm S, which is "simpler."
2N/A */
2N/A
2N/A#pragma weak _lsearch = lsearch
2N/A
2N/A#include "lint.h"
2N/A#include <mtlib.h>
2N/A#include <sys/types.h>
2N/A#include <stddef.h>
2N/A#include <string.h>
2N/A#include <thread.h>
2N/A#include <synch.h>
2N/A
2N/Avoid *
2N/Alsearch(const void *ky, void *bs, size_t *nelp, size_t width,
2N/A int (*compar)(const void *, const void *))
2N/A{
2N/A char *key = (char *)ky;
2N/A char *base = (char *)bs;
2N/A char *next = base + *nelp * width; /* End of table */
2N/A void *res;
2N/A
2N/A for (; base < next; base += width)
2N/A if ((*compar)(key, base) == 0)
2N/A return (base); /* Key found */
2N/A ++*nelp; /* Not found, add to table */
2N/A res = memcpy(base, key, width); /* base now == next */
2N/A return (res);
2N/A}