1 /* 2 ** $Id: lstring.c,v 2.26 2013/01/08 13:50:10 roberto Exp $ 3 ** String table (keeps all strings handled by Lua) 4 ** See Copyright Notice in lua.h 5 */ 6 7 8 #include <string.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 */ 33 int 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 */ 45 int 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 51 unsigned 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 */ 64 void 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 */ 98 static 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 */ 116 static 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 */ 133 static 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 */ 156 TString *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 */ 170 TString *luaS_new (lua_State *L, const char *str) { 171 return luaS_newlstr(L, str, strlen(str)); 172 } 173 174 175 Udata *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
