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 30*7257d1b4Sraf #pragma ident "%Z%%M% %I% %E% SMI" 317c478bd9Sstevel@tonic-gate 327c478bd9Sstevel@tonic-gate /* 337c478bd9Sstevel@tonic-gate * Linear search algorithm, generalized from Knuth (6.1) Algorithm Q. 347c478bd9Sstevel@tonic-gate * 357c478bd9Sstevel@tonic-gate * This version no longer has anything to do with Knuth's Algorithm Q, 367c478bd9Sstevel@tonic-gate * which first copies the new element into the table, then looks for it. 377c478bd9Sstevel@tonic-gate * The assumption there was that the cost of checking for the end of the 387c478bd9Sstevel@tonic-gate * table before each comparison outweighed the cost of the comparison, which 397c478bd9Sstevel@tonic-gate * isn't true when an arbitrary comparison function must be called and when the 407c478bd9Sstevel@tonic-gate * copy itself takes a significant number of cycles. 417c478bd9Sstevel@tonic-gate * Actually, it has now reverted to Algorithm S, which is "simpler." 427c478bd9Sstevel@tonic-gate */ 437c478bd9Sstevel@tonic-gate 44*7257d1b4Sraf #pragma weak _lfind = lfind 457c478bd9Sstevel@tonic-gate 46*7257d1b4Sraf #include "lint.h" 477c478bd9Sstevel@tonic-gate #include <stdlib.h> 487c478bd9Sstevel@tonic-gate #include <mtlib.h> 497c478bd9Sstevel@tonic-gate #include <sys/types.h> 507c478bd9Sstevel@tonic-gate #include <stdio.h> 517c478bd9Sstevel@tonic-gate #include <thread.h> 527c478bd9Sstevel@tonic-gate #include <synch.h> 537c478bd9Sstevel@tonic-gate #include <search.h> 547c478bd9Sstevel@tonic-gate 557c478bd9Sstevel@tonic-gate void * 567c478bd9Sstevel@tonic-gate lfind(const void *ky, const void *bs, size_t *nelp, 577c478bd9Sstevel@tonic-gate size_t width, int (*compar)()) 587c478bd9Sstevel@tonic-gate { 597c478bd9Sstevel@tonic-gate char *key = (char *)ky; 607c478bd9Sstevel@tonic-gate char *base = (char *)bs; 617c478bd9Sstevel@tonic-gate char *next = base + *nelp * width; /* End of table */ 627c478bd9Sstevel@tonic-gate 637c478bd9Sstevel@tonic-gate for (; base < next; base += width) 647c478bd9Sstevel@tonic-gate if ((*compar)(key, base) == 0) 657c478bd9Sstevel@tonic-gate return (base); /* Key found */ 667c478bd9Sstevel@tonic-gate return (NULL); 677c478bd9Sstevel@tonic-gate } 68