#include "config.h"
#include "sl-feat.h"

#include "slang.h"
#include "_slang.h"

typedef struct _SLstring_Type
{
   unsigned int ref_count;
#define IS_STATIC_STRING(x) ((x)->ref_count == (unsigned int)-1)
   struct _SLstring_Type *next;
   union
     {
	char bytes [1];
	char *static_bytes;
     }
   buf;
}
SLstring_Type;

#define SLSTRING_POINTER(x) (IS_STATIC_STRING(x) ? (x)->buf.static_bytes : (x)->buf.bytes)

#define SLSTRING_STATS 0
#if SLSTRING_STATS
static unsigned long Virtual_Size;
static unsigned long Actual_Size;
static unsigned long Max_Virtual_Size;
static unsigned long Max_Actual_Size;
#endif

static SLstring_Type *String_Hash_Table [SLSTRING_HASH_TABLE_SIZE];
static char Single_Char_Strings [256 * 2];

#if _SLANG_OPTIMIZE_FOR_SPEED
static char *Cached_String;
static unsigned int Cached_String_Len;
static unsigned long Cached_String_Hash;
#endif

unsigned long _SLstring_hash (unsigned char *s, unsigned char *smax)
{
   register unsigned long h = 0;
   register unsigned long sum = 0;
   unsigned char *smax4;
   
   smax4 = smax - 4;
   
   while (s < smax4)
     {
	sum += *s++;
	h = sum + (h << 3);
	sum += *s++;
	h = sum + (h << 3);
	sum += *s++;
	h = sum + (h << 3);
	sum += *s++;
	h = sum + (h << 3);
     }
   
   while (s < smax)
     {
	sum += *s++;
	h = sum + (h << 3);
     }

   return h;
}

unsigned long _SLcompute_string_hash (char *s)
{
#if _SLANG_OPTIMIZE_FOR_SPEED   
   if (s == Cached_String)
     return Cached_String_Hash;
#endif
   return _SLstring_hash ((unsigned char *) s, (unsigned char *) s + strlen (s));
}

/* This routine works with any string */
static SLstring_Type *find_string (char *s, unsigned int len, unsigned long hash)
{
   SLstring_Type *sls;
   char ch;

   sls = String_Hash_Table [(unsigned int)(hash % SLSTRING_HASH_TABLE_SIZE)];

   if (sls == NULL)
     return NULL;

   ch = s[0];
   do
     {
	char *bytes = SLSTRING_POINTER(sls);

	if (((s == bytes)
	     || ((ch == *bytes) && (0 == strncmp (s, bytes, len))))
	    && (bytes [len] == 0))
	  break;

	sls = sls->next;
     }
   while (sls != NULL);

   return sls;
}

static SLstring_Type *find_slstring (char *s, unsigned long hash)
{
   SLstring_Type *sls;

   sls = String_Hash_Table [(unsigned int)(hash % SLSTRING_HASH_TABLE_SIZE)];
   while (sls != NULL)
     {
	if (s == SLSTRING_POINTER(sls))
	  return sls;

	sls = sls->next;
     }
   return sls;
}

static char *create_long_string (char *s, unsigned int len, unsigned long hash)
{
   unsigned int pad;
   SLstring_Type *sls;

   sls = find_string (s, len, hash);

   if (sls != NULL)
     {
#if SLSTRING_STATS
	Virtual_Size += len + 1;
	if (Virtual_Size > Max_Virtual_Size)
	  {
	     Max_Virtual_Size = Virtual_Size;
	     Max_Actual_Size = Actual_Size;
	  }
#endif

	if (0 == IS_STATIC_STRING(sls))
	  {
	     sls->ref_count++;
	     s = sls->buf.bytes;
	  }
	else s = sls->buf.static_bytes;

#if _SLANG_OPTIMIZE_FOR_SPEED	
	Cached_String = s;
	Cached_String_Len = len;
	Cached_String_Hash = hash;
#endif
	return s;
     }

#if SLSTRING_STATS
   Actual_Size += len + 1;
   Virtual_Size += len + 1;
   if (Virtual_Size > Max_Virtual_Size)
     {
	Max_Virtual_Size = Virtual_Size;
	Max_Actual_Size = Actual_Size;
     }
#endif

   /* Take advantage of structure padding, if any */
   sls = NULL;
   pad = (unsigned int) (((char *) sls + sizeof (SLstring_Type))
			 - (sls->buf.bytes + 1));

   sls = (SLstring_Type *) SLmalloc (len + (sizeof (SLstring_Type) - pad));
   if (sls == NULL)
     return NULL;

   strncpy (sls->buf.bytes, s, len);
   sls->buf.bytes[len] = 0;
   sls->ref_count = 1;

#if _SLANG_OPTIMIZE_FOR_SPEED
   Cached_String = sls->buf.bytes;
   Cached_String_Len = len;
   Cached_String_Hash = hash;
#endif

   hash = hash % SLSTRING_HASH_TABLE_SIZE;
   sls->next = String_Hash_Table [(unsigned int)hash];
   String_Hash_Table [(unsigned int)hash] = sls;

   return sls->buf.bytes;
}

static char *create_short_string (char *s, unsigned int len)
{
   char ch;

   /* Note: if len is 0, then it does not matter what *s is.  This is 
    * important for SLang_create_nslstring.
    */
   if (len) ch = *s; else ch = 0;
   
   len = 2 * (unsigned int) ((unsigned char) ch);
   Single_Char_Strings [len] = ch;
   Single_Char_Strings [len + 1] = 0;
#if SLSTRING_STATS
   Virtual_Size += 2;
#endif
   return Single_Char_Strings + len;
}

static char *create_nstring (char *s, unsigned int len, unsigned long *hash_ptr)
{
   unsigned long hash;

   if (s == NULL)
     return NULL;

   if (len < 2)
     return create_short_string (s, len);

   hash = _SLstring_hash ((unsigned char *) s, (unsigned char *) (s + len));
   *hash_ptr = hash;

   return create_long_string (s, len, hash);
}

char *SLang_create_nslstring (char *s, unsigned int len)
{
   unsigned long hash;
   return create_nstring (s, len, &hash);
}

char *_SLstring_make_hashed_string (char *s, unsigned int len, unsigned long *hashptr)
{
   unsigned long hash;

   if (s == NULL) return NULL;

   hash = _SLstring_hash ((unsigned char *) s, (unsigned char *) s + len);
   *hashptr = hash;

   if (len < 2)
     return create_short_string (s, len);

   return create_long_string (s, len, hash);
}

char *_SLstring_dup_hashed_string (char *s, unsigned long hash)
{
   unsigned int len;

   if (s == NULL) return NULL;

   len = strlen (s);
   if (len < 2) return create_short_string (s, len);

   return create_long_string (s, len, hash);
}

char *SLang_create_static_slstring (char *s)
{
   SLstring_Type *sls;
   unsigned long hash;
   unsigned int len;

   len = strlen (s);
   if (len < 2)
     return s;			       /* we have a better way in SLcreate_nstring */

   sls = (SLstring_Type *) SLmalloc (sizeof (SLstring_Type));
   if (sls == NULL)
     return NULL;

   sls->ref_count = (unsigned int)-1;
   sls->buf.static_bytes = s;

   hash = _SLstring_hash ((unsigned char *) s, (unsigned char *) (s + len));

#if _SLANG_OPTIMIZE_FOR_SPEED
   Cached_String = s;
   Cached_String_Hash = hash;
   Cached_String_Len = len;
#endif

   hash = hash % SLSTRING_HASH_TABLE_SIZE;
   sls->next = String_Hash_Table [(unsigned int)hash];
   String_Hash_Table [(unsigned int)hash] = sls;

#if SLSTRING_STATS
   Actual_Size += len + 1;
#endif

   return s;
}

static void free_string (char *s, unsigned int len, unsigned long hash)
{
   SLstring_Type *sls, *sls1, *prev;

   if (len < 2)
     {
#if SLSTRING_STATS
	Virtual_Size -= 2;
#endif
	return;			       /* Not malloced. */
     }

   if (NULL == (sls = find_slstring (s, hash)))
     {
	SLang_doerror ("Application internal error: invalid attempt to free string");
	return;
     }

#if SLSTRING_STATS
   if (len + 1 > Virtual_Size)
     SLang_doerror ("Application internal error");
   Virtual_Size -= len + 1;
#endif

   if (IS_STATIC_STRING(sls))
     return;

   sls->ref_count--;
   if (sls->ref_count != 0)
     return;

#if _SLANG_OPTIMIZE_FOR_SPEED
   if (s == Cached_String)
     Cached_String = NULL;	       /* pointer will nolonger be good */
#endif

   hash = hash % SLSTRING_HASH_TABLE_SIZE;

   sls1 = String_Hash_Table [(unsigned int) hash];

   prev = NULL;

   /* Since find_string found it, it will be found here too */
   while (sls1 != sls)
     {
	prev = sls1;
	sls1 = sls1->next;
     }

   if (prev != NULL)
     prev->next = sls->next;
   else
     String_Hash_Table [(unsigned int) hash] = sls->next;

   SLfree ((char *) sls);
#if SLSTRING_STATS
   Actual_Size -= len + 1;
#endif
}

/* This routine may be passed NULL-- it is not an error. */
void SLang_free_slstring (char *s)
{
   unsigned long hash;
   unsigned int len;

   if (s == NULL) return;

#if _SLANG_OPTIMIZE_FOR_SPEED
   if (s == Cached_String)
     {
	free_string (s, Cached_String_Len, Cached_String_Hash);
	return;
     }
#endif

   if ((len = strlen (s)) < 2)
     {
#if SLSTRING_STATS
	hash = 0;
#else
	return;
#endif
     }
   else
     hash = _SLstring_hash ((unsigned char *)s, (unsigned char *) s + len);

   free_string (s, len, hash);
}

char *SLang_create_slstring (char *s)
{
   unsigned long hash;

   if (s == NULL) return NULL;
   
#if _SLANG_OPTIMIZE_FOR_SPEED
   if (s == Cached_String)
     return create_long_string (s, Cached_String_Len, Cached_String_Hash);
#endif

   return create_nstring (s, strlen (s), &hash);
}


void _SLfree_hashed_string (char *s, unsigned int len, unsigned long hash)
{
   if (s == NULL) return;
   free_string (s, len, hash);
}

char *SLang_concat_slstrings (char *a, char *b)
{
   unsigned int lena, len;
   char *c, *sls;

   lena = strlen (a);
   len = lena + strlen (b);

   c = SLmalloc (len + 1);
   if (c == NULL)
     return NULL;

   strcpy (c, a);
   strcpy (c + lena, b);

   sls = SLang_create_slstring (c);
   SLfree (c);
   return sls;
}

#if SLSTRING_STATS
void SLstring_dump_stats (void)
{
   SLstring_Type *sls;
   unsigned int i;
   unsigned long bytes_malloced = 0;
   unsigned long virtual_bytes_malloced = 0;
   unsigned long num_items = 0;
   unsigned int pad;
   unsigned int num_cells;

   sls = NULL;
   pad = (unsigned int) (((char *) sls + sizeof (SLstring_Type))
			 - (sls->buf.bytes + 1));

   pad = sizeof (SLstring_Type) - pad;
   num_cells = 0;

   for (i = 0; i < SLSTRING_HASH_TABLE_SIZE; i++)
     {
	sls = String_Hash_Table [i];
	if (sls != NULL)
	  num_cells++;

	while (sls != NULL)
	  {
	     unsigned int len;

	     if (0 == IS_STATIC_STRING(sls))
	       {
		  len = strlen (sls->buf.bytes);
		  /* Assume 4 byte malloc overhead */
		  bytes_malloced += len + pad + 4;
		  virtual_bytes_malloced += (len + 1 + 4) * sls->ref_count;
	       }
	     num_items++;
	     sls = sls->next;
	  }
     }

   fprintf (stderr, "Bytes malloced: %lu\n", bytes_malloced);
   fprintf (stderr, "Virtual Bytes malloced: %lu\n", virtual_bytes_malloced);
   fprintf (stderr, "Num unique Items: %lu\n", num_items);
   fprintf (stderr, "Num used cells: %u\n", num_cells);
   fprintf (stderr, "Max Virtual/Actual: %lu/%lu\n", Max_Virtual_Size, Max_Actual_Size);
   fprintf (stderr, "Cur Virtual/Actual: %lu/%lu\n", Virtual_Size, Actual_Size);
}
#endif