diff options
| author | lneto <lneto@NetBSD.org> | 2014-07-19 18:38:33 +0000 |
|---|---|---|
| committer | lneto <lneto@NetBSD.org> | 2014-07-19 18:38:33 +0000 |
| commit | c4b1eb35e827c43a0dcf41027c98aaedf46be036 (patch) | |
| tree | f80015954e9c51266af4f2e1c57f2134cbcc1d62 /external/mit/lua/dist/src/lstring.c | |
| parent | c6d74635a1d93d95a3770bd621dcd83ed33100c2 (diff) | |
lua: updated from 5.1 to 5.3 work3
* lua(1):
- changed lua_Integer to intmax_t
- updated distrib/sets/lists and etc/mtree
- updated bsd.lua.mk
- fixed bozohttpd (lua-bozo.c)
- compatibilized bindings: gpio, sqlite
* lua(4):
- removed floating-point and libc dependencies using '#ifndef _KERNEL'
- fixed division by zero and exponentiation
- libkern: added isalnum(), iscntrl(), isgraph(), isprint() and ispunct()
- acpica: removed isprint() from acnetbsd.h
- libc: moved strcspn.c, strpbrk.c and strspn.c to common
- removed stub headers
- compatibilized bindings: luapmf, luasystm
* reorganized luaconf.h
* updated doc/CHANGES and doc/RESPONSIBLE
Diffstat (limited to 'external/mit/lua/dist/src/lstring.c')
| -rw-r--r-- | external/mit/lua/dist/src/lstring.c | 193 |
1 files changed, 132 insertions, 61 deletions
diff --git a/external/mit/lua/dist/src/lstring.c b/external/mit/lua/dist/src/lstring.c index 07350b78f27..b5163ef7001 100644 --- a/external/mit/lua/dist/src/lstring.c +++ b/external/mit/lua/dist/src/lstring.c @@ -1,19 +1,23 @@ -/* $NetBSD: lstring.c,v 1.1.1.2 2012/03/15 00:08:08 alnsn Exp $ */ +/* $NetBSD: lstring.c,v 1.2 2014/07/19 18:38:34 lneto Exp $ */ /* -** $Id: lstring.c,v 1.1.1.2 2012/03/15 00:08:08 alnsn Exp $ +** $Id: lstring.c,v 1.2 2014/07/19 18:38:34 lneto Exp $ ** String table (keeps all strings handled by Lua) ** See Copyright Notice in lua.h */ +#ifndef _KERNEL #include <string.h> +#endif #define lstring_c #define LUA_CORE #include "lua.h" +#include "ldebug.h" +#include "ldo.h" #include "lmem.h" #include "lobject.h" #include "lstate.h" @@ -21,93 +25,160 @@ +/* +** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to +** compute its hash +*/ +#if !defined(LUAI_HASHLIMIT) +#define LUAI_HASHLIMIT 5 +#endif + + +/* +** equality for long strings +*/ +int luaS_eqlngstr (TString *a, TString *b) { + size_t len = a->tsv.len; + lua_assert(a->tsv.tt == LUA_TLNGSTR && b->tsv.tt == LUA_TLNGSTR); + return (a == b) || /* same instance or... */ + ((len == b->tsv.len) && /* equal length and ... */ + (memcmp(getstr(a), getstr(b), len) == 0)); /* equal contents */ +} + + +unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { + unsigned int h = seed ^ cast(unsigned int, l); + size_t l1; + size_t step = (l >> LUAI_HASHLIMIT) + 1; + for (l1 = l; l1 >= step; l1 -= step) + h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1])); + return h; +} + + +/* +** resizes the string table +*/ void luaS_resize (lua_State *L, int newsize) { - GCObject **newhash; - stringtable *tb; int i; - if (G(L)->gcstate == GCSsweepstring) - return; /* cannot resize during GC traverse */ - newhash = luaM_newvector(L, newsize, GCObject *); - tb = &G(L)->strt; - for (i=0; i<newsize; i++) newhash[i] = NULL; - /* rehash */ - for (i=0; i<tb->size; i++) { - GCObject *p = tb->hash[i]; + stringtable *tb = &G(L)->strt; + if (newsize > tb->size) { /* grow table if needed */ + luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *); + for (i = tb->size; i < newsize; i++) + tb->hash[i] = NULL; + } + for (i = 0; i < tb->size; i++) { /* rehash */ + TString *p = tb->hash[i]; + tb->hash[i] = NULL; while (p) { /* for each node in the list */ - GCObject *next = p->gch.next; /* save next */ - unsigned int h = gco2ts(p)->hash; - int h1 = lmod(h, newsize); /* new position */ - lua_assert(cast_int(h%newsize) == lmod(h, newsize)); - p->gch.next = newhash[h1]; /* chain it */ - newhash[h1] = p; - p = next; + TString *hnext = p->tsv.hnext; /* save next */ + unsigned int h = lmod(p->tsv.hash, newsize); /* new position */ + p->tsv.hnext = tb->hash[h]; /* chain it */ + tb->hash[h] = p; + p = hnext; } } - luaM_freearray(L, tb->hash, tb->size, TString *); + if (newsize < tb->size) { /* shrink table if needed */ + /* vanishing slice should be empty */ + lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL); + luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *); + } tb->size = newsize; - tb->hash = newhash; } -static TString *newlstr (lua_State *L, const char *str, size_t l, - unsigned int h) { + +/* +** creates a new string object +*/ +static TString *createstrobj (lua_State *L, const char *str, size_t l, + int tag, unsigned int h) { TString *ts; - stringtable *tb; - if (l+1 > (MAX_SIZET - sizeof(TString))/sizeof(char)) - luaM_toobig(L); - ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString))); + GCObject *o; + size_t totalsize; /* total size of TString object */ + totalsize = sizeof(TString) + ((l + 1) * sizeof(char)); + o = luaC_newobj(L, tag, totalsize); + ts = rawgco2ts(o); ts->tsv.len = l; ts->tsv.hash = h; - ts->tsv.marked = luaC_white(G(L)); - ts->tsv.tt = LUA_TSTRING; - ts->tsv.reserved = 0; + ts->tsv.extra = 0; memcpy(ts+1, str, l*sizeof(char)); ((char *)(ts+1))[l] = '\0'; /* ending 0 */ - tb = &G(L)->strt; - h = lmod(h, tb->size); - ts->tsv.next = tb->hash[h]; /* chain new entry */ - tb->hash[h] = obj2gco(ts); - tb->nuse++; - if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2) - luaS_resize(L, tb->size*2); /* too crowded */ return ts; } -TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { - GCObject *o; - unsigned int h = cast(unsigned int, l); /* seed */ - size_t step = (l>>5)+1; /* if string is too long, don't hash all its chars */ - size_t l1; - for (l1=l; l1>=step; l1-=step) /* compute hash */ - h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1])); - for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)]; - o != NULL; - o = o->gch.next) { - TString *ts = rawgco2ts(o); - if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) { - /* string may be dead */ - if (isdead(G(L), o)) changewhite(o); +void luaS_remove (lua_State *L, TString *ts) { + stringtable *tb = &G(L)->strt; + TString **p = &tb->hash[lmod(ts->tsv.hash, tb->size)]; + while (*p != ts) /* find previous element */ + p = &(*p)->tsv.hnext; + *p = (*p)->tsv.hnext; /* remove element from its list */ + tb->nuse--; +} + + +/* +** checks whether short string exists and reuses it or creates a new one +*/ +static TString *internshrstr (lua_State *L, const char *str, size_t l) { + TString *ts; + global_State *g = G(L); + unsigned int h = luaS_hash(str, l, g->seed); + TString **list = &g->strt.hash[lmod(h, g->strt.size)]; + for (ts = *list; ts != NULL; ts = ts->tsv.hnext) { + if (l == ts->tsv.len && + (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { + /* found! */ + if (isdead(g, obj2gco(ts))) /* dead (but not collected yet)? */ + changewhite(obj2gco(ts)); /* resurrect it */ return ts; } } - return newlstr(L, str, l, h); /* not found */ + if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) { + luaS_resize(L, g->strt.size * 2); + list = &g->strt.hash[lmod(h, g->strt.size)]; /* recompute with new size */ + } + ts = createstrobj(L, str, l, LUA_TSHRSTR, h); + ts->tsv.hnext = *list; + *list = ts; + g->strt.nuse++; + return ts; } -Udata *luaS_newudata (lua_State *L, size_t s, Table *e) { +/* +** new string (with explicit length) +*/ +TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { + if (l <= LUAI_MAXSHORTLEN) /* short string? */ + return internshrstr(L, str, l); + else { + if (l + 1 > (MAX_SIZE - sizeof(TString))/sizeof(char)) + luaM_toobig(L); + return createstrobj(L, str, l, LUA_TLNGSTR, G(L)->seed); + } +} + + +/* +** new zero-terminated string +*/ +TString *luaS_new (lua_State *L, const char *str) { + return luaS_newlstr(L, str, strlen(str)); +} + + +Udata *luaS_newudata (lua_State *L, size_t s) { Udata *u; - if (s > MAX_SIZET - sizeof(Udata)) + GCObject *o; + if (s > MAX_SIZE - sizeof(Udata)) luaM_toobig(L); - u = cast(Udata *, luaM_malloc(L, s + sizeof(Udata))); - u->uv.marked = luaC_white(G(L)); /* is not finalized */ - u->uv.tt = LUA_TUSERDATA; + o = luaC_newobj(L, LUA_TUSERDATA, sizeof(Udata) + s); + u = rawgco2u(o); u->uv.len = s; u->uv.metatable = NULL; - u->uv.env = e; - /* chain it on udata list (after main thread) */ - u->uv.next = G(L)->mainthread->next; - G(L)->mainthread->next = obj2gco(u); + setuservalue(L, u, luaO_nilobject); return u; } |
