/******************************************************************************
 *  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 * );
void temp_hash_add( char *, const int );
char *temp_hash_find( const char * );
static unsigned long get_string_hash( register const char *key );

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

/* 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 * ) calloc( 1, MAX_STRING );
    if ( !string_space )
    {
#if defined(cbuilder)
        logf_string( "[SSM] Cant allocate shared string space." );
        return -1;
#else
        bug( "[SSM] Cant allocate shared string space.", 0 );
        exit( 1 );
#endif
    }

    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 = NULL;
        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 = NULL, *last_free = NULL, *next = NULL;
    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.
 *
 * You must now pass a pointer to the string pointer you're wanting to free.  This
 * way free_string can set that pointer to NULL and not rely on the caller to 
 * set the pointer to null after call free_string.  This method makes it so
 * no-one can free the same string twice (which was causing major string-space
 * corruption). -Zane
 *
 */
void free_string( char **strptr )
{
    char *str;
    BufEntry *ptr;

    str = *strptr;

    if ( !str )
        return;

    if ( str == &str_empty[0] )
    {
        *strptr = NULL;
        return;
    }

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

        if ( --ptr->usage > 0 )
        {
            *strptr = NULL;
            return;
        }
        else if ( ptr->usage < 0 )
        {
            /* Undo the change we made above, avoid memory corruption if possible. */
            ptr->usage++;
            bug( "SSM:free_string: multiple free or invalid string.", 0 );
            bug( str, 0 );
            *strptr = NULL;
            return;
        }

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

        if ( ssm_buf_free > ptr )
            ssm_buf_free = ptr;

        if ( fBootDb )
        {
            TempHash *ptr;
            TempHash *walk;
            unsigned long ihash = get_string_hash( str );

            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;
            }
        }
        *strptr = NULL;
        return;
    }

    sOverFlowString -= strlen( str ) + 1;
    nOverFlowString--;

    if ( sOverFlowString < 0 || nOverFlowString < 0 )
        bug( "SSM:free_string: string free from outside SS space.", 0 );

    free( str );
    *strptr = NULL;
    return;
}

/*
 * 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 )
{
    char buf[MAX_STRING_LENGTH * 4];
    register char *ptr = buf;
    register char c;
    int len;

/*    *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++ = '\r';
            *ptr++ = '\n';
            break;

        case '\r':
            break;

        case '~':
            *ptr = '\0';
            if ( fBootDb )
            {
                len = ptr - buf;

                ptr = temp_hash_find( buf );
                if ( ptr )
                    return str_dup( ptr );

                ptr = str_dup( buf );
                temp_hash_add( ptr, len );
                return ptr;
            }

            return str_dup( buf );
        }
    }
}

char *fread_string_eol( FILE * fp )
{
    signed char buf[MAX_STRING_LENGTH * 4];
    register signed char *ptr = buf;
    register signed char c;
    int len;

    /*
     * Skip blanks.
     * Read first char.
     */
    do
        c = getc( fp );
    while ( c == ' ' || c == '\t' );

    *ptr = c;

    while ( *ptr != '\n' && *ptr != '\r' && *ptr != EOF )
        *++ptr = getc( fp );

    if ( ptr == buf )
        return &str_empty[0];

    *ptr = '\0';

    if ( fBootDb )
    {
        len = ptr - buf;

        ptr = temp_hash_find( buf );
        if ( ptr )
            return str_dup( ptr );

        ptr = str_dup( buf );
        temp_hash_add( ptr, len );
        return ptr;
    }

    return str_dup( buf );
}

/*
 * Read string into user supplied buffer.
 * Modified version of fread_string_eol
 */
int temp_fread_string_eol( FILE * fp, char *outbuf )
{
    register signed char *ptr = outbuf;
    register signed char c;
    bool bEOF = FALSE;

    /*
     * Skip blanks.
     * Read first char.
     */
    do
        c = getc( fp );
    while ( c == ' ' || c == '\t' );

    *ptr = c;

    while ( *ptr != '\n' && *ptr != '\r' && *ptr != EOF )
        *++ptr = getc( fp );

    if ( *ptr == EOF )
        bEOF = TRUE;

    *ptr = '\0';

    return bEOF;
}

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

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

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

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

        case EOF:
#if defined(cbuilder)
            logf_string( "Fread_string: EOF" );
            return -1;
#else
            bug( "Fread_string: EOF", 0 );
            exit( 1 );
#endif
            break;

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

        case '\r':
            break;

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

/*--- ElfHash ---------------------------------------------------
 *  The published hash algorithm used in the UNIX ELF format
 *  for object files. Accepts a pointer to a string to be hashed
 *  and returns an unsigned long.
 *-------------------------------------------------------------*/

static unsigned long get_string_hash( register const char *key )
{
    register unsigned long hash = 0, g;

    while ( *key )
    {
        hash = ( hash << 4 ) + *key++;
        if ( ( g = hash & 0xF0000000 ) )
            hash ^= g >> 24;
        hash &= ~g;
    }

    return hash % MAX_KEY_HASH;
}

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

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

    ihash = get_string_hash( str );

    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, const int len )
{
    TempHash *add;
    unsigned long ihash;

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

    ihash = get_string_hash( str );

    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 */
}