mapit.c

早期freebsd实现

{	register long cindx, pindx;	/* child, parent indices */
	register Cost cost;
	register node *child, *parent;

	child = l->l_to;

	cost = child->n_cost;
	for (cindx = child->n_tloc; cindx > 1; cindx = pindx) {
		pindx = cindx / 2;
		if (Heap[pindx] == 0)	/* sanity check */
			die("impossible error in heapup");
		parent = Heap[pindx]->l_to;
		if (cost > parent->n_cost)
			return;

		/* net/domain heuristic */
		if (cost == parent->n_cost) {
			if (!ISANET(child))
				return;
			if (!ISADOMAIN(parent))
				return;
			if (ISADOMAIN(child))
				return;
		}
		heapswap(cindx, pindx);
	}
}

/* extract min (== Heap[1]) from heap */
STATIC link	*
min_node()
{	link *rval, *lastlink;
	register link **rheap;

	if (Nheap == 0)
		return 0;

	rheap = Heap;		/* in register -- heavily used */
	rval = rheap[1];	/* return this one */

	/* move last entry into root and reheap */
	lastlink = rheap[Nheap];
	rheap[Nheap] = 0;

	if (--Nheap) {
		rheap[1] = lastlink;
		lastlink->l_to->n_tloc = 1;
		heapdown(lastlink);	/* restore heap property */
	}

	return rval;
}

/*
 * swap Heap[i] with smaller child, iteratively down the tree.
 *
 * given the opportunity, attempt to place nets and domains
 * near the root.  this helps tiebreaker() shun domain routes.
 */

STATIC void
heapdown(l)
	link *l;
{	register long pindx, cindx;
	register link **rheap = Heap;	/* in register -- heavily used */
	node *child, *rchild, *parent;

	pindx = l->l_to->n_tloc;
	parent = rheap[pindx]->l_to;	/* invariant */
	for ( ; (cindx = pindx * 2) <= Nheap; pindx = cindx) {
		/* pick lhs or rhs child */
		child = rheap[cindx]->l_to;
		if (cindx < Nheap) {
			/* compare with rhs child */
			rchild = rheap[cindx+1]->l_to;
			/*
			 * use rhs child if smaller than lhs child.
			 * if equal, use rhs if net or domain.
			 */
			if (child->n_cost > rchild->n_cost) {
				child = rchild;
				cindx++;
			} else if (child->n_cost == rchild->n_cost)
				if (ISANET(rchild)) {
					child = rchild;
					cindx++;
				}
		}

		/* child is the candidate for swapping */
		if (parent->n_cost < child->n_cost)
			break;

		/*
		 * heuristics:
		 *	move nets/domains up
		 *	move nets above domains
		 */
		if (parent->n_cost == child->n_cost) {
			if (!ISANET(child))
				break;
			if (ISANET(parent) && ISADOMAIN(child))
				break;
		}

		heapswap(pindx, cindx);
	}
}

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

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

/* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
STATIC int
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;
}

/*
 * everything reachable has been mapped.  what to do about any
 * unreachable hosts?  the sensible thing to do is to dump them on
 * stderr and be done with it.  unfortunately, there are hundreds of
 * such hosts in the usenet maps.  so we take the low road: for each
 * unreachable host, we add a back link from its cheapest mapped child,
 * in the faint that a reverse path works.
 *
 * beats me why people want their error output in their map databases.
 */
STATIC void
backlinks()
{	register link *l;
	register node *n, *child;
	node *nomap;
	long i;

	/* hosts from Hashpart to Tabsize are unreachable */
	for (i = Hashpart; i < Tabsize; i++) {
		nomap = Table[i];
		/* if a copy has been mapped, we're ok */
		if (nomap->n_copy != nomap) {
			dehash(nomap);
			Table[nomap->n_tloc] = 0;
			nomap->n_tloc = 0;
			continue;
		}

		/* TODO: simplify this */		
		/* add back link from minimal cost child */
		child = 0;
		for (l = nomap->n_link; l; l = l->l_next) {
			n = l->l_to;
			/* never ever ever crawl out of a domain */
			if (ISADOMAIN(n))
				continue;
			if ((n = mappedcopy(n)) == 0)
				continue;
			if (child == 0) {
				child = n;
				continue;
			}
			if (n->n_cost > child->n_cost)
				continue;
			if (n->n_cost == child->n_cost) {
				nomap->n_parent = child; /* for tiebreaker */
				if (tiebreaker(nomap, n))
					continue;
			}
			child = n;
		}
		if (child == 0)
			continue;
		(void) dehash(nomap);
		l = addlink(child, nomap, INF, DEFNET, DEFDIR);	/* INF cost */
		nomap->n_parent = child;
		nomap->n_cost = costof(child, l);
		insert(l);
		heapup(l);
		if (Vflag > 1)
			fprintf(stderr, "backlink: %s <- %s\n", nomap->n_name, child->n_name);
	}
	vprintf(stderr, "%d backlinks\n", Nheap);
}

/* find a mapped copy of n if it exists */
STATIC node *
mappedcopy(n)
	register node *n;
{	register node *ncp;

	if (n->n_flag & MAPPED)
		return n;
	for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy)
		if (ncp->n_flag & MAPPED)
			return ncp;
	return 0;
}

/*
 * l has just been added or changed in the heap,
 * so reset the state bits for l->l_to.
 */
STATIC void
setheapbits(l)
	register link *l;
{	register node *n;
	register node *parent;

	n = l->l_to;
	parent = n->n_parent;
	n->n_flag &= ~(NALIAS|HASLEFT|HASRIGHT);	/* reset */

	/* record whether link is an alias */
	if (l->l_flag & LALIAS) {
		n->n_flag |= NALIAS;
		/* TERMINALity is inherited by the alias */
		if (parent->n_flag & NTERMINAL)
			n->n_flag |= NTERMINAL;
	}

	/* set left/right bits */
	if (NETDIR(l) == LLEFT || (parent->n_flag & HASLEFT))
		n->n_flag |= HASLEFT;
	if (NETDIR(l) == LRIGHT || (parent->n_flag & HASRIGHT))
		n->n_flag |= HASRIGHT;
}

STATIC void
mtracereport(from, l, excuse)
	node *from;
	link *l;
	char *excuse;
{	node *to = l->l_to;

	fprintf(stderr, "%-16s ", excuse);
	trprint(stderr, from);
	fputs(" -> ", stderr);
	trprint(stderr, to);
	fprintf(stderr, " (%ld, %ld, %ld) ", from->n_cost, l->l_cost, to->n_cost);
	if (to->n_parent) {
		trprint(stderr, to->n_parent);
		fprintf(stderr, " (%ld)", to->n_parent->n_cost);
	}
	putc('\n', stderr);
}

STATIC void
otracereport(n)
	node *n;
{
	if (n->n_parent)
		trprint(stderr, n->n_parent);
	else
		fputs("[root]", stderr);
	fputs(" -> ", stderr);
	trprint(stderr, n);
	fputs(" mapped\n", stderr);
}
	
#if 0
/* extremely time consuming, exhaustive check of heap sanity. */
chkheap(i)
{	int lhs, rhs;

	lhs = i * 2;
	rhs = lhs + 1;

	if (lhs <= Nheap) {
		if (Heap[i]->l_to->n_cost > Heap[lhs]->l_to->n_cost)
			die("chkheap failure on lhs");
		chkheap(lhs);
	}
	if (rhs <= Nheap) {
		if (Heap[i]->l_to->n_cost > Heap[rhs]->l_to->n_cost)
			die("chkheap failure on rhs");
		chkheap(rhs);
	}
#if 00
	/* this hasn't been used for years */
	for (i = 1; i < Nheap; i++) {
		link *l;

		vprintf(stderr, "%5d %-16s", i, Heap[i]->l_to->n_name);
		if ((l = Heap[i]->l_to->n_link) != 0) do {
			vprintf(stderr, "%-16s", l->l_to->n_name);
		} while ((l = l->l_next) != 0);
		vprintf(stderr, "\n");
	}
	for (i = Hashpart; i < Tabsize; i++) {
		link *l;
		node *n;

		vprintf(stderr, "%5d %-16s", i, Table[i]->n_name);
		if ((l = Table[i]->n_link) != 0) do {
			vprintf(stderr, "%-16s", l->l_to->n_name);
		} while ((l = l->l_next) != 0);
		vprintf(stderr, "\n");
	}
#endif /*00*/
		
}
#endif /*0*/

/* this isn't much use */
#if 0
STATIC int
chkgap()
{	static int gap = -1;
	int newgap;

	newgap = Hashpart - Nheap;
	if (gap == -1 || newgap < gap)
		gap = newgap;
	return gap;
}
#endif /*0*/