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