lstring.c revision 323530
1/* 2** $Id: lstring.c,v 2.26.1.1 2013/04/12 18:48:47 roberto Exp $ 3** String table (keeps all strings handled by Lua) 4** See Copyright Notice in lua.h 5*/ 6 7 8#include <sys/zfs_context.h> 9 10#define lstring_c 11#define LUA_CORE 12 13#include "lua.h" 14 15#include "lmem.h" 16#include "lobject.h" 17#include "lstate.h" 18#include "lstring.h" 19 20 21/* 22** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to 23** compute its hash 24*/ 25#if !defined(LUAI_HASHLIMIT) 26#define LUAI_HASHLIMIT 5 27#endif 28 29 30/* 31** equality for long strings 32*/ 33int luaS_eqlngstr (TString *a, TString *b) { 34 size_t len = a->tsv.len; 35 lua_assert(a->tsv.tt == LUA_TLNGSTR && b->tsv.tt == LUA_TLNGSTR); 36 return (a == b) || /* same instance or... */ 37 ((len == b->tsv.len) && /* equal length and ... */ 38 (memcmp(getstr(a), getstr(b), len) == 0)); /* equal contents */ 39} 40 41 42/* 43** equality for strings 44*/ 45int luaS_eqstr (TString *a, TString *b) { 46 return (a->tsv.tt == b->tsv.tt) && 47 (a->tsv.tt == LUA_TSHRSTR ? eqshrstr(a, b) : luaS_eqlngstr(a, b)); 48} 49 50 51unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { 52 unsigned int h = seed ^ cast(unsigned int, l); 53 size_t l1; 54 size_t step = (l >> LUAI_HASHLIMIT) + 1; 55 for (l1 = l; l1 >= step; l1 -= step) 56 h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1])); 57 return h; 58} 59 60 61/* 62** resizes the string table 63*/ 64void luaS_resize (lua_State *L, int newsize) { 65 int i; 66 stringtable *tb = &G(L)->strt; 67 /* cannot resize while GC is traversing strings */ 68 luaC_runtilstate(L, ~bitmask(GCSsweepstring)); 69 if (newsize > tb->size) { 70 luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *); 71 for (i = tb->size; i < newsize; i++) tb->hash[i] = NULL; 72 } 73 /* rehash */ 74 for (i=0; i<tb->size; i++) { 75 GCObject *p = tb->hash[i]; 76 tb->hash[i] = NULL; 77 while (p) { /* for each node in the list */ 78 GCObject *next = gch(p)->next; /* save next */ 79 unsigned int h = lmod(gco2ts(p)->hash, newsize); /* new position */ 80 gch(p)->next = tb->hash[h]; /* chain it */ 81 tb->hash[h] = p; 82 resetoldbit(p); /* see MOVE OLD rule */ 83 p = next; 84 } 85 } 86 if (newsize < tb->size) { 87 /* shrinking slice must be empty */ 88 lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL); 89 luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *); 90 } 91 tb->size = newsize; 92} 93 94 95/* 96** creates a new string object 97*/ 98static TString *createstrobj (lua_State *L, const char *str, size_t l, 99 int tag, unsigned int h, GCObject **list) { 100 TString *ts; 101 size_t totalsize; /* total size of TString object */ 102 totalsize = sizeof(TString) + ((l + 1) * sizeof(char)); 103 ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts; 104 ts->tsv.len = l; 105 ts->tsv.hash = h; 106 ts->tsv.extra = 0; 107 memcpy(ts+1, str, l*sizeof(char)); 108 ((char *)(ts+1))[l] = '\0'; /* ending 0 */ 109 return ts; 110} 111 112 113/* 114** creates a new short string, inserting it into string table 115*/ 116static TString *newshrstr (lua_State *L, const char *str, size_t l, 117 unsigned int h) { 118 GCObject **list; /* (pointer to) list where it will be inserted */ 119 stringtable *tb = &G(L)->strt; 120 TString *s; 121 if (tb->nuse >= cast(lu_int32, tb->size) && tb->size <= MAX_INT/2) 122 luaS_resize(L, tb->size*2); /* too crowded */ 123 list = &tb->hash[lmod(h, tb->size)]; 124 s = createstrobj(L, str, l, LUA_TSHRSTR, h, list); 125 tb->nuse++; 126 return s; 127} 128 129 130/* 131** checks whether short string exists and reuses it or creates a new one 132*/ 133static TString *internshrstr (lua_State *L, const char *str, size_t l) { 134 GCObject *o; 135 global_State *g = G(L); 136 unsigned int h = luaS_hash(str, l, g->seed); 137 for (o = g->strt.hash[lmod(h, g->strt.size)]; 138 o != NULL; 139 o = gch(o)->next) { 140 TString *ts = rawgco2ts(o); 141 if (h == ts->tsv.hash && 142 l == ts->tsv.len && 143 (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { 144 if (isdead(G(L), o)) /* string is dead (but was not collected yet)? */ 145 changewhite(o); /* resurrect it */ 146 return ts; 147 } 148 } 149 return newshrstr(L, str, l, h); /* not found; create a new string */ 150} 151 152 153/* 154** new string (with explicit length) 155*/ 156TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { 157 if (l <= LUAI_MAXSHORTLEN) /* short string? */ 158 return internshrstr(L, str, l); 159 else { 160 if (l + 1 > (MAX_SIZET - sizeof(TString))/sizeof(char)) 161 luaM_toobig(L); 162 return createstrobj(L, str, l, LUA_TLNGSTR, G(L)->seed, NULL); 163 } 164} 165 166 167/* 168** new zero-terminated string 169*/ 170TString *luaS_new (lua_State *L, const char *str) { 171 return luaS_newlstr(L, str, strlen(str)); 172} 173 174 175Udata *luaS_newudata (lua_State *L, size_t s, Table *e) { 176 Udata *u; 177 if (s > MAX_SIZET - sizeof(Udata)) 178 luaM_toobig(L); 179 u = &luaC_newobj(L, LUA_TUSERDATA, sizeof(Udata) + s, NULL, 0)->u; 180 u->uv.len = s; 181 u->uv.metatable = NULL; 182 u->uv.env = e; 183 return u; 184} 185 186