diff options
author | Li Jin <dragon-fly@qq.com> | 2022-10-31 11:32:33 +0800 |
---|---|---|
committer | Li Jin <dragon-fly@qq.com> | 2022-11-09 11:29:32 +0800 |
commit | 417ec1a37922c6178900adfec70628cad46731ff (patch) | |
tree | a5a2d74927ad2c41b5a16264a78409e1c0334b72 /win-build/Lua53/ltable.c | |
parent | 3dd607c8887d2fe0186668aabca31bb84a41e2da (diff) | |
download | yuescript-417ec1a37922c6178900adfec70628cad46731ff.tar.gz yuescript-417ec1a37922c6178900adfec70628cad46731ff.tar.bz2 yuescript-417ec1a37922c6178900adfec70628cad46731ff.zip |
fix issue #112 and issue #113.
Diffstat (limited to 'win-build/Lua53/ltable.c')
-rw-r--r-- | win-build/Lua53/ltable.c | 688 |
1 files changed, 688 insertions, 0 deletions
diff --git a/win-build/Lua53/ltable.c b/win-build/Lua53/ltable.c new file mode 100644 index 0000000..ea4fe7f --- /dev/null +++ b/win-build/Lua53/ltable.c | |||
@@ -0,0 +1,688 @@ | |||
1 | /* | ||
2 | ** $Id: ltable.c,v 2.118.1.4 2018/06/08 16:22:51 roberto Exp $ | ||
3 | ** Lua tables (hash) | ||
4 | ** See Copyright Notice in lua.h | ||
5 | */ | ||
6 | |||
7 | #define ltable_c | ||
8 | #define LUA_CORE | ||
9 | |||
10 | #include "lprefix.h" | ||
11 | |||
12 | |||
13 | /* | ||
14 | ** Implementation of tables (aka arrays, objects, or hash tables). | ||
15 | ** Tables keep its elements in two parts: an array part and a hash part. | ||
16 | ** Non-negative integer keys are all candidates to be kept in the array | ||
17 | ** part. The actual size of the array is the largest 'n' such that | ||
18 | ** more than half the slots between 1 and n are in use. | ||
19 | ** Hash uses a mix of chained scatter table with Brent's variation. | ||
20 | ** A main invariant of these tables is that, if an element is not | ||
21 | ** in its main position (i.e. the 'original' position that its hash gives | ||
22 | ** to it), then the colliding element is in its own main position. | ||
23 | ** Hence even when the load factor reaches 100%, performance remains good. | ||
24 | */ | ||
25 | |||
26 | #include <math.h> | ||
27 | #include <limits.h> | ||
28 | |||
29 | #include "lua.h" | ||
30 | |||
31 | #include "ldebug.h" | ||
32 | #include "ldo.h" | ||
33 | #include "lgc.h" | ||
34 | #include "lmem.h" | ||
35 | #include "lobject.h" | ||
36 | #include "lstate.h" | ||
37 | #include "lstring.h" | ||
38 | #include "ltable.h" | ||
39 | #include "lvm.h" | ||
40 | |||
41 | |||
42 | /* | ||
43 | ** Maximum size of array part (MAXASIZE) is 2^MAXABITS. MAXABITS is | ||
44 | ** the largest integer such that MAXASIZE fits in an unsigned int. | ||
45 | */ | ||
46 | #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1) | ||
47 | #define MAXASIZE (1u << MAXABITS) | ||
48 | |||
49 | /* | ||
50 | ** Maximum size of hash part is 2^MAXHBITS. MAXHBITS is the largest | ||
51 | ** integer such that 2^MAXHBITS fits in a signed int. (Note that the | ||
52 | ** maximum number of elements in a table, 2^MAXABITS + 2^MAXHBITS, still | ||
53 | ** fits comfortably in an unsigned int.) | ||
54 | */ | ||
55 | #define MAXHBITS (MAXABITS - 1) | ||
56 | |||
57 | |||
58 | #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) | ||
59 | |||
60 | #define hashstr(t,str) hashpow2(t, (str)->hash) | ||
61 | #define hashboolean(t,p) hashpow2(t, p) | ||
62 | #define hashint(t,i) hashpow2(t, i) | ||
63 | |||
64 | |||
65 | /* | ||
66 | ** for some types, it is better to avoid modulus by power of 2, as | ||
67 | ** they tend to have many 2 factors. | ||
68 | */ | ||
69 | #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) | ||
70 | |||
71 | |||
72 | #define hashpointer(t,p) hashmod(t, point2uint(p)) | ||
73 | |||
74 | |||
75 | #define dummynode (&dummynode_) | ||
76 | |||
77 | static const Node dummynode_ = { | ||
78 | {NILCONSTANT}, /* value */ | ||
79 | {{NILCONSTANT, 0}} /* key */ | ||
80 | }; | ||
81 | |||
82 | |||
83 | /* | ||
84 | ** Hash for floating-point numbers. | ||
85 | ** The main computation should be just | ||
86 | ** n = frexp(n, &i); return (n * INT_MAX) + i | ||
87 | ** but there are some numerical subtleties. | ||
88 | ** In a two-complement representation, INT_MAX does not has an exact | ||
89 | ** representation as a float, but INT_MIN does; because the absolute | ||
90 | ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the | ||
91 | ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal | ||
92 | ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when | ||
93 | ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with | ||
94 | ** INT_MIN. | ||
95 | */ | ||
96 | #if !defined(l_hashfloat) | ||
97 | static int l_hashfloat (lua_Number n) { | ||
98 | int i; | ||
99 | lua_Integer ni; | ||
100 | n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN); | ||
101 | if (!lua_numbertointeger(n, &ni)) { /* is 'n' inf/-inf/NaN? */ | ||
102 | lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL)); | ||
103 | return 0; | ||
104 | } | ||
105 | else { /* normal case */ | ||
106 | unsigned int u = cast(unsigned int, i) + cast(unsigned int, ni); | ||
107 | return cast_int(u <= cast(unsigned int, INT_MAX) ? u : ~u); | ||
108 | } | ||
109 | } | ||
110 | #endif | ||
111 | |||
112 | |||
113 | /* | ||
114 | ** returns the 'main' position of an element in a table (that is, the index | ||
115 | ** of its hash value) | ||
116 | */ | ||
117 | static Node *mainposition (const Table *t, const TValue *key) { | ||
118 | switch (ttype(key)) { | ||
119 | case LUA_TNUMINT: | ||
120 | return hashint(t, ivalue(key)); | ||
121 | case LUA_TNUMFLT: | ||
122 | return hashmod(t, l_hashfloat(fltvalue(key))); | ||
123 | case LUA_TSHRSTR: | ||
124 | return hashstr(t, tsvalue(key)); | ||
125 | case LUA_TLNGSTR: | ||
126 | return hashpow2(t, luaS_hashlongstr(tsvalue(key))); | ||
127 | case LUA_TBOOLEAN: | ||
128 | return hashboolean(t, bvalue(key)); | ||
129 | case LUA_TLIGHTUSERDATA: | ||
130 | return hashpointer(t, pvalue(key)); | ||
131 | case LUA_TLCF: | ||
132 | return hashpointer(t, fvalue(key)); | ||
133 | default: | ||
134 | lua_assert(!ttisdeadkey(key)); | ||
135 | return hashpointer(t, gcvalue(key)); | ||
136 | } | ||
137 | } | ||
138 | |||
139 | |||
140 | /* | ||
141 | ** returns the index for 'key' if 'key' is an appropriate key to live in | ||
142 | ** the array part of the table, 0 otherwise. | ||
143 | */ | ||
144 | static unsigned int arrayindex (const TValue *key) { | ||
145 | if (ttisinteger(key)) { | ||
146 | lua_Integer k = ivalue(key); | ||
147 | if (0 < k && (lua_Unsigned)k <= MAXASIZE) | ||
148 | return cast(unsigned int, k); /* 'key' is an appropriate array index */ | ||
149 | } | ||
150 | return 0; /* 'key' did not match some condition */ | ||
151 | } | ||
152 | |||
153 | |||
154 | /* | ||
155 | ** returns the index of a 'key' for table traversals. First goes all | ||
156 | ** elements in the array part, then elements in the hash part. The | ||
157 | ** beginning of a traversal is signaled by 0. | ||
158 | */ | ||
159 | static unsigned int findindex (lua_State *L, Table *t, StkId key) { | ||
160 | unsigned int i; | ||
161 | if (ttisnil(key)) return 0; /* first iteration */ | ||
162 | i = arrayindex(key); | ||
163 | if (i != 0 && i <= t->sizearray) /* is 'key' inside array part? */ | ||
164 | return i; /* yes; that's the index */ | ||
165 | else { | ||
166 | int nx; | ||
167 | Node *n = mainposition(t, key); | ||
168 | for (;;) { /* check whether 'key' is somewhere in the chain */ | ||
169 | /* key may be dead already, but it is ok to use it in 'next' */ | ||
170 | if (luaV_rawequalobj(gkey(n), key) || | ||
171 | (ttisdeadkey(gkey(n)) && iscollectable(key) && | ||
172 | deadvalue(gkey(n)) == gcvalue(key))) { | ||
173 | i = cast_int(n - gnode(t, 0)); /* key index in hash table */ | ||
174 | /* hash elements are numbered after array ones */ | ||
175 | return (i + 1) + t->sizearray; | ||
176 | } | ||
177 | nx = gnext(n); | ||
178 | if (nx == 0) | ||
179 | luaG_runerror(L, "invalid key to 'next'"); /* key not found */ | ||
180 | else n += nx; | ||
181 | } | ||
182 | } | ||
183 | } | ||
184 | |||
185 | |||
186 | int luaH_next (lua_State *L, Table *t, StkId key) { | ||
187 | unsigned int i = findindex(L, t, key); /* find original element */ | ||
188 | for (; i < t->sizearray; i++) { /* try first array part */ | ||
189 | if (!ttisnil(&t->array[i])) { /* a non-nil value? */ | ||
190 | setivalue(key, i + 1); | ||
191 | setobj2s(L, key+1, &t->array[i]); | ||
192 | return 1; | ||
193 | } | ||
194 | } | ||
195 | for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) { /* hash part */ | ||
196 | if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */ | ||
197 | setobj2s(L, key, gkey(gnode(t, i))); | ||
198 | setobj2s(L, key+1, gval(gnode(t, i))); | ||
199 | return 1; | ||
200 | } | ||
201 | } | ||
202 | return 0; /* no more elements */ | ||
203 | } | ||
204 | |||
205 | |||
206 | /* | ||
207 | ** {============================================================= | ||
208 | ** Rehash | ||
209 | ** ============================================================== | ||
210 | */ | ||
211 | |||
212 | /* | ||
213 | ** Compute the optimal size for the array part of table 't'. 'nums' is a | ||
214 | ** "count array" where 'nums[i]' is the number of integers in the table | ||
215 | ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of | ||
216 | ** integer keys in the table and leaves with the number of keys that | ||
217 | ** will go to the array part; return the optimal size. | ||
218 | */ | ||
219 | static unsigned int computesizes (unsigned int nums[], unsigned int *pna) { | ||
220 | int i; | ||
221 | unsigned int twotoi; /* 2^i (candidate for optimal size) */ | ||
222 | unsigned int a = 0; /* number of elements smaller than 2^i */ | ||
223 | unsigned int na = 0; /* number of elements to go to array part */ | ||
224 | unsigned int optimal = 0; /* optimal size for array part */ | ||
225 | /* loop while keys can fill more than half of total size */ | ||
226 | for (i = 0, twotoi = 1; | ||
227 | twotoi > 0 && *pna > twotoi / 2; | ||
228 | i++, twotoi *= 2) { | ||
229 | if (nums[i] > 0) { | ||
230 | a += nums[i]; | ||
231 | if (a > twotoi/2) { /* more than half elements present? */ | ||
232 | optimal = twotoi; /* optimal size (till now) */ | ||
233 | na = a; /* all elements up to 'optimal' will go to array part */ | ||
234 | } | ||
235 | } | ||
236 | } | ||
237 | lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal); | ||
238 | *pna = na; | ||
239 | return optimal; | ||
240 | } | ||
241 | |||
242 | |||
243 | static int countint (const TValue *key, unsigned int *nums) { | ||
244 | unsigned int k = arrayindex(key); | ||
245 | if (k != 0) { /* is 'key' an appropriate array index? */ | ||
246 | nums[luaO_ceillog2(k)]++; /* count as such */ | ||
247 | return 1; | ||
248 | } | ||
249 | else | ||
250 | return 0; | ||
251 | } | ||
252 | |||
253 | |||
254 | /* | ||
255 | ** Count keys in array part of table 't': Fill 'nums[i]' with | ||
256 | ** number of keys that will go into corresponding slice and return | ||
257 | ** total number of non-nil keys. | ||
258 | */ | ||
259 | static unsigned int numusearray (const Table *t, unsigned int *nums) { | ||
260 | int lg; | ||
261 | unsigned int ttlg; /* 2^lg */ | ||
262 | unsigned int ause = 0; /* summation of 'nums' */ | ||
263 | unsigned int i = 1; /* count to traverse all array keys */ | ||
264 | /* traverse each slice */ | ||
265 | for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) { | ||
266 | unsigned int lc = 0; /* counter */ | ||
267 | unsigned int lim = ttlg; | ||
268 | if (lim > t->sizearray) { | ||
269 | lim = t->sizearray; /* adjust upper limit */ | ||
270 | if (i > lim) | ||
271 | break; /* no more elements to count */ | ||
272 | } | ||
273 | /* count elements in range (2^(lg - 1), 2^lg] */ | ||
274 | for (; i <= lim; i++) { | ||
275 | if (!ttisnil(&t->array[i-1])) | ||
276 | lc++; | ||
277 | } | ||
278 | nums[lg] += lc; | ||
279 | ause += lc; | ||
280 | } | ||
281 | return ause; | ||
282 | } | ||
283 | |||
284 | |||
285 | static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) { | ||
286 | int totaluse = 0; /* total number of elements */ | ||
287 | int ause = 0; /* elements added to 'nums' (can go to array part) */ | ||
288 | int i = sizenode(t); | ||
289 | while (i--) { | ||
290 | Node *n = &t->node[i]; | ||
291 | if (!ttisnil(gval(n))) { | ||
292 | ause += countint(gkey(n), nums); | ||
293 | totaluse++; | ||
294 | } | ||
295 | } | ||
296 | *pna += ause; | ||
297 | return totaluse; | ||
298 | } | ||
299 | |||
300 | |||
301 | static void setarrayvector (lua_State *L, Table *t, unsigned int size) { | ||
302 | unsigned int i; | ||
303 | luaM_reallocvector(L, t->array, t->sizearray, size, TValue); | ||
304 | for (i=t->sizearray; i<size; i++) | ||
305 | setnilvalue(&t->array[i]); | ||
306 | t->sizearray = size; | ||
307 | } | ||
308 | |||
309 | |||
310 | static void setnodevector (lua_State *L, Table *t, unsigned int size) { | ||
311 | if (size == 0) { /* no elements to hash part? */ | ||
312 | t->node = cast(Node *, dummynode); /* use common 'dummynode' */ | ||
313 | t->lsizenode = 0; | ||
314 | t->lastfree = NULL; /* signal that it is using dummy node */ | ||
315 | } | ||
316 | else { | ||
317 | int i; | ||
318 | int lsize = luaO_ceillog2(size); | ||
319 | if (lsize > MAXHBITS) | ||
320 | luaG_runerror(L, "table overflow"); | ||
321 | size = twoto(lsize); | ||
322 | t->node = luaM_newvector(L, size, Node); | ||
323 | for (i = 0; i < (int)size; i++) { | ||
324 | Node *n = gnode(t, i); | ||
325 | gnext(n) = 0; | ||
326 | setnilvalue(wgkey(n)); | ||
327 | setnilvalue(gval(n)); | ||
328 | } | ||
329 | t->lsizenode = cast_byte(lsize); | ||
330 | t->lastfree = gnode(t, size); /* all positions are free */ | ||
331 | } | ||
332 | } | ||
333 | |||
334 | |||
335 | typedef struct { | ||
336 | Table *t; | ||
337 | unsigned int nhsize; | ||
338 | } AuxsetnodeT; | ||
339 | |||
340 | |||
341 | static void auxsetnode (lua_State *L, void *ud) { | ||
342 | AuxsetnodeT *asn = cast(AuxsetnodeT *, ud); | ||
343 | setnodevector(L, asn->t, asn->nhsize); | ||
344 | } | ||
345 | |||
346 | |||
347 | void luaH_resize (lua_State *L, Table *t, unsigned int nasize, | ||
348 | unsigned int nhsize) { | ||
349 | unsigned int i; | ||
350 | int j; | ||
351 | AuxsetnodeT asn; | ||
352 | unsigned int oldasize = t->sizearray; | ||
353 | int oldhsize = allocsizenode(t); | ||
354 | Node *nold = t->node; /* save old hash ... */ | ||
355 | if (nasize > oldasize) /* array part must grow? */ | ||
356 | setarrayvector(L, t, nasize); | ||
357 | /* create new hash part with appropriate size */ | ||
358 | asn.t = t; asn.nhsize = nhsize; | ||
359 | if (luaD_rawrunprotected(L, auxsetnode, &asn) != LUA_OK) { /* mem. error? */ | ||
360 | setarrayvector(L, t, oldasize); /* array back to its original size */ | ||
361 | luaD_throw(L, LUA_ERRMEM); /* rethrow memory error */ | ||
362 | } | ||
363 | if (nasize < oldasize) { /* array part must shrink? */ | ||
364 | t->sizearray = nasize; | ||
365 | /* re-insert elements from vanishing slice */ | ||
366 | for (i=nasize; i<oldasize; i++) { | ||
367 | if (!ttisnil(&t->array[i])) | ||
368 | luaH_setint(L, t, i + 1, &t->array[i]); | ||
369 | } | ||
370 | /* shrink array */ | ||
371 | luaM_reallocvector(L, t->array, oldasize, nasize, TValue); | ||
372 | } | ||
373 | /* re-insert elements from hash part */ | ||
374 | for (j = oldhsize - 1; j >= 0; j--) { | ||
375 | Node *old = nold + j; | ||
376 | if (!ttisnil(gval(old))) { | ||
377 | /* doesn't need barrier/invalidate cache, as entry was | ||
378 | already present in the table */ | ||
379 | setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old)); | ||
380 | } | ||
381 | } | ||
382 | if (oldhsize > 0) /* not the dummy node? */ | ||
383 | luaM_freearray(L, nold, cast(size_t, oldhsize)); /* free old hash */ | ||
384 | } | ||
385 | |||
386 | |||
387 | void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) { | ||
388 | int nsize = allocsizenode(t); | ||
389 | luaH_resize(L, t, nasize, nsize); | ||
390 | } | ||
391 | |||
392 | /* | ||
393 | ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i | ||
394 | */ | ||
395 | static void rehash (lua_State *L, Table *t, const TValue *ek) { | ||
396 | unsigned int asize; /* optimal size for array part */ | ||
397 | unsigned int na; /* number of keys in the array part */ | ||
398 | unsigned int nums[MAXABITS + 1]; | ||
399 | int i; | ||
400 | int totaluse; | ||
401 | for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */ | ||
402 | na = numusearray(t, nums); /* count keys in array part */ | ||
403 | totaluse = na; /* all those keys are integer keys */ | ||
404 | totaluse += numusehash(t, nums, &na); /* count keys in hash part */ | ||
405 | /* count extra key */ | ||
406 | na += countint(ek, nums); | ||
407 | totaluse++; | ||
408 | /* compute new size for array part */ | ||
409 | asize = computesizes(nums, &na); | ||
410 | /* resize the table to new computed sizes */ | ||
411 | luaH_resize(L, t, asize, totaluse - na); | ||
412 | } | ||
413 | |||
414 | |||
415 | |||
416 | /* | ||
417 | ** }============================================================= | ||
418 | */ | ||
419 | |||
420 | |||
421 | Table *luaH_new (lua_State *L) { | ||
422 | GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table)); | ||
423 | Table *t = gco2t(o); | ||
424 | t->metatable = NULL; | ||
425 | t->flags = cast_byte(~0); | ||
426 | t->array = NULL; | ||
427 | t->sizearray = 0; | ||
428 | setnodevector(L, t, 0); | ||
429 | return t; | ||
430 | } | ||
431 | |||
432 | |||
433 | void luaH_free (lua_State *L, Table *t) { | ||
434 | if (!isdummy(t)) | ||
435 | luaM_freearray(L, t->node, cast(size_t, sizenode(t))); | ||
436 | luaM_freearray(L, t->array, t->sizearray); | ||
437 | luaM_free(L, t); | ||
438 | } | ||
439 | |||
440 | |||
441 | static Node *getfreepos (Table *t) { | ||
442 | if (!isdummy(t)) { | ||
443 | while (t->lastfree > t->node) { | ||
444 | t->lastfree--; | ||
445 | if (ttisnil(gkey(t->lastfree))) | ||
446 | return t->lastfree; | ||
447 | } | ||
448 | } | ||
449 | return NULL; /* could not find a free place */ | ||
450 | } | ||
451 | |||
452 | |||
453 | |||
454 | /* | ||
455 | ** inserts a new key into a hash table; first, check whether key's main | ||
456 | ** position is free. If not, check whether colliding node is in its main | ||
457 | ** position or not: if it is not, move colliding node to an empty place and | ||
458 | ** put new key in its main position; otherwise (colliding node is in its main | ||
459 | ** position), new key goes to an empty position. | ||
460 | */ | ||
461 | TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) { | ||
462 | Node *mp; | ||
463 | TValue aux; | ||
464 | if (ttisnil(key)) luaG_runerror(L, "table index is nil"); | ||
465 | else if (ttisfloat(key)) { | ||
466 | lua_Integer k; | ||
467 | if (luaV_tointeger(key, &k, 0)) { /* does index fit in an integer? */ | ||
468 | setivalue(&aux, k); | ||
469 | key = &aux; /* insert it as an integer */ | ||
470 | } | ||
471 | else if (luai_numisnan(fltvalue(key))) | ||
472 | luaG_runerror(L, "table index is NaN"); | ||
473 | } | ||
474 | mp = mainposition(t, key); | ||
475 | if (!ttisnil(gval(mp)) || isdummy(t)) { /* main position is taken? */ | ||
476 | Node *othern; | ||
477 | Node *f = getfreepos(t); /* get a free place */ | ||
478 | if (f == NULL) { /* cannot find a free place? */ | ||
479 | rehash(L, t, key); /* grow table */ | ||
480 | /* whatever called 'newkey' takes care of TM cache */ | ||
481 | return luaH_set(L, t, key); /* insert key into grown table */ | ||
482 | } | ||
483 | lua_assert(!isdummy(t)); | ||
484 | othern = mainposition(t, gkey(mp)); | ||
485 | if (othern != mp) { /* is colliding node out of its main position? */ | ||
486 | /* yes; move colliding node into free position */ | ||
487 | while (othern + gnext(othern) != mp) /* find previous */ | ||
488 | othern += gnext(othern); | ||
489 | gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */ | ||
490 | *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */ | ||
491 | if (gnext(mp) != 0) { | ||
492 | gnext(f) += cast_int(mp - f); /* correct 'next' */ | ||
493 | gnext(mp) = 0; /* now 'mp' is free */ | ||
494 | } | ||
495 | setnilvalue(gval(mp)); | ||
496 | } | ||
497 | else { /* colliding node is in its own main position */ | ||
498 | /* new node will go into free position */ | ||
499 | if (gnext(mp) != 0) | ||
500 | gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */ | ||
501 | else lua_assert(gnext(f) == 0); | ||
502 | gnext(mp) = cast_int(f - mp); | ||
503 | mp = f; | ||
504 | } | ||
505 | } | ||
506 | setnodekey(L, &mp->i_key, key); | ||
507 | luaC_barrierback(L, t, key); | ||
508 | lua_assert(ttisnil(gval(mp))); | ||
509 | return gval(mp); | ||
510 | } | ||
511 | |||
512 | |||
513 | /* | ||
514 | ** search function for integers | ||
515 | */ | ||
516 | const TValue *luaH_getint (Table *t, lua_Integer key) { | ||
517 | /* (1 <= key && key <= t->sizearray) */ | ||
518 | if (l_castS2U(key) - 1 < t->sizearray) | ||
519 | return &t->array[key - 1]; | ||
520 | else { | ||
521 | Node *n = hashint(t, key); | ||
522 | for (;;) { /* check whether 'key' is somewhere in the chain */ | ||
523 | if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key) | ||
524 | return gval(n); /* that's it */ | ||
525 | else { | ||
526 | int nx = gnext(n); | ||
527 | if (nx == 0) break; | ||
528 | n += nx; | ||
529 | } | ||
530 | } | ||
531 | return luaO_nilobject; | ||
532 | } | ||
533 | } | ||
534 | |||
535 | |||
536 | /* | ||
537 | ** search function for short strings | ||
538 | */ | ||
539 | const TValue *luaH_getshortstr (Table *t, TString *key) { | ||
540 | Node *n = hashstr(t, key); | ||
541 | lua_assert(key->tt == LUA_TSHRSTR); | ||
542 | for (;;) { /* check whether 'key' is somewhere in the chain */ | ||
543 | const TValue *k = gkey(n); | ||
544 | if (ttisshrstring(k) && eqshrstr(tsvalue(k), key)) | ||
545 | return gval(n); /* that's it */ | ||
546 | else { | ||
547 | int nx = gnext(n); | ||
548 | if (nx == 0) | ||
549 | return luaO_nilobject; /* not found */ | ||
550 | n += nx; | ||
551 | } | ||
552 | } | ||
553 | } | ||
554 | |||
555 | |||
556 | /* | ||
557 | ** "Generic" get version. (Not that generic: not valid for integers, | ||
558 | ** which may be in array part, nor for floats with integral values.) | ||
559 | */ | ||
560 | static const TValue *getgeneric (Table *t, const TValue *key) { | ||
561 | Node *n = mainposition(t, key); | ||
562 | for (;;) { /* check whether 'key' is somewhere in the chain */ | ||
563 | if (luaV_rawequalobj(gkey(n), key)) | ||
564 | return gval(n); /* that's it */ | ||
565 | else { | ||
566 | int nx = gnext(n); | ||
567 | if (nx == 0) | ||
568 | return luaO_nilobject; /* not found */ | ||
569 | n += nx; | ||
570 | } | ||
571 | } | ||
572 | } | ||
573 | |||
574 | |||
575 | const TValue *luaH_getstr (Table *t, TString *key) { | ||
576 | if (key->tt == LUA_TSHRSTR) | ||
577 | return luaH_getshortstr(t, key); | ||
578 | else { /* for long strings, use generic case */ | ||
579 | TValue ko; | ||
580 | setsvalue(cast(lua_State *, NULL), &ko, key); | ||
581 | return getgeneric(t, &ko); | ||
582 | } | ||
583 | } | ||
584 | |||
585 | |||
586 | /* | ||
587 | ** main search function | ||
588 | */ | ||
589 | const TValue *luaH_get (Table *t, const TValue *key) { | ||
590 | switch (ttype(key)) { | ||
591 | case LUA_TSHRSTR: return luaH_getshortstr(t, tsvalue(key)); | ||
592 | case LUA_TNUMINT: return luaH_getint(t, ivalue(key)); | ||
593 | case LUA_TNIL: return luaO_nilobject; | ||
594 | case LUA_TNUMFLT: { | ||
595 | lua_Integer k; | ||
596 | if (luaV_tointeger(key, &k, 0)) /* index is int? */ | ||
597 | return luaH_getint(t, k); /* use specialized version */ | ||
598 | /* else... */ | ||
599 | } /* FALLTHROUGH */ | ||
600 | default: | ||
601 | return getgeneric(t, key); | ||
602 | } | ||
603 | } | ||
604 | |||
605 | |||
606 | /* | ||
607 | ** beware: when using this function you probably need to check a GC | ||
608 | ** barrier and invalidate the TM cache. | ||
609 | */ | ||
610 | TValue *luaH_set (lua_State *L, Table *t, const TValue *key) { | ||
611 | const TValue *p = luaH_get(t, key); | ||
612 | if (p != luaO_nilobject) | ||
613 | return cast(TValue *, p); | ||
614 | else return luaH_newkey(L, t, key); | ||
615 | } | ||
616 | |||
617 | |||
618 | void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { | ||
619 | const TValue *p = luaH_getint(t, key); | ||
620 | TValue *cell; | ||
621 | if (p != luaO_nilobject) | ||
622 | cell = cast(TValue *, p); | ||
623 | else { | ||
624 | TValue k; | ||
625 | setivalue(&k, key); | ||
626 | cell = luaH_newkey(L, t, &k); | ||
627 | } | ||
628 | setobj2t(L, cell, value); | ||
629 | } | ||
630 | |||
631 | |||
632 | static lua_Unsigned unbound_search (Table *t, lua_Unsigned j) { | ||
633 | lua_Unsigned i = j; /* i is zero or a present index */ | ||
634 | j++; | ||
635 | /* find 'i' and 'j' such that i is present and j is not */ | ||
636 | while (!ttisnil(luaH_getint(t, j))) { | ||
637 | i = j; | ||
638 | if (j > l_castS2U(LUA_MAXINTEGER) / 2) { /* overflow? */ | ||
639 | /* table was built with bad purposes: resort to linear search */ | ||
640 | i = 1; | ||
641 | while (!ttisnil(luaH_getint(t, i))) i++; | ||
642 | return i - 1; | ||
643 | } | ||
644 | j *= 2; | ||
645 | } | ||
646 | /* now do a binary search between them */ | ||
647 | while (j - i > 1) { | ||
648 | lua_Unsigned m = (i+j)/2; | ||
649 | if (ttisnil(luaH_getint(t, m))) j = m; | ||
650 | else i = m; | ||
651 | } | ||
652 | return i; | ||
653 | } | ||
654 | |||
655 | |||
656 | /* | ||
657 | ** Try to find a boundary in table 't'. A 'boundary' is an integer index | ||
658 | ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil). | ||
659 | */ | ||
660 | lua_Unsigned luaH_getn (Table *t) { | ||
661 | unsigned int j = t->sizearray; | ||
662 | if (j > 0 && ttisnil(&t->array[j - 1])) { | ||
663 | /* there is a boundary in the array part: (binary) search for it */ | ||
664 | unsigned int i = 0; | ||
665 | while (j - i > 1) { | ||
666 | unsigned int m = (i+j)/2; | ||
667 | if (ttisnil(&t->array[m - 1])) j = m; | ||
668 | else i = m; | ||
669 | } | ||
670 | return i; | ||
671 | } | ||
672 | /* else must find a boundary in hash part */ | ||
673 | else if (isdummy(t)) /* hash part is empty? */ | ||
674 | return j; /* that is easy... */ | ||
675 | else return unbound_search(t, j); | ||
676 | } | ||
677 | |||
678 | |||
679 | |||
680 | #if defined(LUA_DEBUG) | ||
681 | |||
682 | Node *luaH_mainposition (const Table *t, const TValue *key) { | ||
683 | return mainposition(t, key); | ||
684 | } | ||
685 | |||
686 | int luaH_isdummy (const Table *t) { return isdummy(t); } | ||
687 | |||
688 | #endif | ||