/* Copyright 1995, 1997 J"orn Rennecke */

#include <stdio.h>

#include "common.h"
#include "alloc.h"

#define PHASHSTRING(str, len) (aphash(str, len) & ((STRTABLE_SIZE)-1))

struct searchstr {
    struct searchstr *next;
    char block[4];
};

struct searchlstr {
    struct searchlstr *next;
    uint32 len;
    char block[4];
};

struct searchstr *str_table[STRTABLE_SIZE];
struct searchlstr *lstr_table[LSTRTABLE_SIZE];

struct short_string nil_string = { T_STRING, 1, 0, /*len*/ 0, 0 };

static char print_buf
 [P_INT_PRINT_SIZE > DOUBLE_PRINT_SIZE ? P_INT_PRINT_SIZE : DOUBLE_PRINT_SIZE];

void init_global_strings() {
    int i;
    struct searchstr **p;
    struct searchlstr **lp;

    i = NELEM(str_table);
    p = str_table;
    do {
	*p = (struct searchstr *)p;
	p++;
    } while(--i);
    i = NELEM(lstr_table);
    lp = lstr_table;
    do {
	*lp = (struct searchlstr *)lp;
	lp++;
    } while(--i);
    make_string_global(NIL_STRING);
    /* We want to be able to use NIL_STRING without concern about ref counts. */
    SV_STRREF(NIL_STRING) = 255;
}

union svalue make_string(register char *str, mp_int length) {
    svalue res;
    register char *dest;

    if (length > MAX_SMALL_STRING) {
        res = ALLOC_LSTRING(length);
        if (!res.p)
            goto out_of_memory;
        dest = SV_LSTRING(res);
        SV_LSTRREF(res) = 1;
        SV_LSTRLEN(res) = length;
    } else {
        res = ALLOC_STRING(length);
        if (!res.p) {
  out_of_memory:
            error(IE_NOMEM);
            return SV_NULL;
        }
        dest = SV_STRING(res);
        SV_STRREF(res) = 0;
        SV_STRLEN(res) = length;
    }
    memcpy(dest, str, length);
    return res;
}

char *sv_string(union svalue sv, mp_uint *lenp) {
    if (!SV_STRING_IS_LONG(sv)) {
	*lenp = SV_STRLEN(sv);
	return SV_STRING(sv);
    } else {
	*lenp = SV_LSTRLEN(sv);
	return SV_LSTRING(sv);
    }
}

struct counted_string sv_string2(union svalue sv) {
    struct counted_string ret;

    if (!SV_STRING_IS_LONG(sv)) {
	ret.len = SV_STRLEN(sv);
	ret.start =  SV_STRING(sv);
	return ret;
    } else {
	ret.len = SV_LSTRLEN(sv);
	ret.start = SV_LSTRING(sv);
	return ret;
    }
}

union svalue findstring(union svalue s) {
    char *str;
    mp_int len;
    int h;

    switch (SV_TYPE(s)) {
      case T_ISTRING:
      case T_ILSTRING:
	s = SV_ISTRING(s);
      case T_GSTRING:
      case T_GLSTRING:
	return s;
      case T_LSTRING:
      {
	struct searchlstr **anchor, *first, *curr, *prev;

	len = SV_LSTRLEN(s);
	str = SV_LSTRING(s);
	h = PHASHSTRING((char *)str, len);
	prev = 0;
	anchor = &lstr_table[h];
	curr = first = *anchor;
	while (&curr->next != anchor) {
	    adtstat[SHS_LSEARCH]++;
	    if (curr->len == len && !memcmp(curr->block, str, len)) {
		if (prev) {
		    adtstat[SHS_LREORDER]++;
		    prev->next = curr->next;
		    curr->next = first;
		    *anchor = curr;
		    SV_TYPE_LOC(s) += T_ILSTRING - T_LSTRING;
		    return SV_ILSTRING(s) = (uint8 *)curr - sizeof(p_int) + 1;
		}
		adtstat[SHS_LHEADMATCH]++;
		return (uint8 *)curr - sizeof(p_int) + 1;
	    }
	    prev = curr;
	    curr = prev->next;
	}
	adtstat[SHS_LFAIL]++;
	((uint8 *)str)[-8 - sizeof curr] = T_GLSTRING;
	((struct searchlstr *)(void *)&str[4])[-1].next = first;
	*anchor = &((struct searchlstr *)(void *)&str[4])[-1];
	return s;
      }
      default:
#ifdef DEBUG
	fatal("Bad string type\n");
#endif
      case T_STRING:
      {
	struct searchstr **anchor, *first, *curr, *prev;

	len = SV_STRLEN(s);
	str = SV_STRING(s);
	h = PHASHSTRING((char *)str, len);
	prev = 0;
	anchor = &str_table[h];
	curr = first = *anchor;
	while (&curr->next != anchor) {
	    adtstat[SHS_SEARCH]++;
	    if (((uint8 *)curr)[-1] == len && !memcmp(curr->block, str, len)) {
		if (prev) {
		    adtstat[SHS_REORDER]++;
		    prev->next = curr->next;
		    curr->next = first;
		    *anchor = curr;
		    SV_TYPE_LOC(s) += T_ISTRING - T_STRING;
		    return SV_ISTRING(s) = (uint8 *)curr - sizeof(p_int) + 1;
		}
		adtstat[SHS_HEADMATCH]++;
		return (uint8 *)curr - sizeof(p_int) + 1;
	    }
	    prev = curr;
	    curr = curr->next;
	}
	adtstat[SHS_FAIL]++;
	((uint8 *)str)[-sizeof(p_int) - sizeof curr] = T_GSTRING;
	((struct searchstr *)(void *)&str[4])[-1].next = first;
	*anchor = &((struct searchstr *)(void *)&str[4])[-1];
	return s;
      }
    }
}

union svalue make_string_global(union svalue s) {
    union svalue s2;

    s2 = findstring(s); /* hand-inline this call when things stabilize */
    if (s2.p != s.p) {
	if (!++SV_REF(s2))
	    s2 = ref_inc(s2);
	FREE_ALLOCED_SVALUE(s);
    }
    return s2;
}

union svalue make_global_string(char *str, mp_int length) {
    union svalue sv = make_string(str, length);
    if (sv.i)
	sv = make_string_global(sv);
    return sv;
}

svalue unshare_string(svalue s) {
    struct searchstr **search, *curr, *prev;

    adtstat[SHS_UNSHARE]++;
    SV_TYPE_LOC(s) += T_STRING - T_GSTRING;
    search = &SV_STRNXT(s);
    curr = *search;
    do {
	prev = curr;
	curr = curr->next;
    } while(&curr->next != search);
    prev->next = curr->next;
    return s;
}

#if 0
void free_string(union svalue s) {
    struct searchstr **search, *curr, *prev;

    adtstat[SHS_FREE]++;
    search = &SV_STRNXT(s);
    curr = *search;
    do {
	prev = curr;
	curr = curr->next;
    } while(&curr->next != search);
    prev->next = curr->next;
    free_block(
	(uint8 *)search - 3,
	sizeof(uint16 *) + (((uint8 *)search)[-1]+3 & ~3)
    );
}

void free_lstring(union svalue s) {
    struct searchlstr **search, *curr, *prev;

    adtstat[SHS_LFREE]++;
    search = &SV_LSTRNXT(s);
    curr = *search;
    do {
	prev = curr;
	curr = curr->next;
    } while(&curr->next != search);
    prev->next = curr->next;
    free_block(
	(uint8 *)search - 3,
	sizeof(uint16 *) + (((struct searchlstr *)search)->len+3 & ~3)
    );
}
#endif

p_int sv_strcmp(svalue sv0, svalue sv1) {
    struct counted_string str0 = sv_string2(sv0);
    struct counted_string str1 = sv_string2(sv1);
    int len = str0.len > str1.len ? str0.len : str1.len;
    int diff = strncmp(str0.start, str1.start, len);
    return diff ? diff : str0.len - str1.len;
}

svalue add_string(svalue sv0, svalue sv1) {
    struct counted_string str0, str1;
    mp_int total;
    svalue res;
    char *dest;

    if (!SV_IS_NUMBER(sv1)) {
	if (SV_IS_STRING(sv1)) {
	    if (!SV_STRING_IS_LONG(sv1)) {
		str1.len = SV_STRLEN(sv1);
		str1.start =  SV_STRING(sv1);
	    } else {
		str1.len = SV_LSTRLEN(sv1);
		str1.start = SV_LSTRING(sv1);
	    }
	} else if (SV_TYPE(sv1) == T_FLOAT) {
	    sprintf(print_buf, "%g", SV_FLOAT(sv1));
	    str1.start = print_buf;
	    str1.len = strlen(print_buf);
	} else if (SV_TYPE(sv1) == T_DESTRUCTED) {
	    str1.start = "0";
	    str1.len = 1;
	} else {
	    FREE_ALLOCED_SVALUE(sv0);
	    bad_efun_arg(2);
	    return sv1;
	}
    } else {
        sprintf(print_buf, "%ld", sv1.i >> 1);
	str1.start = print_buf;
	str1.len = strlen(print_buf);
	sv1 = NIL_STRING;
    }
    if (!SV_STRING_IS_LONG(sv0)) {
	str0.len = SV_STRLEN(sv0);
	str0.start =  SV_STRING(sv0);
    } else {
	str0.len = SV_LSTRLEN(sv0);
	str0.start = SV_LSTRING(sv0);
    }
    total = str0.len + str1.len;

    if (total > MAX_SMALL_STRING) {
	if (SV_TYPE(sv1) == T_LSTRING && SV_REF(sv1) == 1 &&
	  SV_LSTRREF(sv1) == 1 && /* FIXME: test enough free space. */ 0) {
	    res = sv1;
	    dest = str0.start;
	    goto copy_str1;
	}
        res = ALLOC_LSTRING(total);
        if (!res.p)
            goto out_of_memory;
        dest = SV_LSTRING(res);
        SV_LSTRREF(res) = 1;
        SV_LSTRLEN(res) = total;
    } else {
        res = ALLOC_STRING(total);
        if (!res.p) {
  out_of_memory:
            error(IE_NOMEM);
	    FREE_ALLOCED_SVALUE(sv1);
            return sv0;
        }
        dest = SV_STRING(res);
        SV_STRREF(res) = 0;
        SV_STRLEN(res) = total;
    }
    memcpy(dest, str0.start, str0.len);
    dest += str0.len;
    FREE_ALLOCED_SVALUE(sv0);
  copy_str1:
    memcpy(dest, str1.start, str1.len);
    FREE_ALLOCED_SVALUE(sv1);
    return res;
}

svalue *f_strstr(svalue *sp) {
    struct counted_string str0, str1;
    svalue sv0, sv1, sv2 = *sp;
    p_int offset;
    char *found;

    if (!SV_IS_NUMBER(sv2)) {
	bad_efun_arg(3);
	return sp;
    }
    sv1 = *--sp;
    if (!SV_IS_STRING(sv1)) {
	bad_efun_arg(2);
	return sp;
    }
    sv0 = *--sp;
    if (!SV_IS_STRING(sv0)) {
	bad_efun_arg(1);
	return sp;
    }
    str0 = sv_string2(sv0);
    offset = sv2.i >> 1;
    if (offset < 0) {
	offset += str0.len;
	if (offset < 0)
	    offset = 0;
    }
    if (offset > str0.len) {
	found = 0;
    } else {
	str0.start += offset;
	str1 = sv_string2(sv1);
	found = memmem(str1.start, str1.len, str0.start, str0.len - offset);
    }
    *sp = INT_SVALUE(found ? found - str0.start : -1);
    FREE_ALLOCED_SVALUE(sv0);
    FREE_ALLOCED_SVALUE(sv1);
    return sp;
}