Home | History | Annotate | Line # | Download | only in spellprog
look.c revision 1.1 
      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 u_char	*binary_search(u_char *, u_char *, u_char *);
     52 u_char	*linear_search(u_char *, u_char *, u_char *);
     53 int	 compare(u_char *, u_char *, u_char *);
     54 int	 look(u_char *, u_char *, u_char *);
     55 
     56 int
     57 look(u_char *string, u_char *front, u_char *back)
     58 {
     59 	u_char *s;
     60 
     61 	/* Convert string to lower case before searching. */
     62 	for (s = string; *s; s++) {
     63 		if (isupper(*s))
     64 			*s = _tolower(*s);
     65 	}
     66 
     67 	front = binary_search(string, front, back);
     68 	front = linear_search(string, front, back);
     69 
     70 	return (front != NULL);
     71 }
     72 
     73 /*
     74  * Binary search for "string" in memory between "front" and "back".
     75  *
     76  * This routine is expected to return a pointer to the start of a line at
     77  * *or before* the first word matching "string".  Relaxing the constraint
     78  * this way simplifies the algorithm.
     79  *
     80  * Invariants:
     81  * 	front points to the beginning of a line at or before the first
     82  *	matching string.
     83  *
     84  * 	back points to the beginning of a line at or after the first
     85  *	matching line.
     86  *
     87  * Base of the Invariants.
     88  * 	front = NULL;
     89  *	back = EOF;
     90  *
     91  * Advancing the Invariants:
     92  *
     93  * 	p = first newline after halfway point from front to back.
     94  *
     95  * 	If the string at "p" is not greater than the string to match,
     96  *	p is the new front.  Otherwise it is the new back.
     97  *
     98  * Termination:
     99  *
    100  * 	The definition of the routine allows it return at any point,
    101  *	since front is always at or before the line to print.
    102  *
    103  * 	In fact, it returns when the chosen "p" equals "back".  This
    104  *	implies that there exists a string is least half as long as
    105  *	(back - front), which in turn implies that a linear search will
    106  *	be no more expensive than the cost of simply printing a string or two.
    107  *
    108  * 	Trying to continue with binary search at this point would be
    109  *	more trouble than it's worth.
    110  */
    111 #define	SKIP_PAST_NEWLINE(p, back) \
    112 	while (p < back && *p++ != '\n');
    113 
    114 u_char *
    115 binary_search(u_char *string, u_char *front, u_char *back)
    116 {
    117 	u_char *p;
    118 
    119 	p = front + (back - front) / 2;
    120 	SKIP_PAST_NEWLINE(p, back);
    121 
    122 	/*
    123 	 * If the file changes underneath us, make sure we don't
    124 	 * infinitely loop.
    125 	 */
    126 	while (p < back && back > front) {
    127 		if (compare(string, p, back) > 0)
    128 			front = p;
    129 		else
    130 			back = p;
    131 		p = front + (back - front) / 2;
    132 		SKIP_PAST_NEWLINE(p, back);
    133 	}
    134 	return (front);
    135 }
    136 
    137 /*
    138  * Find the first line that matches string, linearly searching from front
    139  * to back.
    140  *
    141  * Return NULL for no such line.
    142  *
    143  * This routine assumes:
    144  *
    145  * 	o front points at the first character in a line.
    146  *	o front is before or at the first line to be printed.
    147  */
    148 u_char *
    149 linear_search(u_char *string, u_char *front, u_char *back)
    150 {
    151 	int result;
    152 
    153 	while (front < back) {
    154 		result = compare(string, front, back);
    155 		if (result == 0)
    156 			return (front);	/* found it */
    157 		if (result < 0)
    158 			return (NULL);	/* not there */
    159 
    160 		SKIP_PAST_NEWLINE(front, back);
    161 	}
    162 	return (NULL);
    163 }
    164 
    165 int
    166 compare(u_char *s1, u_char *s2, u_char *back)
    167 {
    168 	int ch;
    169 
    170 	/* Note that s1 is already upper case. */
    171 	for (;; ++s1, ++s2) {
    172 		if (*s2 == '\n' || s2 == back)
    173 			ch = '\0';
    174 		else if (isupper(*s2))
    175 			ch = _tolower(*s2);
    176 		else
    177 			ch = *s2;
    178 		if (*s1 != ch)
    179 			return (*s1 - ch);
    180 		if (ch == '\0')
    181 			return (0);
    182 	}
    183 }
    184