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