From: geoff@world.std.com (Geoff Collyer)
Subject: rn and trn "bogus newsgroups" drastic speed up
Organization: Software Tool & Die Netnews Research Center
Date: Wed, 8 Apr 1992 01:47:07 GMT

You've probably noticed that (t)rn upon noticing an obsolete newsgroup in
your .newsrc spends a long, long time deciding which groups are valid.
This is because they re-read the active file from the start for each
group in your .newsrc, more or less.  Assuming 3,000 groups in your
active file and your .newsrc, that's about 4,500,000 calls to fgets, since
the average case requires reading only half the active file; this takes a
while.  On our Sun 4/280 this can take 25 - 45 minutes, depending on
system load.  Users understandably get a little impatient waiting for
something that nn takes in stride.

My fix assumes that the size in bytes of your active file fits in an int,
so it may not work on compilers with 16-bit ints and active files over 32k
(or 64k, depending upon the phase of the moon).  This is an ugly wart,
but too many standard subroutines, like malloc, take int arguments, and
I'm not highly motivated to make (t)rn fast on tiny machines.  This fix
works on rn 4.4.3 and trn 2.2 and some older versions we ran here, and
will probably work on most versions of rn and trn.

You need to edit ngdata.c to delete the function findact, and change the
function ngdata_init so that the only code between
	#else	/* not SERVER */
and
	#endif
is the single line

	ngdatansrv_init();

Then change Makefile to compile and link in nghash.o, hash.o and hdbm.o,
and type "make".

nghash.c contains ngdatansrv_init() and a replacement findact().  They
read the active file into core and hash lookups by newsgroup name; this
cuts the "bogus newsgroup" start-up time of rn on our machine to 10
seconds real time.  It's probably possible to do even better, but this
seems adequate for now.

hash* and hdbm* are source and manual page for approximately the hash
library that we will be distributing with C News, and is covered by a
similar copyright; see hdbm.c.



# To unbundle, sh this file
echo hash.3 1>&2
sed 's/^X//' >hash.3 <<'!'
X.TH HASH 3 "7 November 1991"
X.SH NAME
hash: hashcreate, hashdestroy, hashstore, hashentry, hashfetch,
hashdelete, hashwalk \- string interface to
general-purpose in-memory hashed lookup
X.br
hash: hdbmcreate, hdbmdestroy, hdbmstore, hdbmentry, hdbmfetch,
hdbmdelete, hdbmwalk \- dbm interface to
general-purpose in-memory hashed lookup
X.SH SYNOPSIS
X.ft B
X.nf
X#include <hdbm.h>
X#include <hash.h>
X.sp 0.3v
HASHTABLE *hashcreate(size, hashfunc)
unsigned size;
unsigned (*hashfunc)();
X.sp 0.3v
hashdestroy(tbl)
HASHTABLE *tbl;
X.sp 0.3v
int hashstore(tbl, key, data)
HASHTABLE *tbl;
HASHDATUM key, data;
X.sp 0.3v
HASHDATUM hashentry(tbl, key, allocator)
HASHTABLE *tbl;
HASHDATUM key;
HASHDATUM (*allocator)();
X.sp 0.3v
HASHDATUM hashfetch(tbl, key)
HASHTABLE *tbl;
HASHDATUM key;
X.sp 0.3v
int hashdelete(tbl, key)
HASHTABLE *tbl;
HASHDATUM key;
X.sp 0.3v
hashwalk(tbl, nodefunc, hook)
HASHTABLE *tbl;
int (*nodefunc)();
char *hook;
X.fi
X.DA 
X.ft
X.SH DESCRIPTION
This package maintains,
searches,
and
enumerates
multiple hash tables in memory simultaneously.
X(Hashing is a technique to map a
X`key'
to the data corresponding to that key very quickly
by use of a
X.I hash
function.)
This package implements hashing with chaining.
X.PP
X.I Hash.h
defines some data types:
HASHDATUM
is the type of keys and data objects
manipulated by these routines;
X(HASHTABLE *)
is a magic cookie returned by
X.I hashcreate
and used by the other routines:
X.PP
X.ft B
X.nf
X.in +0.5i
typedef char *HASHDATUM;
X.in -0.5i
X.fi
X.ft
X.PP
X.I Hashcreate
allocates a fresh hash table of
X.I size
entries
and set up to use the hashing function
X.IR hashfunc .
It returns a magic cookie which refers to the new hash table,
for use with the other routines.
The precise value of
X.I size
doesn't matter;
it only affects efficiency:
larger values consume more memory
but generally result in faster lookups.
Some theoreticians believe that prime numbers make better sizes,
but it's not clear that it really matters in practice.
If
X.I hashfunc
is a null pointer,
a default hash function will be used.
Otherwise,
X.I hashfunc(key)
will be called for each
HASHDATUM
X.I key
that must be hashed;
the result will be taken modulus the hash table size
to determine the hash chain to search for the corresponding
X.IR data .
X.I Hashdestroy
destroys utterly the hash table corresponding to
X.IR tbl .
X.PP
X.I Hashstore
associates the
X.I data
pointer with
X.I key
in the table corresponding to
X.IR tbl .
Any prior association with
X.I key
in this table is lost.
X.I Hashstore
assumes that data pointed to by a
X.I key
HASHDATUM remains constant,
and that data pointed to by a
X.I data
HASHDATUM
does not move in memory and is not
X.IR free d,
during the life of the table.
X.I Hashentry
returns the data
associated with
X.I key
in the table corresponding to
X.IR tbl ,
if any,
else invokes
X.IB allocator ( key )
and associates the result with
X.IR key ,
and returns the result.
X.I Hashentry
is primarily an optimisation
for symbol table maintenance.
X.I Hashfetch
returns
the data
associated with
X.I key
in the table corresponding to
X.IR tbl ,
if any,
else 0.
X.I Hashdelete
removes any entry for
X.IR key .
X.PP
X.I Hashwalk
visits each entry in the table corresponding to
X.I tbl
in no particularly useful order
and executes
X.IR nodefunc( "key, data, " hook);
for each,
where
X.I key
and
X.I data
are the values of the mapping for that entry.
X.I Hook
is a crude attempt to allow side effects in
X.I nodefunc
with reentrancy.
X.PP
There exists a parallel set of routines
with whose names are the same except that
the prefix
X.B hash
is replaced with
X.BR hdbm .
These routines operate on the data type
HDBMDATUM
rather than
HASHDATUM;
HDBMDATUM
is a (pointer, size) pair
defined by
X.I hdbm.h
and contains these members:
X.PP
X.ft B
X.nf
X	char	*dat_ptr;
X	unsigned dat_len;
X.fi
X.ft
X.PP
An implementation of
X.IR hsearch (3)
is also provided;
see
X.IR hsearch (3)
for details.
X.SH DIAGNOSTICS
XFunctions which return a value
return 0 on failure,
except for
X.I hdbmfetch
and
X.IR hdbmentry ,
which return an HDBMDATUM whose
X.I dat_ptr
is set to 0.
X.SH EXAMPLE
X.ft B
X.nf
static char Unix[] = "UNIX", plan9[] = "Plan 9";
HASHTABLE *tbl = hashcreate(100, (unsigned (*)())NULL);
if (tbl == 0)
X	error("can't hash", "");
if (!hashstore(tbl, Unix, "is a registered trademark of AT&T, etc."))
X	error("can't install %s", Unix);
if (!hashstore(tbl, plan9, "is probably a trademark of MCA"))
X	error("can't install %s", plan9);
printf("%s %s\en", Unix, hashfetch(tbl, Unix));
printf("%s %s\en", plan9, hashfetch(tbl, plan9));
hashdestroy(tbl);
X.fi
X.ft
X.SH SEE ALSO
X.IR hsearch (3),
X.IR tsearch (3)
X.br
The Art of Computer Programming,
Donald E. Knuth
X.SH HISTORY
Written by Geoff Collyer of Software Tool & Die
because
X.IR hsearch (3)
is inadequate for serious hashing.
!
echo hash.c 1>&2
sed 's/^X//' >hash.c <<'!'
X/*
X * general-purpose in-core hashing, normal interface (wrapper)
X */

X#include <stdio.h>
X#include <string.h>
X#include "hdbm.h"
X#include "hash.h"
X#include "hashint.h"

X#ifdef notdef
static unsigned				/* not yet taken modulus table size */
hashdef(key)
register HASHDATUM key;
X{
X	register unsigned hash = 0;
X	register char c;

X	while ((c = *key++) != '\0')
X		hash += c;
X	return hash;
X}
X#endif

HASHTABLE *
hashcreate(size, hashfunc)
unsigned size;				/* a crude guide to size */
unsigned (*hashfunc)();
X{
X	return hdbmcreate(size, hashfunc);
X}

hashdestroy(tbl)
register HASHTABLE *tbl;
X{
X	hdbmdestroy(tbl);
X}

int
hashstore(tbl, key, data)
HASHTABLE *tbl;
register HASHDATUM key, data;
X{
X	register HDBMDATUM hdbmkey, hdbmdata;

X	hdbmkey.dat_ptr = key;			/* actually a string */
X	hdbmkey.dat_len = strlen(key);
X	hdbmdata.dat_ptr = data;		/* just an address */
X	hdbmdata.dat_len = 0;			/* no promises */
X	return hdbmstore(tbl, hdbmkey, hdbmdata);
X}

static HASHDATUM (*hashalloc)();

static HDBMDATUM
hdbmalloc(key)			/* hdbm->hash->hdbm allocator translator */
HDBMDATUM key;
X{
X	register HDBMDATUM hdbmdata;

X	hdbmdata.dat_ptr = (*hashalloc)(key.dat_ptr);
X	hdbmdata.dat_len = 0;			/* just a string */
X	return hdbmdata;
X}

X/* return any existing entry for key; otherwise call allocator to make one */
HASHDATUM
hashentry(tbl, key, allocator)
register HASHTABLE *tbl;
HASHDATUM key;
HASHDATUM (*allocator)();
X{
X	register HDBMDATUM hdbmkey, hdbmdata;

X	hdbmkey.dat_ptr = key;			/* just a string */
X	hdbmkey.dat_len = strlen(key);
X	hashalloc = allocator;
X	hdbmdata = hdbmentry(tbl, hdbmkey, hdbmalloc);
X	return hdbmdata.dat_ptr;
X}

HASHDATUM					/* data corresponding to key */
hashfetch(tbl, key)
HASHTABLE *tbl;
register HASHDATUM key;
X{
X	register HDBMDATUM hdbmkey, hdbmdata;

X	hdbmkey.dat_ptr = key;			/* actually a string */
X	hdbmkey.dat_len = strlen(key);
X	hdbmdata = hdbmfetch(tbl, hdbmkey);
X	return hdbmdata.dat_ptr;		/* just an address */
X}

int
hashdelete(tbl, key)
HASHTABLE *tbl;
register HASHDATUM key;
X{
X	register HDBMDATUM hdbmkey;

X	hdbmkey.dat_ptr = key;			/* actually a string */
X	hdbmkey.dat_len = strlen(key);
X	return hdbmdelete(tbl, hdbmkey);
X}

struct translate {
X	char *realhook;
X	int (*func)();
X};

static
hdbmtohash(key, data, hook)
HDBMDATUM key, data;
char *hook;
X{
X	register struct translate *thp = (struct translate *)hook;

X	(*thp->func)(key.dat_ptr, data.dat_ptr, thp->realhook);
X}

X/*
X * arrange that at each node, hdbmtohash gets called to map the
X * HDBMDATUM arguments to HASHDATUM arguments.  this also demonstrates
X * how to use the hook argument.
X */
hashwalk(tbl, nodefunc, hook)
HASHTABLE *tbl;
int (*nodefunc)();
char *hook;					/* (void *) really */
X{
X	struct translate transhook;
X	register struct translate *tp = &transhook;

X	tp->realhook = hook;
X	tp->func = nodefunc;
X	hdbmwalk(tbl, hdbmtohash, (char *)tp);
X}
!
echo hash.h 1>&2
sed 's/^X//' >hash.h <<'!'
X/*
X * general-purpose in-core hashing, normal interface
X */

typedef char *HASHDATUM;			/* #define won't do due to * */

X#ifndef HASHTABLE
X#define HASHTABLE struct hashtable
X#endif

extern HASHTABLE *hashcreate();
extern hashdestroy(), hashwalk();
extern int hashstore(), hashdelete();
extern HASHDATUM hashfetch(), hashentry();
!
echo hashint.h 1>&2
sed 's/^X//' >hashint.h <<'!'
X/*
X * general-purpose in-core hashing, normal interface (internals)
X */
!
echo hdbm.c 1>&2
sed 's/^X//' >hdbm.c <<'!'
X/*
X * Copyright (c) 1992 Geoffrey Collyer
X * All rights reserved.
X * Written by Geoffrey Collyer.
X *
X * This software is not subject to any license of the American Telephone
X * and Telegraph Company, the Regents of the University of California, or
X * the Free Software Foundation.
X *
X * Permission is granted to anyone to use this software for any purpose on
X * any computer system, and to alter it and redistribute it freely, subject
X * to the following restrictions:
X *
X * 1. The author is not responsible for the consequences of use of this
X *    software, no matter how awful, even if they arise from flaws in it.
X *
X * 2. The origin of this software must not be misrepresented, either by
X *    explicit claim or by omission.  Since few users ever read sources,
X *    credits must appear in the documentation.
X *
X * 3. Altered versions must be plainly marked as such, and must not be
X *    misrepresented as being the original software.  Since few users
X *    ever read sources, credits must appear in the documentation.
X *
X * 4. This notice may not be removed or altered.
X */
X/*
X * general-purpose in-core hashing, dbm interface
X */

X#include <stdio.h>
X#include <stdlib.h>
X#include <string.h>
X#include "hdbm.h"
X#include "hdbmint.h"

X/* tunable parameters */
X#define RETAIN 300		/* retain & recycle this many HASHENTs */

X/* fundamental constants */
X#define YES 1
X#define NO 0

static HASHENT *hereuse = NULL;
static int reusables = 0;

static unsigned				/* not yet taken modulus table size */
hdbmdef(key)
HDBMDATUM key;
X{
X	register char *s = key.dat_ptr;
X	register unsigned len = key.dat_len;
X	register unsigned hash = 0;

X	while (len-- > 0)
X		hash += *s++;
X	return hash;
X}

HASHTABLE *
hdbmcreate(size, hashfunc)
register unsigned size;			/* a crude guide to size */
unsigned (*hashfunc)();
X{
X	register HASHTABLE *tbl;
X	register HASHENT **hepp;
X	/*
X	 * allocate HASHTABLE and (HASHENT *) array together to reduce the
X	 * number of malloc calls.  this idiom ensures correct alignment of
X	 * the array.
X	 * dmr calls the one-element array trick `unwarranted chumminess with
X	 * the compiler' though.
X	 */
X	register struct alignalloc {
X		HASHTABLE ht;
X		HASHENT *hepa[1];	/* longer than it looks */
X	} *aap;

X	aap = (struct alignalloc *)
X		malloc(sizeof *aap + (size-1)*sizeof(HASHENT *));
X	if (aap == NULL)
X		return NULL;
X	tbl = &aap->ht;
X	tbl->ht_size = (size == 0? 1: size);	/* size of 0 is nonsense */
X	tbl->ht_magic = HASHMAG;
X	tbl->ht_hash = (hashfunc == NULL? hdbmdef: hashfunc);
X	tbl->ht_addr = hepp = aap->hepa;
X	while (size-- > 0)
X		hepp[size] = NULL;
X	return tbl;
X}

X/*
X * free all the memory associated with tbl, erase the pointers to it, and
X * invalidate tbl to prevent further use via other pointers to it.
X */
hdbmdestroy(tbl)
register HASHTABLE *tbl;
X{
X	register unsigned idx;
X	register HASHENT *hp, *next;
X	register HASHENT **hepp;
X	register int tblsize;

X	if (tbl == NULL || BADTBL(tbl))
X		return;
X	tblsize = tbl->ht_size;
X	hepp = tbl->ht_addr;
X	for (idx = 0; idx < tblsize; idx++) {
X		for (hp = hepp[idx]; hp != NULL; hp = next) {
X			next = hp->he_next;
X			hp->he_next = NULL;
X			hefree(hp);
X		}
X		hepp[idx] = NULL;
X	}
X	tbl->ht_magic = 0;		/* de-certify this table */
X	tbl->ht_addr = NULL;
X	free((char *)tbl);
X}

X/*
X * The returned value is the address of the pointer that refers to the
X * found object.  Said pointer may be NULL if the object was not found;
X * if so, this pointer should be updated with the address of the object
X * to be inserted, if insertion is desired.
X */
static HASHENT **
hdbmfind(tbl, key)
register HASHTABLE *tbl;
HDBMDATUM key;
X{
X	register HASHENT *hp, *prevhp = NULL;
X	register char *hpkeydat, *keydat = key.dat_ptr;
X	register int keylen = key.dat_len;
X	register HASHENT **hepp;
X	register unsigned size; 

X	if (BADTBL(tbl))
X		return NULL;
X	size = tbl->ht_size;
X	if (size == 0)			/* paranoia: avoid division by zero */
X		size = 1;
X	hepp = &tbl->ht_addr[(*tbl->ht_hash)(key) % size];
X	for (hp = *hepp; hp != NULL; prevhp = hp, hp = hp->he_next) {
X		hpkeydat = hp->he_key.dat_ptr;
X		if (hp->he_key.dat_len == keylen && hpkeydat[0] == keydat[0] &&
X		    memcmp(hpkeydat, keydat, keylen) == 0)
X			break;
X	}
X	/* assert: *(returned value) == hp */
X	return (prevhp == NULL? hepp: &prevhp->he_next);
X}

static HASHENT *
healloc()					/* allocate a hash entry */
X{
X	register HASHENT *hp;

X	if (hereuse == NULL)
X		return (HASHENT *)malloc(sizeof(HASHENT));
X	/* pull the first reusable one off the pile */
X	hp = hereuse;
X	hereuse = hereuse->he_next;
X	hp->he_next = NULL;			/* prevent accidents */
X	reusables--;
X	return hp;
X}

static
hefree(hp)					/* free a hash entry */
register HASHENT *hp;
X{
X	if (reusables >= RETAIN)		/* compost heap is full? */
X		free((char *)hp);		/* yup, just pitch this one */
X	else {					/* no, just stash for reuse */
X		++reusables;
X		hp->he_next = hereuse;
X		hereuse = hp;
X	}
X}

int
hdbmstore(tbl, key, data)
register HASHTABLE *tbl;
HDBMDATUM key, data;
X{
X	register HASHENT *hp;
X	register HASHENT **nextp;

X	if (BADTBL(tbl))
X		return NO;
X	nextp = hdbmfind(tbl, key);
X	if (nextp == NULL)
X		return NO;
X	hp = *nextp;
X	if (hp == NULL) {			/* absent; allocate an entry */
X		hp = healloc();
X		if (hp == NULL)
X			return NO;
X		hp->he_next = NULL;
X		hp->he_key = key;
X		*nextp = hp;			/* append to hash chain */
X	}
X	hp->he_data = data;	/* supersede any old data for this key */
X	return YES;
X}

X/* return any existing entry for key; otherwise call allocator to make one */
HDBMDATUM
hdbmentry(tbl, key, allocator)
register HASHTABLE *tbl;
HDBMDATUM key;
HDBMDATUM (*allocator)();
X{
X	register HASHENT *hp;
X	register HASHENT **nextp;
X	static HDBMDATUM errdatum = { NULL, 0 };

X	if (BADTBL(tbl))
X		return errdatum;
X	nextp = hdbmfind(tbl, key);
X	if (nextp == NULL)
X		return errdatum;
X	hp = *nextp;
X	if (hp == NULL) {			/* absent; allocate an entry */
X		hp = healloc();
X		if (hp == NULL)
X			return errdatum;
X		hp->he_next = NULL;
X		hp->he_key = key;
X		hp->he_data = (*allocator)(key);
X		*nextp = hp;			/* append to hash chain */
X	}
X	return hp->he_data;
X}

int
hdbmdelete(tbl, key)
register HASHTABLE *tbl;
HDBMDATUM key;
X{
X	register HASHENT *hp;
X	register HASHENT **nextp;

X	nextp = hdbmfind(tbl, key);
X	if (nextp == NULL)
X		return NO;
X	hp = *nextp;
X	if (hp == NULL)				/* absent */
X		return NO;
X	*nextp = hp->he_next;			/* skip this entry */
X	hp->he_next = NULL;
X	hp->he_data.dat_ptr = hp->he_key.dat_ptr = NULL;
X	hefree(hp);
X	return YES;
X}

HDBMDATUM					/* data corresponding to key */
hdbmfetch(tbl, key)
register HASHTABLE *tbl;
HDBMDATUM key;
X{
X	register HASHENT *hp;
X	register HASHENT **nextp;
X	static HDBMDATUM errdatum = { NULL, 0 };

X	if (BADTBL(tbl))
X		return errdatum;
X	nextp = hdbmfind(tbl, key);
X	if (nextp == NULL)
X		return errdatum;
X	hp = *nextp;
X	if (hp == NULL)				/* absent */
X		return errdatum;
X	else
X		return hp->he_data;
X}

X/*
X * visit each entry by calling nodefunc at each, with key, data and hook as
X * arguments.  hook is an attempt to allow side-effects and reentrancy at
X * the same time.
X */
hdbmwalk(tbl, nodefunc, hook)
HASHTABLE *tbl;
register int (*nodefunc)();
register char *hook;				/* (void *) really */
X{
X	register unsigned idx;
X	register HASHENT *hp;
X	register HASHENT **hepp;
X	register int tblsize;

X	if (BADTBL(tbl))
X		return;
X	hepp = tbl->ht_addr;
X	tblsize = tbl->ht_size;
X	for (idx = 0; idx < tblsize; idx++)
X		for (hp = hepp[idx]; hp != NULL; hp = hp->he_next)
X			(*nodefunc)(hp->he_key, hp->he_data, hook);
X}
!
echo hdbm.h 1>&2
sed 's/^X//' >hdbm.h <<'!'
X/*
X * general-purpose in-core hashing, dbm interface
X */

X#define HDBMDATUM struct hdbmdatum
HDBMDATUM {
X	char	*dat_ptr;
X	unsigned dat_len;
X};

X#ifndef HASHTABLE
X#define HASHTABLE struct hashtable
X#endif

extern HASHTABLE *hdbmcreate();
extern hdbmdestroy(), hdbmwalk();
extern int hdbmstore(), hdbmdelete();
extern HDBMDATUM hdbmfetch(), hdbmentry();
!
echo hdbmint.h 1>&2
sed 's/^X//' >hdbmint.h <<'!'
X/*
X * general-purpose in-core hashing, dbm interface (internals)
X */

X#define	STREQ(a, b)	(*(a) == *(b) && strcmp((a), (b)) == 0)

X#define BADTBL(tbl)	(((tbl)->ht_magic&BYTEMASK) != HASHMAG)

X#define HASHMAG  0257
X#define BYTEMASK 0377

X#define HASHENT struct hashent

HASHENT {
X	HASHENT	*he_next;		/* in hash chain */
X	HDBMDATUM he_key;		/* to verify a match */
X	HDBMDATUM he_data;
X};

HASHTABLE {
X	HASHENT **ht_addr;		/* array of HASHENT pointers */
X	unsigned ht_size;
X	char	ht_magic;
X	unsigned (*ht_hash)();
X};
!
echo nghash.c 1>&2
sed 's/^X//' >nghash.c <<'!'
X/*
X * This software is Copyright 1991 by Stan Barber.
X *
X * Permission is hereby granted to copy, reproduce, redistribute or otherwise
X * use this software as long as: there is no monetary profit gained
X * specifically from the use or reproduction of this software, it is not
X * sold, rented, traded or otherwise marketed, and this copyright notice is
X * included prominently in any copy made.
X *
X * The author make no claims as to the fitness or correctness of this software
X * for any use whatsoever, and it is provided as is. Any use of this software
X * is at the user's own risk.
X */

X#include "EXTERN.h"
X#include "common.h"
X#include "ndir.h"
X#include "rcstuff.h"
X#include "rn.h"
X#include "intrp.h"
X#include "final.h"
X#include "rcln.h"
X#include "util.h"
X#ifdef SERVER
X#include "server.h"
X#endif
X#include "ngdata.h"

X#include <string.h>
X#include "hdbm.h"

static HASHTABLE *acthash;
static char *actfile;

void
ngdatansrv_init()		/* non-SERVER initialisation */
X{
X	register long offset = 0;
X	char *cp = filexp(ACTIVE);
X	struct stat actstat;

X	actfp = fopen(cp, "r");
X	if (actfp == Nullfp) {
X		printf(cantopen, cp) FLUSH;
X		finalize(1);
X	}

X	/*
X	 * rn was being a slug about rereading the active file over and
X	 * over; try using a really big buffer to keep it in core.
X	 */
X	(void) fstat(fileno(actfp), &actstat);
X	actfile = safemalloc(actstat.st_size + 1);
X	rewind(actfp);
X	/*
X	 * NOTE: this won't work on machines with ints too small to hold
X	 * the size of the active file.
X	 */
X	if (fread(actfile, 1, (int)actstat.st_size, actfp) !=
X	    actstat.st_size) {
X		fprintf(stderr, "active file not read\n");
X		actfile[0] = '\0';
X	}
X	rewind(actfp);
X	actfile[actstat.st_size] = '\0';

X	acthash = hdbmcreate((int)(actstat.st_size/40), (unsigned (*)())NULL);
X	if (acthash == NULL) {
X		fprintf(stderr, "can't hash %s\n", filexp(ACTIVE));
X		finalize(1);
X	}

X	/* count entries */
X	rewind(actfp);
X	for (activeitems = 0; fgets(buf, LBUFLEN, actfp) != NULL;
X	     activeitems++) {
X		register char *p = strchr(buf, ' ');
X		HDBMDATUM key, data;

X		/*
X		 * key.dat_ptr must be allocated to make it permanent for
X		 * hashstore
X		 */
X		if (p == NULL)
X			p = buf;
X		data.dat_ptr = key.dat_ptr = actfile + offset;
X		key.dat_len = p - buf;
X		data.dat_len = strlen(buf);
X		if (!hdbmstore(acthash, key, data)) {
X			fprintf(stderr, "can't install hash key %s\n",
X			     key.dat_ptr);
X			finalize(1);
X		}
X		offset += data.dat_len;
X	}
X}

ACT_POS
findact(outbuf, nam, len, suggestion)
register char *outbuf;
register char *nam;
register int len;
register long suggestion;
X{
X	register ACT_POS retval;
X	extern int debug;

X	/* see if we know the right place and can just return */
X	if (suggestion != 0 && fseek(actfp, suggestion, 0) >= 0 && 
X	    fgets(outbuf, 80, actfp) != NULL && outbuf[len] == ' ' &&
X	    strnEQ(outbuf, nam, len))
X		return suggestion;

X	/* hmm, apparently not, gotta look it up. */
X	if (debug & DEB_SOFT_POINTERS)
X		printf("Missed, looking for %s in %sLen = %d\n",
X		     nam, outbuf, len) FLUSH;
X	/* can we just do a quick hashed lookup? */
X	if (acthash != NULL) {
X		HDBMDATUM key, data;

X		outbuf[0] = '\0';
X		key.dat_ptr = nam;
X		key.dat_len = len;
X		data = hdbmfetch(acthash, key);
X		if (data.dat_ptr == NULL)
X			return -1;
X		else {
X			(void) memcpy(outbuf, data.dat_ptr, (int)data.dat_len);
X			outbuf[data.dat_len] = '\0';
X			return data.dat_ptr - actfile;
X		}
X	}

X	/* apparently not.  gotta do it the slow way. */
X	(void) fseek(actfp, 0L, 0);
X	for (retval = 0; fgets(outbuf, 80, actfp) != NULL;
X	     retval += strlen(outbuf))
X		if (outbuf[len] == ' ' && strnEQ(outbuf, nam, len))
X			break;
X	if (ferror(actfp)) {
X		perror("error on active file");
X		sig_catcher(0);
X		/* NOTREACHED */
X	} else if (feof(actfp))
X		return -1;	/* no such group */
X	else
X		return retval;
X}
!
-- 
Geoff Collyer		world.std.com!geoff, uunet.uu.net!geoff