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 #define lstring_c 9 #define LUA_CORE 10 11 #include <sys/lua/lua.h> 12 13 #include "lmem.h" 14 #include "lobject.h" 15 #include "lstate.h" 16 #include "lstring.h" 17 18 19 /* 20 ** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to 21 ** compute its hash 22 */ 23 #if !defined(LUAI_HASHLIMIT) 24 #define LUAI_HASHLIMIT 5 25 #endif 26 27 28 /* 29 ** equality for long strings 30 */ 31 int luaS_eqlngstr (TString *a, TString *b) { 32 size_t len = a->tsv.len; 33 lua_assert(a->tsv.tt == LUA_TLNGSTR && b->tsv.tt == LUA_TLNGSTR); 34 return (a == b) || /* same instance or... */ 35 ((len == b->tsv.len) && /* equal length and ... */ 36 (memcmp(getstr(a), getstr(b), len) == 0)); /* equal contents */ 37 } 38 39 40 /* 41 ** equality for strings 42 */ 43 int luaS_eqstr (TString *a, TString *b) { 44 return (a->tsv.tt == b->tsv.tt) && 45 (a->tsv.tt == LUA_TSHRSTR ? eqshrstr(a, b) : luaS_eqlngstr(a, b)); 46 } 47 48 49 unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { 50 unsigned int h = seed ^ cast(unsigned int, l); 51 size_t l1; 52 size_t step = (l >> LUAI_HASHLIMIT) + 1; 53 for (l1 = l; l1 >= step; l1 -= step) 54 h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1])); 55 return h; 56 } 57 58 59 /* 60 ** resizes the string table 61 */ 62 void luaS_resize (lua_State *L, int newsize) { 63 int i; 64 stringtable *tb = &G(L)->strt; 65 /* cannot resize while GC is traversing strings */ 66 luaC_runtilstate(L, ~bitmask(GCSsweepstring)); 67 if (newsize > tb->size) { 68 luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *); 69 for (i = tb->size; i < newsize; i++) tb->hash[i] = NULL; 70 } 71 /* rehash */ 72 for (i=0; i<tb->size; i++) { 73 GCObject *p = tb->hash[i]; 74 tb->hash[i] = NULL; 75 while (p) { /* for each node in the list */ 76 GCObject *next = gch(p)->next; /* save next */ 77 unsigned int h = lmod(gco2ts(p)->hash, newsize); /* new position */ 78 gch(p)->next = tb->hash[h]; /* chain it */ 79 tb->hash[h] = p; 80 resetoldbit(p); /* see MOVE OLD rule */ 81 p = next; 82 } 83 } 84 if (newsize < tb->size) { 85 /* shrinking slice must be empty */ 86 lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL); 87 luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *); 88 } 89 tb->size = newsize; 90 } 91 92 93 /* 94 ** creates a new string object 95 */ 96 static TString *createstrobj (lua_State *L, const char *str, size_t l, 97 int tag, unsigned int h, GCObject **list) { 98 TString *ts; 99 char *sbuf; 100 size_t totalsize; /* total size of TString object */ 101 totalsize = sizeof(TString) + ((l + 1) * sizeof(char)); 102 ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts; 103 ts->tsv.len = l; 104 ts->tsv.hash = h; 105 ts->tsv.extra = 0; 106 sbuf = (char *)(TString *)(ts + 1); 107 memcpy(sbuf, str, l*sizeof(char)); 108 sbuf[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