/******************************************************************************
* 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> *
******************************************************************************/
/* Shared string manager to replace the Merc read only system.
* Uses usage counts and 'first-fit' algorithm.
* See p84-85 of "Modern Operating Systems", Andrew S. Tanenbaum
*/
#include <time.h>
#include <string.h>
#include <stdio.h>
#include <malloc.h>
#include <ctype.h>
#include "merc.h"
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 */
};
/* 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;
/* These are the replacement functions,
* comment them out in db.c
*/
char *str_dup ( const char * );
void free_string ( char * );
char *fread_string ( FILE * );
/*
* buf_head points to start of shared space,
* buf_free points to next free block
*/
BufEntry *buf_head, *buf_free;
/* Increase MAX_STRING as needed, ie. when you start to
* get bug logs about string space being full.
*/
int MAX_STRING = 2100000;
int HEADER_SIZE;
int AllocMode; /* If string space is filled this is toggled */
void init_string_space()
{
string_space = (char *)malloc( MAX_STRING );
if( !string_space )
{
bug( "Cant allocate shared string space.", 0 );
exit(0);
}
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 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;
}
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( "defrag_heap() : made %d block merges. Good.", merges );
else
bug( "defrag_heap() : resulted in 0 merges.", 0 );
return merges;
}
/*
* This is meant to be a bulletproof string allocation function
* but theres gotta be a bug or two in there.
* Fusion
*/
char *str_dup( const char *str )
{
BufEntry *ptr;
int len;
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;
}
len = strlen( str ) + 1;
/*
* Round up to word boundary if not already.
* Don't remove this, because when the BufEntry struct is overlaid
* the integers must be aligned on word boundarys.
*/
if( len & 3 )
len += 4-(len&3);
if( !AllocMode )
{
if( !buf_free )
{
bug( "string_space is full! Starting allocation mode.", 0 );
AllocMode = 1;
return strdup( str );
}
else
{
RETRY:
for( ptr=buf_free; ptr; ptr=ptr->next )
if( ptr->usage <= 0 && ptr->size >= len )
break;
if( !ptr )
{
int merges;
bug( "string_space has become too fragmented!", 0 );
bug( "Attemping to optimize heap.", 0 );
merges = defrag_heap();
if( merges )
{
/* goto is fine because defrag will return 0 next time */
bug( "str_dup() : retrying allocation.", 0 );
goto RETRY;
}
else
{
bug( "str_dup() : switching to Alloc mode.", 0 );
AllocMode = 1;
return strdup( str );
}
}
/* If there is at least header size break it up so
* it will be available for merging
*/
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;
}
else
return strdup( str );
}
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;
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;
AllocMode = 0;
}
else
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';
return str_dup( buf );
}
}
}