usr/src/man/man3c/lsearch.3c

   1 '\" te
   2 .\" Copyright 1989 AT&T.  Copyright (c) 2004, Sun Microsystems, Inc.  All Rights Reserved.
   3 .\" 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.
   4 .\" 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.
   5 .\" 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]
   6 .TH LSEARCH 3C "Dec 6, 2004"
   7 .SH NAME
   8 lsearch, lfind \- linear search and update
   9 .SH SYNOPSIS
  10 .LP
  11 .nf
  12 #include <search.h>
  13
  14 \fBvoid *\fR\fBlsearch\fR(\fBconst void *\fR\fIkey\fR, \fBvoid *\fR\fIbase\fR, \fBsize_t *\fR\fInelp\fR,
  15      \fBsize_t\fR \fIwidth\fR, \fBint\fR (*\fIcompar\fR)(\fBconst void *\fR, \fBconst void *\fR));
  16 .fi
  17
  18 .LP
  19 .nf
  20 \fBvoid *\fR\fBlfind\fR(\fBconst void *\fR\fIkey\fR, \fBconst void *\fR\fIbase\fR, \fBsize_t *\fR\fInelp\fR,
  21      \fBsize_t\fR \fIwidth\fR, \fBint (*\fR\fIcompar\fR)(const void *, \fBconst void *));\fR
  22 .fi
  23
  24 .SH DESCRIPTION
  25 .sp
  26 .LP
  27 The \fBlsearch()\fR function is a linear search routine generalized from Knuth
  28 (6.1) Algorithm S. (see \fIThe Art of Computer Programming, Volume 3, Section
  29 6.1, by Donald E. Knuth.\fR). It returns a pointer to a table indicating where
  30 a datum can be found. If the datum does not occur, it is added at the end of
  31 the table. The \fIkey\fR argument points to the datum to be sought in the
  32 table. The \fIbase\fR argument points to the first element in the table. The
  33 \fInelp\fR argument points to an integer containing the current number of
  34 elements in the table. The integer is incremented if the datum is added to the
  35 table. The \fIwidth\fR argument is the size of an element in bytes. The
  36 \fIcompar\fR argument is a pointer to the comparison function that the user
  37 must supply (\fBstrcmp\fR(3C) for example). It is called with two arguments
  38 that point to the elements being compared. The function must return zero if the
  39 elements are equal and non-zero otherwise.
  40 .sp
  41 .LP
  42 The \fBlfind()\fR function is the same as \fBlsearch()\fR except that if the
  43 datum is not found, it is not added to the table.  Instead, a null pointer is
  44 returned.
  45 .sp
  46 .LP
  47 It is important to note the following:
  48 .RS +4
  49 .TP
  50 .ie t \(bu
  51 .el o
  52 The pointers to the key and the element at the base of the table can be
  53 pointers to any type.
  54 .RE
  55 .RS +4
  56 .TP
  57 .ie t \(bu
  58 .el o
  59 The comparison function need not compare every byte, so arbitrary data can be
  60 contained in the elements in addition to the values being compared.
  61 .RE
  62 .RS +4
  63 .TP
  64 .ie t \(bu
  65 .el o
  66 The value returned should be cast into type pointer-to-element.
  67 .RE
  68 .SH RETURN VALUES
  69 .sp
  70 .LP
  71 If the searched-for datum is found, both \fBlsearch()\fR and  \fBlfind()\fR
  72 return a pointer to it. Otherwise, \fBlfind()\fR returns \fINULL\fR and
  73 \fBlsearch()\fR returns a pointer to the newly added element.
  74 .SH USAGE
  75 .sp
  76 .LP
  77 Undefined results can occur if there is not enough room in the table to add a
  78 new item.
  79 .sp
  80 .LP
  81 The \fBlsearch()\fR and \fBlfind()\fR functions safely allows concurrent access
  82 by multiple threads to disjoint data, such as overlapping subtrees or tables.
  83 .SH EXAMPLES
  84 .LP
  85 \fBExample 1 \fRA sample code using the \fBlsearch()\fR function.
  86 .sp
  87 .LP
  88 This program will read in less than \fBTABSIZE\fR strings of length less than
  89 \fBELSIZE\fR and store them in a table, eliminating duplicates, and then will
  90 print each entry.
  91
  92 .sp
  93 .in +2
  94 .nf
  95 #include <search.h>
  96 #include <string.h>
  97 #include <stdlib.h>
  98 #include <stdio.h>
  99
 100 #define TABSIZE 50
 101 #define ELSIZE 120
 102
 103 main()
 104 {
 105     char line[ELSIZE];          /* buffer to hold input string */
 106     char tab[TABSIZE][ELSIZE];  /* table of strings */
 107     size_t nel = 0;             /* number of entries in tab */
 108     int i;
 109
 110     while (fgets(line, ELSIZE, stdin) != NULL &&
 111             nel < TABSIZE)
 112             (void) lsearch(line, tab, &nel, ELSIZE, mycmp);
 113     for( i = 0; i < nel; i++ )
 114             (void)fputs(tab[i], stdout);
 115     return 0;
 116 }
 117 .fi
 118 .in -2
 119
 120 .SH ATTRIBUTES
 121 .sp
 122 .LP
 123 See \fBattributes\fR(5) for descriptions of the following attributes:
 124 .sp
 125
 126 .sp
 127 .TS
 128 box;
 129 c | c
 130 l | l .
 131 ATTRIBUTE TYPE  ATTRIBUTE VALUE
 132 _
 133 Interface Stability     Standard
 134 _
 135 MT-Level        MT-Safe
 136 .TE
 137
 138 .SH SEE ALSO
 139 .sp
 140 .LP
 141 \fBbsearch\fR(3C), \fBhsearch\fR(3C), \fBstring\fR(3C), \fBtsearch\fR(3C),
 142 \fBattributes\fR(5), \fBstandards\fR(5)
 143 .sp
 144 .LP
 145 \fIThe Art of Computer Programming, Volume 3, Sorting and Searching by Donald
 146 E. Knuth, published by Addison-Wesley Publishing Company, 1973.\fR