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