This is mapit.c in view mode; [Download] [Up]
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)mapit.c 9.11 88/05/09";
#endif
#include "def.h"
#define chkheap(i) /* void */
#ifdef DEBUG
#define watchgap(i) i = chkgap(i)
#else
#define watchgap(i) /* void */
#endif
#define trprint(stream, n) \
fprintf((stream), (n)->n_flag & NTERMINAL ? "<%s>" : "%s", (n)->n_name)
/* exports */
/* invariant while mapping: Nheap < Hashpart */
long Hashpart; /* start of unreached nodes */
long Nheap; /* end of heap */
long Ncopy, Nlink, Lcopy;
void mapit();
/* imports */
extern long Nheap, Hashpart, Tabsize, Tcount;
extern int Tflag, Vflag;
extern node *Home;
extern char *Linkout, *Graphout;
#ifdef M_I286
extern node * huge Table[];
#else
extern node **Table;
#endif
extern void freelink(), resetnodes(), printit(), dumpgraph();
extern void showlinks(), die();
extern long pack(), allocation();
extern link *newlink(), *addlink();
extern int maptrace(), tiebreaker();
extern node *ncopy();
/* privates */
static long Heaphighwater;
#ifdef M_I286
static link * huge * Heap;
#else
static link **Heap;
#endif
STATIC void insert(), heapup(), heapdown(), heapswap(), backlinks();
STATIC void setheapbits(), mtracereport(), heapchildren(), otracereport();
STATIC link *min_node();
STATIC int dehash(), skiplink(), skipterminalalias();
STATIC Cost costof();
STATIC node *mappedcopy();
/* transform the graph to a shortest-path tree by marking tree edges */
void
mapit()
{ register node *n;
register link *l;
int gap = -1;
vprintf(stderr, "*** mapping\n");
vprintf(stderr, "ncopy = %ld, nlink = %ld, lcopy = %ld, tcount = %ld\n", Ncopy, Nlink, Lcopy, Tcount);
Tflag = Tflag && Vflag; /* tracing here only if verbose */
/* re-use the hash table space for the heap */
#ifdef M_I286
Heap = (link * huge *) Table;
#else
Heap = (link **) Table;
#endif
Hashpart = pack(0L, Tabsize - 1);
/* expunge penalties from -a option and make circular copy lists */
resetnodes();
if (Linkout && *Linkout) /* dump cheapest links */
showlinks();
if (Graphout && *Graphout) /* dump the edge list */
dumpgraph();
/* insert Home to get things started */
l = newlink(); /* link to get things started */
l->l_to = Home;
(void) dehash(Home);
insert(l);
/* main mapping loop */
do {
Heaphighwater = Nheap;
while ((l = min_node()) != 0) {
l->l_flag |= LTREE;
n = l->l_to;
if (n->n_flag & MAPPED) /* sanity check */
die("mapped node in heap");
if (Tflag && maptrace(n, n))
otracereport(n); /* tracing */
chkheap(1); watchgap(gap); /* debugging */
n->n_flag |= MAPPED;
heapchildren(n); /* add children to heap */
}
vprintf(stderr, "heap hiwat %d\nalloc %ldk, ncopy = %ld, nlink = %ld, lcopy = %ld\n", Heaphighwater, allocation(), Ncopy, Nlink, Lcopy);
if (Nheap != 0) /* sanity check */
die("null entry in heap");
/*
* add back links from unreachable hosts to reachable
* neighbors, then remap. asymptotically, this is
* quadratic; in practice, this is done once or twice,
* when n is small.
*/
backlinks();
} while (Nheap > 0);
vprintf(stderr, "minimum gap %d%%\n", (gap * 100) / Tabsize);
if (Hashpart < Tabsize) {
int found = 0; /* 1 ==> found something detached */
for ( ; Hashpart < Tabsize; Hashpart++) {
if ((Table[Hashpart]->n_flag & ISPRIVATE) == 0) {
if (found == 0) {
fputs(
"You can't get there from here:\n",
stderr);
found = 1;
}
putc('\t', stderr);
trprint(stderr, Table[Hashpart]);
putc('\n', stderr);
}
}
if (found != 0) {
putc('\n', stderr);
}
}
}
STATIC void
heapchildren(n)
register node *n;
{ register link *l;
register node *next;
register int mtrace;
register Cost cost;
for (l = n->n_link; l; l = l->l_next) {
next = l->l_to; /* neighboring node */
mtrace = Tflag && maptrace(n, next);
if (l->l_flag & LTREE)
continue;
if (l->l_flag & LTERMINAL)
l->l_to = next = ncopy(n, l);
if ((n->n_flag & NTERMINAL) && (l->l_flag & LALIAS))
if (skipterminalalias(n, next))
continue;
else
l->l_to = next = ncopy(n, l);
if (next->n_flag & MAPPED) {
if (mtrace)
mtracereport(n, l, "-\talready mapped");
continue;
}
cost = costof(n, l);
if (skiplink(l, n, cost, mtrace))
continue;
/*
* put this link in the heap and restore the
* heap property.
*/
if (mtrace) {
if (next->n_parent)
mtracereport(next->n_parent, l, "*\tdrop");
mtracereport(n, l, "+\tadd");
}
next->n_parent = n;
if (dehash(next) == 0) { /* first time */
next->n_cost = cost;
insert(l); /* insert at end */
heapup(l);
} else {
/* replace inferior path */
Heap[next->n_tloc] = l;
if (cost > next->n_cost) {
/* increase cost (gateway) */
next->n_cost = cost;
heapdown(l);
} else if (cost < next->n_cost) {
/* cheaper route */
next->n_cost = cost;
heapup(l);
}
}
setheapbits(l);
chkheap(1);
}
}
/*
* bizarro special case. this merits comment.
*
* n is a terminal node just sucked out of the heap, next is an alias
* for n. because n is terminal, it must have one or more "copies."
* if next is one of those copies, don't put next in the heap.
*
* does that clear things up?
*/
STATIC int
skipterminalalias(n, next)
node *n, *next;
{
while (n->n_flag & NALIAS) {
n = n->n_parent;
if (ALTEREGO(n, next))
return 1;
}
return 0;
}
/*
* return 1 if we definitely don't want want this link in the
* shortest path tree, 0 if we might want it, i.e., best so far.
*
* if tracing is turned on, report only if this node is being skipped.
*/
STATIC int
skiplink(l, parent, cost, trace)
link *l; /* new link to this node */
node *parent; /* (potential) new parent of this node */
register Cost cost; /* new cost to this node */
int trace; /* trace this link? */
{ register node *n; /* this node */
register link *lheap; /* old 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)) {
if (trace)
mtracereport(parent, l, "-\told gateway");
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 && (DEADLINK(lheap) || DEADLINK(l)))
die("dup dead link");
/* examine cost */
if (cost < n->n_cost)
return 0;
if (cost > n->n_cost) {
if (trace)
mtracereport(parent, l, "-\tcheaper");
return 1;
}
/* all other things being equal, ask the oracle */
if (tiebreaker(n, parent)) {
if (trace)
mtracereport(parent, l, "-\ttiebreaker");
return 1;
}
return 0;
}
/* compute cost to l->l_to via parent */
STATIC Cost
costof(prev, l)
register node *prev;
register link *l;
{ register node *next;
register Cost cost;
if (l->l_flag & LALIAS)
return prev->n_cost; /* by definition */
next = l->l_to;
cost = prev->n_cost + l->l_cost; /* basic cost */
/*
* heuristics:
* charge for a dead link.
* charge for getting past a terminal host
* or getting out of a dead host.
* charge for getting into a gatewayed net (except at a gateway).
* discourage mixing of syntax (when prev is a host).
*
* life was simpler when pathalias computed true shortest paths.
*/
if (DEADLINK(l))
cost += INF; /* dead link */
if (DEADHOST(prev))
cost += INF; /* dead parent */
if (GATEWAYED(next) && !(l->l_flag & LGATEWAY))
cost += INF; /* not gateway */
if (!ISANET(prev)) {
if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
|| (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
cost += INF; /* mixed syntax */
}
return cost;
}
/* binary heap implementation of priority queue */
STATIC void
insert(l)
link *l;
{ register node *n;
n = l->l_to;
if (n->n_flag & MAPPED)
die("insert mapped node");
Heap[n->n_tloc] = 0;
if (Heap[Nheap+1] != 0)
die("heap error in insert");
if (Nheap++ == 0) {
Heap[1] = l;
n->n_tloc = 1;
return;
}
if (Vflag && Nheap > Heaphighwater)
Heaphighwater = Nheap; /* diagnostics */
/* insert at the end. caller must heapup(l). */
Heap[Nheap] = l;
n->n_tloc = Nheap;
}
/*
* "percolate" up the heap by exchanging with the parent. as in
* min_node(), give tiebreaker() a chance to produce better, stable
* routes by moving nets and domains close to the root, nets closer
* than domains.
*
* i know this seems obscure, but it's harmless and cheap. trust me.
*/
STATIC void
heapup(l)
link *l;
{ 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;
if (Nheap == 0)
return 0;
rval = Heap[1]; /* return this one */
/* move last entry into root and reheap */
lastlink = Heap[Nheap];
Heap[Nheap] = 0;
if (--Nheap) {
Heap[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;
node *child, *rchild, *parent;
pindx = l->l_to->n_tloc;
parent = Heap[pindx]->l_to; /* invariant */
for ( ; (cindx = pindx * 2) <= Nheap; pindx = cindx) {
/* pick lhs or rhs child */
child = Heap[cindx]->l_to;
if (cindx < Nheap) {
/* compare with rhs child */
rchild = Heap[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;
temp = Heap[i];
Heap[i] = Heap[j];
Heap[j] = temp;
Heap[j]->l_to->n_tloc = j;
Heap[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*/
#ifdef DEBUG
chkgap(gap)
{ int newgap;
newgap = Hashpart - Nheap;
if (gap == -1 || newgap < gap)
return newgap;
return gap;
}
#endif
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.