mapitem.cc #1

/*
 * Copyright 1995, 1996 Perforce Software.  All rights reserved.
 *
 * This file is part of Perforce - the FAST SCM System.
 */

/*
 * MapItem -- mapping entries on a chain
 *
 * A MapItem holds two MapHalfs that constitute a single entry in
 * a MapTable.  MapItem also implement fast searching for entries
 * for MapTable::Check() and MapTable::Translate().
 */

# include <stdhdrs.h>
# include <error.h>
# include <strbuf.h>
# include <vararray.h>

# include <debug.h>

# include "maphalf.h"
# include "maptable.h"
# include "mapstring.h"
# include "mapdebug.h"
# include "mapitem.h"

/*
 * MapItem::Reverse - reverse the chain, to swap precedence
 */

MapItem *
MapItem::Reverse()
{
	MapItem *m = this;
	MapItem *entry = 0;
	int top = m ? m->slot : 0;

	while( m )
	{
	    MapItem *n = m->chain;
	    m->chain = entry;
	    m->slot = top - m->slot;
	    entry = m;
	    m = n;
	}

	return entry;
}

/*
 * MapItem::Tree - recursively construct a trinary sort tree
 */

MapItem *
MapItem::Tree( 
	MapItem **start,
	MapItem **end,
	MapTableT dir,
	MapItem *parent,
	int &depth )
{
	/* No empties */

	if( start == end )
	    return 0;

	/*
	 * start li (middle) ri end 
	 *
	 * (middle) is halfway between start and end.
	 * li is first item that is a parent of middle.
	 * ri is last item li is a parent of.
	 *
	 * We return
	 *
	 *	         *li
	 *             /  |  \
	 *            /   |   \
	 *	     /    |    \
	 *          /     |     \
	 * start->li   li+1->ri  ri->end
	 */

	MapItem **li = start;
	MapItem **ri;

	/*
	 * Quick check: the center tree often ends up in the
	 * shape of a linked list (due to identical entries).
	 * This is an optimization for that case.
	 */

	if( start == end - 1 || (*start)->IsParent( end[-1], dir ) )
	{
	    ri = end;

	    int overlap = 0;
	    int depthBelow = 0;
	    int maxSlot = 0;
	    int pLength = (*start)->Ths( dir )->GetFixedLen();

	    MapItem *last = 0;
	    MapItem::MapWhole *t;

	    while( --ri > start )
		if( (*ri)->Ths( dir )->GetFixedLen() == pLength )
		    break;

	    if( parent )
		overlap = (*start)->Ths( dir )->GetCommonLen( parent->Ths( dir ) );
	    if( ri < end - 1 )
	    {
		t = (*ri)->Whole( dir );

		t->overlap = overlap;
		t->maxSlot = (*ri)->slot;
		t->right = t->left = NULL;

		t->center = Tree( ri + 1, end, dir, *ri, depthBelow );

		if( maxSlot < t->maxSlot )
		    maxSlot = t->maxSlot;

		last = *ri--;
		++depthBelow;
	    }

	    depthBelow += ri - start + 1;

	    while( ri >= start )
	    {
		t = (*ri)->Whole( dir );

		t->overlap = overlap;
		if( maxSlot < (*ri)->slot )
		    maxSlot = (*ri)->slot;
		t->maxSlot = maxSlot;
		t->right = t->left = NULL;
		t->center = last;
		last = *ri--;
	    }

	    if( parent && parent->Whole( dir )->maxSlot < maxSlot )
		parent->Whole( dir )->maxSlot = maxSlot;

	    if( depth < depthBelow )
		depth = depthBelow;

	    return *li;
	}
	else 

	/*
	 * Start in middle.
	 * Move li from start until we find first parent of ri.
	 * Move ri right until we find last child of li.
	 */

	{
	    ri = start + ( end - start ) / 2;

	    while( li < ri && !(*li)->IsParent( *ri, dir ) )
		++li;

	    while( ri < end && (*li)->IsParent( *ri, dir ) )
		++ri;
	}

	/*
	 * Fill in the *li node, which we will return.
	 *
	 * left, right, center computed recursively.
	 */

	MapItem::MapWhole *t = (*li)->Whole( dir );

	int depthBelow = 0;

	t->overlap = 0;
	t->maxSlot = (*li)->slot;

	t->left =    Tree( start, li, dir, *li, depthBelow );
	t->center =  Tree( li + 1, ri, dir, *li, depthBelow );
	t->right =   Tree( ri, end, dir, *li, depthBelow );

	/*
	 * Current depth is 1 + what's below us, as long as one of
	 * our peers isn't deeper.
	 */

	if( depth < depthBelow + 1 )
	    depth = depthBelow + 1;

	/*
	 * Relationship to parent:
	 * parent's maxSlot includes our maxSlot.
	 * our initial substring overlap with our parent.
	 */

	if( parent )
	{
	    if( parent->Whole( dir )->maxSlot < t->maxSlot )
		parent->Whole( dir )->maxSlot = t->maxSlot;

	    t->overlap = t->half.GetCommonLen( parent->Ths( dir ) );
	}

	return *li;
}

/*
 * MapItem::Match() - find best matching MapItem
 *
 * We have a chain of MapItems, but instead use trinary tree constructed
 * by MapItem::Tree for this direction.
 *
 * This has three separate optimizations:
 *
 *	1. The trinary tree itself (instead of a linear scan).  We use
 *	   a trinary tree because we need to order mappings that are
 *	   neither less than nor greater than others, but including them.
 *	   e.g. //depot/main/... includes //depot/main/p4...  As we
 *	   decend the tree, we use MapHalf::Match1 to compare the initial
 *	   substring.  If it matches, we will use MapHalf::Match2 to
 *	   do the wildcard comparison and then follow the center down.
 *
 *	2. Slot precedence.  Once we've had a match, we only need to Match2
 *	   nodes with better precedence (map->slot > best).  Further, once
 *	   we've had a match, we can give up entirely if the tree below
 *	   has no nodes with higher precedence (best > t->maxSlot).
 *
 *	3. Overlap.  As we decend the tree, many of the strings have
 *	   initial substrings in common.  So we remember the offset of 
 *	   the last matching character in the parent's MapHalf, adjust it 
 *	   down if needed so as not to exceed the operlap with this
 *	   MapHalf, and start the match from there.
 */

MapItem *
MapItem::Match( MapTableT dir, const StrPtr &from )
{
	int coff = 0;
	int best = -1;
	MapItem *map = 0;
	MapItem *tree = this;
	MapParams params;

	/* Decend */

	while( tree )
	{
	    MapItem::MapWhole *t = tree->Whole( dir );

	    /*
	     * No better precendence below?  Bail. 
	     */

	    if( best > t->maxSlot )
		break;

	    /*
	     * Match with prev map greater than overlap?  trim. 
	     */

	    if( coff > t->overlap )
		coff = t->overlap;

	    /*
	     * Match initial substring (by which the tree is ordered). 
	     * Can skip match if same initial substring as previous map.
	     */

	    int r = 0;

	    if( coff < t->half.GetFixedLen() )
		r = t->half.Match1( from, coff );

	    /*
	     * Match?  Higher precedence?  Wildcard match?  Save. 
	     */

	    if( !r && best < tree->slot && t->half.Match2( from, params ) )
		map = tree, best = map->slot;

	    /*
	     * Follow to appropriate child. 
	     */

	    if( r < 0 ) 	tree = t->left;
	    else if( r > 0 ) 	tree = t->right;
	    else 		tree = t->center;
	}

	/* 
	 * Best mapping an unmapping?  That's no mapping.
	 */

	if( !map || map->mapFlag == MfUnmap )
	    return 0;

	return map;
}

/*
 * MapPairArray -- pre-join two maps by using the MapTrees
 */

int 
MapPairArray::Compare( const void *a1, const void *a2 ) const
{
	return ((MapPair *)a1)->CompareSlot( (MapPair *)a2 );
}

void
MapPairArray::Match( MapItem *item1, MapItem *tree2 )
{
	// Do non-wildcard initial substrings match?

	MapItem::MapWhole *t1 = item1->Whole( dir1 );

	do {

	    MapItem::MapWhole *t2 = tree2->Whole( dir2 );

	    int r = t2->half.MatchHead( t1->half );

	    if( DEBUG_JOIN )
		p4debug.printf("cmp %d %s %s\n", r, t1->half.Text(), t2->half.Text() );

	    // On match, add this to list of pairs for MapHalf::Join()

	    if( !r && !t2->half.MatchTail( t1->half ) )
		Put( new MapPair( item1, tree2, &t1->half, &t2->half ) );

	    // Recursively explore other matching possibilities.

	    if( r <= 0 && t2->left )   Match( item1, t2->left );
	    if( r >= 0 && t2->right )  Match( item1, t2->right );

	    if( r != 0 )
		return;

	    // tail iteration down the center

	    tree2 = t2->center;
	} while( tree2 );
}

/*
* MapItem::Dump() - dump tree, rooted at this
 */

void
MapItem::Dump( MapTableT d, const char *name, int l )
{
	static const char tabs[] = "\t\t\t\t\t\t\t\t";
	const char *indent = l > 8 ? tabs : tabs + 8 - l;

	if( !l )
	    p4debug.printf( "MapTree\n" );

	if( Whole( d )->left ) 
	    Whole( d )->left->Dump( d, "<<<", l+1 );

	p4debug.printf("%s%s %c%s\n", indent, name, " -+$"[ mapFlag ], Ths(d)->Text() );

	if( Whole( d )->center )
	    Whole( d )->center->Dump( d, "===", l+1 );

	if( Whole( d )->right )
	    Whole( d )->right->Dump( d, ">>>", l+1 );
}