/****************************************************************************
 * [S]imulated [M]edieval [A]dventure multi[U]ser [G]ame      |				*
 * -----------------------------------------------------------|   \\._.//	*
 * SmaugWiz (C) 1998 by Russ Pillsbury (Windows NT version)   |   (0...0)	*
 * -----------------------------------------------------------|    ).:.(	*
 * SMAUG (C) 1994, 1995, 1996 by Derek Snider                 |    {o o}	*
 * -----------------------------------------------------------|   / ' ' \	*
 * SMAUG code team: Thoric, Altrag, Blodkai, Narn, Haus,      |~'~.VxvxV.~'~*
 * Scryn, Swordbearer, Rennard, Tricops, and Gorog.           |				*
 * ------------------------------------------------------------------------ *
 * Merc 2.1 Diku Mud improvments copyright (C) 1992, 1993 by Michael        *
 * Chastain, Michael Quan, and Mitchell Tse.                                *
 * Original Diku Mud copyright (C) 1990, 1991 by Sebastian Hammer,          *
 * Michael Seifert, Hans Henrik Staerfeldt, Tom Madsen, and Katja Nyboe.    *
 ****************************************************************************/

/****************************************************************************
 * 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 delete 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	"stdafx.h"
#include	"smaug.h"
#include	"log.h"
#include	"SmaugWizDoc.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 */
};

int			str_free (char *str);
void		show_hash (int count);
char *		hash_stats ();

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 (const char *str)
{
	int		len = strlen (str);
	int		psize = sizeof (hashstr_data);
	int		hash = len % STR_HASH_SIZE;

	hashstr_data	*hd = string_hash [hash];
	while (hd) {
		if (len == hd->length && ! strcmp (str, (char*) hd + psize)) {
			if (hd->links < 65535)
				++hd->links;
			return (char*) hd + psize;
		}
		hd = hd->next;
	}
		
	char	*ptr = (char*) malloc (len + psize + 1);
	hd = (hashstr_data*) ptr;
	ptr += psize;

	strcpy (ptr, len ? str : "");

	hd->links = 1;
	hd->length = len;
	hd->next = string_hash [hash];
	string_hash [hash] = hd;

	return ptr;
}


// 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 (const char *str)
{
	register hashstr_data	*ptr;

	ptr = (hashstr_data*) (str - sizeof (hashstr_data));

	if (ptr->links == 0) {
		gpDoc->m_pLog->Printf (LOG_ALWAYS, "quick_link: bad pointer\n");
		return NULL;
	}
	if (ptr->links < 65535)
		++ptr->links;

	return NCCP str;
}


void StrFree (char *str, const char* file, int line)
{
	if (str)
		if (str_free (str) == -1)
			gpDoc->m_pLog->Printf (LOG_ALL,
				"STRFREEing bad pointer in %s, line %d\n", file, line);
}


// 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) {
		gpDoc->m_pLog->Printf (LOG_ALL, "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;
			}
		}
		gpDoc->m_pLog->Printf (LOG_ALWAYS,
			"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++);
		gpDoc->m_pLog->Printf (LOG_ALWAYS, " %d", c);
	}
	gpDoc->m_pLog->Printf (LOG_ALWAYS, "\n");
}


void hash_dump (int hash)
{
	struct	hashstr_data *ptr;
	char	*str;
	int		c, psize;

	if (hash > STR_HASH_SIZE || hash < 0) {
		gpDoc->m_pLog->Printf (LOG_ALWAYS, "hash_dump: invalid hash size\n\r");
		return;
	}

	psize = sizeof (struct hashstr_data);
	for (c=0, ptr = string_hash [hash]; ptr; ptr = ptr->next, c++) {
		str = (char *) (( (int) ptr) + psize);
		gpDoc->m_pLog->Printf (LOG_ALWAYS, "Len:%4d Lnks:%5d Str: %s\n\r",
			ptr->length, ptr->links, str);
	}
	gpDoc->m_pLog->Printf (LOG_ALWAYS,
		"Total strings in hash %d: %d\n\r", hash, c);
}


char *check_hash (char *str)
{
   static char buf[1024];
   int len, hash, psize, p, 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\n\rLinks: %d  Position: %d/%d  Hash: %d  Length: %d\n\r",
	  str, fnd->links, p, c, hash, fnd->length);
   else
     sprintf (buf, "%s not found.\n\r", 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 * (ptr->length + 1));
	}
    }
    sprintf (buf, "Hash strings allocated:%8d  Total links  : %d\n\rString bytes allocated:%8d  Bytes saved  : %d\n\rUnique (wasted) links :%8d  Hi-Link count: %d\n\r",
	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 *) (( (int) ptr) + psize);
				gpDoc->m_pLog->Printf (LOG_ALWAYS,
					"Links: %5d  String: >%s<\n\r", ptr->links, str);
			}
}


void DeleteAllHash ()
{
	hashstr_data	*pNext, *pStr;

	for (int hash=0; hash < STR_HASH_SIZE; ++hash) {
		pStr = string_hash [hash];
		while (pStr) {
			pNext = pStr->next;
			free (pStr);
			pStr = pNext;
		}
		string_hash [hash] = NULL;
	}
}