/* htab.c - table hashing routines */

#include "autoconf.h"
#include "copyright.h"
#ifndef	lint
static char RCSid[] = "$Id: htab.c,v 1.7 1995/03/21 00:00:31 ambar Exp $";
USE(RCSid);
#endif

#ifndef STANDALONE
#include "externs.h"
#include "htab.h"
#include "alloc.h"
#endif /* STANDALONE */

#include "mudconf.h"

/* ---------------------------------------------------------------------------
 * hashval: Compute hash value of a string for a hash table.
 */

int 
hashval(str, hashmask)
    char *str;
    int hashmask;
{
    int hash = 0;
    char *sp;

    /*
     * If the string pointer is null, return 0.  If not, add up the
     * numeric value of all the characters and return the sum,
     * modulo the size of the hash table.
     */

    if (str == NULL)
	return 0;
    for (sp = str; *sp; sp++)
	hash = (hash << 5) + hash + *sp;
    return (hash & hashmask);
}

#ifndef STANDALONE

/* ----------------------------------------------------------------------
 * get_hashmask: Get hash mask for mask-style hashing.
 */

int 
get_hashmask(size)
    int *size;
{
    int tsize;

    /* Get next power-of-two >= size, return power-1 as the mask
     * for ANDing
     */

    for (tsize = 1; tsize < *size; tsize = tsize << 1);
    *size = tsize;
    return tsize - 1;
}

/* ---------------------------------------------------------------------------
 * hashinit: Initialize a new hash table.
 */

void 
hashinit(htab, size)
    HASHTAB *htab;
    int size;
{
    int i;

    htab->mask = get_hashmask(&size);
    htab->hashsize = size;
    htab->checks = 0;
    htab->scans = 0;
    htab->max_scan = 0;
    htab->hits = 0;
    htab->entries = 0;
    htab->deletes = 0;
    htab->nulls = size;
    htab->entry = (HASHARR *) XMALLOC(size * sizeof(struct hashentry *),
				      "hashinit");

    for (i = 0; i < size; i++)
	htab->entry->element[i] = NULL;
}

/* ---------------------------------------------------------------------------
 * hashreset: Reset hash table stats.
 */

void 
hashreset(htab)
    HASHTAB *htab;
{
    htab->checks = 0;
    htab->scans = 0;
    htab->hits = 0;
}

/* ---------------------------------------------------------------------------
 * hashfind: Look up an entry in a hash table and return a pointer to its
 * hash data.
 */

int *
hashfind(str, htab)
    char *str;
    HASHTAB *htab;
{
    int hval, numchecks;
    HASHENT *hptr;

    numchecks = 0;
    htab->scans++;
    hval = hashval(str, htab->mask);
    for (hptr = htab->entry->element[hval]; hptr != NULL; hptr = hptr->next) {
	numchecks++;
	if (strcmp(str, hptr->target) == 0) {
	    htab->hits++;
	    if (numchecks > htab->max_scan)
		htab->max_scan = numchecks;
	    htab->checks += numchecks;
	    return hptr->data;
	}
    }
    if (numchecks > htab->max_scan)
	htab->max_scan = numchecks;
    htab->checks += numchecks;
    return (int *) NULL;
}

/* ---------------------------------------------------------------------------
 * hashadd: Add a new entry to a hash table.
 */

int 
hashadd(str, hashdata, htab)
    char *str;
    int *hashdata;
    HASHTAB *htab;
{
    int hval;
    HASHENT *hptr;

    /*
     * Make sure that the entry isn't already in the hash table.  If it
     * is, exit with an error.  Otherwise, create a new hash block and
     * link it in at the head of its thread.
     */

    if (hashfind(str, htab) != NULL)
	return -1;
    hval = hashval(str, htab->mask);
    htab->entries++;
    if (htab->entry->element[hval] == NULL)
	htab->nulls--;
    hptr = (HASHENT *) XMALLOC(sizeof(HASHENT), "hashadd");
    hptr->target = (char *) strsave(str);
    hptr->data = hashdata;
    hptr->next = htab->entry->element[hval];
    htab->entry->element[hval] = hptr;
    return 0;
}

/* ---------------------------------------------------------------------------
 * hashdelete: Remove an entry from a hash table.
 */

void 
hashdelete(str, htab)
    char *str;
    HASHTAB *htab;
{
    int hval;
    HASHENT *hptr, *last;

    hval = hashval(str, htab->mask);
    last = NULL;
    for (hptr = htab->entry->element[hval];
	 hptr != NULL;
	 last = hptr, hptr = hptr->next) {
	if (strcmp(str, hptr->target) == 0) {
	    if (last == NULL)
		htab->entry->element[hval] = hptr->next;
	    else
		last->next = hptr->next;
	    free(hptr->target);
	    free(hptr);
	    htab->deletes++;
	    htab->entries--;
	    if (htab->entry->element[hval] == NULL)
		htab->nulls++;
	    return;
	}
    }
}

/* ---------------------------------------------------------------------------
 * hashflush: free all the entries in a hashtable.
 */

void 
hashflush(htab, size)
    HASHTAB *htab;
    int size;
{
    HASHENT *hent, *thent;
    int i;

    for (i = 0; i < htab->hashsize; i++) {
	hent = htab->entry->element[i];
	while (hent != NULL) {
	    thent = hent;
	    hent = hent->next;
	    free(thent->target);
	    free(thent);
	}
	htab->entry->element[i] = NULL;
    }

    /* Resize if needed.  Otherwise, just zero all the stats */

    if ((size > 0) && (size != htab->hashsize)) {
	free(htab->entry);
	hashinit(htab, size);
    } else {
	htab->checks = 0;
	htab->scans = 0;
	htab->max_scan = 0;
	htab->hits = 0;
	htab->entries = 0;
	htab->deletes = 0;
	htab->nulls = htab->hashsize;
    }
}

/* ---------------------------------------------------------------------------
 * hashrepl: replace the data part of a hash entry.
 */

int 
hashrepl(str, hashdata, htab)
    char *str;
    int *hashdata;
    HASHTAB *htab;
{
    HASHENT *hptr;
    int hval;

    hval = hashval(str, htab->mask);
    for (hptr = htab->entry->element[hval];
	 hptr != NULL;
	 hptr = hptr->next) {
	if (strcmp(str, hptr->target) == 0) {
	    hptr->data = hashdata;
	    return 0;
	}
    }
    return -1;
}

/* ---------------------------------------------------------------------------
 * hashinfo: return an mbuf with hashing stats
 */

char *
hashinfo(tab_name, htab)
    const char *tab_name;
    HASHTAB *htab;
{
    char *buff;

    buff = alloc_mbuf("hashinfo");
    sprintf(buff, "%-15s %4d%8d%8d%8d%8d%8d%8d%8d",
	    tab_name, htab->hashsize, htab->entries, htab->deletes,
	    htab->nulls, htab->scans, htab->hits, htab->checks,
	    htab->max_scan);
    return buff;
}

/* Returns the key for the first hash entry in 'htab'. */

int *
hash_firstentry(htab)
    HASHTAB *htab;
{
    int hval;

    for (hval = 0; hval < htab->hashsize; hval++)
	if (htab->entry->element[hval] != NULL) {
	    htab->last_hval = hval;
	    htab->last_entry = htab->entry->element[hval];
	    return htab->entry->element[hval]->data;
	}
    return (int *) NULL;
}

int *
hash_nextentry(htab)
    HASHTAB *htab;
{
    int hval;
    HASHENT *hptr;

    hval = htab->last_hval;
    hptr = htab->last_entry;
    if (hptr->next != NULL) {	/* We can stay in the same chain */
	htab->last_entry = hptr->next;
	return hptr->next->data;
    }
    /* We were at the end of the previous chain, go to the next one */
    hval++;
    while (hval < htab->hashsize) {
	if (htab->entry->element[hval] != NULL) {
	    htab->last_hval = hval;
	    htab->last_entry = htab->entry->element[hval];
	    return htab->entry->element[hval]->data;
	}
	hval++;
    }
    return (int *) NULL;
}

/* ---------------------------------------------------------------------------
 * nhashfind: Look up an entry in a numeric hash table and return a pointer
 * to its hash data.
 */

int *
nhashfind(val, htab)
    int val;
    NHSHTAB *htab;
{
    int hval, numchecks;
    NHSHENT *hptr;

    numchecks = 0;
    htab->scans++;
    hval = (val & htab->mask);
    for (hptr = htab->entry->element[hval]; hptr != NULL; hptr = hptr->next) {
	numchecks++;
	if (val == hptr->target) {
	    htab->hits++;
	    if (numchecks > htab->max_scan)
		htab->max_scan = numchecks;
	    htab->checks += numchecks;
	    return hptr->data;
	}
    }
    if (numchecks > htab->max_scan)
	htab->max_scan = numchecks;
    htab->checks += numchecks;
    return (int *) NULL;
}

/* ---------------------------------------------------------------------------
 * nhashadd: Add a new entry to a numeric hash table.
 */

int 
nhashadd(val, hashdata, htab)
    int val, *hashdata;
    NHSHTAB *htab;
{
    int hval;
    NHSHENT *hptr;

    /*
     * Make sure that the entry isn't already in the hash table.  If it
     * is, exit with an error.  Otherwise, create a new hash block and
     * link it in at the head of its thread.
     */

    if (nhashfind(val, htab) != NULL)
	return -1;
    hval = (val & htab->mask);
    htab->entries++;
    if (htab->entry->element[hval] == NULL)
	htab->nulls--;
    hptr = (NHSHENT *) XMALLOC(sizeof(NHSHENT), "nhashadd");
    hptr->target = val;
    hptr->data = hashdata;
    hptr->next = htab->entry->element[hval];
    htab->entry->element[hval] = hptr;
    return 0;
}

/* ---------------------------------------------------------------------------
 * nhashdelete: Remove an entry from a numeric hash table.
 */

void 
nhashdelete(val, htab)
    int val;
    NHSHTAB *htab;
{
    int hval;
    NHSHENT *hptr, *last;

    hval = (val & htab->mask);
    last = NULL;
    for (hptr = htab->entry->element[hval];
	 hptr != NULL;
	 last = hptr, hptr = hptr->next) {
	if (val == hptr->target) {
	    if (last == NULL)
		htab->entry->element[hval] = hptr->next;
	    else
		last->next = hptr->next;
	    free(hptr);
	    htab->deletes++;
	    htab->entries--;
	    if (htab->entry->element[hval] == NULL)
		htab->nulls++;
	    return;
	}
    }
}

/* ---------------------------------------------------------------------------
 * nhashflush: free all the entries in a hashtable.
 */

void 
nhashflush(htab, size)
    NHSHTAB *htab;
    int size;
{
    NHSHENT *hent, *thent;
    int i;

    for (i = 0; i < htab->hashsize; i++) {
	hent = htab->entry->element[i];
	while (hent != NULL) {
	    thent = hent;
	    hent = hent->next;
	    free(thent);
	}
	htab->entry->element[i] = NULL;
    }

    /* Resize if needed.  Otherwise, just zero all the stats */

    if ((size > 0) && (size != htab->hashsize)) {
	free(htab->entry);
	nhashinit(htab, size);
    } else {
	htab->checks = 0;
	htab->scans = 0;
	htab->max_scan = 0;
	htab->hits = 0;
	htab->entries = 0;
	htab->deletes = 0;
	htab->nulls = htab->hashsize;
    }
}

/* ---------------------------------------------------------------------------
 * nhashrepl: replace the data part of a hash entry.
 */

int 
nhashrepl(val, hashdata, htab)
    int val, *hashdata;
    NHSHTAB *htab;
{
    NHSHENT *hptr;
    int hval;

    hval = (val & htab->mask);
    for (hptr = htab->entry->element[hval];
	 hptr != NULL;
	 hptr = hptr->next) {
	if (hptr->target == val) {
	    hptr->data = hashdata;
	    return 0;
	}
    }
    return -1;
}

/* ---------------------------------------------------------------------------
 * search_nametab: Search a name table for a match and return the flag value.
 */

int 
search_nametab(player, ntab, flagname)
    dbref player;
    NAMETAB *ntab;
    char *flagname;
{
    NAMETAB *nt;

    for (nt = ntab; nt->name; nt++) {
	if (minmatch(flagname, nt->name, nt->minlen)) {
	    if (check_access(player, nt->perm)) {
		return nt->flag;
	    }
	}
    }
    return -1;
}

/* ---------------------------------------------------------------------------
 * find_nametab_ent: Search a name table for a match and return a pointer to it.
 */

NAMETAB *
find_nametab_ent(player, ntab, flagname)
    dbref player;
    NAMETAB *ntab;
    char *flagname;
{
    NAMETAB *nt;

    for (nt = ntab; nt->name; nt++) {
	if (minmatch(flagname, nt->name, nt->minlen)) {
	    if (check_access(player, nt->perm)) {
		return nt;
	    }
	}
    }
    return (NAMETAB *) NULL;
}

/* ---------------------------------------------------------------------------
 * display_nametab: Print out the names of the entries in a name table.
 */

void 
display_nametab(player, ntab, prefix, list_if_none)
    dbref player;
    NAMETAB *ntab;
    char *prefix;
    int list_if_none;
{
    char *buf, *bp, *cp;
    NAMETAB *nt;
    int got_one;

    buf = alloc_lbuf("display_nametab");
    bp = buf;
    got_one = 0;
    for (cp = prefix; *cp; cp++)
	*bp++ = *cp;
    for (nt = ntab; nt->name; nt++) {
	if (God(player) || check_access(player, nt->perm)) {
	    *bp++ = ' ';
	    for (cp = nt->name; *cp; cp++)
		*bp++ = *cp;
	    got_one = 1;
	}
    }
    *bp = '\0';
    if (got_one || list_if_none)
	notify(player, buf);
    free_lbuf(buf);
}



/* ---------------------------------------------------------------------------
 * interp_nametab: Print values for flags defined in name table.
 */

void 
interp_nametab(player, ntab, flagword, prefix, true_text, false_text)
    dbref player;
    NAMETAB *ntab;
    int flagword;
    char *prefix, *true_text, *false_text;
{
    char *buf, *bp, *cp;
    NAMETAB *nt;

    buf = alloc_lbuf("interp_nametab");
    bp = buf;
    for (cp = prefix; *cp; cp++)
	*bp++ = *cp;
    nt = ntab;
    while (nt->name) {
	if (God(player) || check_access(player, nt->perm)) {
	    *bp++ = ' ';
	    for (cp = nt->name; *cp; cp++)
		*bp++ = *cp;
	    *bp++ = '.';
	    *bp++ = '.';
	    *bp++ = '.';
	    if ((flagword & nt->flag) != 0)
		cp = true_text;
	    else
		cp = false_text;
	    while (*cp)
		*bp++ = *cp++;
	    if ((++nt)->name)
		*bp++ = ';';
	}
    }
    *bp = '\0';
    notify(player, buf);
    free_lbuf(buf);
}

/* ---------------------------------------------------------------------------
 * listset_nametab: Print values for flags defined in name table.
 */

void 
listset_nametab(player, ntab, flagword, prefix, list_if_none)
    dbref player;
    NAMETAB *ntab;
    int flagword, list_if_none;
    char *prefix;
{
    char *buf, *bp, *cp;
    NAMETAB *nt;
    int got_one;

    buf = bp = alloc_lbuf("listset_nametab");
    for (cp = prefix; *cp; cp++)
	*bp++ = *cp;
    nt = ntab;
    got_one = 0;
    while (nt->name) {
	if (((flagword & nt->flag) != 0) &&
	    (God(player) || check_access(player, nt->perm))) {
	    *bp++ = ' ';
	    for (cp = nt->name; *cp; cp++)
		*bp++ = *cp;
	    got_one = 1;
	}
	nt++;
    }
    *bp = '\0';
    if (got_one || list_if_none)
	notify(player, buf);
    free_lbuf(buf);
}

/* ---------------------------------------------------------------------------
 * cf_ntab_access: Change the access on a nametab entry.
 */

extern CF_HDCL(cf_modify_bits);
extern void FDECL(cf_log_notfound, (dbref, char *, const char *, char *));

CF_HAND(cf_ntab_access)
{
    NAMETAB *np;
    char *ap;

    for (ap = str; *ap && !isspace(*ap); ap++);
    if (*ap)
	*ap++ = '\0';
    while (*ap && isspace(*ap))
	ap++;
    for (np = (NAMETAB *) vp; np->name; np++) {
	if (minmatch(str, np->name, np->minlen)) {
	    return cf_modify_bits(&(np->perm), ap, extra,
				  player, cmd);
	}
    }
    cf_log_notfound(player, cmd, "Entry", str);
    return -1;
}

#endif
