/******************************************************************************
 *  SSM v2.2 (shared string manager)                                          *
 *                                                                            *
 *  Copyright(C) 1996 Melvin Smith (Fusion) for EnvyMUD 2.2                   *
 *                                                                            *
 *  Due to alignment differences on 32 bit and 64 bit machines, memory        *
 *  usage is now virtually identical to standard Merc on 32-bit               *
 *  architecture, but slightly larger on 64-bit. Memory usage is still        *
 *  smaller than SSM 2.0 or earlier. The manager now uses short ints for      *
 *  the count and size of chunks, so to increase MAX_STRING you must          *
 *  increase MAX_CHUNKS instead. String have a max reference count of         *
 *  +32766 and max size of CHUNK_SIZE (0xfff0). Fragmentation is also         *
 *  handled more efficiently by marking failed chunks with -1 to temporarily  *
 *  disable them until a defrag_heap() recycles them. This helps when a       *
 *  4 byte chunk is freed low in the heap, so string_dup() doesn't walk       *
 *  the whole heap every time.                                                *
 *                                                                            *
 *  <msmith@falcon.mercer.peachnet.edu>                                       *
 *                                                                            *
 *  ROM2.4 modifications by Tom Adriaenssen (Jan 1996) -- Wreck               *
 *                                                                            *
 *  <tadriaen@zorro.ruca.ua.ac.be>                                            *
 *                                                                            *
 *  Removed ROM 2.4 modifications as Envy doesnt need *fread_string_eol -Kahn *
 *                                                                            *
 *****************************************************************************/

#include <sys/types.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "merc.h"

#if !defined( ultrix )
#include <memory.h>
#endif

#define intType        short int
#define uintType       unsigned intType
#define intTypeSize  ( sizeof( intType ) )
#define addrType       void * 
#define addrTypeSize ( sizeof( addrType ) )
#define addrSizeMask ( sizeof( addrType ) - 1 )

#if !defined( macintosh )
extern  int     _filbuf         args( (FILE *) );
#endif

typedef struct BE BufEntry;

struct BE
{
    BufEntry *next;
    uintType  size;   /* size of the chunk (regardless of NULL CHAR) */ 
    intType   usage;  /* how many pointers to the string */ 
    char      buf[1]; /* chunk starts here */
};

/*
 * This is for the temporary hashing of strings at bootup to speedup
 * comparison/crunching of the string space. The temp_string_hash will
 * be freed after boot_done() is called.
 */
typedef struct TH TempHash;

struct TH
{
    TempHash *next;
    uintType  len;
    char     *str;
};

TempHash **temp_string_hash; 

/* These are the original Merc vars in db.c */
extern bool  fBootDb;
char         str_empty[1];
char        *string_space;
char        *top_string;
long         nAllocString;
long         sAllocString;
long         nOverFlowString;
long         sOverFlowString;

int          numFree;
bool         Full;

char         *str_dup        ( const char * );
void          free_string    ( char * );
char         *fread_string   ( FILE *, int * );
void          temp_hash_add  ( char * );
char         *temp_hash_find ( const char * );

/*
 * ssm_buf_head points to start of shared space,
 * ssm_buf_free points to next free block
 */ 
BufEntry *ssm_buf_head, *ssm_buf_free;

/* To allocate more memory increase MAX_CHUNKS in merc.h. */
#define CHUNK_SIZE   0xfff0                  /* DO NOT mess with this! */ 
long    MAX_STRING = MAX_CHUNKS * CHUNK_SIZE;
int     HEADER_SIZE;

/*
 * Not sure what is a good value for MAX_FREE 
 * If a dup fails str_dup will not defrag unless the number
 * of numFree >= MAX_FREE. numFree is NOT the current number of free blocks,
 * it is just a counter so defrag doesnt start dragging the game in the
 * case of a lot of failed dups.
 */
#define MAX_FREE     1000

void init_string_space()
{
    BufEntry *walk;
    int i;

    string_space = (char *)malloc( MAX_STRING );
    if( !string_space )
    {
        bug( "[SSM] Cant allocate shared string space.", 0 );
        exit(1);
    }

    top_string   = string_space + MAX_STRING-1;
    ssm_buf_head = (BufEntry *)string_space;
    HEADER_SIZE  = (int)( (char*)&ssm_buf_head->buf[0] - (char*)ssm_buf_head );

    walk = ssm_buf_head;
    for( i = 0; ;i++ )
    {
	walk->usage = 0;
	walk->size  = CHUNK_SIZE - HEADER_SIZE;
	if( i < MAX_CHUNKS - 1 )
	{
	    walk->next = (BufEntry *)( (char*)walk + CHUNK_SIZE );
	    walk       = walk->next;
	    continue;
	}

	walk->next = 0;
	break;
    }

    ssm_buf_free        = ssm_buf_head;
    temp_string_hash    = (TempHash **)calloc( sizeof(TempHash *),
					      MAX_KEY_HASH );
}

int defrag_heap()
{
    /*
     * Walk through the shared heap and merge adjacent free blocks.
     * Free blocks are merged in str_free if free->next is free but
     * if the block preceding free is free, it stays unmerged. I would
     * rather not have the heap as a DOUBLE linked list for 2 reasons...
     *  (1) Extra 4 bytes per struct uses more mem
     *  (2) Speed - don't want to bog down str_ functions with heap management
     * The "orphaned" blocks will eventually be either merged or reused.
     * The str_dup function will call defrag if it cant allocate a buf.
     */

    BufEntry *walk, *last_free, *next;
    int merges   = 0;
    ssm_buf_free = 0;

    for( walk=ssm_buf_head,last_free=0; walk; walk = next )
      {
	next = walk->next;
	if( walk->usage > 0 )
	{
	    /* this block is in use so set last_free to NULL */
	    last_free = 0;
	    continue;
	}
	else if( !last_free )
	{
	    /* OK found a NEW free block, set last_free and move to next */
	    last_free = walk;
	    if( !ssm_buf_free )
	        ssm_buf_free = walk; 

	    continue; 
	}
	else
	{
	    /* previous block free so merge walk into last_free and move on */
	    if( (long)last_free->size + (long)walk->size <= CHUNK_SIZE )
	    {
		merges++;
		last_free->size += walk->size + HEADER_SIZE;
		last_free->next  = walk->next;
		last_free->usage = 0;
	    }
	    else
	        last_free = walk;
	}
    }

    if( merges )
        bug( "[SSM] defrag_heap : made %d block merges.", merges );
    else
        bug( "[SSM] defrag_heap : resulted in 0 merges.", 0 ); 

    /* Start count over again */ 
    numFree = 0;
    return merges;
}


/*
 * Dup a string into shared space. If string exists, the usage count
 * gets incremented and the reference is returned. If the string does
 * not exist in heap, space is allocated and usage is 1.
 * This is a linked list first fit algorithm, so strings can be
 * freed. Upon bootup, there is a seperate hash table constructed in order
 * to do crunching, then the table is destroyed.
 */
char *str_dup( const char *str )
{
    BufEntry *ptr;
    char     *str_new;
    int       len;
    int       rlen;

    if( !str || !*str )
        return &str_empty[0];

    if( str > string_space && str < top_string )
    {
	ptr = (BufEntry *)( str - HEADER_SIZE );
	if( ptr->usage <= 0 )
	{
	    bug( "str_dup : invalid str", 0 );
	    bug( str, 0 );
	}

	ptr->usage++;
	return (char *)str;
    }

    rlen = len = (int)strlen( str ) + 1;

    /* 
     * Round up to machine dependant address size.
     * Don't remove this, because when the BufEntry struct is overlaid
     * the struct must be aligned correctly.
     */

    if( ( len + HEADER_SIZE ) & addrSizeMask ) 
        len += addrTypeSize - ( ( len + HEADER_SIZE ) & addrSizeMask );

    if( ssm_buf_free )
    { 
        RETRY:
	for( ptr = ssm_buf_free; ptr; ptr = ptr->next )
	    if( ptr->usage == 0 && ptr->size >= len )
	        break;

	if( !ptr )
	{
	    if( numFree >= MAX_FREE )
	    {
		int merges;

		bug( "[SSM] Attempting to optimize shared string heap.", 0 );
		merges = defrag_heap();

		/* goto is fine because defrag will return 0 next time */
		if( merges )
		    goto RETRY;
	    }	

	    str_new = (char *)malloc( rlen );
	    strcpy( str_new, str ); 
	    sOverFlowString += rlen;
	    nOverFlowString++;
	    return str_new;
	}

	/* If there is at least header size excess break it up */
	else if( ptr->size - len >= HEADER_SIZE ) 
	{
	    BufEntry *temp;

	    /* WARNING! - DONT REMOVE THE CASTS BELOW! - Fusion */
	    temp = (BufEntry*)( (char *)ptr + HEADER_SIZE + len );
	    temp->size   = ptr->size - ( len + HEADER_SIZE );
	    temp->next   = ptr->next;
	    temp->usage  = 0;
	    ptr->size    = len;
	    ptr->next    = temp;
	    ptr->usage   = 1;
	    ssm_buf_free = temp;
	}
	else
	{
	    ptr->usage = 1;
	    if( ptr != ssm_buf_free )
	        ssm_buf_free->usage--; /* buf_free was skipped */

	    for( ssm_buf_free = ssm_buf_head; ssm_buf_free;
		ssm_buf_free = ssm_buf_free->next )
	        if( ssm_buf_free->usage == 0 )
		    break;
	}

	str_new = (char *)&ptr->buf[0];
	strcpy( str_new, str ); 
	nAllocString++;
	sAllocString += ptr->size + HEADER_SIZE;
    }
    else  
    {
	/* A one time toggle just for bugging purposes */
	if( !Full )
	{
	    bug( "[SSM] The shared string heap is full!", 0 );
	    Full = 1;
	}

	str_new = (char *)malloc( rlen );
	strcpy( str_new, str ); 
	sOverFlowString += rlen;
	nOverFlowString++;
    } 

    return str_new;
}

/*
 * If string is in shared space, decrement usage, if usage then is 0,
 * free the chunk and attempt to merge with next node. Other
 * strings are freed with standard free.
 * Never call free/delete externally on a shared string.
 */
void free_string( char *str )
{
    BufEntry *ptr;

    if( !str || str == &str_empty[0] )
        return;

    if( str > string_space && str < top_string )
    {
	ptr = (BufEntry *)( str - HEADER_SIZE );

	if( --ptr->usage > 0 )
	    return;
	else if( ptr->usage < 0 )
	{
	    bug( "SSM:free_string: multiple free or invalid string.", 0 );
	    bug( (char*)&ptr->buf[0], 0 );
	    return;
	}

	numFree++;
	sAllocString -= ( ptr->size + HEADER_SIZE );
	nAllocString--;

	if( ssm_buf_free > ptr )
	    ssm_buf_free = ptr;

	if( fBootDb )
	{
	    TempHash *ptr;
	    TempHash *walk;
	    int ihash = strlen( str ) % MAX_KEY_HASH;

	    for( ptr = temp_string_hash[ ihash ]; ptr; ptr = ptr->next )
	    {
		if( ptr->str != str )
		    continue;
		else if( ptr == temp_string_hash[ ihash ] )
		    temp_string_hash[ ihash ] = ptr->next;
		else
		    for( walk = temp_string_hash[ ihash ]; walk;
			walk = walk->next )
		    {
			if( walk->next == ptr )
			{
			    walk->next = ptr->next;
			    break;
			}
		    }

		free( ptr );
		break; 
	    }
	}
	return;
    }

    sOverFlowString -= strlen( str ) + 1;
    nOverFlowString--;
    if ( sOverFlowString < 0 || nOverFlowString < 0 )
    {
	bug( "SSM:free_string: string free from outside SS space.", 0 );
	bug( str, 0 );
    }
    free( str );
}


/*
 * Read and allocate space for a string from a file.
 * This replaces db.c fread_string
 * This is modified version of Furey's fread_string from Merc
 */
char *fread_string( FILE *fp, int *status )
{
    char buf[ MAX_STRING_LENGTH*4 ];
    char *ptr = buf;
    char  c;

    *status = 0;

    do { c = getc( fp ); }
    while( isspace( c ) );

    if( ( *ptr++ = c ) == '~' )
        return &str_empty[0];

    for ( ;; )
    {
	switch ( *ptr = getc( fp ) )
	{
	    default:
	        ptr++;
		break;

	    case EOF:
		bug( "Fread_string: EOF", 0 );
		*status = 1;
		return NULL;
		break;

	    case '\n':
		ptr++;
		*ptr++ = '\r';
		break;

	    case '\r':
		break;

	    case '~':
		*ptr = '\0';
		if( fBootDb )
		{ 
		    ptr = temp_hash_find( buf ); 
		    if( ptr )
		        return str_dup( ptr ); 
		    
		    ptr = str_dup( buf );
		    temp_hash_add( ptr );
		    return ptr;
		}

		return str_dup( buf );
	}
    }
}


/*
 * Read string into user supplied buffer.
 * Modified version of Furey's fread_string
 */
void temp_fread_string( FILE *fp, char *buf )
{
    char *ptr = buf;
    char  c;

    do { c = getc( fp ); }
    while ( isspace( c ) );

    if ( ( *ptr++ = c ) == '~' )
    {   
	*buf = '\0';
	return;
    }

    for ( ;; )
    {
	switch ( *ptr = getc( fp ) )
	{
	    default:
	        ptr++;
		break;

	    case EOF:
		bug( "Fread_string: EOF", 0 );
		exit( 1 );
		break;

	    case '\n':
		ptr++;
		*ptr++ = '\r';
		break;

	    case '\r':
		break;

	    case '~':
		*ptr = '\0';
		return;
	}
    }
}


/* Lookup the string in the boot-time hash table. */
char *temp_hash_find( const char *str )
{
    TempHash *ptr;
    int       len;
    int       ihash;

    if( !fBootDb || !*str )
        return 0;

    len   = strlen( str );
    ihash = len % MAX_KEY_HASH;

    for( ptr = temp_string_hash[ ihash ]; ptr; ptr = ptr->next )
    {
	if( *ptr->str != *str )
	    continue;
	else if( strcmp( ptr->str, str ) )
	    continue;
	else return ptr->str;
    }

    return 0;
}


/*
 * Add a reference in the temporary hash table.
 * String is still in the linked list structure but
 * reference is kept here for quick lookup at boot time;
 */
void temp_hash_add( char *str )
{
    TempHash *add;
    int      len;
    int      ihash;

    if( !fBootDb || !*str || ( str <= string_space && str >= top_string ) )
        return;

    len   = strlen( str );
    ihash = len % MAX_KEY_HASH;
    add   = (TempHash *)malloc( sizeof( TempHash ) );
    add->next = temp_string_hash[ ihash ];
    temp_string_hash[ ihash ] = add;
    add->len = len;
    add->str = str;
}


/* Free the temp boot string hash table */
void boot_done( void )
{
    TempHash *ptr, *next;
    int       ihash;

    for( ihash = 0; ihash < MAX_KEY_HASH; ihash++ )
    {
	for( ptr = temp_string_hash[ ihash ]; ptr; ptr = next )
	{
	    next = ptr->next;
	    free( ptr );
	}
    }

    free( temp_string_hash );
    temp_string_hash = 0; /* Bug check in case someone accesses later */
}