diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2013-09-05 16:31:49 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2013-09-05 16:31:49 -0300 |
commit | d3bbb34c24cfe3e5296c6a5d3faacf6c8679fe70 (patch) | |
tree | b245be2289ab4fdbb558a0f52a81dd5631871ee3 /lstring.c | |
parent | 0ad15fc10041f59b5466fe902637b1a2fb64565d (diff) | |
download | lua-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.c | 121 |
1 files changed, 43 insertions, 78 deletions
@@ -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) { | |||
74 | void luaS_resize (lua_State *L, int newsize) { | 67 | void 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 | ||
119 | static 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 | |||
135 | LUAI_FUNC void luaS_remove (lua_State *L, TString *ts) { | 114 | LUAI_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 | */ |
151 | static TString *internshrstr (lua_State *L, const char *str, size_t l) { | 129 | static 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 | ||