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

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

#include "def.h"

extern void	lowercase(), rehash();
extern node	*isprivate();
extern long	hash();

/*
 * these numbers are chosen because:
 *	-> they are prime,
 *	-> they are monotonic increasing,
 *	-> each is a tad smaller than a multiple of 1024,
 *	-> they form a fibonacci sequence (almost).
 * the first point yields good hash functions, the second is used for the
 * standard re-hashing implementation of open addressing, the third
 * optimizes for quirks in some mallocs i have seen, and the fourth simply
 * appeals to me.
 */
static int Primes[]	= {
#ifndef SQUANDER
	1021, 2039, 3067, 5113, 8179,
#endif
	13309, 21499, 0
};

static int	Tabindex = -1;
static int	Collision;	/* mark host name collisions in hash() */

node	*
addnode(name)
register char	*name;
{
	register long	i;
	register node	*n;

	if (Iflag)
		lowercase(name);

	/* is it a private host? */
	n = isprivate(name);
	if (n)
		return(n);

	i = hash(name, 0);
	if (Table[i]) 
		return(Table[i]);

	n = newnode();
	n->n_name = strsave(name);
	Table[i] = n;
	n->n_tloc = i;	/* essentially a back link to the table */
	if (Collision)
		n->n_flag |= COLLISION;	/* name collision with private host */

	return(n);
}

alias(n1, n2)
node	*n1, *n2;
{
	link	*l;
	extern link *addlink();

	l = addlink(n1, n2, (Cost) 0, DEFNET, DEFDIR);
	l->l_flag |= LALIAS;
	l = addlink(n2, n1, (Cost) 0, DEFNET, DEFDIR);
	l->l_flag |= LALIAS;
	if (Tflag)
		atrace(n1, n2);
}

/*
 * fold a string into a long int.  this algorithm ignores all but the last
 * eight bytes, which affects < 15% of all host names, many of which have
 * common prefixes anyway.
 */
STATIC long
fold(str)
register char	*str;
{
	register long	sum;

	sum = *str++;
	while (*str) {
		sum <<= 4;
		sum += *str++;
	}
	if (sum < 0) 
		sum = -sum;
	return(sum);
}

#define HASH1(n) ((n) % Tabsize);
#define HASH2(n) (Tabsize - 2 - ((n) % (Tabsize-2)))	/* princeton!rs */

/*
 * with a 0.75 high water mark, probes per access should be 1.84.
 * use long constant to force promotion.
 */
#define HIGHWATER	75L
#define isfull(n, size)	((n) > ((size) * HIGHWATER) / 100)

STATIC long
hash(name, unique)
char	*name;
{
	register long	probe, hash2;
	register node	*n;

	if (Tabindex < 0) {			/* first time */
		Tabindex = 0;
		Tabsize = Primes[0];
		Table = newtable(Tabsize);
	} else if (isfull(Ncount, Tabsize))
		rehash();			/* more, more! */
				
	probe = fold(name);
	/* don't change the order of the next two lines */
	hash2 = HASH2(probe);
	probe = HASH1(probe);
	/* thank you! */

	/*
	 * probe the hash table.
	 * if unique is set, we require a fresh slot.
	 * otherwise, use double hashing to find either
	 *  (1) an empty slot, or
	 *  (2) a non-private copy of this host name
	 *
	 * as a side effect, if we notice a collision with a private host
	 * we mark the other so that it is skipped at output time.
	 */
	Collision = 0;
	while ((n = Table[probe]) != 0) {
		if (strcmp(n->n_name, name) == 0) {
			if (unique)
				n->n_flag |= COLLISION;
			else if (n->n_flag & ISPRIVATE)
				Collision++;
			else
				break;	/* this is it! */
		}
		probe -= hash2;
		if (probe < 0)
			probe += Tabsize;
	}
	return(probe);
}

STATIC void
rehash()
{
	register node	**otable, **optr;
	register long	probe;
	long	osize;

#ifdef DEBUG
	hashanalyze();
#endif
	optr = Table + Tabsize - 1;	/* ptr to last */
	otable = Table;
	osize = Tabsize;
	Tabsize = Primes[++Tabindex];
	if (Tabsize == 0) {	/* need more prime numbers */
		fprintf(stderr, "%s: > %d hosts\n", ProgName, Primes[Tabindex-1]);
		badmagic(1);
	}
	vprintf(stderr, "rehash into %d\n", Tabsize);
	Table = newtable(Tabsize);

	do {
		if (*optr == 0)
			continue;	/* empty slot in old table */
		probe = hash((*optr)->n_name, (*optr)->n_flag & ISPRIVATE);
		if (Table[probe] != 0) {
			fprintf(stderr, "%s: rehash error\n", ProgName);
			badmagic(1);
		}
		Table[probe] = *optr;
		(*optr)->n_tloc = probe;
	} while (optr-- > otable);
	freetable(otable, osize);
}

hashanalyze()
{
	long	probe, hash2;
	int	count, i, collision[8];
	int	longest = 0, total = 0, slots = 0;
	int	nslots = sizeof(collision)/sizeof(collision[0]);

	if (!Vflag)
		return;

	strclear((char *) collision, sizeof(collision));
	for (i = 0; i < Tabsize; i++) {
		if (Table[i] == 0)
			continue;
		/* private hosts too hard to account for ... */
		if (Table[i]->n_flag & ISPRIVATE)
			continue;
		count = 1;
		probe = fold(Table[i]->n_name);
		/* don't change the order of the next two lines */
		hash2 = HASH2(probe);
		probe = HASH1(probe);
		/* thank you! */
		while (Table[probe] != 0
		    && strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
			count++;
			probe -= hash2;
			if (probe < 0)
				probe += Tabsize;
		}
		if (Table[probe] == 0) {
			fprintf(stderr, "%s: impossible hash error for %s\n",
					ProgName, Table[i]->n_name);
			badmagic(1);
		}
		
		total += count;
		slots++;
		if (count > longest)
			longest = count;
		if (count >= nslots)
			count = 0;
		collision[count]++;
	}
	for (i = 1; i < nslots; i++)
		if (collision[i])
			fprintf(stderr, "%d chains: %d (%ld%%)\n",
				i, collision[i], (collision[i] * 100L)/ slots);
		if (collision[0])
			fprintf(stderr, "> %d chains: %d (%ld%%)\n",
				nslots - 1, collision[0],
				(collision[0] * 100L)/ slots);
	fprintf(stderr, "%2.2f probes per access, longest chain: %d\n",
		(double) total / slots, longest);
}

STATIC void
lowercase(s)
register char	*s;
{
	do {
		if (isupper(*s))
			*s -= 'A' - 'a';	/* assumes ASCII */
	} while (*s++);
}

/*
 * this might have to be recoded for performance if privates catch on
 */
STATIC node	*
isprivate(name)
register char	*name;
{
	register node	*n;

	for (n = Private; n != 0; n = n->n_private)
		if (strcmp(name, n->n_name) == 0)
			return(n);
	return(0);
}

fixprivate()
{
	register node	*n, *next;
	register long	i;

	for (n = Private; n != 0; n = next) {
		n->n_flag |= ISPRIVATE;		/* overkill, but safe */
		i = hash(n->n_name, 1);
		if (Table[i] != 0) {
			fprintf(stderr, "%s: impossible private node error on %s\n",
				ProgName, n->n_name);
			badmagic(1);
		}
	
		Table[i] = n;
		n->n_tloc = i;	/* essentially a back link to the table */
		next = n->n_private;
		n->n_private = 0;	/* clear for later use */
	}
	Private = 0;
}

node	*
addprivate(name)
register char	*name;
{
	register node	*n;

	if (Iflag)
		lowercase(name);
	if ((n = isprivate(name)) != 0)
		return(n);

	n = newnode();
	n->n_name = strsave(name);
	n->n_private = Private;
	Private = n;
	return(n);
}