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