mapitem.cc #2

  • //
  • guest/
  • perforce_software/
  • p4/
  • 2016-1/
  • dbsupp/
  • mapitem.cc
  • View
  • Commits
  • Open Download .zip Download (13 KB)
/*
 * 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::Move - moves an item up the chain
 */

MapItem *
MapItem::Move( int slot )
{
	MapItem *m = this;
	MapItem *entry = m->chain;

	int start = m->slot;

	// This has no error state, but this is bad
	// We can't go below 0 and we can't go back up either
	if( start <= slot )
	    return m;

	if( slot < 0 )
	    slot = 0;


	MapItem *n = m->chain;
	while( n )
	{
	    if( n->slot != slot )
	    {
	        n->slot++;
	        n = n->chain;
	        continue;
	    }
	    
	    n->slot++;
	    m->slot = slot;
	    m->chain = n->chain;
	    n->chain = m;
	    
	    break;
	}

	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 hasands = 0;
	    int maxSlotNoAnds = -1;
	    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->hasands = 0;
		t->maxSlotNoAnds = (*ri)->Flag() != MfAndmap ? (*ri)->slot : -1;

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

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

		if( t->hasands )
		    hasands = 1;

		if( parent && ( (*ri)->mapFlag == MfAndmap || t->hasands ) )
		    parent->Whole( dir )->hasands = 1;

		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;

		if( (*ri)->Flag() != MfAndmap && maxSlotNoAnds < (*ri)->slot )
		    maxSlotNoAnds = (*ri)->slot;
		t->maxSlotNoAnds = maxSlotNoAnds;

		hasands = ( last && last->mapFlag == MfAndmap ) ? 1 : 0;
		t->hasands = hasands;

		t->right = t->left = NULL;
		t->center = last;
		last = *ri--;
	    }

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

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

	    if( parent && ( hasands || ( last && last->mapFlag == MfAndmap ) ))
		parent->Whole( dir )->hasands = 1;

	    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->hasands = 0;
	t->maxSlotNoAnds = (*li)->Flag() != MfAndmap ? (*li)->slot : -1;

	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;

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

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

	    if( (*li)->mapFlag == MfAndmap || t->hasands )
		parent->Whole( dir )->hasands = 1;
	}

	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, MapItemArray *ands )
{
	int coff = 0;
	int best = -1;
	int bestnotands = -1;
	int ourarray = 0;
	MapItem *map = 0;
	MapItem *tree = this;
	MapParams params;

	if( !ands && (tree->Whole( dir )->hasands || tree->Flag() == MfAndmap))
	{
	    ourarray = 1;
	    ands = new MapItemArray;
	}

	/* Decend */

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

	    /*
	     * No better precendence below?  Bail. 
	     * Unless we're looking for andmaps
	     */

	    if( best > t->maxSlot &&	    // Have we already got the best?
		!t->hasands &&		    // Are there andmaps down the tree?
		tree->Flag() != MfAndmap && // This is an andmap?
		bestnotands > t->maxSlotNoAnds ) // We prefer a real mapping
		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;
		if( ands )
		    ands->Put( tree );
		if( tree->Flag() != MfAndmap )
		    bestnotands = tree->slot;
	    }

	    /*
	     * Not higher precedence? AndMap Array? Wildcard match? Save
	     */

	    if( !r &&
		ands &&
		map != tree &&
		best >= tree->slot &&
		t->half.Match2( from, params ) )
	    {
		ands->Put( tree );
		if( tree->Flag() != MfAndmap )
		    bestnotands = tree->slot;
	    }

	    /*
	     * Follow to appropriate child. 
	     */

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

	/*
	 * If we were dealing with & maps, we need to make sure we either:
	 *   1. return the highest precedence non-andmap mapping
	 *   2. return the highest precedence andmap mapping
	 */

	if( map && ands )
	{
	    MapItem *m0 = 0;
	    int i = 0;
	    while( ( m0 = (MapItem *) ands->Get( i++ ) ) )
		if( m0->Flag() != MfAndmap )
		{
		    if( m0->mapFlag == MfUnmap )
			break; // Take the best & mapping and break

		    map = m0; // Take the best non-& mapping and break
		    break;
		}
		else if( i == 1 )
		    map = m0; // Take the best & mapping; keep going
	}

	if( ourarray )
	    delete ands;

	/* 
	 * 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 );
}

/*
 * MapItemArray -- Slot ordered list of MapItems
 */

struct MapWrap {
	MapItem *map;
	StrBuf to;
} ;

MapItemArray::~MapItemArray()
{
	for( int i = 0; i < Count(); i++ )
	    delete (MapWrap *) VarArray::Get( i );
}

MapItem *
MapItemArray::Get( int i )
{
	MapWrap *w = (MapWrap *) VarArray::Get( i );
	return w ? w->map : 0;
}

StrPtr *
MapItemArray::GetTranslation( int i )
{
	MapWrap *w = (MapWrap *) VarArray::Get( i );
	return w ? &w->to : 0;
}

MapItem *
MapItemArray::Put( MapItem *item, StrPtr *trans )
{
	// add the item to the end of the list
	MapWrap *wrap = new MapWrap;
	wrap->map = item;
	if( trans )
	    wrap->to = *trans;

	VarArray::Put( wrap );

	int s = Count(); // index of item + 1

	if( s <= 1 )
	    return item; // only the item we've just added: must be sorted!

	// find the index of the first item with a lower slot than item's
	int i = 0;
	while( Get( i )->slot > item->slot )
	    i++;

	// shuffle the pointers along so that item takes its rightful place
	while( s-- > i + 1)
	    Swap( s - 1, s );

	return item;
}

int
MapItemArray::PutTree( MapItem *item, MapTableT dir )
{
	if( !item )
	    return 0;

	Put( item );
	int count = 1;
	count += PutTree( item->Whole( dir )->left, dir );
	count += PutTree( item->Whole( dir )->center, dir );
	count += PutTree( item->Whole( dir )->right, dir );

	return count;
}

void
MapItemArray::Dump( const char *name )
{
	for( int i = 0; i < Count(); i++ )
	    p4debug.printf( "%s %c%s <-> %s (slot %d)\n",
		name,
		" -+$@&    123456789"[Get( i )->mapFlag],
		Get( i )->Lhs()->Text(),
		Get( i )->Rhs()->Text(),
		Get( i )->slot );
}

/*
* 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 <-> %s%s (maxslot %d (%d))\n", indent, name,
	    " -+$@&    123456789"[ mapFlag ], Ths(d)->Text(), Ohs(d)->Text(),
	    Whole( d )->hasands ? " (has &)" : "", Whole( d )->maxSlot, Whole( d )->maxSlotNoAnds);

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

	if( Whole( d )->right )
	    Whole( d )->right->Dump( d, ">>>", l+1 );
}
# Change User Description Committed
#2 20494 Thomas Gray Update of p4 source code to 16.1/1429894.
#1 19472 Liz Lam Initial add of the 2016.1 p4/p4api source code.