/*
 * kmp_sum.h --
 *
 *	Copyright (C) 1997 by Sony Computer Entertainment
 *			All rights Reserved
 */
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <memory.h>
#include "kmp_sub.h"

Search_key *create_search_key(char *key, int keylen)
{
    Search_key *result;
    char	*cp;
    int		*ip;
    int		str_i, key_i;

    result = malloc( sizeof(Search_key)
				  + keylen + (keylen+2)*sizeof(int));
    if( result == NULL ) {
	return result;
    }
    cp = (char *)result;
    result->skiptbl = (int *)(cp + sizeof(Search_key));
    ip = result->skiptbl;
    cp = (char *)ip;
    result->key =  cp+(keylen+2)*sizeof(int);
    result->point = 0;
    result->keylen = keylen;
    if( keylen == 0 ) return 0;	/* key is null --> allways found */
    memcpy(result->key,key,keylen);

    /*--- make skip table ---*/
    str_i = 1; key_i = 0; result->skiptbl[1] = 0;
    while( str_i < keylen ) {
	if( result->key[str_i]==result->key[key_i] )
    			{ str_i++; key_i++; result->skiptbl[str_i] = key_i; }
	else if( key_i==0 )	{ str_i ++;  result->skiptbl[str_i] = key_i; }
	else			{ key_i = result->skiptbl[key_i]; }
    }
    return result;
}

void	reset_search_key(Search_key *key)
{
    key->point = 0;
}

int	search_key(char *str, int strlen, Search_key *key)
{
    register int  si, ki;
    register int  *sktb = key->skiptbl;
    register char *keystr = key->key;

    if( key->keylen == 0 && key->point == 0 ) {
	key->point = 1;
	return 1;	/* key is null --> allways found */
    }
    if( key->point >= key->keylen ) return 0;	/* already found */

    si = 0;
    ki = key->point;
    while( si < strlen && key->keylen > ki ) {
	if( *str == keystr[ki] ) {
	    str++; si++; ki++;
	} else if( ki == 0 ) {
	    str++; si++;
	} else {
	    ki = sktb[ki];
	}
    }
    key->point = ki;
    if( key->keylen <= ki )
	return si;			/* found */
    else if( ki > 0 )
	return -1;			/* not found but now matching*/
    else
	return -2;			/* not found */

}

int	key_found_p(Search_key  *key)
{
    return ( key->keylen <= key->point );
}