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