1 /* $NetBSD: lstring.c,v 1.1.1.1 2010/10/31 11:16:59 mbalmer Exp $ */ 2 3 /* 4 ** Id: lstring.c,v 2.8.1.1 2007/12/27 13:02:25 roberto Exp 5 ** String table (keeps all strings handled by Lua) 6 ** See Copyright Notice in lua.h 7 */ 8 9 10 #include <string.h> 11 12 #define lstring_c 13 #define LUA_CORE 14 15 #include "lua.h" 16 17 #include "lmem.h" 18 #include "lobject.h" 19 #include "lstate.h" 20 #include "lstring.h" 21 22 23 24 void luaS_resize (lua_State *L, int newsize) { 25 GCObject **newhash; 26 stringtable *tb; 27 int i; 28 if (G(L)->gcstate == GCSsweepstring) 29 return; /* cannot resize during GC traverse */ 30 newhash = luaM_newvector(L, newsize, GCObject *); 31 tb = &G(L)->strt; 32 for (i=0; i<newsize; i++) newhash[i] = NULL; 33 /* rehash */ 34 for (i=0; i<tb->size; i++) { 35 GCObject *p = tb->hash[i]; 36 while (p) { /* for each node in the list */ 37 GCObject *next = p->gch.next; /* save next */ 38 unsigned int h = gco2ts(p)->hash; 39 int h1 = lmod(h, newsize); /* new position */ 40 lua_assert(cast_int(h%newsize) == lmod(h, newsize)); 41 p->gch.next = newhash[h1]; /* chain it */ 42 newhash[h1] = p; 43 p = next; 44 } 45 } 46 luaM_freearray(L, tb->hash, tb->size, TString *); 47 tb->size = newsize; 48 tb->hash = newhash; 49 } 50 51 52 static TString *newlstr (lua_State *L, const char *str, size_t l, 53 unsigned int h) { 54 TString *ts; 55 stringtable *tb; 56 if (l+1 > (MAX_SIZET - sizeof(TString))/sizeof(char)) 57 luaM_toobig(L); 58 ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString))); 59 ts->tsv.len = l; 60 ts->tsv.hash = h; 61 ts->tsv.marked = luaC_white(G(L)); 62 ts->tsv.tt = LUA_TSTRING; 63 ts->tsv.reserved = 0; 64 memcpy(ts+1, str, l*sizeof(char)); 65 ((char *)(ts+1))[l] = '\0'; /* ending 0 */ 66 tb = &G(L)->strt; 67 h = lmod(h, tb->size); 68 ts->tsv.next = tb->hash[h]; /* chain new entry */ 69 tb->hash[h] = obj2gco(ts); 70 tb->nuse++; 71 if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2) 72 luaS_resize(L, tb->size*2); /* too crowded */ 73 return ts; 74 } 75 76 77 TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { 78 GCObject *o; 79 unsigned int h = cast(unsigned int, l); /* seed */ 80 size_t step = (l>>5)+1; /* if string is too long, don't hash all its chars */ 81 size_t l1; 82 for (l1=l; l1>=step; l1-=step) /* compute hash */ 83 h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1])); 84 for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)]; 85 o != NULL; 86 o = o->gch.next) { 87 TString *ts = rawgco2ts(o); 88 if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) { 89 /* string may be dead */ 90 if (isdead(G(L), o)) changewhite(o); 91 return ts; 92 } 93 } 94 return newlstr(L, str, l, h); /* not found */ 95 } 96 97 98 Udata *luaS_newudata (lua_State *L, size_t s, Table *e) { 99 Udata *u; 100 if (s > MAX_SIZET - sizeof(Udata)) 101 luaM_toobig(L); 102 u = cast(Udata *, luaM_malloc(L, s + sizeof(Udata))); 103 u->uv.marked = luaC_white(G(L)); /* is not finalized */ 104 u->uv.tt = LUA_TUSERDATA; 105 u->uv.len = s; 106 u->uv.metatable = NULL; 107 u->uv.env = e; 108 /* chain it on udata list (after main thread) */ 109 u->uv.next = G(L)->mainthread->next; 110 G(L)->mainthread->next = obj2gco(u); 111 return u; 112 } 113 114