turbo_index.c

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

		/* a return of OK means it was the first one inserted */
		if ( avl_insert( &pindex[ i ].i_root, (caddr_t) imem, index_cmp,
		    index_dup ) == OK ) {
			pindex[ i ].i_count++;
			imem = NULLINDEXNODE;

		} else if ( substr ) {
			save = AttrV_cpy( &av->avseq_av );
			savestr = (char *) save->av_struct;
			save->av_struct = strrev( savestr );
			AttrV_free( (AttributeValue) imem->in_value );
			free( savestr );
			imem->in_value = (caddr_t) save;
		} else {
			AttrV_free( (AttributeValue) imem->in_value );
			free( (char *) imem->in_entries );
			free( (char *) imem );
		}
		if ( substr && imem == NULLINDEXNODE ) {
			imem = (Index_node *) malloc( sizeof(Index_node) );

			save = AttrV_cpy( &av->avseq_av );
			savestr = (char *) save->av_struct;
			save->av_struct = strrev( savestr );
			free( savestr );
			imem->in_value = (caddr_t) save;
			imem->in_entries = (struct entry **) malloc(
			    sizeof(struct entry *) );
			imem->in_entries[ 0 ] = (struct entry *) e;
			imem->in_num = 1;
			imem->in_max = 1;
		}

		/* insert into the reverse index, if appropriate */
		if ( substr ) {
			if ( avl_insert( &pindex[ i ].i_rroot, (caddr_t) imem,
			    index_cmp, index_dup ) == OK ) {
				pindex[ i ].i_rcount++;
				imem = NULLINDEXNODE;

			} else {
				AttrV_free( (AttributeValue) imem->in_value );
				free( (char *) imem->in_entries );
				free( (char *) imem );
			}
		}

		if ( approxfn( attr->oa_syntax ) != soundex_match )
			continue;

		for ( word = first_word((char *) av->avseq_av.av_struct);
		    word; word = next_word( word ) ) {
			code = NULL;
			soundex( word, &code );
			imem = (Index_node *) malloc( sizeof(Index_node) );
			imem->in_value = (caddr_t) code;
			imem->in_entries = (struct entry **) malloc(
			    sizeof(struct entry *) );
			imem->in_entries[ 0 ] = (struct entry *) e;
			imem->in_num = 1;
			imem->in_max = 1;

			if ( avl_insert( &pindex[i].i_sroot, (caddr_t) imem, sindex_cmp,
			    index_dup ) == OK ) {
				pindex[ i ].i_scount++;
			} else {
				free( (char *) imem->in_value );
				free( (char *) imem->in_entries );
				free( (char *) imem );
			}
		}
	}
}

/*
 * turbo_add2index -- search through the given entry's attribute list for
 * attrs to optimize. if an attr to optimize is found, we add that attribute 
 * along with a pointer to the corresponding entry to the appropriate 
 * attribute index.
 */

turbo_add2index( e )
Entry	e;		/* the entry these attrs belong to */
{
	Entry		parent;
	Attr_Sequence	as, entry_find_type();
	DN		pdn, dn, tmpdn, prevdn, savedn;
	int		pcmp, nonleaf;
	Index		*subindex;
	Index		*sibindex;
	extern AttributeType at_masterdsa, at_slavedsa;

	if ( sibling_index == (Avlnode *) 0 && subtree_index == (Avlnode *) 0 )
		return;

	nonleaf = !e->e_leaf;

	parent = e->e_parent;
	pdn = get_copy_dn( parent );
	dn = get_copy_dn( e );

	sibindex = get_sibling_index( pdn );

	/* for each attribute in the entry... */
	for ( as = e->e_attributes; as != NULLATTR; as = as->attr_link ) {
		if ( turbo_isoptimized( as->attr_type ) == 0 )
			continue;
		SET_HEAP( as->attr_type );

		/* sibling index */
		if ( sibindex ) {
			(void) turbo_attr_insert( sibindex, e, as->attr_type,
			    as->attr_value );
		}

		savedn = NULLDN;
		while ( dn->dn_parent != NULLDN ) {
			if ( subindex = get_subtree_index( dn ) ) {
				(void) turbo_attr_insert( subindex, e,
				    as->attr_type, as->attr_value );
			}

			for ( prevdn = NULLDN, tmpdn = dn;
			    tmpdn->dn_parent != NULLDN;
			    prevdn = tmpdn, tmpdn = tmpdn->dn_parent )
				;	/* NULL */
			tmpdn->dn_parent = savedn;
			savedn = tmpdn;
			prevdn->dn_parent = NULLDN;
		}
		dn->dn_parent = savedn;
	}
	RESTORE_HEAP;

	/* now add references in nonleafkids and nonlocalaliases... */
	if ( sibindex )
		if ( e->e_alias && th_prefix( sibindex->i_dn, e->e_alias ) != -2 )
			add_nonlocalalias( e, sibindex );

	if ( nonleaf == 0 && e->e_alias == NULLDN ) {
		dn_free( dn );
		dn_free( pdn );
		return;
	}

	/* could be a subtree index with all parents & this node */
	savedn = NULLDN;
	while ( dn->dn_parent != NULLDN ) {
		if ( subindex = get_subtree_index( dn ) ) {
			if ( e->e_alias ) {
				pcmp = th_prefix( subindex->i_dn, e->e_alias );
				if ( pcmp > 0 )
					add_nonlocalalias(e, subindex);
			}

			if ( nonleaf )
				add_nonleafkid(e, subindex);
		}
		for ( prevdn = NULLDN, tmpdn = dn;
		    tmpdn->dn_parent != NULLDN;
		    prevdn = tmpdn, tmpdn = tmpdn->dn_parent )
			;	/* NULL */
		tmpdn->dn_parent = savedn;
		savedn = tmpdn;
		prevdn->dn_parent = NULLDN;
	}
	dn->dn_parent = savedn;

	dn_free( dn );
	dn_free( pdn );

	return;
}

/*
 * turbo_attr_delete -- delete entry e from index for values of attribute
 * attr.
 */

static turbo_attr_delete( pindex, e, attr, values )
Index		*pindex;
Entry		e;
AttributeType	attr;
AV_Sequence	values;
{
	int		i, j, k;
	AV_Sequence	av;
	Index_node	*node, *imem;
	struct entry	**p;
	char		*code, *word;
	char		*first_word(), *next_word();

	/* 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_delete: cannot find optimized attribute") );
		return;
	}

	/* delete all values */
	for ( av = values; av != NULLAV; av = av->avseq_next ) {
		node = (Index_node *) avl_find( pindex[ i ].i_root, 
		    (caddr_t) &av->avseq_av, (IFP)indexav_cmp );

		if ( node == NULLINDEXNODE ) {
			LLOG( log_dsap, LLOG_EXCEPTIONS, ("Optimized attribute value not found! (%s)\n", attr->oa_ot.ot_name) );
			continue;
		}

		/* find the entry we want to delete */
		p = node->in_entries;
		for ( j = 0; j < node->in_num; j++, p++ )
			if ( *p == (struct entry *) e )
				break;

		if ( j == node->in_num ) {
			LLOG( log_dsap, LLOG_EXCEPTIONS, ("Optimized av entry not found") );
			continue;
		}

		if ( --(node->in_num) == 0 ) {
			imem = (Index_node *) avl_delete( &pindex[ i ].i_root,
			    (caddr_t) &av->avseq_av, indexav_cmp );
			( void ) AttrV_free( (AttributeValue) imem->in_value );
			( void ) free( (char *) imem->in_entries );
			( void ) free( (char *) imem );
			pindex[ i ].i_count--;
		} else {
			for ( k = j; k < node->in_num; k++ )
				node->in_entries[ k ] =
				    node->in_entries[ k + 1 ];
			node->in_entries = (struct entry **)
			    realloc( (char *) node->in_entries, (unsigned) node->in_num
			    * sizeof(struct entry *) );
		}

		/* if there's a soundex index, delete from that too */
		if ( pindex[i].i_sroot == NULLAVL )
			continue;

		for ( word = first_word((char *)av->avseq_av.av_struct);
		    word != NULL; word = next_word( word ) ) {
			code = NULL;
			soundex( word, &code );

			/*
			 * not finding the node is ok if the entry happens
			 * to be the only one with this code and was deleted
			 * on a previous pass through this loop.  we hope.
			 */

			if ((imem = (Index_node *) avl_find(pindex[i].i_sroot,
			    code, index_soundex_cmp)) == NULLINDEXNODE) {
				free(code);
				continue;
			}

			/* find the entry */
			p = imem->in_entries;
			for ( j = 0; j < imem->in_num; j++, p++ )
				if ( *p == (struct entry *) e )
					break;

			/*
			 * not finding the entry is this is ok for the soundex
			 * index since an entry can appear more than once and
			 * might have already been deleted on a previous pass
			 */

			if ( j == imem->in_num )
				continue;

			if ( --(imem->in_num) == 0 ) {
				imem = (Index_node *)
				    avl_delete( &pindex[ i ].i_sroot,
				    (caddr_t) code, index_soundex_cmp );

				free( (char *) imem->in_value );
				free( (char *) imem->in_entries );
				free( (char *) imem );
			} else {
				for ( k = j; k < imem->in_num; k++ )
					imem->in_entries[ k ] =
					    imem->in_entries[ k+1 ];

				imem->in_entries = (struct entry **)
				    realloc( (char *) imem->in_entries,
				    (unsigned) imem->in_num * sizeof(struct entry *) );
			}
			free(code);
		}
	}
}

/*
 * turbo_index_delete -- delete attribute index entries for the given
 * entry from the attribute index associated with the entry's parent
 * node.
 */

turbo_index_delete( e )
Entry	e;
{
	Entry		parent;
	Attr_Sequence	as;
	DN		pdn, dn, tmpdn, prevdn, savedn;
	Index		*subindex;
	Index		*sibindex;
	int		pcmp, nonleaf;

	if ( subtree_index == NULLAVL && sibling_index == NULLAVL )
		return;

	nonleaf = (! isleaf(e));

	parent = e->e_parent;
	pdn = get_copy_dn( parent );
	dn = get_copy_dn( e );

	sibindex = get_sibling_index( pdn );

	/* for each attribute in the entry... */
	for ( as = e->e_attributes; as != NULLATTR; as = as->attr_link ) {
		if ( turbo_isoptimized( as->attr_type ) == 0 )
			continue;

		/* sibling index */
		if ( sibindex ) {
			(void) turbo_attr_delete( sibindex, e, as->attr_type,
			    as->attr_value );
		}

		savedn = NULLDN;
		while ( dn->dn_parent != NULLDN ) {
			if ( subindex = get_subtree_index( dn ) ) {
				(void) turbo_attr_delete( subindex, e,
				    as->attr_type, as->attr_value );
			}

			for ( prevdn = NULLDN, tmpdn = dn;
			    tmpdn->dn_parent != NULLDN;
			    prevdn = tmpdn, tmpdn = tmpdn->dn_parent )
				;	/* NULL */
			tmpdn->dn_parent = savedn;
			savedn = tmpdn;
			prevdn->dn_parent = NULLDN;
		}
		dn->dn_parent = savedn;
	}

	/* now delete references in nonleafkids and nonlocalaliases... */
	if ( sibindex && e->e_alias
	    && th_prefix( sibindex->i_dn, e->e_alias ) != -2 )
		delete_nonlocalalias( e, sibindex );

	if ( nonleaf == 0 && e->e_alias == NULLDN ) {
		dn_free( pdn );
		dn_free( dn );
		return;
	}

	/* could be a subtree index with all parents & this node */
	savedn = NULLDN;
	while ( dn->dn_parent != NULLDN ) {
		if ( subindex = get_subtree_index( dn ) ) {
			if ( e->e_alias ) {
				pcmp = th_prefix( subindex->i_dn, e->e_alias );
				if ( pcmp > 0 )
					delete_nonlocalalias( e, subindex );
			}

			if ( nonleaf )
				delete_nonleafkid( e, subindex );
		}
		for ( prevdn = NULLDN, tmpdn = dn;
		    tmpdn->dn_parent != NULLDN;
		    prevdn = tmpdn, tmpdn = tmpdn->dn_parent )
			;	/* NULL */
		tmpdn->dn_parent = savedn;
		savedn = tmpdn;
		prevdn->dn_parent = NULLDN;
	}
	dn->dn_parent = savedn;

	dn_free( pdn );
	dn_free( dn );

	return;
}

/*
 * turbo_isoptimized -- return TRUE if attr is to be optimized, FALSE
 * otherwise.
 */

turbo_isoptimized( attr )
AttributeType	attr;
{
	int	i;

	for ( i = 0; i < turbo_index_num; i++ ) {
		if ( AttrT_cmp( attr, turbo_index_types[ i ] ) == 0 )
			return( 1 );
	}

	return( 0 );
}

/*
 * turbo_optimize -- add attribute attr to the list of attributes to be 
 * optimized this routine creates an empty index and arranges for the 
 * attribute to be optimized during loading.
 */

turbo_optimize( attr )
char	*attr;
{
	AttributeType	a;

	if ( (a = str2AttrT( attr )) == NULLAttrT ) {
		LLOG(log_dsap, LLOG_EXCEPTIONS, ("Bad attribute type (%s)", attr));
		return;
	}

	if ( subtree_index || sibling_index )
		fatal( -99, "optimized attributes MUST be specified before subtree or sibling index" );

	if ( turbo_index_types == (AttributeType *) 0 )
		turbo_index_types = (AttributeType *) malloc(
		    sizeof(AttributeType *));
	else
		turbo_index_types = (AttributeType *) realloc(
		    (char *) turbo_index_types, (unsigned) (turbo_index_num + 1) *
		    sizeof(AttributeType *));

	if ( turbo_index_types == (AttributeType *) 0 )
		fatal(66, "turbo_optimize: malloc failed!\n");

	turbo_index_types[ turbo_index_num ] = AttrT_cpy(a);
	turbo_index_num++;

	return;
}

/*
 * index_subtree - arrange for the subtree starting at tree to be indexed.
 */

index_subtree( tree )
char	*tree;
{
	DN		dn, str2dn();
	Index		*pindex;

	if ( (dn = str2dn( tree )) == NULLDN ) {
		LLOG( log_dsap, LLOG_EXCEPTIONS, ("Invalid subtree (%s)\n", tree) );
		return;
	}
	if ( turbo_index_num == 0 ) {
		LLOG( log_dsap, LLOG_EXCEPTIONS, ("WARNING: cannot index subtree - no attributes have been optimized"));
		return;
	}

	pindex = new_index( dn );
	dn_free( dn );
	if ( avl_insert( &subtree_index, (caddr_t) pindex, i_cmp, i_dup ) == NOTOK ) {
		LLOG(log_dsap, LLOG_EXCEPTIONS, ("Subtree index for %s already exists\n", tree));
		index_free( pindex );
	}

	return;
}

/*
 * index_siblings - arrange for the children of parent to be indexed.
 */

index_siblings( parent )
char	*parent;
{
	DN		dn, str2dn();
	Index		*pindex;

	if ( (dn = str2dn( parent )) == NULLDN ) {
		LLOG( log_dsap, LLOG_EXCEPTIONS, ("Invalid parent (%s)\n", parent) );
		return;
	}
	if ( turbo_index_num == 0 ) {
		LLOG( log_dsap, LLOG_EXCEPTIONS, ("WARNING: cannot index siblings - no attributes have been optimized"));
		return;
	}

	pindex = new_index( dn );
	dn_free( dn );
	if ( avl_insert( &sibling_index, (caddr_t) pindex, i_cmp, i_dup ) == NOTOK ) {
		LLOG(log_dsap, LLOG_EXCEPTIONS, ("Sibling index for %s already exists\n", parent));
		index_free( pindex );
	}

	return;
}

#endif /* turbo_index */