turbo_index.c

来自「ftam等标准协议服务器和客户端的源代码。」· C语言 代码 · 共 1,015 行 · 第 1/2 页

/* turbo_index.c */

#ifndef	lint
static char *rcsid = "$Header: /xtel/isode/isode/dsap/common/RCS/turbo_index.c,v 9.0 1992/06/16 12:12:39 isode Rel $";
#endif

/* 
 * $Header: /xtel/isode/isode/dsap/common/RCS/turbo_index.c,v 9.0 1992/06/16 12:12:39 isode Rel $
 *
 *
 * $Log: turbo_index.c,v $
 * Revision 9.0  1992/06/16  12:12:39  isode
 * Release 8.0
 *
 */

/*
 *				  NOTICE
 *
 *    Acquisition, use, and distribution of this module and related
 *    materials are subject to the restrictions of a license agreement.
 *    Consult the Preface in the User's Manual for the full terms of
 *    this agreement.
 *
 */


#include <stdio.h>
#include "quipu/config.h"
#include "quipu/attr.h"
#include "quipu/entry.h"
#include "quipu/turbo.h"
#include "logger.h"
#include "quipu/malloc.h"

#ifdef TURBO_INDEX

extern LLog * log_dsap;

AttributeType	*turbo_index_types;	/* array of attributes to optimize */
int		turbo_index_num;	/* number of attributes to optimize */
Avlnode		*subtree_index;		/* array of subtree indexes */
Avlnode		*sibling_index;		/* array of sibling indexes */
int		optimized_only;		/* only allow indexed searches */

char *strrev( s )
char	*s;
{
	char	*start, *rev, *rsave;
	int	len;

	len = strlen( start = s );
	rsave = rev = malloc( (unsigned) (len + 1) );
	for ( s += len; s != start; *rev++ = *--s )
		;	/* NULL */
	*rev = '\0';
	return( rsave );
}

static index_cmp( a, b )
Index_node	*a;
Index_node	*b;
{
	return( AttrV_cmp( (AttributeValue) a->in_value,
	    (AttributeValue) b->in_value ) );
}

static sindex_cmp( a, b )
Index_node	*a;
Index_node	*b;
{
	return( strcmp( (char *) a->in_value, (char *) b->in_value ) );
}

index_soundex_cmp( code, node )
char		*code;
Index_node	*node;
{
	return( strcmp( code, (char *) node->in_value ) );
}

index_soundex_prefix( code, node, len )
char		*code;
Index_node	*node;
int		len;
{
	return( strncmp( code, (char *) node->in_value, len ) );
}

substring_prefix_cmp( val, node, len )
char		*val;
Index_node	*node;
int		len;
{
	return(strncmp(val,
	    (char *) (((AttributeValue) node->in_value)->av_struct), len));
}

substring_prefix_tel_cmp( val, node, len )
char		*val;
Index_node	*node;
int		len;
{
	return(telncmp(val,
	    (char *) (((AttributeValue) node->in_value)->av_struct), len));
}

substring_prefix_case_cmp( val, node, len )
char		*val;
Index_node	*node;
int		len;
{
	return(lexnequ(val,
	    (char *) (((AttributeValue) node->in_value)->av_struct), len));
}

indexav_cmp( av, node )
AttributeValue	av;
Index_node	*node;
{
	return( AttrV_cmp( av, (AttributeValue) node->in_value ) );
}

Index_node *new_indexnode()
{
	Index_node	*new;

	new = (Index_node *) malloc( sizeof(Index_node) );
	new->in_value = (caddr_t) NULLAttrV;
	new->in_entries = (Entry *) 0;
	new->in_num = 0;
	new->in_max = 0;

	return( new );
}

static index_dup( node, dup )
Index_node	*node;
Index_node	*dup;
{
	int	j;
	int	low, mid, high;
	Entry	tmp1, tmp2;

	/* 
	 * Check for duplicates.  If there are over 20 elements we do
	 * a binary search, otherwise a simple linear one.  This is just
	 * a guess.  It seems to work pretty well, though.
	 */

	tmp1 = dup->in_entries[0];

	if ( node->in_num > 20 ) {
		low = 0;
		high = node->in_num - 1;
		mid = (low + high) / 2;
		while ( low < high ) {
			if ( node->in_entries[mid] < tmp1 )
				low = mid + 1;
			else if ( node->in_entries[mid] > tmp1 )
				high = mid - 1;
			else
				break;	/* found a duplicates */

			mid = (low + high) / 2;
		}

		if ( node->in_entries[mid] == tmp1 )
			return( NOTOK );
		else if ( node->in_entries[mid] < tmp1 )
			mid++;
	} else {
		for ( mid = 0; mid < node->in_num; mid++ ) {
			if ( node->in_entries[mid] == tmp1 )
				return( NOTOK );
			if ( node->in_entries[mid] > tmp1 )
				break;
		}
	}

	/*
	 * Realloc double the space we got last time.  This may waste
	 * some space in the index, but it speeds things up, works
	 * around the QUIPU_MALLOC problem, and cuts down on fragmentation.
	 */

	if (node->in_num >= node->in_max) {
		if (node->in_max == 0)
			node->in_max = 1;
		else
			node->in_max *= 2;
		node->in_entries =
		    (struct entry **) realloc((char *)node->in_entries, 
		    (unsigned) (sizeof(struct entry *) * node->in_max));
	}
	node->in_num++;

	tmp1 = dup->in_entries[0];
	for (j = mid; j < node->in_num; j++) {
		tmp2 = node->in_entries[j];
		node->in_entries[j] = tmp1;
		tmp1 = tmp2;
	}

	return( NOTOK );
}

static indexav_free( node )
Index_node	*node;
{
	AttrV_free( (AttributeValue) node->in_value );
	free( (char *) node->in_entries );
	free( (char *) node );
}

static soundex_free( node )
Index_node	*node;
{
	free( (char *) node->in_value );
	free( (char *) node->in_entries );
	free( (char *) node );
}

static index_free( pindex )
Index	*pindex;
{
	dn_free( pindex->i_dn );
	(void) avl_free( pindex->i_root, indexav_free );
	(void) avl_free( pindex->i_sroot, soundex_free );
	free( (char *) pindex );
}

/* ARGSUSED */
static i_dup( a )
Index	*a;
{
	return( NOTOK );
}

static i_cmp( a, b )
Index	*a;
Index	*b;
{
	return( dn_order_cmp( a->i_dn, b->i_dn ) );
}

idn_cmp( a, b )
DN	a;
Index	*b;
{
	return( dn_order_cmp( a, b->i_dn ) );
}

/*
 * th_prefix - returns the following:
 *	-2	=>	b is an immediate child of a
 *      -1      =>      a is some other prefix of b
 *      0       =>      a and b are equal
 *      1       =>      b is a prefix of a
 *      2       =>      neither a nor b is a prefix of the other
 */

th_prefix( a, b )
DN      a;
DN      b;
{
        for ( ; a && b; a = a->dn_parent, b = b->dn_parent )
                if ( dn_comp_cmp( a, b ) == NOTOK )
                        return( 2 );    /* neither is prefix */

        if ( a == NULLDN && b == NULLDN )
                return( 0 );            /* they are equal */
        else if ( a == NULLDN && b->dn_parent == NULLDN )
                return( -2 );           /* b is a child is a */
        else if ( a == NULLDN )
                return( -1 );           /* a is a prefix of b */
        else
                return( 1 );            /* b is a prefix of a */
}

static Index *new_index( dn )
DN	dn;
{
	Index	*pindex;
	int	i;

	pindex = (Index *) malloc( (unsigned) (sizeof(Index) * turbo_index_num ));

	for ( i = 0; i < turbo_index_num; i++ ) {
		pindex[ i ].i_attr = turbo_index_types[ i ];
		pindex[ i ].i_count = 0;
		pindex[ i ].i_rcount = 0;
		pindex[ i ].i_scount = 0;
		pindex[ i ].i_root = NULLAVL;
		pindex[ i ].i_rroot = NULLAVL;
		pindex[ i ].i_sroot = NULLAVL;
		pindex[ i ].i_nonleafkids = (struct entry **) 0;
		pindex[ i ].i_nonlocalaliases = (struct entry **) 0;
		pindex[ i ].i_dn = dn_cpy( dn );
	}

	return( pindex );
}

#ifdef notdef

/* ARGSUSED */
static print_soundex_node( n, ps )
Index_node	*n;
int		ps;
{
	int	i;

	(void) printf( "\t(%s)\n",n->in_value );
	for ( i = 0; i < n->in_num; i++ )
		(void) printf( "\t\t%s\n",
		    n->in_entries[i]->e_name->rdn_av.av_struct);
	return( OK );
}

#endif /* not used */

/*
 * add_nonlocalalias - add entry e to the list of nonlocal aliases
 * kept with index index.
 */

static add_nonlocalalias( e, pindex )
Index		*pindex;
struct entry	*e;
{
	struct entry	**tmp;
	int		i;

	if ( pindex == NULLINDEX )
		return;

	if ( pindex->i_nonlocalaliases == (struct entry **) 0 ) {
		pindex->i_nonlocalaliases = (struct entry **) malloc(
		    sizeof(struct entry *) * 2 );
		pindex->i_nonlocalaliases[ 0 ] = (struct entry *) 0;
	}

	/* first, check for duplicates */
	for ( i = 0, tmp = pindex->i_nonlocalaliases;
	    *tmp != (struct entry *) 0; 
	    tmp++, i++ ) {
		if ( *tmp == e )
			return;
	}

	pindex->i_nonlocalaliases = (struct entry **) realloc(
	    (char *)pindex->i_nonlocalaliases, (unsigned) sizeof(struct entry *) * (i + 2) );

	pindex->i_nonlocalaliases[ i ] = e;
	pindex->i_nonlocalaliases[ i + 1 ] = NULLENTRY;
}

/* 
 * addnonleafkids - add entry e to the list of nonlocal kids kept
 * in index index.
 */

static add_nonleafkid( e, pindex )
Index		*pindex;
struct entry	*e;
{
	struct entry	**tmp;
	int		i;

	if ( pindex == NULLINDEX )
		return;

	if ( pindex->i_nonleafkids == (struct entry **) 0 ) {
		pindex->i_nonleafkids = (struct entry **) malloc(sizeof(Entry));
		pindex->i_nonleafkids[ 0 ] = (Entry) 0;
	}

	/* first, check for duplicates */
	for ( i = 0, tmp = pindex->i_nonleafkids; *tmp != NULLENTRY;
	    tmp++, i++ ) {
		if ( *tmp == e ) {
			return;
		}
	}

	pindex->i_nonleafkids = (struct entry **) realloc(
	    (char *) pindex->i_nonleafkids,
	    (unsigned) (sizeof(struct entry *) * (i + 2)) );

	pindex->i_nonleafkids[ i ] = e;
	pindex->i_nonleafkids[ i + 1 ] = NULLENTRY;
}

/*
 * delete_nonleafkid - delete a reference to nonleaf child entry e
 * in index index.
 */

static delete_nonleafkid( e, pindex )
struct entry	*e;
Index		*pindex;
{
	int		i, j;
	struct entry	**tmp;

	if ( pindex->i_nonleafkids == (struct entry **) 0 ) {
		LLOG(log_dsap, LLOG_EXCEPTIONS, ("Index has no non-leaf entries"));
		return;
	}

	for ( i = 0, tmp = pindex->i_nonleafkids; *tmp; tmp++, i++ )
		if ( *tmp == e ) break;

	if ( *tmp == NULLENTRY ) {
		LLOG(log_dsap, LLOG_EXCEPTIONS, ("Cannot find non-leaf entry"));
		return;
	}

	for ( j = i + 1; pindex->i_nonleafkids[ j ]; j++ )
		pindex->i_nonleafkids[ j - 1 ] = pindex->i_nonleafkids[ j ];
	pindex->i_nonleafkids[ j - 1 ] = NULLENTRY;

	return;
}

/*
 * delete_nonlocalalias - delete a reference to nonlocal alias entry e
 * in index index.
 */

static delete_nonlocalalias( e, pindex )
struct entry	*e;
Index		*pindex;
{
	int		i, j;
	struct entry	**tmp;

	if ( pindex->i_nonlocalaliases == (struct entry **) 0 ) {
		LLOG(log_dsap, LLOG_EXCEPTIONS, ("index has no non-local aliases"));
		return;
	}

	for ( i = 0, tmp = pindex->i_nonlocalaliases; *tmp; tmp++, i++ )
		if ( *tmp == e ) break;

	if ( *tmp == (struct entry *) 0 ) {
		LLOG(log_dsap, LLOG_EXCEPTIONS, ("Cannot find non-local alias"));
		return;
	}

	for ( j = i + 1; pindex->i_nonlocalaliases[ j ]; j++ )
		pindex->i_nonlocalaliases[ j - 1 ] =
		    pindex->i_nonlocalaliases[ j ];
	pindex->i_nonlocalaliases[ j - 1 ] = NULLENTRY;

	return;
}

/*
 * turbo_attr_insert -- mark entry e as having attribute value val in
 * index for attribute type attr.
 */

static turbo_attr_insert( pindex, e, attr, values )
Index		*pindex;
Entry		e;
AttributeType	attr;
AV_Sequence	values;
{
	int		i;
	int		substr;
	AV_Sequence	av;
	AttributeValue	save;
	Index_node	*imem;
	char		*word, *code, *savestr;
	char		*first_word(), *next_word();
	IFP		approxfn();
	int		soundex_match();

	/* find the appropriate index */
	for ( i = 0; i < turbo_index_num; i++ )
		if ( AttrT_cmp( pindex[ i ].i_attr, attr ) == 0 )
			break;

	if ( i == turbo_index_num ) {
		LLOG( log_dsap, LLOG_EXCEPTIONS, ("turbo_attr_insert: cannot find optimized attribute") );
		return;
	}

	substr = sub_string( attr->oa_syntax );
	/* insert all values */
	for ( av = values; av != NULLAV; av = av->avseq_next ) {
		imem = (Index_node *) malloc( sizeof(Index_node) );
		imem->in_value = (caddr_t) AttrV_cpy( &av->avseq_av );
		imem->in_entries = (struct entry **) malloc( sizeof(struct
		    entry *) );
		imem->in_entries[ 0 ] = (struct entry *) e;
		imem->in_num = 1;
		imem->in_max = 1;

		/*
		 * Now we insert the entry into the appropriate index.
		 * If the attribute has a soundex approximate matching
		 * function, we insert the entry into the appropriate
		 * soundex index for that attribute.
		 */