/*
#ident "@(#)smail/src:RELEASE-3_2_0_121:hash.c,v 1.32 2005/07/11 19:38:17 woods Exp"
*/
/*
* Copyright (C) 1987, 1988 Ronald S. Karr and Landon Curt Noll
* Copyright (C) 1992 Ronald S. Karr
*
* See the file COPYING, distributed with smail, for restriction
* and warranty information.
*/
/*
* hash:
* perform a string hashing algorithm functions
*
* Hash tables are defined by their size. It is suggested that the
* size be a prime value, say:
* 13, 29, 47, 61, 113, 181, 251, 359, 509, 751, 1021, 1511,
* 2039, 3079, 4093, 6151, 8179, 12377, 16381, 24571, 32749,
* 49139, 65557, 98299, 132049, 180023, 216091, 321367, 521539, ...
* An advantage with the above primes is that they are at last 3 less
* than 2^n, and no closer than 3 away from 3*(2^m) for the larger
* values of m. Most malloc systems are most efficient when one allocates
* 3 words less than 2^n bytes, i.e., 4*(2^n - 3) bytes.
*
* external functions:
* add_to_hash, lookup_in_hash, delete_from_hash,
* delete_from_hash, store_in_hash, new_hash_table,
* write_hash_table, walk_hash, free_hash_element,
* free_hash_table
*/
#include "defs.h"
#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#include <ctype.h>
#ifdef STDC_HEADERS
# include <stdlib.h>
# include <stddef.h>
#else
# ifdef HAVE_STDLIB_H
# include <stdlib.h>
# endif
#endif
#ifdef HAVE_STRING_H
# if !defined(STDC_HEADERS) && defined(HAVE_MEMORY_H)
# include <memory.h>
# endif
# include <string.h>
#endif
#ifdef HAVE_STRINGS_H
# include <strings.h>
#endif
#ifdef __STDC__
# include <stdarg.h>
#else
# include <varargs.h>
#endif
#if defined(HAVE_UNISTD_H)
# include <unistd.h>
#endif
#include "smail.h"
#include "alloc.h"
#include "list.h"
#include "smailarch.h"
#include "main.h"
#include "addr.h"
#include "exitcodes.h"
#include "hash.h"
#include "smailstring.h"
#include "dys.h"
#include "log.h"
#include "extern.h"
#include "debug.h"
#include "smailport.h"
/* static functions used in this file */
static int hash_str __P((char *, unsigned int));
static int hash_stric __P((char *, unsigned int));
static struct hash *new_hash_element __P((char *, void *, size_t, struct hash_table *));
#ifdef STANDALONE
int debug = 0; /* default debug level is NONE */
# define errfile stderr
extern void panic();
# define xmalloc(x) (malloc(x)) /* naive allocator */
# define bmalloc(x,y) (malloc(x)) /* naive allocator */
# define xfree(x) (free(x)) /* naive deallocator */
# define bfree(x,y) (free(x)) /* naive deallocator */
/* functions imported by this file */
# if !defined(HAVE_STDLIB_H) && !defined(HAVE_MALLOC_H)
extern char *malloc();
extern char *realloc();
extern void free(); /* int on SunOS */
# endif
#endif /* STANDALONE */
/*
* hash_str - convert a trying into a hash value
*
* We build the hash value one character at a time by repeating the following
* steps for each character:
*
* 1) The previous value is shifted up (by HASH_UP_SHIFT) and the
* current character is added
* 2) any upper level excess bits are fetched (by masking with
* {H,L}_HASH_MASK) and xor-ed into bits near the bottom
* 3) the upper level excess bits are cleared
*
* In the end, the hash value is taken modulo `mod' to produce a slot number.
*
* input:
* str - string to hash
* mod - number of hash table entries
* output:
* the slot number on which `str' belongs
*
* NOTE: For more optimal hashing of smaller hash tables (entries < HASH_LEVEL)
* we L_ value constants. This gives us a faster hash fold. For larger
* hash tables, this is not needed so H_ value constants are used.
*
* NOTE: mod should be a prime <= ~H_HASH_MASK
*/
static int
hash_str(str, mod)
register char *str; /* the string to hash */
unsigned int mod; /* prime modulus, size of hash table */
{
register unsigned long val; /* current hash value */
register unsigned long excess; /* upper/excess bits in val */
register unsigned long c; /* the current string character */
/* firewall - bogus case, but be safe anyway */
if (str == NULL) {
return 0;
}
/*
* hash each character in the string
*
* if our mod is small enough, then use L_ value constants so that
* strings can fold into themselves faster.
*/
if (mod < HASH_LEVEL) {
/* hash each character using the L_ values */
for (val = 0; (c = (unsigned long) *str); ++str) {
val = (val << HASH_UP_SHIFT) + c;
val ^= ((excess = (val & L_HASH_MASK)) >> L_DOWN_SHIFT);
val ^= excess;
}
} else {
/* hash each character using the H_ values */
for (val = 0; (c = (unsigned long) *str); ++str) {
val = (val << HASH_UP_SHIFT) + c;
val ^= ((excess = (val & H_HASH_MASK)) >> H_DOWN_SHIFT);
val ^= excess;
}
}
return (int) (val % mod); /* our hash value, mod the hash size */
}
/*
* hash_stric - convert a trying into a hash value without regard to case
*
* We build the hash value one character at a time by repeating the following
* steps for each character:
*
* 1) The previous value is shifted up (by HASH_UP_SHIFT) and the
* current character is added
* 2) any upper level excess bits are fetched (by masking with
* {H,L}_HASH_MASK) and xor-ed into bits near the bottom
* 3) the upper level excess bits are cleared
*
* In the end, the hash value is taken modulo `mod' to produce a slot number.
*
* input:
* str - string to hash without regard to case
* mod - number of hash table entries
* output:
* the slot number on which `str' belongs
*
* NOTE: For more optimal hashing of smaller hash tables (entries < HASH_LEVEL)
* we L_ value constants. This gives us a faster hash fold. For larger
* hash tables, this is not needed so H_ value constants are used.
*
* NOTE: mod should be a prime <= ~H_HASH_MASK
*/
static int
hash_stric(str, mod)
register char *str; /* the string to hash disregarding case */
unsigned int mod; /* prime modulus, size of hash table */
{
register unsigned long val; /* current hash value */
register unsigned long excess; /* upper/excess bits in val */
register unsigned long c; /* the current string character */
/* firewall - bogus case, but be safe anyway */
if (str == NULL) {
return 0;
}
/*
* hash each character in the string
*
* if our mod is small enough, then use L_ value constants so that
* strings can fold into themselves faster.
*/
if (mod < HASH_LEVEL) {
/* hash each character using the L_ values */
for (val = 0; (c = (unsigned long) tolower((int) *str)); ++str) {
val = (val << HASH_UP_SHIFT) + c;
val ^= ((excess = (val & L_HASH_MASK)) >> L_DOWN_SHIFT);
val ^= excess;
}
} else {
/* hash each character using the H_ values */
for (val = 0; (c = (unsigned long) tolower((int) *str)); ++str) {
val = (val << HASH_UP_SHIFT) + c;
val ^= ((excess = (val & H_HASH_MASK)) >> H_DOWN_SHIFT);
val ^= excess;
}
}
return (int) (val % mod); /* our hash value, mod the hash size */
}
/*
* walk_hash - walk thru a hash table
*
* returns NULL if there is no next element in the hash table
*
* input:
* cur - our current location, or NULL to start at the beginning
* table - the table to be walked
* output:
* a pointer to the next element, or NULL if no next element
*
* WARNING: results will be unpredictable or fatal if `cur' != NULL, and
* `cur' != `the previous walk location', and `cur' is an element
* that has been either deleted or replaced by another element.
* It should be noted that this `cur' will never be the `previous
* walk location' if our previous call ran off the end of the table.
*/
struct hash *
walk_hash(cur, table)
struct hash *cur; /* where we are now */
struct hash_table *table; /* hash table being walked */
{
register struct hash *prev; /* our previous walk location */
register unsigned int indx; /* our previous hash slot */
register unsigned int len; /* the table length */
/*
* firewall
*/
if (table == NULL) {
panic(EX_SOFTWARE, "walk_hash: table is NULL");
}
/* fetch these values for faster use */
prev = table->prev;
indx = table->indx;
len = table->len;
/*
* find the first hash slot if cur is NULL (due to a restart request)
*/
if (cur == NULL) {
/* note that we really don't have a location yet */
prev = NULL;
/* find the first slot and return it */
for (indx=0; indx < len; ++indx) {
if (full_slot(table->slot[indx])) {
/* we found the first entry of the first non-empty chain */
prev = table->slot[indx];
break;
}
}
/*
* walk from our current location to the next location
*/
} else {
/*
* if `cur' is not the previous `cur', then find `cur' and
* note where our hash table index now resides
*/
if (cur != prev) {
/* find the hash table index */
indx = hash_string(cur->keystr, len, table->flags&HASH_CASEFOLD);
/* if `cur' is an empty slot, panic */
if (empty_slot(table->slot[indx])) {
panic(EX_SOFTWARE, "walk_hash: <%v> hash slot is empty",
cur->keystr);
}
/* walk down the hash table chain looking for our entry */
for (prev = table->slot[indx];
cur != prev && prev != NULL;
prev = next_hash(prev,table)) {
}
}
/* if `cur' is not in the hash table, panic */
if (prev == NULL) {
panic(EX_SOFTWARE, "walk_hash: <%v> is not in table", cur->keystr);
}
/*
* if we were at the end of a chain, then our successor will
* be the start of the next non-empty chain
*/
if ((prev = next_hash(prev,table)) == NULL) {
/* find the next non-empty chain */
for (++indx; indx < len; ++indx) {
if (full_slot(table->slot[indx])) {
/* return first element of this chain */
prev = table->slot[indx];
break;
}
}
}
}
/*
* return the pointer the next element or NULL
*/
/* remember our location for next time */
table->prev = hash_addr(prev, table);
table->indx = indx;
return table->prev;
}
/*
* new_hash_element - creat a new hash element
*
* return a malloced new hash element with the lengths correctly filled out
*
* inputs:
* keystr - the key of this data element
* data - the data to accompany `keystr', or NULL if no data
* datalen - the length of `data' in bytes, or 0 is no data
* table - the hash table which will get this element
*/
static struct hash *
new_hash_element(keystr, data, datalen, table)
char *keystr; /* the keystring to be added */
void *data; /* the associated data if any */
size_t datalen; /* length of data, 0 ==> no data */
struct hash_table *table; /* hash table being added to */
{
struct hash *new; /* the new slot chain location */
size_t keylen; /* the length of the string, padded */
unsigned long lk; /* temp var for key length */
/*
* firewall - check for bad pointers and values
*/
if (keystr == NULL || table == NULL) {
panic(EX_SOFTWARE, "new_hash_element: NULL keystring or table");
}
lk = keystr_len(keystr); /* compute padded key length */
if (lk >= (unsigned long) (1L << BITS_PER_SHORT)) {
panic(EX_SOFTWARE, "new_hash_element: key too long");
}
keylen = (size_t) lk; /* now we know it will fit in an int */
/* firewall - check against bad data being passed to us */
if ((datalen > 0 && data == NULL) ||
datalen >= (unsigned long) (1L << BITS_PER_SHORT)) {
panic(EX_SOFTWARE,
"new_hash_element: bad data passed with: <%v> datalen: <%lu>",
keystr, datalen);
}
/*
* malloc the storage
*/
new = (struct hash *) bmalloc((size_t) hashslot_size(keylen, datalen), table->life);
/* firewall */
if (is_odd(new)) {
panic(EX_SOFTWARE,
"new_hash_element: bmalloc() returned an odd-numbered address: %p",
(POINTER_TYPE) new);
}
/*
* return the prebuild element
*/
new->succ = NULL;
new->keylen = keylen;
strcpy(new->keystr, keystr);
new->datalen = datalen;
if (datalen > 0) {
memcpy(hash_data(new), data, (size_t) datalen);
}
return new;
}
/*
* free_hash_element - free an old hash element
*
* Frees a hash table element according to the life of the hash table.
* Removes the hash table element if it in the hash table unless explicitly
* told that the element is not in the table.
*
* inputs:
* cur - the element which which we will free
* search - non-zero means delete `cur' from table prior to the free
* table - the table on which `cur' resides, or the table to which
* `cur' would have been added
*
* WARNING: It is important that the `cur' element NOT be in a hash table
* after the free. Unpredictable results will happen otherwise.
* If `search' is non-zero, we will first attempt to delete `cur'
* from `table'. It is a fatal error if `search' is non-zero and
* `cur' is not in `table'.
*
* WARNING: It is important that `cur' was individually malloced (perhaps
* by new_hash_element) so that the free of its address will
* be valid.
*/
void
free_hash_element(cur, search, table)
struct hash *cur; /* what we will delete */
unsigned int search; /* non-zero => delete `cur' first */
struct hash_table *table; /* table `cur' does/would_have belonged to */
{
/*
* firewall - check for bad pointers and values
*/
if (cur == NULL || table == NULL) {
panic(EX_SOFTWARE, "free_hash_element: NULL cur or table");
}
/*
* delete the element first if requested
*/
if (search != 0 && delete_from_hash(cur->keystr, table) == NULL) {
panic(EX_SOFTWARE,"free_hash_element: <%v> not in table",cur->keystr);
}
/*
* free the storage
*/
if (!table->life) {
DEBUG(DBG_HASH_LO, "free_hash_element(): about to panic() with NULL block\n");
}
bfree((char *) cur, table->life);
return;
}
/*
* new_hash_table - creat a new hash table
*
* return a malloced new hash table with correctly setup initial pointers
*
* input:
* tablelen - number of slots in the hash table
* life - the alloc block to which this is to be associated, or NULL
* meaning the permanent block
* output:
* a pointer to a malloced empty hash table
*/
struct hash_table *
new_hash_table(tablelen, life, flags)
unsigned int tablelen; /* number of slots in the hash table */
struct block *life; /* is the hash table permanent or temporary */
int flags; /* hash table flag as per struct hash_table */
{
register unsigned int i; /* index */
struct hash_table *table; /* the malloced hash table */
/*
* firewalls
*/
DEBUG3(DBG_HASH_LO,
"new_hash_table: tablelen: %u life: %p flags: 0x%lx\n", tablelen, (POINTER_TYPE) life, flags);
/*
* malloc the hash table
*/
table = (struct hash_table *) bmalloc(table_size(tablelen), life);
/* firewall */
if (is_odd(table)) {
panic(EX_SOFTWARE,
"new_hash_table: malloc returned odd address: %p",
(POINTER_TYPE) table);
}
/*
* initialize the table
*/
table->len = tablelen;
table->flags = flags & HASH_FLAGMASK;
table->life = life;
table->prev = NULL; /* no current walk_hash() location */
table->indx = 0; /* no current walk_hash() slot index */
for (i=0; i < tablelen; i++) {
table->slot[i] = NULL;
}
return table; /* return our new table */
}
/*
* free_hash_table - free a hash table and its associated data
*
* Free all storage associated with a hash table.
*
* NOTE: any malloced elements should be freed prior to calling this routine.
*
* input:
* table - the hash table to free
*/
void
free_hash_table(table)
struct hash_table *table; /* the hash table to free */
{
/*
* firewalls
*/
if (table == NULL ) {
panic(EX_SOFTWARE, "free_hash_table: NULL table");
}
DEBUG(DBG_HASH_LO,"free_hash_table: start\n");
/*
* free the table slots
*/
if (!table->life) {
DEBUG(DBG_HASH_LO, "free_hash_table(): about to panic() with NULL block\n");
}
bfree((char *) table, table->life);
/* XXX why don't we free 'table' itself? or free_block() it? */
return;
}
/*
* add_to_hash - add an element to the a hash table
*
* inputs:
* keystr - the key of the data to add
* data - the data to accompany `keystr', or NULL if no data
* datalen - the length of `data' in bytes, or 0 if no data
* table - a pointer to the hash table which is being modified
* output:
* returns ALREADY_HASHED if `keystr' is already in the `table', or
* JUST_HASHED if we just added a no key. The `table' is not modified
* if the key is already exists.
*/
int
add_to_hash(keystr, data, datalen, table)
char *keystr; /* the keystring to be added */
void *data; /* the associated data if any */
size_t datalen; /* length of data, 0 ==> no data */
struct hash_table *table; /* the hash table to add it to */
{
register struct hash *cur; /* the current slot chain location */
register struct hash *prev; /* the previous slot chain location */
register int cmp; /* -1, 0, or 1 for < = > compare */
register int caseflag; /* 0 ==> use strcmp, 1 ==> strcmpic */
int loc; /* the hash slot to add onto */
struct hash *new; /* the new slot chain location */
/*
* firewall - watch for NULLs
*/
if (keystr == NULL) {
panic(EX_SOFTWARE, "add_to_hash: NULL keystr");
}
if (table == NULL) {
panic(EX_SOFTWARE, "add_to_hash: NULL table");
}
/*
* determine the slot on which this entry is to be added
*/
caseflag = table->flags & HASH_CASEFOLD;
loc = hash_string(keystr, table->len, caseflag);
DEBUG2(DBG_HASH_LO, "add_to_hash: keystr: <%v> slot: %d\n", keystr, loc);
/*
* search the slot chain for our entry
*/
/* special case for empty slot chains */
if (empty_slot(table->slot[loc])) {
DEBUG(DBG_HASH_MID, "add_to_hash: insert in NULL slot\n");
new = new_hash_element(keystr, data, datalen, table);
insert_hash(&table->slot[loc], new);
return JUST_HASHED;
}
/*
* search the chain
*/
DEBUG2(DBG_HASH_VHI, "add_to_hash: slot: %p cur: %p\n",
(POINTER_TYPE) table->slot[loc], (POINTER_TYPE) table->slot[loc]);
for (prev = NULL, cur = table->slot[loc];
cur != NULL;
prev = cur, cur = next_hash(cur, table)) {
/*
* if we found the entry, stop
*/
DEBUG2(DBG_HASH_VHI, "add_to_hash: comparing <%v> to <%v>\n",
keystr, cur->keystr);
if ((cmp = stringcmp(keystr, cur->keystr, caseflag)) == 0) {
DEBUG(DBG_HASH_MID, "add_to_hash: already hashed\n");
return ALREADY_HASHED;
/*
* we are past the insertion point, insert before here and stop
* note if we are inserting at the beginning a a chain or in the middle
*/
} else if (cmp < 0) {
new = new_hash_element(keystr, data, datalen, table);
if (prev == NULL) {
DEBUG(DBG_HASH_MID, "add_to_hash: insert at front\n");
insert_hash(&table->slot[loc], new); /* insert at beginning */
} else {
DEBUG(DBG_HASH_MID, "add_to_hash: insert in middle\n");
insert_hash(prev, new); /* insert in middle */
}
return JUST_HASHED;
}
}
/*
* case: insertion at the end of the chain
*/
DEBUG(DBG_HASH_MID, "add_to_hash: insert at END\n");
new = new_hash_element(keystr, data, datalen, table);
insert_hash(prev, new);
return JUST_HASHED;
}
/*
* replace_in_hash - replace an existing element in a hash table
*
* inputs:
* keystr - the key of the data to replace
* data - the data to accompany `keystr', or NULL if no data
* datalen - the length of `data' in bytes, or 0 if no data
* table - a pointer to the hash table which is being modified
* output:
* returns a pointer to the element that was replaced, or NULL
* if no element was replaced due to `keystr' not in `table'
*/
struct hash *
replace_in_hash(keystr, data, datalen, table)
char *keystr; /* the keystring to replace */
void *data; /* the associated data if any */
size_t datalen; /* length of data, 0 ==> no data */
struct hash_table *table; /* the hash table to add it to */
{
register struct hash *cur; /* the current slot chain location */
register struct hash *prev; /* the previous slot chain location */
register int cmp; /* -1, 0, or 1 for < = > compare */
register int caseflag; /* 0 ==> use strcmp, 1 ==> strcmpic */
int loc; /* the hash slot to add onto */
struct hash *new; /* the new slot chain location */
/*
* firewall - watch for NULLs
*/
if (keystr == NULL) {
panic(EX_SOFTWARE, "replace_in_hash: NULL keystr");
}
if (table == NULL) {
panic(EX_SOFTWARE, "replace_in_hash: NULL table");
}
/*
* determine the slot on which this entry is to be added
*/
caseflag = table->flags & HASH_CASEFOLD;
loc = hash_string(keystr, table->len, caseflag);
DEBUG2(DBG_HASH_LO, "replace_in_hash: keystr: <%v> slot: %d\n",keystr,loc);
/*
* search the slot chain for our entry
*/
/* special case for empty slow chains */
if (empty_slot(table->slot[loc])) {
DEBUG(DBG_HASH_MID, "replace_in_hash: slot NULL\n");
return NULL; /* no entry to replace */
}
/*
* search the chain
*/
for (prev=NULL, cur=table->slot[loc]; cur != NULL;
prev=cur, cur=next_hash(cur, table)) {
/*
* if we found the entry, stop
*/
if ((cmp = stringcmp(keystr, cur->keystr, caseflag)) == 0) {
new = new_hash_element(keystr, data, datalen, table);
if (prev == NULL) {
DEBUG(DBG_HASH_MID, "replace_in_hash: replaced at front\n");
/* insert at beginning */
replace_hash(table->slot[loc], cur, new);
} else {
DEBUG(DBG_HASH_MID, "replace_in_hash: replaced in middle\n");
replace_hash(prev->succ, cur, new); /* insert in middle */
}
return cur;
/* if we have gone past our entry, stop searching */
} else if (cmp < 0) {
break;
}
}
/*
* entry not found, nothing to replace
*/
DEBUG(DBG_HASH_MID, "replace_in_hash: not found\n");
return NULL;
}
/*
* store_in_hash - store an existing element in a hash table
*
* inputs:
* keystr - the key of the data to store
* data - the data to accompany `keystr', or NULL if no data
* datalen - the length of `data' in bytes, or 0 if no data
* table - a pointer to the hash table which is being modified
* output:
* returns a pointer to the element that was replaced, or NULL
* if no element was replaced. In any case the element is added.
*/
struct hash *
store_in_hash(keystr, data, datalen, table)
char *keystr; /* the keystring to replace */
void *data; /* the associated data if any */
size_t datalen; /* length of data, 0 ==> no data */
struct hash_table *table; /* the hash table to add it to */
{
register struct hash *cur; /* the current slot chain location */
register struct hash *prev; /* the previous slot chain location */
register int cmp; /* -1, 0, or 1 for < = > compare */
register int caseflag; /* 0 ==> use strcmp, 1 ==> strcmpic */
int loc; /* the hash slot to add onto */
struct hash *new; /* the new slot chain location */
/*
* firewall - watch for NULLs
*/
if (keystr == NULL) {
panic(EX_SOFTWARE, "store_in_hash: NULL keystr");
}
if (table == NULL) {
panic(EX_SOFTWARE, "store_in_hash: NULL table");
}
/*
* determine the slot on which this entry is to be added
*/
caseflag = table->flags & HASH_CASEFOLD;
loc = hash_string(keystr, table->len, caseflag);
DEBUG2(DBG_HASH_LO, "store_in_hash: keystr: <%v> loc: %d\n", keystr, loc);
/*
* search the slot chain for our entry
*/
/* special case for empty slow chains */
if (empty_slot(table->slot[loc])) {
DEBUG(DBG_HASH_MID, "store_in_hash: insert on NULL slot\n");
new = new_hash_element(keystr, data, datalen, table);
insert_hash(&table->slot[loc], new);
return NULL;
}
/*
* search the chain
*/
for (prev=NULL, cur=table->slot[loc]; cur != NULL;
prev=cur, cur=next_hash(cur, table)) {
/*
* if we found the entry, stop
*/
if ((cmp = stringcmp(keystr, cur->keystr, caseflag)) == 0) {
new = new_hash_element(keystr, data, datalen, table);
if (prev == NULL) {
DEBUG(DBG_HASH_MID, "store_in_hash: replaced at front\n");
/* insert at beginning */
replace_hash(table->slot[loc], cur, new);
} else {
DEBUG(DBG_HASH_MID, "store_in_hash: replaced in middle\n");
replace_hash(prev->succ, cur, new); /* insert in middle */
}
return cur;
/*
* we are past the insertion point, insert before here and stop
* note if we are inserting at the beginning a a chain or in the middle
*/
} else if (cmp < 0) {
new = new_hash_element(keystr, data, datalen, table);
if (prev == NULL) {
DEBUG(DBG_HASH_MID, "store_in_hash: insert at front\n");
insert_hash(&table->slot[loc], new); /* insert at beginning */
} else {
DEBUG(DBG_HASH_MID, "store_in_hash: insert in middle\n");
insert_hash(&prev->succ, new); /* insert in middle */
}
return NULL;
}
}
/*
* case: insertion at the end of the chain
*/
DEBUG(DBG_HASH_MID, "store_in_hash: insert at END\n");
new = new_hash_element(keystr, data, datalen, table);
insert_hash(&prev->succ, new);
return NULL;
}
/*
* lookup_in_hash - lookup an element in a hash table and return
* the associated data
*
* inputs:
* keystr - the key of the data to add
* data - pointer to a pointer, or 0 if no data is wanted
* datalen - pointer to the data length, or NULL if no length is wanted
* table - a pointer to the hash table which is being modified
* output:
* returns ALREADY_HASHED if `keystr' is already in the `table', or
* NOT_HASHED the key was not found
* data - if `data' was non-NULL points at the key's data or NULL
* no data
* datalen - if `datalen' was non-NULL, points at the length of the
* key's data
*/
int
lookup_in_hash(keystr, datap, datalenp, table)
char *keystr; /* the key to lookup */
void **datap; /* where to point at data, or NULL */
size_t *datalenp; /* where to place data len or NULL */
struct hash_table *table; /* the hash table to add it to */
{
register struct hash *cur; /* the slot chain location */
unsigned int loc; /* the hash slot to add onto */
unsigned int caseflag; /* 0 ==> use strcmp, 1 ==> strcmpic */
int cmp; /* compare function result */
/*
* firewall - watch for NULLs
*/
if (keystr == NULL) {
panic(EX_SOFTWARE, "lookup_in_hash: NULL keystr");
}
if (table == NULL) {
panic(EX_SOFTWARE, "lookup_in_hash: table is NULL");
}
/*
* determine the hash slot to search on
*/
caseflag = table->flags & HASH_CASEFOLD;
loc = hash_string(keystr, table->len, caseflag);
DEBUG2(DBG_HASH_LO, "lookup_in_hash: keystr: <%v> slot: %d\n",keystr,loc);
/* watch out for empty chains, there is nothing on them */
if (empty_slot(table->slot[loc])) {
DEBUG(DBG_HASH_MID, "lookup_in_hash: found at slot END\n");
return NOT_HASHED;
}
/*
* search the chain
*/
for (cur=table->slot[loc]; cur != NULL; cur=next_hash(cur, table)) {
/*
* if we found the entry, stop
*/
if ((cmp = stringcmp(keystr, cur->keystr, caseflag)) == 0) {
DEBUG(DBG_HASH_MID, "lookup_in_hash: found\n");
/*
* fill in the requested args
*/
if (datap != NULL) {
*datap = hash_data(cur);
}
if (datalenp != NULL) {
*datalenp = cur->datalen;
}
return ALREADY_HASHED;
/* if we have gone past our entry, stop searching */
} else if (cmp < 0) {
break;
}
}
/* found nothing */
DEBUG(DBG_HASH_MID, "lookup_in_hash: not found\n");
return NOT_HASHED;
}
/*
* delete_from_hash - delete an element in the hash table
*
* inputs:
* keystr - the key of the data to add
* table - a pointer to the hash table which is being modified
* output:
* returns a pointer to the element that was deleted, or NULL
* if no element was deleted due to `keystr' not in `table'
*/
struct hash *
delete_from_hash(keystr, table)
char *keystr; /* the key to lookup */
struct hash_table *table; /* the hash table to add it to */
{
register struct hash *cur; /* the slot chain location */
register struct hash *prev; /* previous element */
unsigned int loc; /* the hash slot to add onto */
unsigned int caseflag; /* 0 ==> use strcmp, 1 ==> strcmpic */
int cmp; /* compare function result */
/*
* firewall - watch for NULLs
*/
if (keystr == NULL) {
panic(EX_SOFTWARE, "delete_from_hash: keystr is NULL");
}
if (table == NULL) {
panic(EX_SOFTWARE, "delete_from_hash: table is NULL");
}
/*
* determine the hash slot to search on
*/
caseflag = table->flags & HASH_CASEFOLD;
loc = hash_string(keystr, table->len, caseflag);
DEBUG2(DBG_HASH_LO, "delete_from_hash: keystr: <%v> loc: %d\n",keystr,loc);
/* watch out for empty chains, there is nothing on them */
if (empty_slot(table->slot[loc])) {
DEBUG(DBG_HASH_MID, "delete_from_hash: EMPTY slot\n");
return NULL; /* key is not in the table */
}
/*
* search the chain for the element to delete
*/
for (prev=NULL, cur=table->slot[loc]; cur != NULL;
prev=cur, cur=next_hash(cur, table)) {
/*
* if we found the entry, stop
*/
if ((cmp = stringcmp(keystr, cur->keystr, caseflag)) == 0) {
if (prev == NULL) {
DEBUG(DBG_HASH_MID, "delete_from_hash: delete at front\n");
/* delete at the beginning */
delete_hash(&table->slot[loc], cur);
} else {
DEBUG(DBG_HASH_MID, "delete_from_hash: delete in middle\n");
delete_hash(&prev->succ, cur); /* delete in middle */
}
return cur;
/*
* if we have gone past the entry, stop looking
*/
} else if (cmp < 0) {
DEBUG(DBG_HASH_MID, "delete_from_hash: past spot\n");
break;
}
}
/* found nothing */
DEBUG(DBG_HASH_MID, "delete_from_hash: not found\n");
return NULL; /* nothing was deleted */
}
/*
* write_hash_table - write a hash table to a stream
*
* input:
* tab - the hash table to write
* stream - the stream on which to write
*/
void
write_hash_table(table, stream)
struct hash_table *table; /* the table to write */
FILE *stream; /* the stream on which to write table */
{
register size_t i; /* index */
off_t tab_loc; /* file location of hash_table start */
long loc; /* current location */
int size; /* size of the current element */
off_t offset; /* current offset within the file */
long disc_succ; /* cur->succ as written to disc */
struct hash *cur; /* the current hash element */
struct hash_table *tab; /* disk copy of table */
/*
* firewalls
*/
if (table == NULL || stream == NULL) {
panic(EX_SOFTWARE, "write_hash_table: NULL arguments");
}
if (table->len <= 0) {
panic(EX_SOFTWARE, "write_hash_table: table length: %d", table->len);
}
DEBUG2(DBG_HASH_LO, "write_hash_table: size: %d life: %p\n",
table->len, (POINTER_TYPE) table->life);
/*
* allocate a temporary disk copy of the hash table
*/
tab = (struct hash_table *)xmalloc(table_size(table->len));
tab->life = table->life; /* preserve life type */
tab->len = table->len; /* preserve table length */
tab->flags = table->flags; /* preserve flags - XXX all bits ??? */
tab->prev = NULL; /* clear walking location */
tab->indx = 0; /* clear walking slot index */
/*
* skip the hash table block
*/
tab_loc = ftell(stream);
if (fseek(stream, (long int) table_size(table->len), 1) < 0) {
panic(EX_IOERR, "write_hash_table: bad skip of %d over table",
table_size(table->len));
}
/*
* write out each hash table chain
*/
for (i=0; i < table->len; i++) {
/* don't write out chains that don't exist */
if (empty_slot(table->slot[i])) {
/* slot is empty, deal with it quickly */
set_ptr(tab->slot[i], (int) NULL);
continue;
}
/* note starting offset of hash chain */
offset = ftell(stream) - tab_loc;
if (is_odd(offset)) {
panic(EX_IOERR, "write_hash_table: slot %d offset is odd: 0x%lx",
i, (unsigned long int) offset);
}
set_ptr(tab->slot[i], to_odd(offset));
/* write up to the last chain element */
for (cur=table->slot[i]; cur != NULL; cur=next_hash(cur, table)) {
/* compute the current element length */
size = hash_len(cur);
if (is_odd(size)) {
panic(EX_IOERR,
"write_hash_table: size is odd: 0x%lx for <%v>",
(unsigned long int) offset, cur->keystr);
}
offset += size; /* note file movement */
/* write the hash element disk successor element */
disc_succ = (cur->succ == NULL) ? 0 : to_odd(offset);
if (fwrite((char *)&disc_succ, sizeof(disc_succ), (size_t) 1, stream) != 1) {
panic(EX_IOERR,
"write_hash_table: bad succ write <%v> on slot %d",
cur->keystr, i);
}
/* write the rest of the hash element data */
if (fwrite((char *)cur+sizeof(cur->succ), size-sizeof(cur->succ),
(size_t) 1, stream) != 1) {
panic(EX_IOERR,
"write_hash_table: bad write <%v> on slot %d",
cur->keystr, i);
}
}
}
/*
* write the hash table back in its place and return to our
* current position
*/
loc = ftell(stream); /* remember our current location */
if (fseek(stream, (long int) tab_loc, 0) < 0) {
panic(EX_IOERR, "write_hash_table: bad skip back to table at 0x%lx", (unsigned long int) tab_loc);
}
if (fwrite((char *)tab, table_size(tab->len), (size_t) 1, stream) != 1) {
panic(EX_IOERR, "write_hash_table: bad table write");
}
if (fseek(stream, (long int) loc, 0) < 0) {
panic(EX_IOERR, "write_hash_table: bad end seek to 0x%lx", (unsigned long int) loc);
}
/*
* free the temporary disk copy of the hash table
*/
xfree((char *)tab);
return;
}
#ifdef STANDALONE
#include <sys/types.h>
#include <sys/stat.h>
#include <limits.h>
#include "dys.h"
#ifdef HAVE_UNISTD_H
# include <unistd.h>
#endif
#ifdef USE_VMALLOC
# include <vmalloc.h>
# define malloc_check() vmdbcheck(Vmheap)
#endif
#if !defined(HAVE_STDLIB_H) && !defined(HAVE_MALLOC_H)
extern char *mktemp();
#endif
#ifndef malloc_check
# define malloc_check() /* NO-OP */
#endif
#if !defined(SIZE_T_MAX) && defined(UINT_MAX)
# define SIZE_T_MAX UINT_MAX /* most modern systems use UINT_MAX */
#elif !defined(SIZE_T_MAX)
# define SIZE_T_MAX 0xffffffffU /* XXX 'U' is not a valid suffix in traditional C */
#endif
#define TABLE_LEN 3 /* use only a few slots to stress the chain code */
int return_to_sender = FALSE;
char *tempname = "/tmp/smhtXXXXXX"; /* tempory hash file name */
void
main(argc, argv)
int argc; /* arg count */
char *argv[]; /* args */
{
int i; /* index */
char *buf; /* the input buffer for stdin args */
struct hash *cur; /* pointer to walk the table */
struct block *table_block; /* bmalloc() for bfree() */
struct block *tableic_block; /* bmalloc() for bfree() */
struct hash_table *table; /* our allocated table */
struct hash_table *tableic; /* allocated table without regard to case */
void test(); /* test an with an element */
void dump_hash_table(); /* dump the contents of the hash table */
void hash_file_test(); /* perform hash file testing */
/*
* establish debug level
*/
DEBUG(DBG_HASH_LO, "main: start\n");
if (argc > 1 && strncmp(argv[1], "-v", 2) == 0) {
/* we have a debug level, use it */
if (argv[1][2] != '\0') {
debug = atoi(&argv[1][2]);
--argc;
++argv;
} else if (argc > 2) {
debug = atoi(argv[2]);
argc -= 2;
argv += 2;
}
}
DEBUG1(DBG_HASH_LO, "main: debug level: %d\n", debug);
/*
* setup a hash table
*/
table_block = malloc_block();
table = new_hash_table(TABLE_LEN, table_block, HASH_CASEFOLD);
tableic_block = malloc_block();
tableic = new_hash_table(TABLE_LEN, tableic_block, 0);
/*
* special case: no args means read one arg per line
*/
if (argc == 1) {
while ((buf = read_line(stdin))) {
int len;
/* trim the trailing newline, if any */
len = strlen(buf);
if (buf[len - 1] == '\n') {
buf[len - 1] = '\0';
}
DEBUG1(DBG_HASH_LO,
"main: testing <%v> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n", buf);
test(buf, table);
if (debug >= DBG_HASH_HI) {
dump_hash_table(table);
}
DEBUG1(DBG_HASH_LO,
"main: testing ignore case <%v> -*-*-*-*-*-*-*-*-*-\n", buf);
test(buf, tableic);
if (debug >= DBG_HASH_HI) {
dump_hash_table(tableic);
}
}
/*
* hash each argument
*/
} else {
for (i = 1; i < argc; ++i) {
DEBUG1(DBG_HASH_LO,
"main: testing <%v> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n", buf);
test(argv[i], table);
if (debug >= DBG_HASH_HI) {
dump_hash_table(table);
}
DEBUG1(DBG_HASH_LO,
"main: testing ignore case <%v> -*-*-*-*-*-*-*-*-*-\n", buf);
test(argv[i], tableic);
if (debug >= DBG_HASH_HI) {
dump_hash_table(tableic);
}
}
}
/*
* test the file operations
*/
DEBUG(DBG_HASH_LO, "main: hash_file_test\n");
hash_file_test(table);
DEBUG(DBG_HASH_LO, "main: hash_file_test ignore case\n");
hash_file_test(tableic);
/*
* final cleanup
*/
DEBUG(DBG_HASH_LO, "main: free memory\n");
/* free the hash table elements */
cur = walk_hash((struct hash *) NULL, table);
while (cur) {
struct hash *next; /* pointer to the next element */
next = walk_hash(cur, table); /* find the next entry */
free_hash_element(cur, 0, table); /* free the current without deletion */
cur = next;
}
free_hash_table(table); /* free up the header memory */
free_block(table_block);
DEBUG(DBG_HASH_LO, "main: free memory ignore case\n");
cur = walk_hash((struct hash *) NULL, tableic);
while (cur) {
struct hash *next; /* pointer to the next element */
next = walk_hash(cur, tableic); /* find the next entry */
free_hash_element(cur, 0, tableic); /* free the current without deletion */
cur = next;
}
free_hash_table(tableic); /* free up the header memory */
free_block(tableic_block);
DEBUG(DBG_HASH_LO, "main: end\n");
exit(EX_OK);
}
/*
* perform various tests on a string
*/
void
test(buf, table)
char *buf; /* the key to add */
struct hash_table *table; /* our allocated table */
{
register struct hash *cur; /* the current hash entry */
void *data; /* the data we stored */
size_t datalen; /* length of data */
size_t buflen; /* length of the buffer string + NULL */
int i; /* index */
register int caseflag; /* 0 ==> use strcmp, 1 ==> strcmpic */
/* test adding */
buflen = strlen(buf) + 1;
i = add_to_hash(buf, buf, buflen, table);
DEBUG2(DBG_HASH_LO, "test: <%v> add: %d\n", buf, i);
/* test the lookup function */
DEBUG1(DBG_HASH_MID, "test: <%v> lookup\n", buf);
caseflag = table->flags & HASH_CASEFOLD;
if (lookup_in_hash(buf, &data, &datalen, table) != ALREADY_HASHED) {
panic(EX_SOFTWARE,
"test: add_to_hash lost <%v>", buf);
} else if (stringcmp(buf, data, caseflag) != 0 || buflen != datalen) {
panic(EX_SOFTWARE,
"test: add_to_hash lookup <%v> != <%v>", buf, data);
}
i = add_to_hash(buf, buf, buflen, table);
if (i != ALREADY_HASHED) {
panic(EX_SOFTWARE, "test: add_to_hash returned: %d for #2\n", i);
}
/* test the delete function */
DEBUG1(DBG_HASH_MID, "test: <%v> delete\n", buf);
cur = delete_from_hash(buf, table); /* delete something that exists */
if (cur == NULL) {
panic(EX_SOFTWARE,
"test: delete_from_hash unable to delete <%v>", buf);
} else if (stringcmp(buf, hash_data(cur), caseflag) != 0 ||
buflen != cur->datalen) {
panic(EX_SOFTWARE,
"test: delete_from_hash mis delete of <%v>", buf);
} else {
free_hash_element(cur, 0, table); /* free up memory */
}
DEBUG1(DBG_HASH_MID, "test: <%v> empty delete\n", buf);
cur = delete_from_hash(buf, table); /* delete a nothing */
if (cur != NULL) {
panic(EX_SOFTWARE,
"test: delete_from_hash ghost delete #2 of <%v>", buf);
}
/* test the store function */
DEBUG1(DBG_HASH_MID, "test: <%v> store\n", buf);
cur = store_in_hash(buf, buf, buflen, table);
if (cur != NULL) {
panic(EX_SOFTWARE,
"test: store_in_hash ghost store of <%v>", buf);
}
DEBUG1(DBG_HASH_MID, "test: <%v> store #2\n", buf);
cur = store_in_hash(buf, buf, buflen, table);
if (cur == NULL) {
panic(EX_SOFTWARE,
"test: store_in_hash lost store #2 of <%v>", buf);
} else if (stringcmp(buf, hash_data(cur), caseflag) != 0 ||
buflen != cur->datalen) {
panic(EX_SOFTWARE,
"test: store_in_hash mis store #2 of <%v>", buf);
} else {
free_hash_element(cur, 0, table); /* free up memory */
}
/* test the replace function */
DEBUG1(DBG_HASH_MID, "test: <%v> replace_in_hash\n", buf);
cur = replace_in_hash(buf, buf, buflen, table);
if (cur == NULL) {
panic(EX_SOFTWARE,
"test: replace_in_hash lost <%v>", buf);
} else if (stringcmp(buf, hash_data(cur), caseflag) != 0 ||
buflen != cur->datalen) {
panic(EX_SOFTWARE,
"test: replace_in_hash mis replace of <%v>", buf);
} else {
free_hash_element(cur, 0, table); /* free up memory */
}
DEBUG1(DBG_HASH_MID, "test: <%v> replace_in_hash empty\n", buf);
cur = delete_from_hash(buf, table); /* delete something that exists */
if (cur == NULL) {
panic(EX_SOFTWARE,
"test: delete_from_hash unable to delete #3 <%v>", buf);
} else {
free_hash_element(cur, 0, table); /* free up memory */
}
cur = replace_in_hash(buf, buf, buflen, table);
if (cur != NULL) {
panic(EX_SOFTWARE,
"test: replace_in_hash ghost replace of <%v>", buf);
} else {
/* put it back for keeps */
cur = store_in_hash(buf, buf, buflen, table);
if (cur != NULL) {
panic(EX_SOFTWARE,
"test: store_in_hash store #3 lost <%v>", buf);
}
}
}
/*
* dump_hash_table - dump the hash table
*/
void
dump_hash_table(table)
struct hash_table *table; /* our allocated table */
{
int i; /* index */
struct hash *cur; /* the current hash entry */
/*
* check the hash chains
*/
for (i = 0; i < TABLE_LEN; ++i) {
DEBUG1(DBG_HASH_HI, "dump: slot[%d]:", i);
/* check for empty slots */
if (empty_slot(table->slot[i])) {
DEBUG(DBG_HASH_HI, "Empty\n");
continue;
}
for (cur = table->slot[i]; cur; cur = next_hash(cur, table)) {
if (cur->keylen == 0) {
DEBUG2(DBG_HASH_HI, " %p: <%v> :EOC ",
(POINTER_TYPE) cur, cur->keystr);
} else {
DEBUG3(DBG_HASH_HI, " %p: <%v> :%p ",
(POINTER_TYPE) cur, cur->keystr, (POINTER_TYPE) cur->succ);
}
}
DEBUG(DBG_HASH_HI, "\n");
}
}
/*
* hash_file_test - test the hash table file operations
*/
void
hash_file_test(table)
struct hash_table *table; /* the hash table to operate on */
{
char *filename; /* the file to operate on */
struct stat buf; /* file status buffer */
struct hash *cur; /* current location in hash table */
struct hash *cur2; /* current location in hash table2 */
struct hash_table *table2; /* the hash table to operate on */
int caseflag; /* 0 ==> use strcmp, 1 ==> strcmpic */
char *template; /* template for mktemp */
FILE *stream; /* the file stream */
int table_len; /* */
/*
* open up a file to perform hash table operations into
*/
template = xmalloc(strlen(tempname)+1);
strcpy(template, tempname);
filename = mktemp(template);
DEBUG1(DBG_HASH_LO, "hash_file_test: using <%v>\n", filename);
if (! (stream = fopen(filename, "w"))) {
panic(EX_CANTCREAT, "hash_file_test: can not fopen(%s, 'w'): %s", filename, strerror(errno));
}
/*
* write out the hash table
*/
write_hash_table(table, stream);
if (fclose(stream) != 0) {
panic(EX_IOERR, "hash_file_test: can not fclose(): %s", strerror(errno));
}
/*
* reread the hash table into memory
*/
DEBUG1(DBG_HASH_MID, "hash_file_test: rereading <%v>\n", filename);
if (! (stream = fopen(filename, "r"))) {
panic(EX_NOINPUT, "hash_file_test: can not fopen(%s, 'r'): %s", filename, strerror(errno));
}
if (fstat(fileno(stream), &buf) < 0) {
panic(EX_IOERR, "hash_file_test: can not fstat(%s): ", filename, strerror(errno));
}
if (buf.st_size > SIZE_T_MAX) {
panic(EX_IOERR, "hash_file_test: file <%v> too big to read! (%ld)", filename, (long) buf.st_size);
}
table_len = buf.st_size;
DEBUG2(DBG_HASH_LO, "hash_file_test: about to allocate %d bytes to be read from %s.\n", table_len, filename)
table2 = (struct hash_table *) xmalloc(table_len * sizeof(char));
if (fread((char *) table2, sizeof(char), table_len, stream) != table_len) {
panic(EX_IOERR, "hash_file_test: can not fread(%s): %s", filename, strerror(errno));
}
/*
* walk thru each hash table and verify string/data
*/
caseflag = table->flags & HASH_CASEFOLD;
DEBUG(DBG_HASH_MID, "hash_file_test: verify\n");
for (cur = walk_hash((struct hash *) NULL, table), cur2 = walk_hash((struct hash *) NULL, table2);
cur && cur2;
cur = walk_hash(cur, table), cur2 = walk_hash(cur2, table2)) {
/*
* compare cur and cur2
*/
if (stringcmp(cur->keystr, cur2->keystr, caseflag) != 0) {
panic(EX_SOFTWARE,
"hash_file_test: key mismatch: <%v> != <%v>\n",
cur->keystr, cur2->keystr);
}
if (cur->datalen != cur2->datalen) {
panic(EX_SOFTWARE,
"hash_file_test: key mismatch: %d != %d\n",
cur->datalen, cur2->datalen);
}
if (memcmp(hash_data(cur), hash_data(cur2), cur->datalen) != 0) {
panic(EX_SOFTWARE,
"hash_file_test: data mismatch between <%v> and <%v>\n",
cur->keystr, cur2->keystr);
}
}
if (cur != NULL && cur2 != NULL) {
panic(EX_SOFTWARE,
"hash_file_test: %s longer than %s!\n",
cur ? "cur" : "cur2",
cur ? "cur2" : "cur");
}
/*
* cleanup
*/
DEBUG(DBG_HASH_MID, "hash_file_test: cleanup\n");
xfree(table2);
}
#endif /* STANDALONE */
/*
* Local Variables:
* c-file-style: "smail"
* End:
*/
syntax highlighted by Code2HTML, v. 0.9.1