lsearch, lfind

Purpose

     Performs a linear search and update.

Library

     Standard C Library (libc.a)

Syntax

     char *lsearch ((char *)key, (char *)base, nelp, sizeof (*key), compar)
     unsigned int *nelp;
     int (*compar) ( );

     char *lfind ((char *)key, (char *)base, nelp, sizeof (*key), compar)
     unsigned int *nelp;
     int (*compar) ( );

Description

     The lsearch subroutine performs  a linear search general-
     ized from Donald E. Knuth's  The Art of Computer Program-
     ming, Volume 3, 6.1, Algorithm S.(*) It returns a pointer
     into 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 key parameter points to the datum to be sought in the
     table. The base parameter points  to the first element in
     the table.  The nelp parameter  points to an integer con-
     taining  the current  number  of elements  in the  table.
     This integer is incremented if  the datum is added to the
     table.  The compar  parameter is the name  of the compar-
     ison function that you must supply (strcmp, for example).
     It is called  with two parameters that point  to the ele-
     ments being compared.  The  compar function must return a
     value of 0 if the elements  are equal and nonzero if they
     are not equal.

     The lfind subroutine is identical to lsearch, except that
     if the  datum is not found,  then it is not  added to the
     table.  Instead, a NULL pointer is returned in this case.

     The pointers  to the key and  the element at the  base of
     the table  should be of type  pointer-to-element and cast
     to type pointer-to-character.  Although it is declared as
     type pointer-to-character,  the value returned  should be
     cast into type pointer-to-element.

     ---------------

     (*)  Reading, Massachusetts:  Addison-Wesley, 1981.

     The  comparison function  need  not  compare every  byte;
     therefore,  the elements  can contain  arbitrary data  in
     addition to the values being compared.

     Warning:   Undefined results  can occur  if there  is not
     enough room in the table for lsearch to add a new item.

Example

     The  following  code  fragment   reads  up  to  "TABSIZE"
     strings, each of which is  up to "ELSIZE" bytes long, and
     stores them into a table, eliminating duplicates.

       #include <stdio.h>

       #define TABSIZE 50
       #define ELSIZE  120

       char *lsearch();
       int  strcmp();
       char line[ELSIZE], tab[TABSIZE][ELSIZE];
       unsigned nel = 0;
        . . .
          while (fgets(line, ELSIZE, stdin) != NULL && nel < TABSIZE)
          {
             (void) lsearch(line, (char *)tab, &nel, ELSIZE, strcmp);
          }
        . . .

Related Information

     In this  book:  "bsearch," "hsearch,  hcreate, hdestroy,"
     and  "tsearch, tdelete, twalk."