/*******************WARNING*********************

This is a *MODIFIED* version of Geoff Coller's proof-of-concept NOV
implementation.

It has been modified to support threading directly from a file handle
to a NNTP server without a temporary file.

This is not a complete distribution.  We have only distributed enough
to support NN's needs.

The original version came from world.std.com:/src/news/nov.dist.tar.Z
and was dated 11 Aug 1993.

In any case, bugs you find here are probably my fault, as I've trimmed
a fair bit of unused code.

-Peter Wemm  <peter@DIALix.oz.au>
*/

/*
 * Copyright (c) Geoffrey Collyer 1992, 1993.
 * All rights reserved.
 * Written by Geoffrey Collyer.
 * Thanks to UUNET Communications Services Inc for financial support.
 *
 * This software is not subject to any license of the American Telephone
 * and Telegraph Company, the Regents of the University of California, or
 * the Free Software Foundation.
 *
 * Permission is granted to anyone to use this software for any purpose on
 * any computer system, and to alter it and redistribute it freely, subject
 * to the following restrictions:
 *
 * 1. The authors are not responsible for the consequences of use of this
 *    software, no matter how awful, even if they arise from flaws in it.
 *
 * 2. The origin of this software must not be misrepresented, either by
 *    explicit claim or by omission.  Since few users ever read sources,
 *    credits must appear in the documentation.
 *
 * 3. Altered versions must be plainly marked as such, and must not be
 *    misrepresented as being the original software.  Since few users
 *    ever read sources, credits must appear in the documentation.
 *
 * 4. This notice may not be removed or altered.
 */


/*
 * general-purpose in-core hashing, dbm interface
 */

#include <stdlib.h>
#include <string.h>
#include "config.h"
#include "hdbm.h"
#include "hdbmint.h"

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

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

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

static HASHENT *healloc(void);

/*
 * Gosling EMACS hash (h = 33*h + *s++) optimized, loop unrolled with
 * "Duff's Device".  Thanks to Chris Torek.
 */
static unsigned
hdbmdef(register HDBMDATUM key)
{
    register unsigned char *s = (unsigned char *) key.dat_ptr;
    register int    len = key.dat_len;
    register unsigned h;
    register int    loop;

#define HASHC   h = (h << 5) + h + *s++;

    h = 0;
    if (len > 0) {
	loop = (len + 8 - 1) >> 3;

	switch (len & (8 - 1)) {
	    case 0:
		do {		/* All fall throughs */
		    HASHC;
	    case 7:
		    HASHC;
	    case 6:
		    HASHC;
	    case 5:
		    HASHC;
	    case 4:
		    HASHC;
	    case 3:
		    HASHC;
	    case 2:
		    HASHC;
	    case 1:
		    HASHC;
		} while (--loop);
	}

    }
    return (h);
}

HASHTABLE      *
hdbmcreate(register unsigned size, unsigned (*hashfunc) ())
 /* size			a crude guide to size */
{
    register HASHTABLE *tbl;
    register HASHENT **hepp;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    if (BADTBL(tbl))
	return;
    hepp = tbl->ht_addr;
    tblsize = tbl->ht_size;
    for (idx = 0; idx < tblsize; idx++)
	for (hp = hepp[idx]; hp != NULL; hp = hp->he_next)
	    (*nodefunc) (hp->he_key, hp->he_data, hook);
}