usr.bin/spell/spellprog/look.c

   1 /*      $NetBSD: look.c,v 1.1 2005/06/29 21:06:12 perry Exp $   */
   2
   3 /* derived from: OpenBSD: look.c,v 1.3 2003/06/03 02:56:16 millert Exp */
   4
   5 /*-
   6  * Copyright (c) 1991, 1993
   7  *      The Regents of the University of California.  All rights reserved.
   8  *
   9  * This code is derived from software contributed to Berkeley by
  10  * David Hitz of Auspex Systems, Inc.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  * 3. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #ifndef lint
  38 #if 0
  39 static const char sccsid[] = "@(#)look.c        8.2 (Berkeley) 5/4/95";
  40 #endif
  41 static const char rcsid[] = "$NetBSD: look.c,v 1.1 2005/06/29 21:06:12 perry Exp $";
  42 #endif /* not lint */
  43
  44 #include <sys/types.h>
  45 #include <ctype.h>
  46 #include <stdio.h>
  47 #include <stdlib.h>
  48 #include <string.h>
  49 #include <err.h>
  50
  51 #include "extern.h"
  52
  53 static u_char   *binary_search(u_char *, u_char *, u_char *);
  54 static u_char   *linear_search(u_char *, u_char *, u_char *);
  55 static int       compare(u_char *, u_char *, u_char *);
  56
  57 int
  58 look(u_char *string, u_char *front, u_char *back)
  59 {
  60         u_char *s;
  61
  62         /* Convert string to lower case before searching. */
  63         for (s = string; *s; s++) {
  64                 if (isupper(*s))
  65                         *s = _tolower(*s);
  66         }
  67
  68         front = binary_search(string, front, back);
  69         front = linear_search(string, front, back);
  70
  71         return (front != NULL);
  72 }
  73
  74 /*
  75  * Binary search for "string" in memory between "front" and "back".
  76  *
  77  * This routine is expected to return a pointer to the start of a line at
  78  * *or before* the first word matching "string".  Relaxing the constraint
  79  * this way simplifies the algorithm.
  80  *
  81  * Invariants:
  82  *      front points to the beginning of a line at or before the first
  83  *      matching string.
  84  *
  85  *      back points to the beginning of a line at or after the first
  86  *      matching line.
  87  *
  88  * Base of the Invariants.
  89  *      front = NULL;
  90  *      back = EOF;
  91  *
  92  * Advancing the Invariants:
  93  *
  94  *      p = first newline after halfway point from front to back.
  95  *
  96  *      If the string at "p" is not greater than the string to match,
  97  *      p is the new front.  Otherwise it is the new back.
  98  *
  99  * Termination:
 100  *
 101  *      The definition of the routine allows it return at any point,
 102  *      since front is always at or before the line to print.
 103  *
 104  *      In fact, it returns when the chosen "p" equals "back".  This
 105  *      implies that there exists a string is least half as long as
 106  *      (back - front), which in turn implies that a linear search will
 107  *      be no more expensive than the cost of simply printing a string or two.
 108  *
 109  *      Trying to continue with binary search at this point would be
 110  *      more trouble than it's worth.
 111  */
 112 #define SKIP_PAST_NEWLINE(p, back) \
 113         while (p < back && *p++ != '\n') \
 114                 continue;
 115
 116 static u_char *
 117 binary_search(u_char *string, u_char *front, u_char *back)
 118 {
 119         u_char *p;
 120
 121         p = front + (back - front) / 2;
 122         SKIP_PAST_NEWLINE(p, back);
 123
 124         /*
 125          * If the file changes underneath us, make sure we don't
 126          * infinitely loop.
 127          */
 128         while (p < back && back > front) {
 129                 if (compare(string, p, back) > 0)
 130                         front = p;
 131                 else
 132                         back = p;
 133                 p = front + (back - front) / 2;
 134                 SKIP_PAST_NEWLINE(p, back);
 135         }
 136         return (front);
 137 }
 138
 139 /*
 140  * Find the first line that matches string, linearly searching from front
 141  * to back.
 142  *
 143  * Return NULL for no such line.
 144  *
 145  * This routine assumes:
 146  *
 147  *      o front points at the first character in a line.
 148  *      o front is before or at the first line to be printed.
 149  */
 150 static u_char *
 151 linear_search(u_char *string, u_char *front, u_char *back)
 152 {
 153         int result;
 154
 155         while (front < back) {
 156                 result = compare(string, front, back);
 157                 if (result == 0)
 158                         return (front); /* found it */
 159                 if (result < 0)
 160                         return (NULL);  /* not there */
 161
 162                 SKIP_PAST_NEWLINE(front, back);
 163         }
 164         return (NULL);
 165 }
 166
 167 static int
 168 compare(u_char *s1, u_char *s2, u_char *back)
 169 {
 170         int ch;
 171
 172         /* Note that s1 is already upper case. */
 173         for (;; ++s1, ++s2) {
 174                 if (*s2 == '\n' || s2 == back)
 175                         ch = '\0';
 176                 else if (isupper(*s2))
 177                         ch = _tolower(*s2);
 178                 else
 179                         ch = *s2;
 180                 if (*s1 != ch)
 181                         return (*s1 - ch);
 182                 if (ch == '\0')
 183                         return (0);
 184         }
 185 }