/* strings.c -- Copyright 1989, 1994 Liam R. Quin.
 * All Rights Reserved.
 * This code is NOT in the public domain.
 * See the file COPYRIGHT for full details.
 */

/* $Id: strings.c,v 1.5 1995/09/06 15:59:21 lee Exp $ */

/* LQU_StringContainedIn(s1, s2) - true if s2 contains an instance of s1;
 */


#include "error.h"
#include <stdio.h>
#include <sys/types.h>
#include "globals.h"
#include "lqutil.h"

#ifdef HAVE_STRING_H
# include <string.h>
#else
# include <strings.h>
#endif /*HAVE_STRING_H*/


# if 0

/* A little helper function... but not needed because it's included
 * inline in Strcontains().  It's here in case I ever want it again!
 * Modern Unix systems have a library routine to do this, see strstr.
 */

PRIVATE INLINE int
strprefix(Prefix, String)
    register char *Prefix;
    register char *String;
{
    while (*String++ == *Prefix++) {
	if (!*Prefix) return 1;
    }
    return 0;
}

#endif

/* <Function>
 *   <Name>LQU_StringContainedIn
 *   <Class>Utilities/Strings
 *   <Purpose>
 *      Determines whether the given ShortString is contained anywhere 
 *	in the LongString, and, if so, returns non-zero.
 *   <Returns>
 *      <LIST>
 *        <LI>1 if the shorter string is contained in the longer, or
 *	      if the strings are equal, of if ShortString is of length zero
 *        <LI>0 otherwise
 *	</LIST>
 *   <Notes>
 *	See strstr for a more efficient way to do this.  Some Unix systems
 *	do not have strstr, though.
 *   </Notes>
 * </Function>
 */
API int
LQU_StringContainedIn(ShortString, LongString)
    CONST char *ShortString;
    CONST char *LongString;
{
    register CONST char *p;
    unsigned int LongStringLength;
    unsigned int ShortStringLength;
    int LastShortCharacter;

    /* This is basically a simple "grep" algorithm.
     * Adding Boyer-Moore style delta tables would speed it up, but
     * it isn't used all that often in lq-text - at most a dozen or so
     * times per input file.  I've gone as far as putting strprefix() inline,
     * to save a few function calls, but that's all.
     */

    if (!LongString || !*LongString || !ShortString) {
	return 0;
    } else if (!ShortString) {
	return 1; /* null prefix */
    }

    LongStringLength = strlen(LongString);

    ShortStringLength = 0;
    for (p = ShortString; *p; p++) {
	++ShortStringLength;
    }

    LastShortCharacter = p[ShortStringLength - 1];

    for (
	p = LongString;
	p - LongString <= LongStringLength - ShortStringLength;
	p++
    ) {
	/* check both the first and last strings are equal.
	 * This is a slight burden on 1-character prefixes, but
	 * potentially a big win on what is otherwise an n^2
	 * algorithm if the two strings are of nearly equal lengths.
	 */
	if (
	    *p == *ShortString &&
	    p[ShortStringLength - 1] == LastShortCharacter
	) {
	    register CONST char *String = p;
	    register CONST char *Prefix = ShortString;

	    while (*String++ == *Prefix++) {
		if (!*Prefix) {
		    return 1;
		}
	    }
	}
    }
    return 0;
}