/*~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
 ~  Original Diku Mud copyright (C) 1990, 1991 by Sebastian Hammer,        ~
 ~  Michael Seifert, Hans Henrik St{rfeldt, Tom Madsen, and Katja Nyboe.   ~
 ~                                                                         ~
 ~  Merc Diku Mud improvments copyright (C) 1992, 1993 by Michael          ~
 ~  Chastain, Michael Quan, and Mitchell Tse.                              ~
 ~                                                                         ~
 ~  Ack 2.2 improvements copyright (C) 1994 by Stephen Dooley              ~
 ~  ACK!MUD is modified Merc2.0/2.1/2.2 code (c)Stephen Zepp 1998 Ver: 4.3 ~
 ~                                                                         ~
 ~  In order to use any part of this  PA  Diku Mud, you must comply with   ~
 ~  both the original Diku license in 'license.doc' as well the Merc       ~
 ~  license in 'license.txt', and the Ack!Mud license in 'ack_license.txt'.~
 ~  In particular, you may not remove any of these copyright notices.      ~
 ~                                                                         ~
 ~           _______      _____                                            ~
 ~          /  __  /\    / ___ \       222222        PA_MUD by Amnon Kruvi ~
 ~         /______/ /   / /___\ \            2       PA_MUD is modified    ~
 ~        / _______/   / _______ \           2       Ack!Mud, v4.3         ~
 ~       /_/          /_/       \_\        2                               ~
 ~                                      2                                  ~
 ~                                     2222222                             ~
 ~                                                                         ~
 ~                                                                         ~
 ~   Years of work have been invested to create DIKU, Merc, Ack and PA.    ~
 ~   Please show your respect by following the licenses, and issuing       ~
 ~   credits where due.                                                    ~
 ~                                                                         ~
 ~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-*/
 
/******************************************************************************
 *  SSM v2.1.9 (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 "ack.h"
#include <signal.h>
#if !defined( ultrix )
#include <memory.h>
#endif

#include "ssm.h"

TempHash **temp_string_hash;

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

static unsigned get_string_hash args( ( register const char *, int ) );

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

long MAX_STRING = (MAX_CHUNKS * CHUNK_SIZE);
int HEADER_SIZE;
long tot = 0;

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

  string_space = (char *) malloc(MAX_STRING);
  if (!string_space)
  {
    bugf("SSM: Can't allocate %ld bytes shared string space.", MAX_STRING);
    raise(SIGSEGV);
  }

  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)
    log_f("SSM: defrag_heap: made %d block merges.", merges);
  else
    log_f("SSM: defrag_heap: resulted in 0 merges.");

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

/* for alarm_update crosschecking */
int ssm_dup_count;
int ssm_loops;
int ssm_recent_loops;

char *_str_dup(const char *str, const char *caller)
{
  BufEntry *ptr;
  int len;
  int rlen;
  char *str_new;

  ssm_dup_count++;
  ssm_recent_loops=0;

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

  if (str > string_space && str < top_string)
  {
    ptr = (BufEntry *) (str - HEADER_SIZE);
    if (ptr->usage <= 0)
    {
      bugf("str_dup: invalid string from %s: %20.20s",
	   caller, str);
      ptr->usage=0; /* make it valid again */
    }

    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);

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

  if (ptr)
    ptr->usage = 1;
  
  if (!ptr)
  {
    if (numFree > 1)
      numFree++;

    if (numFree >= MAX_FREE)
    {
      int merges;
      log_f("SSM: Attempting to optimize shared string heap.");
      merges = defrag_heap();
      
      /* goto is fine because defrag will return 0 next time */
      if (merges)
	goto RETRY;
    }
    
    /* A one time toggle just for bugging purposes */
    if (!Full)
    {
      bugf("SSM: The shared string heap is full!");
      Full = 1;
    }

    str_new = (char *) malloc(rlen);
    strcpy(str_new, str);
    sOverFlowString += rlen;
    nOverFlowString++;
    if (sOverFlowString > hwOverFlow)
      hwOverFlow=sOverFlowString;
    return str_new;
  }
  /* If there is at least header size excess break it up */
  else if (ptr->size - len >= (HEADER_SIZE+8))
  {
    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;
    
    ssm_buf_free = temp;
  }
  else
  {
    if (ptr != ssm_buf_free)
      ssm_buf_free->usage--;	/* buf_free was skipped */
    
    /* spec: don't start from the start of the heap again! */
    for ( ; ssm_buf_free; ssm_buf_free = ssm_buf_free->next)
    {
      ssm_loops++;
      ssm_recent_loops++;
      if (ssm_buf_free->usage == 0)
	break;
    }
  }
  
  str_new = (char *) &ptr->buf[0];
  strcpy(str_new, str);
  ptr->caller=caller;
  nAllocString++;
  sAllocString += ptr->size + 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/delete externally on a shared string.
 */
void _free_string(char *str, const char *caller)
{
  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)
    {
      bugf("SSM: free_string: multiple free/invalid from %s: %20.20s",
	   caller, (char *)&ptr->buf[0]);
      return;
    }

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

    if (!ssm_buf_free || ssm_buf_free > ptr)
      ssm_buf_free = ptr;

    if (fBootDb)
    {
      TempHash *ptr;
      TempHash *walk;
      int ihash = get_string_hash( str, strlen( 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;
      }
    }
    return;
  }

  sOverFlowString -= strlen(str) + 1;
  nOverFlowString--;
  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, const char *caller)
{
  char buf[MAX_STRING_LENGTH * 4];
  char *ptr = buf;
  char c;

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

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

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

    case EOF:
      bugf("Fread_string: EOF");
      raise(SIGSEGV);
      break;

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

    case '\r':
      break;

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

	ptr = temp_hash_find(buf, len);
	if (ptr)
	  return _str_dup(ptr, caller);

	ptr = _str_dup(buf, caller);
	temp_hash_add(ptr, len);
	return ptr;
      }

      ptr=_str_dup(buf, caller);
      tail_chain();
      return ptr;
    }
  }
}


/* 
 * This is a modified version of fread_string:
 * It reads till a '\n' or a '\r' instead of a '~' (like fread_string).
 * ROM uses this function to read in the socials.
 * -- Wreck
 */
char *_fread_string_eol(FILE * fp, const char *caller)
{
  char buf[MAX_STRING_LENGTH * 4];
  char *ptr = buf;
  char c;

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

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

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

    case EOF:
      bugf("Fread_string: EOF");
      raise(SIGSEGV);
      break;

    case '\n':
    case '\r':
      *ptr = '\0';
      if (fBootDb)
      {
	int len = ptr - buf;
	
	ptr = temp_hash_find(buf, len);
	if (ptr)
	  return _str_dup(ptr, caller);

	ptr = _str_dup(buf, caller);
	temp_hash_add(ptr, len);
	return ptr;
      }

      return _str_dup(buf, caller);
    }
  }
}

/*
 * 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:
      bugf("Fread_string: EOF");
      raise(SIGSEGV);
      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, int len)
{
  TempHash *ptr;
  int ihash;

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

  ihash = get_string_hash( str, len );

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

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

  ihash = get_string_hash( str, len );

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

static unsigned get_string_hash( register const char *key, int len )
{
    register int      i		= UMIN( len, 32 );
    register unsigned hash	= 0;

    while( i-- )
	hash = hash * 33U + *key++;

    return hash % MAX_KEY_HASH;
}