/* 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