/* htab.c - table hashing routines */ #include "copyright.h" #include <stdio.h> #include <string.h> #include "db.h" #include "mudconf.h" #include "externs.h" #include "htab.h" /* --------------------------------------------------------------------------- * hashinit: Initialize a new hash table. */ void hashinit (HASHTAB *htab, int size) { int i; 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 *)malloc(size * sizeof(struct hashentry *)); for (i=0; i<size; i++) htab->entry->element[i] = NULL; } /* --------------------------------------------------------------------------- * hashreset: Reset hash table stats. */ void hashreset (HASHTAB *htab) { htab->checks = 0; htab->scans = 0; htab->hits = 0; } /* --------------------------------------------------------------------------- * hashval: Compute hash value of a string for a hash table. */ int hashval (char *str, HASHTAB *htab) { int hash; 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, * mudulo the size of the hash table. */ if (str == NULL) return 0; hash = 0; for (sp=str; *sp; sp++) hash += *sp; return (hash % htab->hashsize); } /* --------------------------------------------------------------------------- * hashfind: Look up an entry in a hash table and return a pointer to its * hash data. */ int *hashfind (char *str, HASHTAB *htab) { int hval, numchecks; HASHENT *hptr; numchecks = 0; htab->scans++; hval = hashval(str, htab); 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 NULL; } /* --------------------------------------------------------------------------- * hashadd: Add a new entry to a hash table. */ int hashadd (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); htab->entries++; if (htab->entry->element[hval] == NULL) htab->nulls--; hptr = (HASHENT *)malloc(sizeof(HASHENT)); 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 (char *str, HASHTAB *htab) { int hval; HASHENT *hptr, *last; hval = hashval(str, htab); 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 (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); } 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 (char *str, int *hashdata, HASHTAB *htab) { HASHENT *hptr; int hval; hval = hashval(str, htab); for (hptr=htab->entry->element[hval]; hptr!=NULL; hptr=hptr->next) { if (strcmp(str, hptr->target) == 0) { hptr->data = hashdata; return 1; } } return 0; } /* --------------------------------------------------------------------------- * hashinfo: return an mbuf with hashing stats */ char *hashinfo(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; } /* --------------------------------------------------------------------------- * nhashfind: Look up an entry in a numeric hash table and return a pointer * to its hash data. */ int *nhashfind (int val, NHSHTAB *htab) { int hval, numchecks; NHSHENT *hptr; numchecks = 0; htab->scans++; hval = val % htab->hashsize; 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 NULL; } /* --------------------------------------------------------------------------- * nhashadd: Add a new entry to a numeric hash table. */ int nhashadd (int val, int *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->hashsize; htab->entries++; if (htab->entry->element[hval] == NULL) htab->nulls--; hptr = (NHSHENT *)malloc(sizeof(NHSHENT)); 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 (int val, NHSHTAB *htab) { int hval; NHSHENT *hptr, *last; hval = val % htab->hashsize; 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 (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 (int val, int *hashdata, NHSHTAB *htab) { NHSHENT *hptr; int hval; hval = val % htab->hashsize; for (hptr=htab->entry->element[hval]; hptr!=NULL; hptr=hptr->next) { if (hptr->target == val) { hptr->data = hashdata; return 1; } } return 0; } /* --------------------------------------------------------------------------- * search_nametab: Search a name table for a match and return the flag value. */ int search_nametab (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 (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 NULL; } /* --------------------------------------------------------------------------- * display_nametab: Print out the names of the entries in a name table. */ void display_nametab (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 (dbref player, NAMETAB *ntab, int flagword, char *prefix, char *true_text, char *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 (dbref player, NAMETAB *ntab, int flagword, char *prefix, int list_if_none) { 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 int cf_modify_bits (int *vp, char *str, int *extra, dbref player, char *cmd); extern void cf_log_notfound (dbref player, char *cmd, const char *thingname, char *thing); int cf_ntab_access (int *vp, char *str, int *extra, dbref player, char *cmd) { 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; }