aboutsummaryrefslogtreecommitdiff
path: root/lstring.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2013-09-05 16:31:49 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2013-09-05 16:31:49 -0300
commitd3bbb34c24cfe3e5296c6a5d3faacf6c8679fe70 (patch)
treeb245be2289ab4fdbb558a0f52a81dd5631871ee3 /lstring.c
parent0ad15fc10041f59b5466fe902637b1a2fb64565d (diff)
downloadlua-d3bbb34c24cfe3e5296c6a5d3faacf6c8679fe70.tar.gz
lua-d3bbb34c24cfe3e5296c6a5d3faacf6c8679fe70.tar.bz2
lua-d3bbb34c24cfe3e5296c6a5d3faacf6c8679fe70.zip
back to open hashing for the string table (but with a different
'hnext' field, to strings are still collected like all other objects)
Diffstat (limited to 'lstring.c')
-rw-r--r--lstring.c121
1 files changed, 43 insertions, 78 deletions
diff --git a/lstring.c b/lstring.c
index c76b6724..4adfbf41 100644
--- a/lstring.c
+++ b/lstring.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: lstring.c,v 2.32 2013/08/27 20:04:00 roberto Exp roberto $ 2** $Id: lstring.c,v 2.33 2013/08/28 18:30:26 roberto Exp roberto $
3** String table (keeps all strings handled by Lua) 3** String table (keeps all strings handled by Lua)
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -20,13 +20,6 @@
20#include "lstring.h" 20#include "lstring.h"
21 21
22 22
23/* mark for vacant places in hash table */
24#define VACANTK cast(TString *, cast(size_t, -1))
25
26
27/* second hash (for double hash) */
28#define h2(h1,hash,size) lmod(h1 + ((hash % 61) | 1), size)
29
30 23
31/* 24/*
32** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to 25** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to
@@ -74,30 +67,32 @@ unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {
74void luaS_resize (lua_State *L, int newsize) { 67void luaS_resize (lua_State *L, int newsize) {
75 int i; 68 int i;
76 stringtable *tb = &G(L)->strt; 69 stringtable *tb = &G(L)->strt;
77 TString **oldhash = tb->hash; 70 if (newsize > tb->size) { /* grow table if needed */
78 int oldsize = tb->size; 71 luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *);
79 tb->hash = luaM_newvector(L, newsize, TString *); 72 for (i = tb->size; i < newsize; i++)
80 tb->size = newsize; 73 tb->hash[i] = NULL;
81 /* keep load factor below 75% */ 74 }
82 tb->empty = newsize/2 + newsize/4 - tb->nuse; 75 for (i = 0; i < tb->size; i++) { /* rehash */
83 for (i = 0; i < newsize; i++) tb->hash[i] = NULL; 76 TString *p = tb->hash[i];
84 tb->nuse = 0; 77 tb->hash[i] = NULL;
85 /* rehash */ 78 while (p) { /* for each node in the list */
86 for (i = 0; i < oldsize; i++) { 79 TString *hnext = p->tsv.hnext; /* save next */
87 TString *ts = oldhash[i]; 80 unsigned int h = lmod(p->tsv.hash, newsize); /* new position */
88 if (ts != NULL && ts != VACANTK) { 81 p->tsv.hnext = tb->hash[h]; /* chain it */
89 unsigned int hash = ts->tsv.hash; 82 tb->hash[h] = p;
90 int h1 = lmod(hash, tb->size); 83 p = hnext;
91 while (tb->hash[h1] != NULL)
92 h1 = h2(h1, hash, tb->size);
93 tb->hash[h1] = ts;
94 tb->nuse++;
95 } 84 }
96 } 85 }
97 luaM_freearray(L, oldhash, oldsize); 86 if (newsize < tb->size) { /* shrink table if needed */
87 /* vanishing slice should be empty */
88 lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL);
89 luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *);
90 }
91 tb->size = newsize;
98} 92}
99 93
100 94
95
101/* 96/*
102** creates a new string object 97** creates a new string object
103*/ 98*/
@@ -116,32 +111,15 @@ static TString *createstrobj (lua_State *L, const char *str, size_t l,
116} 111}
117 112
118 113
119static void rehash (lua_State *L, stringtable *tb) {
120 int size = tb->size;
121 if (tb->nuse < size / 2) { /* using less than half the size? */
122 if (tb->nuse < size / 4) /* using less than half of that? */
123 size /= 2; /* shrink table */
124 /* else keep size (but reorganize table) */
125 }
126 else { /* table must grow */
127 if (size >= MAX_INT/2) /* avoid arith. overflow */
128 luaD_throw(L, LUA_ERRMEM); /* regular errors need new strings... */
129 size *= 2;
130 }
131 luaS_resize(L, size);
132}
133
134
135LUAI_FUNC void luaS_remove (lua_State *L, TString *ts) { 114LUAI_FUNC void luaS_remove (lua_State *L, TString *ts) {
136 stringtable *tb = &G(L)->strt; 115 stringtable *tb = &G(L)->strt;
137 unsigned int hash = ts->tsv.hash; 116 TString **p = &tb->hash[lmod(ts->tsv.hash, tb->size)];
138 int h1 = lmod(hash, tb->size); 117 while (*p != ts) /* find previous element */
139 while (tb->hash[h1] != ts) { 118 p = &(*p)->tsv.hnext;
140 lua_assert(tb->hash[h1] != NULL); 119 *p = (*p)->tsv.hnext; /* remove element from its list */
141 h1 = h2(h1, hash, tb->size);
142 }
143 tb->hash[h1] = VACANTK;
144 tb->nuse--; 120 tb->nuse--;
121 if (tb->nuse < tb->size/4)
122 luaS_resize(L, tb->size/2);
145} 123}
146 124
147 125
@@ -150,39 +128,26 @@ LUAI_FUNC void luaS_remove (lua_State *L, TString *ts) {
150*/ 128*/
151static TString *internshrstr (lua_State *L, const char *str, size_t l) { 129static TString *internshrstr (lua_State *L, const char *str, size_t l) {
152 TString *ts; 130 TString *ts;
153 unsigned int hash = luaS_hash(str, l, G(L)->seed); 131 global_State *g = G(L);
154 stringtable *tb = &G(L)->strt; 132 unsigned int h = luaS_hash(str, l, g->seed);
155 int vacant = -1; 133 TString **list = &g->strt.hash[lmod(h, g->strt.size)];
156 int h1; 134 for (ts = *list; ts != NULL; ts = ts->tsv.hnext) {
157 h1 = lmod(hash, tb->size); /* previous call can changed 'size' */ 135 if (l == ts->tsv.len &&
158 while ((ts = tb->hash[h1]) != NULL) { /* search the string in hash table */ 136 (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
159 if (ts == VACANTK) {
160 if (vacant < 0) vacant = h1; /* keep track of first vacant place */
161 }
162 else if (l == ts->tsv.len &&
163 (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
164 /* found! */ 137 /* found! */
165 if (isdead(G(L), obj2gco(ts))) /* dead (but was not collected yet)? */ 138 if (isdead(g, obj2gco(ts))) /* dead (but not collected yet)? */
166 changewhite(obj2gco(ts)); /* resurrect it */ 139 changewhite(obj2gco(ts)); /* resurrect it */
167 if (vacant >= 0) { /* is there a better place for this string? */ 140 return ts;
168 tb->hash[vacant] = ts; /* move it up the line */
169 tb->hash[h1] = VACANTK;
170 }
171 return ts; /* found */
172 } 141 }
173 h1 = h2(h1, hash, tb->size);
174 } 142 }
175 if (tb->empty <= 0) { /* no more empty spaces? */ 143 if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) {
176 rehash(L, tb); 144 luaS_resize(L, g->strt.size * 2);
177 return internshrstr(L, str, l); /* recompute insertion with new size */ 145 list = &g->strt.hash[lmod(h, g->strt.size)]; /* recompute with new size */
178 } 146 }
179 ts = createstrobj(L, str, l, LUA_TSHRSTR, hash); 147 ts = createstrobj(L, str, l, LUA_TSHRSTR, h);
180 tb->nuse++; 148 ts->tsv.hnext = *list;
181 if (vacant < 0) /* found no vacant place? */ 149 *list = ts;
182 tb->empty--; /* will have to use the empty place */ 150 g->strt.nuse++;
183 else
184 h1 = vacant; /* use vacant place */
185 tb->hash[h1] = ts;
186 return ts; 151 return ts;
187} 152}
188 153