'\" te
.\" Copyright 1989 AT&T.  Copyright (c) 2004, Sun Microsystems, Inc.  All Rights Reserved.
.\" The contents of this file are subject to the terms of the Common Development and Distribution License (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]
.TH LSEARCH 3C "Dec 6, 2004"
.SH NAME
lsearch, lfind \- linear search and update
.SH SYNOPSIS
.LP
.nf
#include <search.h>

\fBvoid *\fR\fBlsearch\fR(\fBconst void *\fR\fIkey\fR, \fBvoid *\fR\fIbase\fR, \fBsize_t *\fR\fInelp\fR,
     \fBsize_t\fR \fIwidth\fR, \fBint\fR (*\fIcompar\fR)(\fBconst void *\fR, \fBconst void *\fR));
.fi

.LP
.nf
\fBvoid *\fR\fBlfind\fR(\fBconst void *\fR\fIkey\fR, \fBconst void *\fR\fIbase\fR, \fBsize_t *\fR\fInelp\fR,
     \fBsize_t\fR \fIwidth\fR, \fBint (*\fR\fIcompar\fR)(const void *, \fBconst void *));\fR
.fi

.SH DESCRIPTION
.sp
.LP
The \fBlsearch()\fR function is a linear search routine generalized from Knuth
(6.1) Algorithm S. (see \fIThe Art of Computer Programming, Volume 3, Section
6.1, by Donald E. Knuth.\fR). It returns a pointer to a table indicating where
a datum can be found. If the datum does not occur, it is added at the end of
the table. The \fIkey\fR argument points to the datum to be sought in the
table. The \fIbase\fR argument points to the first element in the table. The
\fInelp\fR argument points to an integer containing the current number of
elements in the table. The integer is incremented if the datum is added to the
table. The \fIwidth\fR argument is the size of an element in bytes. The
\fIcompar\fR argument is a pointer to the comparison function that the user
must supply (\fBstrcmp\fR(3C) for example). It is called with two arguments
that point to the elements being compared. The function must return zero if the
elements are equal and non-zero otherwise.
.sp
.LP
The \fBlfind()\fR function is the same as \fBlsearch()\fR except that if the
datum is not found, it is not added to the table.  Instead, a null pointer is
returned.
.sp
.LP
It is important to note the following:
.RS +4
.TP
.ie t \(bu
.el o
The pointers to the key and the element at the base of the table can be
pointers to any type.
.RE
.RS +4
.TP
.ie t \(bu
.el o
The comparison function need not compare every byte, so arbitrary data can be
contained in the elements in addition to the values being compared.
.RE
.RS +4
.TP
.ie t \(bu
.el o
The value returned should be cast into type pointer-to-element.
.RE
.SH RETURN VALUES
.sp
.LP
If the searched-for datum is found, both \fBlsearch()\fR and  \fBlfind()\fR
return a pointer to it. Otherwise, \fBlfind()\fR returns \fINULL\fR and
\fBlsearch()\fR returns a pointer to the newly added element.
.SH USAGE
.sp
.LP
Undefined results can occur if there is not enough room in the table to add a
new item.
.sp
.LP
The \fBlsearch()\fR and \fBlfind()\fR functions safely allows concurrent access
by multiple threads to disjoint data, such as overlapping subtrees or tables.
.SH EXAMPLES
.LP
\fBExample 1 \fRA sample code using the \fBlsearch()\fR function.
.sp
.LP
This program will read in less than \fBTABSIZE\fR strings of length less than
\fBELSIZE\fR and store them in a table, eliminating duplicates, and then will
print each entry.

.sp
.in +2
.nf
#include <search.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define TABSIZE 50
#define ELSIZE 120

main()
{
    char line[ELSIZE];          /* buffer to hold input string */
    char tab[TABSIZE][ELSIZE];  /* table of strings */
    size_t nel = 0;             /* number of entries in tab */
    int i;

    while (fgets(line, ELSIZE, stdin) != NULL &&
            nel < TABSIZE)
            (void) lsearch(line, tab, &nel, ELSIZE, mycmp);
    for( i = 0; i < nel; i++ )
            (void)fputs(tab[i], stdout);
    return 0;
}
.fi
.in -2

.SH ATTRIBUTES
.sp
.LP
See \fBattributes\fR(5) for descriptions of the following attributes:
.sp

.sp
.TS
box;
c | c
l | l .
ATTRIBUTE TYPE	ATTRIBUTE VALUE
_
Interface Stability	Standard
_
MT-Level	MT-Safe
.TE

.SH SEE ALSO
.sp
.LP
\fBbsearch\fR(3C), \fBhsearch\fR(3C), \fBstring\fR(3C), \fBtsearch\fR(3C),
\fBattributes\fR(5), \fBstandards\fR(5)
.sp
.LP
\fIThe Art of Computer Programming, Volume 3, Sorting and Searching by Donald
E. Knuth, published by Addison-Wesley Publishing Company, 1973.\fR