1 /*
2 ** $Id: lstring.c,v 1.2 2002/07/12 07:49:04 jcatki 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 #include "lua.h"
11
12 #include "lmem.h"
13 #include "lobject.h"
14 #include "lstate.h"
15 #include "lstring.h"
16
17
18 /*
19 ** type equivalent to TString, but with maximum alignment requirements
20 */
21 union L_UTString {
22 TString ts;
23 union L_Umaxalign dummy; /* ensures maximum alignment for `local' udata */
24 };
25
26
27
luaS_init(lua_State * L)28 void luaS_init (lua_State *L) {
29 L->strt.hash = luaM_newvector(L, 1, TString *);
30 L->udt.hash = luaM_newvector(L, 1, TString *);
31 L->nblocks += 2*sizeof(TString *);
32 L->strt.size = L->udt.size = 1;
33 L->strt.nuse = L->udt.nuse = 0;
34 L->strt.hash[0] = L->udt.hash[0] = NULL;
35 }
36
37
luaS_freeall(lua_State * L)38 void luaS_freeall (lua_State *L) {
39 LUA_ASSERT(L->strt.nuse==0, "non-empty string table");
40 L->nblocks -= (L->strt.size + L->udt.size)*sizeof(TString *);
41 luaM_free(L, L->strt.hash);
42 LUA_ASSERT(L->udt.nuse==0, "non-empty udata table");
43 luaM_free(L, L->udt.hash);
44 }
45
46
hash_s(const char * s,size_t l)47 static unsigned long hash_s (const char *s, size_t l) {
48 unsigned long h = l; /* seed */
49 size_t step = (l>>5)|1; /* if string is too long, don't hash all its chars */
50 for (; l>=step; l-=step)
51 h = h ^ ((h<<5)+(h>>2)+(unsigned char)*(s++));
52 return h;
53 }
54
55
luaS_resize(lua_State * L,stringtable * tb,int newsize)56 void luaS_resize (lua_State *L, stringtable *tb, int newsize) {
57 TString **newhash = luaM_newvector(L, newsize, TString *);
58 int i;
59 for (i=0; i<newsize; i++) newhash[i] = NULL;
60 /* rehash */
61 for (i=0; i<tb->size; i++) {
62 TString *p = tb->hash[i];
63 while (p) { /* for each node in the list */
64 TString *next = p->nexthash; /* save next */
65 unsigned long h = (tb == &L->strt) ? p->u.s.hash : IntPoint(p->u.d.value);
66 int h1 = h&(newsize-1); /* new position */
67 LUA_ASSERT(h%newsize == (h&(newsize-1)),
68 "a&(x-1) == a%x, for x power of 2");
69 p->nexthash = newhash[h1]; /* chain it in new position */
70 newhash[h1] = p;
71 p = next;
72 }
73 }
74 luaM_free(L, tb->hash);
75 L->nblocks += (newsize - tb->size)*sizeof(TString *);
76 tb->size = newsize;
77 tb->hash = newhash;
78 }
79
80
newentry(lua_State * L,stringtable * tb,TString * ts,int h)81 static void newentry (lua_State *L, stringtable *tb, TString *ts, int h) {
82 ts->nexthash = tb->hash[h]; /* chain new entry */
83 tb->hash[h] = ts;
84 tb->nuse++;
85 if (tb->nuse > (lint32)tb->size && tb->size < MAX_INT/2) /* too crowded? */
86 luaS_resize(L, tb, tb->size*2);
87 }
88
89
90
luaS_newlstr(lua_State * L,const char * str,size_t l)91 TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
92 unsigned long h = hash_s(str, l);
93 int h1 = h & (L->strt.size-1);
94 TString *ts;
95 for (ts = L->strt.hash[h1]; ts; ts = ts->nexthash) {
96 if (ts->len == l && (memcmp(str, ts->str, l) == 0))
97 return ts;
98 }
99 /* not found */
100 ts = (TString *)luaM_malloc(L, sizestring(l));
101 ts->marked = 0;
102 ts->nexthash = NULL;
103 ts->len = l;
104 ts->u.s.hash = h;
105 ts->u.s.constindex = 0;
106 memcpy(ts->str, str, l);
107 ts->str[l] = 0; /* ending 0 */
108 L->nblocks += sizestring(l);
109 newentry(L, &L->strt, ts, h1); /* insert it on table */
110 return ts;
111 }
112
113
luaS_newudata(lua_State * L,size_t s,void * udata)114 TString *luaS_newudata (lua_State *L, size_t s, void *udata) {
115 union L_UTString *uts = (union L_UTString *)luaM_malloc(L,
116 (lint32)sizeof(union L_UTString)+s);
117 TString *ts = &uts->ts;
118 ts->marked = 0;
119 ts->nexthash = NULL;
120 ts->len = s;
121 ts->u.d.tag = 0;
122 ts->u.d.value = (s > 0) ? uts+1 : udata;
123 L->nblocks += sizestring(s);
124 /* insert it on table */
125 newentry(L, &L->udt, ts, IntPoint(ts->u.d.value) & (L->udt.size-1));
126 return ts;
127 }
128
129
luaS_createudata(lua_State * L,void * udata,int tag)130 TString *luaS_createudata (lua_State *L, void *udata, int tag) {
131 int h1 = IntPoint(udata) & (L->udt.size-1);
132 TString *ts;
133 for (ts = L->udt.hash[h1]; ts; ts = ts->nexthash) {
134 if (udata == ts->u.d.value && (tag == ts->u.d.tag || tag == LUA_ANYTAG))
135 return ts;
136 }
137 /* not found */
138 ts = luaS_newudata(L, 0, udata);
139 if (tag != LUA_ANYTAG)
140 ts->u.d.tag = tag;
141 return ts;
142 }
143
144
luaS_new(lua_State * L,const char * str)145 TString *luaS_new (lua_State *L, const char *str) {
146 return luaS_newlstr(L, str, strlen(str));
147 }
148
149
luaS_newfixed(lua_State * L,const char * str)150 TString *luaS_newfixed (lua_State *L, const char *str) {
151 TString *ts = luaS_new(L, str);
152 if (ts->marked == 0) ts->marked = FIXMARK; /* avoid GC */
153 return ts;
154 }
155
156