/******************************************************************************
* ssm.c (shared string manager) *
* *
* Copyright(C) 1995 Melvin Smith - Mercer University, Macon GA. *
* *
* This code was scrapped from MUD++ in favor of a String class *
* I converted it over to drop into Merc/Envy code by request of *
* Jason Dinkel to go with OLC. *
* --Fusion *
* <msmith@falcon.mercer.peachnet.edu> *
******************************************************************************/
#if defined( macintosh )
#include <types.h>
#else
#include <sys/types.h>
#endif
#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
typedef struct B BufEntry;
struct B
{
BufEntry *next;
int size; /* size of the chunk (regardless of NULL_CHAR) */
short int usage; /* keeps track of 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 Hash table will
* be freed after boot_done() is called.
*/
typedef struct T TempHash;
struct T
{
TempHash *next;
int len;
char *str;
};
TempHash **temp_string_hash;
/* These are the original Merc vars in db.c */
extern char str_empty[];
extern char *string_space;
extern char *top_string;
extern int nAllocString;
extern int sAllocString;
extern bool fBootDb;
int numFree;
int Full;
/* These are the replacement functions,
* comment them out in db.c
*/
char *str_dup ( const char * );
void free_string ( char * );
char *fread_string ( FILE * );
char *fread_word_dup ( FILE * ); /* Implement later to check words also */
void temp_hash_add ( char * );
char *temp_hash_find ( const char * );
/*
* buf_head points to start of shared space,
* buf_free points to next free block
*/
BufEntry *buf_head, *buf_free;
int MAX_STRING = 1400000;
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 ton of failed dups
* --Fusion
*/
#define MAX_FREE 100
void init_string_space()
{
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;
buf_head = (BufEntry *)string_space;
/*
* Would be nice to use sizeof()-1 here but word alignment
* adds some nice padding that puts it off. The REAL size of
* the struct is probably 16 bytes, 8 words but since we are overlaying
* the struct on the character space we need the exact offset.
* No less portable as far as I can see. --Fusion
*/
HEADER_SIZE = (int)((char*)buf_head->buf-(char*)buf_head);
buf_head->usage = 0;
buf_head->size = MAX_STRING - HEADER_SIZE;
buf_head->next = NULL;
buf_free = 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;
buf_free = NULL;
for( walk=buf_head,last_free=NULL;walk;walk = next )
{
next = walk->next;
if( walk->usage > 0 )
{
/* this block is in use so set last_free to NULL */
last_free = NULL;
continue;
}
else if( !last_free )
{
/* OK found a NEW free block, set last_free and move to next */
last_free = walk;
if( walk > buf_free )
buf_free = walk;
continue;
}
else
{
/* previous block is free so merge walk into last_free and move on */
merges++;
last_free->size += walk->size + HEADER_SIZE;
last_free->next = walk->next;
}
}
if( merges )
bug( "[SSM] defrag_heap() : made %d block merges. Good.", 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;
int len;
int rlen;
char *str_new;
if( !str || !*str || str == &str_empty[0] )
return &str_empty[0];
if( str > string_space && str < top_string )
{
ptr = (BufEntry *)(str - HEADER_SIZE);
ptr->usage++;
return (char *)str;
}
rlen = len = strlen( str ) + 1;
/*
* Round up to word boundary if not already.
* Don't remove this, because when the BufEntry struct is overlaid
* the struct must be aligned on word boundarys.
*/
if( len & 3 )
len += 4-(len&3);
if( !buf_free )
{
/* 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 );
return str_new;
}
else
{
RETRY:
for( ptr = 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();
if( merges )
/* goto is fine because defrag will return 0 next time */
goto RETRY;
}
str_new = (char *) malloc( rlen );
strcpy( str_new, str );
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;
if( ptr == buf_free )
buf_free = temp;
}
ptr->usage = 1;
str_new = ptr->buf;
if( ptr == buf_free )
for( buf_free = buf_head; buf_free; buf_free = buf_free->next )
if( buf_free->usage <= 0 )
break;
strcpy( str_new, str );
nAllocString++;
sAllocString += len + HEADER_SIZE;
}
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() 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;
numFree++;
sAllocString -= (ptr->size + HEADER_SIZE);
nAllocString--;
if( ptr->next && ptr->next->usage <= 0 )
{
ptr->size += ptr->next->size + HEADER_SIZE;
ptr->next = ptr->next->next;
}
if( buf_free > ptr )
buf_free = ptr;
return;
}
free( str );
}
/*
* Read and allocate space for a string from a file.
* This replaces db.c fread_string
*/
char *fread_string( FILE *fp )
{
char buf[ MAX_STRING_LENGTH*2 ];
char *ptr = buf;
char c;
/*
* Skip blanks.
* Read first char.
*/
do
{
c = getc( fp );
}
while ( isspace( c ) );
if ( ( *ptr++ = c ) == '~' )
return &str_empty[0];
for ( ;; )
{
/*
* Back off the char type lookup,
* it was too dirty for portability.
* -- Furey
*/
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';
if( fBootDb ) /* PATCHED */
{
ptr = temp_hash_find( buf );
if( ptr )
return str_dup( ptr );
ptr = str_dup( buf );
temp_hash_add( ptr );
return ptr;
} /* END PATCH */
return str_dup( buf );
}
}
}
/* 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 NULL;
len = strlen( str );
ihash = len % MAX_KEY_HASH;
for( ptr = temp_string_hash[ ihash ]; ptr; ptr = ptr->next )
{
if( ptr->len != len )
continue;
else if( *ptr->str != *str )
continue;
else if( strcmp( ptr->str, str ) )
continue;
else return ptr->str;
}
return NULL;
}
/*
* 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 )
{
int len;
int ihash;
TempHash *add;
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 );
}
}
}