/****************************************************************************
* ResortMUD 4.0 Beta by Ntanel, Garinan, Badastaz, Josh, Digifuzz, Senir, *
* Kratas, Scion, Shogar and Tagith. Special thanks to Thoric, Nivek, *
* Altrag, Arlorn, Justice, Samson, Dace, HyperEye and Yakkov. *
****************************************************************************
* Copyright (C) 1996 - 2001 Haslage Net Electronics: MudWorld *
* of Lorain, Ohio - ALL RIGHTS RESERVED *
* The text and pictures of this publication, or any part thereof, may not *
* be reproduced or transmitted in any form or by any means, electronic or *
* mechanical, includes photocopying, recording, storage in a information *
* retrieval system, or otherwise, without the prior written or e-mail *
* consent from the publisher. *
****************************************************************************
* GREETING must mention ResortMUD programmers and the help file named *
* CREDITS must remain completely intact as listed in the SMAUG license. *
****************************************************************************/
/****************************************************************************
* Advanced string hashing functions (c)1996 D.S.D. Software, written by *
* Derek Snider for use in SMAUG. *
* *
* These functions keep track of how many "links" are pointing to the *
* memory allocated, and will free the memory if all the links are removed. *
* Make absolutely sure you do not mix use of strdup and free with these *
* functions, or nasty stuff will happen! *
* Most occurances of strdup/str_dup should be replaced with str_alloc, and *
* any free/DISPOSE used on the same pointer should be replaced with *
* str_free. If a function uses strdup for temporary use... it is best if *
* it is left as is. Just don't get usage mixed up between conventions. *
* The hashstr_data size is 8 bytes of overhead. Don't be concerned about *
* this as you still save lots of space on duplicate strings. -Thoric *
****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#define STR_HASH_SIZE 1024
struct hashstr_data
{
struct hashstr_data *next; /* next hash element */
unsigned short int links; /* number of links to this string */
unsigned short int length; /* length of string */
};
char *str_alloc( char *str );
char *quick_link( char *str );
int str_free( char *str );
void show_hash( int count );
char *hash_stats( void );
struct hashstr_data *string_hash[STR_HASH_SIZE];
/*
* Check hash table for existing occurance of string.
* If found, increase link count, and return pointer,
* otherwise add new string to hash table, and return pointer.
*/
char *str_alloc( char *str )
{
register int len, hash, psize;
register struct hashstr_data *ptr;
len = strlen( str );
psize = sizeof( struct hashstr_data );
hash = len % STR_HASH_SIZE;
for( ptr = string_hash[hash]; ptr; ptr = ptr->next )
if( len == ptr->length && !strcmp( str, ( char * )ptr + psize ) )
{
if( ptr->links < 65535 )
++ptr->links;
return ( char * )ptr + psize;
}
ptr = ( struct hashstr_data * )malloc( len + psize + 1 );
ptr->links = 1;
ptr->length = len;
if( len )
strcpy( ( char * )ptr + psize, str );
/* memcpy( (char *) ptr+psize, str, len+1 ); */
else
strcpy( ( char * )ptr + psize, "" );
ptr->next = string_hash[hash];
string_hash[hash] = ptr;
return ( char * )ptr + psize;
}
/*
* Used to make a quick copy of a string pointer that is known to be already
* in the hash table. Function increments the link count and returns the
* same pointer passed.
*/
char *quick_link( char *str )
{
register struct hashstr_data *ptr;
ptr = ( struct hashstr_data * )( str - sizeof( struct hashstr_data ) );
if( ptr->links == 0 )
{
fprintf( stderr, "quick_link: bad pointer\n" );
return NULL;
}
if( ptr->links < 65535 )
++ptr->links;
return str;
}
/*
* Used to remove a link to a string in the hash table.
* If all existing links are removed, the string is removed from the
* hash table and disposed of.
* returns how many links are left, or -1 if an error occurred.
*/
int str_free( char *str )
{
register int len, hash;
register struct hashstr_data *ptr, *ptr2, *ptr2_next;
len = strlen( str );
hash = len % STR_HASH_SIZE;
ptr = ( struct hashstr_data * )( str - sizeof( struct hashstr_data ) );
if( ptr->links == 65535 ) /* permanent */
return ptr->links;
if( ptr->links == 0 )
{
fprintf( stderr, "str_free: bad pointer\n" );
return -1;
}
if( --ptr->links == 0 )
{
if( string_hash[hash] == ptr )
{
string_hash[hash] = ptr->next;
free( ptr );
return 0;
}
for( ptr2 = string_hash[hash]; ptr2; ptr2 = ptr2_next )
{
ptr2_next = ptr2->next;
if( ptr2_next == ptr )
{
ptr2->next = ptr->next;
free( ptr );
return 0;
}
}
fprintf( stderr, "str_free: pointer not found for string: %s\n", str );
return -1;
}
return ptr->links;
}
void show_hash( int count )
{
struct hashstr_data *ptr;
int x, c;
for( x = 0; x < count; x++ )
{
for( c = 0, ptr = string_hash[x]; ptr; ptr = ptr->next, c++ );
fprintf( stderr, " %d", c );
}
fprintf( stderr, "\n" );
}
void hash_dump( int hash )
{
struct hashstr_data *ptr;
char *str;
int c, psize;
if( hash > STR_HASH_SIZE || hash < 0 )
{
fprintf( stderr, "hash_dump: invalid hash size\r\n" );
return;
}
psize = sizeof( struct hashstr_data );
for( c = 0, ptr = string_hash[hash]; ptr; ptr = ptr->next, c++ )
{
str = ( char * )( ( ( long )ptr ) + psize );
fprintf( stderr, "Len:%4d Lnks:%5d Str: %s\r\n", ptr->length, ptr->links, str );
}
fprintf( stderr, "Total strings in hash %d: %d\r\n", hash, c );
}
char *check_hash( char *str )
{
static char buf[1024];
int len, hash, psize, p = 0, c;
struct hashstr_data *ptr, *fnd;
buf[0] = '\0';
len = strlen( str );
psize = sizeof( struct hashstr_data );
hash = len % STR_HASH_SIZE;
for( fnd = NULL, ptr = string_hash[hash], c = 0; ptr; ptr = ptr->next, c++ )
if( len == ptr->length && !strcmp( str, ( char * )ptr + psize ) )
{
fnd = ptr;
p = c + 1;
}
if( fnd )
sprintf( buf, "Hash info on string: %s\r\nLinks: %d Position: %d/%d Hash: %d Length: %d\r\n",
str, fnd->links, p, c, hash, fnd->length );
else
sprintf( buf, "%s not found.\r\n", str );
return buf;
}
char *hash_stats( void )
{
static char buf[1024];
struct hashstr_data *ptr;
int x, c, total, totlinks, unique, bytesused, wouldhave, hilink;
totlinks = unique = total = bytesused = wouldhave = hilink = 0;
for( x = 0; x < STR_HASH_SIZE; x++ )
{
for( c = 0, ptr = string_hash[x]; ptr; ptr = ptr->next, c++ )
{
total++;
if( ptr->links == 1 )
unique++;
if( ptr->links > hilink )
hilink = ptr->links;
totlinks += ptr->links;
bytesused += ( ptr->length + 1 + sizeof( struct hashstr_data ) );
wouldhave += ( ( ptr->links * sizeof(struct hashstr_data) ) + ( ptr->links * ( ptr->length + 1 ) ) );
}
}
sprintf( buf,
"Hash strings allocated:%8d Total links : %d\r\nString bytes allocated:%8d Bytes saved : %d\r\nUnique (wasted) links :%8d Hi-Link count: %d\r\n",
total, totlinks, bytesused, wouldhave - bytesused, unique, hilink );
return buf;
}
void show_high_hash( int top )
{
struct hashstr_data *ptr;
int x, psize;
char *str;
psize = sizeof( struct hashstr_data );
for( x = 0; x < STR_HASH_SIZE; x++ )
for( ptr = string_hash[x]; ptr; ptr = ptr->next )
if( ptr->links >= top )
{
str = ( char * )( ( ( long )ptr ) + psize );
fprintf( stderr, "Links: %5d String: >%s<\r\n", ptr->links, str );
}
}