1323530Savg/* 2323530Savg** $Id: lstring.c,v 2.26.1.1 2013/04/12 18:48:47 roberto Exp $ 3323530Savg** String table (keeps all strings handled by Lua) 4323530Savg** See Copyright Notice in lua.h 5323530Savg*/ 6323530Savg 7323530Savg 8323530Savg#include <sys/zfs_context.h> 9323530Savg 10323530Savg#define lstring_c 11323530Savg#define LUA_CORE 12323530Savg 13323530Savg#include "lua.h" 14323530Savg 15323530Savg#include "lmem.h" 16323530Savg#include "lobject.h" 17323530Savg#include "lstate.h" 18323530Savg#include "lstring.h" 19323530Savg 20323530Savg 21323530Savg/* 22323530Savg** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to 23323530Savg** compute its hash 24323530Savg*/ 25323530Savg#if !defined(LUAI_HASHLIMIT) 26323530Savg#define LUAI_HASHLIMIT 5 27323530Savg#endif 28323530Savg 29323530Savg 30323530Savg/* 31323530Savg** equality for long strings 32323530Savg*/ 33323530Savgint luaS_eqlngstr (TString *a, TString *b) { 34323530Savg size_t len = a->tsv.len; 35323530Savg lua_assert(a->tsv.tt == LUA_TLNGSTR && b->tsv.tt == LUA_TLNGSTR); 36323530Savg return (a == b) || /* same instance or... */ 37323530Savg ((len == b->tsv.len) && /* equal length and ... */ 38323530Savg (memcmp(getstr(a), getstr(b), len) == 0)); /* equal contents */ 39323530Savg} 40323530Savg 41323530Savg 42323530Savg/* 43323530Savg** equality for strings 44323530Savg*/ 45323530Savgint luaS_eqstr (TString *a, TString *b) { 46323530Savg return (a->tsv.tt == b->tsv.tt) && 47323530Savg (a->tsv.tt == LUA_TSHRSTR ? eqshrstr(a, b) : luaS_eqlngstr(a, b)); 48323530Savg} 49323530Savg 50323530Savg 51323530Savgunsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { 52323530Savg unsigned int h = seed ^ cast(unsigned int, l); 53323530Savg size_t l1; 54323530Savg size_t step = (l >> LUAI_HASHLIMIT) + 1; 55323530Savg for (l1 = l; l1 >= step; l1 -= step) 56323530Savg h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1])); 57323530Savg return h; 58323530Savg} 59323530Savg 60323530Savg 61323530Savg/* 62323530Savg** resizes the string table 63323530Savg*/ 64323530Savgvoid luaS_resize (lua_State *L, int newsize) { 65323530Savg int i; 66323530Savg stringtable *tb = &G(L)->strt; 67323530Savg /* cannot resize while GC is traversing strings */ 68323530Savg luaC_runtilstate(L, ~bitmask(GCSsweepstring)); 69323530Savg if (newsize > tb->size) { 70323530Savg luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *); 71323530Savg for (i = tb->size; i < newsize; i++) tb->hash[i] = NULL; 72323530Savg } 73323530Savg /* rehash */ 74323530Savg for (i=0; i<tb->size; i++) { 75323530Savg GCObject *p = tb->hash[i]; 76323530Savg tb->hash[i] = NULL; 77323530Savg while (p) { /* for each node in the list */ 78323530Savg GCObject *next = gch(p)->next; /* save next */ 79323530Savg unsigned int h = lmod(gco2ts(p)->hash, newsize); /* new position */ 80323530Savg gch(p)->next = tb->hash[h]; /* chain it */ 81323530Savg tb->hash[h] = p; 82323530Savg resetoldbit(p); /* see MOVE OLD rule */ 83323530Savg p = next; 84323530Savg } 85323530Savg } 86323530Savg if (newsize < tb->size) { 87323530Savg /* shrinking slice must be empty */ 88323530Savg lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL); 89323530Savg luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *); 90323530Savg } 91323530Savg tb->size = newsize; 92323530Savg} 93323530Savg 94323530Savg 95323530Savg/* 96323530Savg** creates a new string object 97323530Savg*/ 98323530Savgstatic TString *createstrobj (lua_State *L, const char *str, size_t l, 99323530Savg int tag, unsigned int h, GCObject **list) { 100323530Savg TString *ts; 101323530Savg size_t totalsize; /* total size of TString object */ 102323530Savg totalsize = sizeof(TString) + ((l + 1) * sizeof(char)); 103323530Savg ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts; 104323530Savg ts->tsv.len = l; 105323530Savg ts->tsv.hash = h; 106323530Savg ts->tsv.extra = 0; 107323530Savg memcpy(ts+1, str, l*sizeof(char)); 108323530Savg ((char *)(ts+1))[l] = '\0'; /* ending 0 */ 109323530Savg return ts; 110323530Savg} 111323530Savg 112323530Savg 113323530Savg/* 114323530Savg** creates a new short string, inserting it into string table 115323530Savg*/ 116323530Savgstatic TString *newshrstr (lua_State *L, const char *str, size_t l, 117323530Savg unsigned int h) { 118323530Savg GCObject **list; /* (pointer to) list where it will be inserted */ 119323530Savg stringtable *tb = &G(L)->strt; 120323530Savg TString *s; 121323530Savg if (tb->nuse >= cast(lu_int32, tb->size) && tb->size <= MAX_INT/2) 122323530Savg luaS_resize(L, tb->size*2); /* too crowded */ 123323530Savg list = &tb->hash[lmod(h, tb->size)]; 124323530Savg s = createstrobj(L, str, l, LUA_TSHRSTR, h, list); 125323530Savg tb->nuse++; 126323530Savg return s; 127323530Savg} 128323530Savg 129323530Savg 130323530Savg/* 131323530Savg** checks whether short string exists and reuses it or creates a new one 132323530Savg*/ 133323530Savgstatic TString *internshrstr (lua_State *L, const char *str, size_t l) { 134323530Savg GCObject *o; 135323530Savg global_State *g = G(L); 136323530Savg unsigned int h = luaS_hash(str, l, g->seed); 137323530Savg for (o = g->strt.hash[lmod(h, g->strt.size)]; 138323530Savg o != NULL; 139323530Savg o = gch(o)->next) { 140323530Savg TString *ts = rawgco2ts(o); 141323530Savg if (h == ts->tsv.hash && 142323530Savg l == ts->tsv.len && 143323530Savg (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { 144323530Savg if (isdead(G(L), o)) /* string is dead (but was not collected yet)? */ 145323530Savg changewhite(o); /* resurrect it */ 146323530Savg return ts; 147323530Savg } 148323530Savg } 149323530Savg return newshrstr(L, str, l, h); /* not found; create a new string */ 150323530Savg} 151323530Savg 152323530Savg 153323530Savg/* 154323530Savg** new string (with explicit length) 155323530Savg*/ 156323530SavgTString *luaS_newlstr (lua_State *L, const char *str, size_t l) { 157323530Savg if (l <= LUAI_MAXSHORTLEN) /* short string? */ 158323530Savg return internshrstr(L, str, l); 159323530Savg else { 160323530Savg if (l + 1 > (MAX_SIZET - sizeof(TString))/sizeof(char)) 161323530Savg luaM_toobig(L); 162323530Savg return createstrobj(L, str, l, LUA_TLNGSTR, G(L)->seed, NULL); 163323530Savg } 164323530Savg} 165323530Savg 166323530Savg 167323530Savg/* 168323530Savg** new zero-terminated string 169323530Savg*/ 170323530SavgTString *luaS_new (lua_State *L, const char *str) { 171323530Savg return luaS_newlstr(L, str, strlen(str)); 172323530Savg} 173323530Savg 174323530Savg 175323530SavgUdata *luaS_newudata (lua_State *L, size_t s, Table *e) { 176323530Savg Udata *u; 177323530Savg if (s > MAX_SIZET - sizeof(Udata)) 178323530Savg luaM_toobig(L); 179323530Savg u = &luaC_newobj(L, LUA_TUSERDATA, sizeof(Udata) + s, NULL, 0)->u; 180323530Savg u->uv.len = s; 181323530Savg u->uv.metatable = NULL; 182323530Savg u->uv.env = e; 183323530Savg return u; 184323530Savg} 185323530Savg 186