4.3BSD/usr/contrib/pathalias/mapit.c

/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char	*sccsid = "@(#)mapit.c	8.1 (down!honey) 86/01/19";
#endif

#include "def.h"

/* privates */
extern void	reheap(), insert(), heapswap();
extern link	*min_node(), *rmlink();
extern Cost	costof();

static long	Nheap;
static long	Heaphighwater;
static link	**Heap;


/* transform the graph to a shortest-path tree by marking tree edges */

mapit()
{
	register node *n, *next;
	register link *l;
	link	*lprev, *lnext;
	Cost cost;

	/*
	 * re-use the hash table space for the heap.
	 */
	Heap = (link **) Table;

	pack();		/* remove holes in the Table */
	if (Linkout && *Linkout)	/* dump cheapest links */
		showlinks();
	if (Graphout && *Graphout)	/* dump the edge list */
		dumpgraph();

	/* invent and insert a link for Home to get things started */
	l = newlink();
	l->l_to = Home;
	(void) dehash(Home);
	insert(l);

	/* main mapping loop */
remap:
	Heaphighwater = Nheap;
	while ((l = min_node()) != 0) {
		l->l_flag |= LTREE;
		n = l->l_to;
		n->n_flag |= MAPPED;
 
		/* add children to heap */
		lprev = 0;
		for (l = n->n_link; l != 0; l = lnext) {

			next = l->l_to;		/* neighboring node */
			if (next->n_flag & MAPPED) {
				lnext = rmlink(l, lprev, n);
				continue;
			}
			cost = costof(n, l);

			if (skiplink(l, n, cost)) {
				lnext = rmlink(l, lprev, n);
				continue;
			}

			/*
			 * put this link in the heap, in a place where it may
			 * percolate up, but not down.  if new, or if cost is
			 * being increased, move to end.  otherwise, cost is
			 * same or less, so leave it where it is.  unfortunately,
			 * freeing a link already in the heap is too costly at
			 * this point.
			 *
			 * TODO: avoid heaping aliases and network members.
			 */
			if (dehash(next) == 0)	/* first time in heap */
				insert(l);	/* insert at end */
			else {
				/* replace heaped link by this one */
				if (cost > next->n_cost) {	/* gateway */
					/* move old link to end of heap */
					heapswap((long) (next->n_tloc), Nheap);
					next->n_tloc = Nheap;
				}
				Heap[next->n_tloc] = l;
			}
				
			next->n_cost = cost;
			next->n_parent = n;
			reheap(l);		/* restore heap property */

			/*
			 * note whether we got here via a gatewayed net.
			 * domains are presumed to require gateways.
			 * aliases inherit parent's gateway status.
			 */
			next->n_flag &= ~GATEWAYIN;
			if (l->l_flag & LALIAS)
				next->n_flag |= (n->n_flag & GATEWAYIN);
			else if (GATEWAYED(n))
				next->n_flag |= GATEWAYIN;
			lprev = l;	/* this link's a keeper */
			lnext = l->l_next;
		}

	}
	vprintf(stderr, "heap high water mark was %d\n", Heaphighwater);

	/* sanity check on implementation */
	if (Nheap != 0) {
		fprintf(stderr, "%s: null entry found in heap\n", ProgName);
		badmagic(1);
	}

	if (Hashpart < Tabsize) {
		/*
		 * add back links from unreachable hosts to reachable
		 * neighbors, then remap.  asymptotically, this is
		 * quadratic.  in practice, this is done exactly once.
		 */
		backlinks();
		if (Nheap)
			goto remap;
	}
	if (Hashpart < Tabsize) {
		fputs("You can't get there from here:\n", stderr);
		for ( ; Hashpart < Tabsize; Hashpart++) {
			fprintf(stderr, "\t%s", Table[Hashpart]->n_name);
			if (Table[Hashpart]->n_flag & (ISPRIVATE|COLLISION))
				fputs(" (private)", stderr);
			putc('\n', stderr);
		}
	}
}

/*
 * can this link be ignored?  if yes, return 1, o.w. 0.
 * a link can be skipped if it is not in the shortest path tree.
 */
STATIC int
skiplink(l, parent, cost)
link	*l;			/* new link to this node */
node	*parent;		/* new parent of this node */
Cost	cost;			/* new cost to this node */
{
	node	*n;		/* this node */
	link	*lheap;		/* existing link to this node */

	n = l->l_to;

	/* first time we've reached this node? */
	if (n->n_tloc >= Hashpart)
		return(0);

	lheap = Heap[n->n_tloc];

	/* examine links to nets that require gateways */
	if (GATEWAYED(n)) {
		/* if exactly one is a gateway, use it */
		if ((lheap->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY))
			return(1);	/* old is gateway */
		if (!(lheap->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY))
			return(0);	/* new is gateway */

		/* no gateway or both gateways;  resolve in standard way ... */
	}

	/* examine dup link (sanity check) */
	if (n->n_parent == parent && ((lheap->l_flag & LDEAD) || (l->l_flag & LDEAD))) {
		fprintf(stderr, "%s: dup dead link not eliminated: %s -> %s\n",
			ProgName, parent->n_name, n->n_name);
		badmagic(1);
	}


	/*  examine cost */
	if (cost < n->n_cost)
		return(0);
	if (cost > n->n_cost)
		return(1);

	/* all other things being equal, consult the oracle */
	return(tiebreaker(n, parent));
}

STATIC Cost
costof(prev, l)
register node	*prev;
register link	*l;
{
	register node	*next;
	register Cost	cost;

	next = l->l_to;

	if (l->l_flag & LALIAS) {
		/* copy left/right bits */
		next->n_flag &= ~(HASLEFT|HASRIGHT);
		next->n_flag |= (prev->n_flag & (HASLEFT|HASRIGHT));
		return(prev->n_cost);	/* by definition */
	}

		
	cost = prev->n_cost + l->l_cost;	/* basic cost */

	/*
	 * heuristics:
	 *    charge for a dead link.
	 *    charge for getting out of a dead host.
	 *    charge for getting into a gatewayed net (except at a gateway).
	 *    discourage mixing of left and right syntax when next is a host.
	 *    charge for leaving a gatewayed net.
	 *
	 * life was simpler when pathalias computed true shortest paths.
	 */
	if (l->l_flag & LDEAD)		/* dead link */
		cost += INF/2;
	if (DEADHOST(prev))		/* dead host */
		cost += INF/2;
	if (GATEWAYED(next) && !(l->l_flag & LGATEWAY))	/* not gateway */
		cost += INF/2;
	if (!ISANET(next)) {
		/* charge for mixed syntax here */
		if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
		 || (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
			cost += DEFCOST;
	}
	/*
	 * if reached by a gatewayed net, discourage further links.
	 * this has some relevance to common carriers and the FCC ...
	 * the penalty inheres to hosts, not aliases, nets, or domains.
	 */
	if ((prev->n_flag & GATEWAYIN) && !ISADOMAIN(prev) && !(prev->n_flag & NNET))
		cost += INF/2;	/* heavyweight, but appropriate */

	/* set left/right bits */
	next->n_flag &= ~(HASLEFT|HASRIGHT);
	if (NETDIR(l) == LLEFT || (prev->n_flag & HASLEFT))
		next->n_flag |= HASLEFT;
	if (NETDIR(l) == LRIGHT || (prev->n_flag & HASRIGHT))
		next->n_flag |= HASRIGHT;

	return(cost);
}

STATIC link *
rmlink(l, lprev, n)
link	*l, *lprev;
node	*n;
{
	link	*lnext;

	lnext = l->l_next;
	if (lprev)
		lprev->l_next = l->l_next;
	else
		n->n_link = l->l_next;
	free((char *) l);
	return(lnext);
}

/*
 * binary heap implementation of priority queue.
 * TODO: make the heap smaller by giving inserting a placeholder
 * for net members when the net is extracted.  this requires storing the
 * cost of a net in the net node itself -- yuck.  is it worth it?
 */

STATIC void
insert(l)
link	*l;
{
	register node	*n;

	n = l->l_to;
	Heap[n->n_tloc] = 0;
	if (Heap[Nheap+1] != 0) {
		fprintf(stderr, "%s: heap error in insert\n", ProgName);
		badmagic(1);
	}
	if (Nheap++ == 0) {
		Heap[1] = l;
		n->n_tloc = 1;
		return;
	}
	if (Vflag && Nheap > Heaphighwater)
		Heaphighwater = Nheap;	/* diagnostics */

	/* insert at the end.  caller must reheap(). */
	Heap[Nheap] = l;
	n->n_tloc = Nheap;
}

/*
 * replace existing link in heap by this one, then
 * "percolate" up the heap by exchanging with the parent
 */
STATIC void
reheap(l)
link	*l;
{
	register long	loc, parent;
	register Cost	cost;
	register node	*n, *np;

	n = l->l_to;

	cost = n->n_cost;
	for (loc = n->n_tloc; loc > 1; loc = parent) {
		parent = loc / 2;
		/* sanity check on implementation */
		if (Heap[parent] == 0) {
			fprintf(stderr, "%s: heap error in insert\n", ProgName);
			badmagic(1);
		}
		np = Heap[parent]->l_to;
		if (cost > np->n_cost)
			return;
		/* move nets below hosts for output stability */
		if (cost == np->n_cost && ((n->n_flag & NNET) || !(np->n_flag & NNET)))
			return;
		heapswap(loc, parent);
	}
}

/* extract min (== Heap[1]) from heap */
STATIC link	*
min_node()
{
	link *rval;
	register link **regheap;
	register long	i, child;
	
	if (Nheap == 0)
		return(0);

	regheap = Heap;		/* in register -- heavily used */
	rval = regheap[1];	/* return this one */
			
	/* move last entry into root, percolate down */
	regheap[1] = regheap[Nheap];
	regheap[1]->l_to->n_tloc = 1;
	regheap[Nheap] = 0;
	if (--Nheap == 0)
		return(rval);

	i = 1;
	for (;;) {
		/* swap with smaller child down the tree */
		child = i * 2;	/* lhs child is 2i, rhs is 2i+1. */
		if (child >= Nheap)
			return(rval);
		/* use rhs child if smaller than lhs child */
		if (regheap[child]->l_to->n_cost > regheap[child+1]->l_to->n_cost
		 || (regheap[child]->l_to->n_cost == regheap[child+1]->l_to->n_cost
		  && !ISANET(regheap[child+1]->l_to)))
			child++;
			
		if (regheap[i]->l_to->n_cost < regheap[child]->l_to->n_cost)
			return(rval);
		/* move nets below hosts for output stability */
		if (regheap[i]->l_to->n_cost == regheap[child]->l_to->n_cost
		 && (!ISANET(regheap[i]->l_to) || ISANET(regheap[child]->l_to)))
			return(rval);
		heapswap(i, child);
		i = child;
	}
	/*NOTREACHED*/
}

/* exchange Heap[i] and Heap[j] pointers */
STATIC void
heapswap(i, j)
long	i, j;
{
	register link	*temp, **regheap;

	regheap = Heap;	/* heavily used -- put in register */
	temp = regheap[i];
	regheap[i] = regheap[j];
	regheap[j] = temp;
	regheap[j]->l_to->n_tloc = j;
	regheap[i]->l_to->n_tloc = i;
}

/* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
dehash(n)
register node	*n;
{
	if (n->n_tloc < Hashpart)
		return(1);

	/* swap with entry in Table[Hashpart] */
	Table[Hashpart]->n_tloc = n->n_tloc;
	Table[n->n_tloc] = Table[Hashpart];
	Table[Hashpart] = n;

	n->n_tloc = Hashpart++;
	return(0);
}

backlinks()
{
	link *l;
	node *n, *parent, *nomap;
	long i;

	for (i = Hashpart; i < Tabsize; i++) {
		nomap = Table[i];
		parent = 0;
		for (l = nomap->n_link; l; l = l->l_next) {
			n = l->l_to;
			if (!(n->n_flag & MAPPED))
				continue;
			if (parent == 0) {
				parent = n;
				continue;
			}
			if (n->n_cost > parent->n_cost)
				continue;
			if (n->n_cost == parent->n_cost) {
				nomap->n_parent = parent;
				if (tiebreaker(nomap, n))
					continue;
			}
			parent = n;
		}
		if (parent == 0)
			continue;
		(void) dehash(nomap);
		l = addlink(parent, nomap, INF, DEFNET, DEFDIR);
		nomap->n_parent = parent;
		nomap->n_cost = costof(parent, l);
		insert(l);
		reheap(l);
	}
	vprintf(stderr, "%d backlinks\n", Nheap);
}