/* htab.c - table hashing routines */ /* $Id: htab.c,v 1.27 2002/10/20 18:26:43 rmg Exp $ */ #include "copyright.h" #include "autoconf.h" #include "config.h" #include "alloc.h" /* required by mudconf */ #include "flags.h" /* required by mudconf */ #include "htab.h" /* required by mudconf */ #include "mudconf.h" /* required by code */ #include "db.h" /* required by externs */ #include "externs.h" /* required by code */ /* --------------------------------------------------------------------------- * 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); } /* ---------------------------------------------------------------------- * 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, flags) HASHTAB *htab; int size, flags; { 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; if ((flags & HT_TYPEMASK) == HT_NUM) { /* Numeric hashtabs implicitly store keys by reference */ flags |= HT_KEYREF; } htab->flags = flags; htab->entry = (HASHENT **) XCALLOC(size, sizeof(HASHENT *), "hashinit"); for (i = 0; i < size; i++) htab->entry[i] = NULL; } /* --------------------------------------------------------------------------- * hashreset: Reset hash table stats. */ void hashreset(htab) HASHTAB *htab; { htab->checks = 0; htab->scans = 0; htab->hits = 0; } /* --------------------------------------------------------------------------- * hashfind_generic: Look up an entry in a hash table and return a pointer * to its hash data. Works for both string and numeric hash tables. */ int *hashfind_generic(key, htab) HASHKEY key; HASHTAB *htab; { int htype, hval, numchecks; HASHENT *hptr, *prev; numchecks = 0; htab->scans++; htype = htab->flags & HT_TYPEMASK; if (htype == HT_STR) { hval = hashval(key.s, htab->mask); } else { hval = (key.i & htab->mask); } for (prev = hptr = htab->entry[hval]; hptr != NULL; hptr = hptr->next) { numchecks++; if ((htype == HT_STR && strcmp(key.s, hptr->target.s) == 0) || (htype == HT_NUM && key.i == hptr->target.i)) { htab->hits++; if (numchecks > htab->max_scan) htab->max_scan = numchecks; htab->checks += numchecks; return hptr->data; } prev = hptr; } if (numchecks > htab->max_scan) htab->max_scan = numchecks; htab->checks += numchecks; return NULL; } /* --------------------------------------------------------------------------- * hashfindflags_generic: Look up an entry in a hash table and return * its flags. Works for both string and numeric hash tables. */ int hashfindflags_generic(key, htab) HASHKEY key; HASHTAB *htab; { int htype, hval, numchecks; HASHENT *hptr, *prev; numchecks = 0; htab->scans++; htype = htab->flags & HT_TYPEMASK; if (htype == HT_STR) { hval = hashval(key.s, htab->mask); } else { hval = (key.i & htab->mask); } for (prev = hptr = htab->entry[hval]; hptr != NULL; hptr = hptr->next) { numchecks++; if ((htype == HT_STR && strcmp(key.s, hptr->target.s) == 0) || (htype == HT_NUM && key.i == hptr->target.i)) { htab->hits++; if (numchecks > htab->max_scan) htab->max_scan = numchecks; htab->checks += numchecks; return hptr->flags; } prev = hptr; } if (numchecks > htab->max_scan) htab->max_scan = numchecks; htab->checks += numchecks; return 0; } /* --------------------------------------------------------------------------- * hashadd_generic: Add a new entry to a hash table. Works for both string * and numeric hashtables. */ int hashadd_generic(key, hashdata, htab, flags) HASHKEY key; int *hashdata; HASHTAB *htab; int flags; { int htype, 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_generic(key, htab) != NULL) return (-1); htype = htab->flags & HT_TYPEMASK; if (htype == HT_STR) { hval = hashval(key.s, htab->mask); } else { hval = (key.i & htab->mask); } htab->entries++; if (htab->entry[hval] == NULL) htab->nulls--; hptr = (HASHENT *) XMALLOC(sizeof(HASHENT), "hashadd"); if (htab->flags & HT_KEYREF) { hptr->target = key; } else { hptr->target.s = XSTRDUP(key.s, "hashadd.target"); } hptr->data = hashdata; hptr->flags = flags; hptr->next = htab->entry[hval]; htab->entry[hval] = hptr; return (0); } /* --------------------------------------------------------------------------- * hashdelete_generic: Remove an entry from a hash table. Works for both * string and numeric hashtables. */ void hashdelete_generic(key, htab) HASHKEY key; HASHTAB *htab; { int htype, hval; HASHENT *hptr, *last; htype = htab->flags & HT_TYPEMASK; if (htype == HT_STR) { hval = hashval(key.s, htab->mask); } else { hval = (key.i & htab->mask); } last = NULL; for (hptr = htab->entry[hval]; hptr != NULL; last = hptr, hptr = hptr->next) { if ((htype == HT_STR && strcmp(key.s, hptr->target.s) == 0) || (htype == HT_NUM && key.i == hptr->target.i)) { if (last == NULL) htab->entry[hval] = hptr->next; else last->next = hptr->next; if (!(htab->flags & HT_KEYREF)) { XFREE(hptr->target.s, "hashdelete.target"); } XFREE(hptr, "hashdelete.hptr"); htab->deletes++; htab->entries--; if (htab->entry[hval] == NULL) htab->nulls++; return; } } } void hashdelall(old, htab) int *old; HASHTAB *htab; { int hval; HASHENT *hptr, *prev, *nextp; for (hval = 0; hval < htab->hashsize; hval++) { prev = NULL; for (hptr = htab->entry[hval]; hptr != NULL; hptr = nextp) { nextp = hptr->next; if (hptr->data == old) { if (prev == NULL) htab->entry[hval] = nextp; else prev->next = nextp; if (!(htab->flags & HT_KEYREF)) { XFREE(hptr->target.s, "hashdelall.target"); } XFREE(hptr, "hashdelall.hptr"); htab->deletes++; htab->entries--; if (htab->entry[hval] == NULL) htab->nulls++; continue; } prev = hptr; } } } /* --------------------------------------------------------------------------- * 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[i]; while (hent != NULL) { thent = hent; hent = hent->next; if (!(htab->flags & HT_KEYREF)) { XFREE(thent->target.s, "hashflush.target"); } XFREE(thent, "hashflush.hent"); } htab->entry[i] = NULL; } /* Resize if needed. Otherwise, just zero all the stats */ if ((size > 0) && (size != htab->hashsize)) { XFREE(htab->entry, "hashflush.table"); hashinit(htab, size, htab->flags); } 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_generic: replace the data part of a hash entry. Works for both * string and numeric hashtables. */ int hashrepl_generic(key, hashdata, htab) HASHKEY key; int *hashdata; HASHTAB *htab; { HASHENT *hptr; int htype, hval; htype = htab->flags & HT_TYPEMASK; if (htype == HT_STR) { hval = hashval(key.s, htab->mask); } else { hval = (key.i & htab->mask); } for (hptr = htab->entry[hval]; hptr != NULL; hptr = hptr->next) { if ((htype == HT_STR && strcmp(key.s, hptr->target.s) == 0) || (htype == HT_NUM && key.i == hptr->target.i)) { hptr->data = hashdata; return 1; } } return 0; } void hashreplall(old, new, htab) int *old, *new; HASHTAB *htab; { int hval; HASHENT *hptr; for (hval = 0; hval < htab->hashsize; hval++) for (hptr = htab->entry[hval]; hptr != NULL; hptr = hptr->next) { if (hptr->data == old) hptr->data = new; } } /* --------------------------------------------------------------------------- * 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 %5d%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 data 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[hval] != NULL) { htab->last_hval = hval; htab->last_entry = htab->entry[hval]; return htab->entry[hval]->data; } return 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[hval] != NULL) { htab->last_hval = hval; htab->last_entry = htab->entry[hval]; return htab->entry[hval]->data; } hval++; } return NULL; } /* Returns the key for the first hash entry in 'htab'. */ HASHKEY hash_firstkey_generic(htab) HASHTAB *htab; { int hval; for (hval = 0; hval < htab->hashsize; hval++) if (htab->entry[hval] != NULL) { htab->last_hval = hval; htab->last_entry = htab->entry[hval]; return htab->entry[hval]->target; } if ((htab->flags & HT_TYPEMASK) == HT_STR) { return (HASHKEY) ((char *) NULL); } else { return (HASHKEY) ((int) -1); } } HASHKEY hash_nextkey_generic(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->target; } /* We were at the end of the previous chain, go to the next one */ hval++; while (hval < htab->hashsize) { if (htab->entry[hval] != NULL) { htab->last_hval = hval; htab->last_entry = htab->entry[hval]; return htab->entry[hval]->target; } hval++; } if ((htab->flags & HT_TYPEMASK) == HT_STR) { return (HASHKEY) ((char *) NULL); } else { return (HASHKEY) ((int) -1); } } /* --------------------------------------------------------------------------- * hashresize: Resize a hash table, to adjust the number of slots to be * a power of 2 appropriate to the number of entries in it. */ void hashresize(htab, min_size) HASHTAB *htab; int min_size; { int size, i, htype, hval; HASHTAB new_htab; HASHENT *hent, *thent; size = (htab->entries) * HASH_FACTOR; size = (size < min_size) ? min_size : size; get_hashmask(&size); if ((size > 512) && (size > htab->entries * 1.33 * HASH_FACTOR)) size /= 2; if (size == htab->hashsize) { /* We're already at the correct size. Don't do anything. */ return; } hashinit(&new_htab, size, htab->flags); htype = htab->flags & HT_TYPEMASK; for (i = 0; i < htab->hashsize; i++) { hent = htab->entry[i]; while (hent != NULL) { thent = hent; hent = hent->next; /* don't free and reallocate entries, just copy the pointers */ if (htype == HT_STR) { hval = hashval(thent->target.s, new_htab.mask); } else { hval = (thent->target.i & new_htab.mask); } if (new_htab.entry[hval] == NULL) new_htab.nulls--; thent->next = new_htab.entry[hval]; new_htab.entry[hval] = thent; } } XFREE(htab->entry, "hashinit"); htab->hashsize = new_htab.hashsize; htab->mask = new_htab.mask; htab->checks = new_htab.checks; htab->scans = new_htab.scans; htab->max_scan = new_htab.max_scan; htab->hits = new_htab.hits; htab->deletes = new_htab.deletes; htab->nulls = new_htab.nulls; htab->entry = new_htab.entry; htab->last_hval = new_htab.last_hval; htab->last_entry = new_htab.last_entry; /* number of entries doesn't change */ /* flags don't change */ } /* --------------------------------------------------------------------------- * 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; } else return -2; } } 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 NULL; } /* --------------------------------------------------------------------------- * find_nametab_ent_flag: Search a name table for a match by flag value * and return a pointer to it. */ NAMETAB *find_nametab_ent_flag(player, ntab, flag) dbref player; NAMETAB *ntab; int flag; { NAMETAB *nt; for (nt = ntab; nt->name; nt++) { if (flag == nt->flag) { 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(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. */ 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; }