/src/testdir/build/lua-master/source/ltable.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | ** $Id: ltable.c $ |
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 | | ** MAXABITS is the largest integer such that MAXASIZE fits in an |
44 | | ** unsigned int. |
45 | | */ |
46 | 99.5k | #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1) |
47 | | |
48 | | |
49 | | /* |
50 | | ** MAXASIZE is the maximum size of the array part. It is the minimum |
51 | | ** between 2^MAXABITS and the maximum size that, measured in bytes, |
52 | | ** fits in a 'size_t'. |
53 | | */ |
54 | 31.2k | #define MAXASIZE luaM_limitN(1u << MAXABITS, TValue) |
55 | | |
56 | | /* |
57 | | ** MAXHBITS is the largest integer such that 2^MAXHBITS fits in a |
58 | | ** signed int. |
59 | | */ |
60 | 5.66k | #define MAXHBITS (MAXABITS - 1) |
61 | | |
62 | | |
63 | | /* |
64 | | ** MAXHSIZE is the maximum size of the hash part. It is the minimum |
65 | | ** between 2^MAXHBITS and the maximum size such that, measured in bytes, |
66 | | ** it fits in a 'size_t'. |
67 | | */ |
68 | 2.83k | #define MAXHSIZE luaM_limitN(1u << MAXHBITS, Node) |
69 | | |
70 | | |
71 | | /* |
72 | | ** When the original hash value is good, hashing by a power of 2 |
73 | | ** avoids the cost of '%'. |
74 | | */ |
75 | 29.2M | #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) |
76 | | |
77 | | /* |
78 | | ** for other types, it is better to avoid modulo by power of 2, as |
79 | | ** they can have many 2 factors. |
80 | | */ |
81 | 1.44M | #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) |
82 | | |
83 | | |
84 | 29.1M | #define hashstr(t,str) hashpow2(t, (str)->hash) |
85 | 11.9k | #define hashboolean(t,p) hashpow2(t, p) |
86 | | |
87 | | |
88 | 1.26k | #define hashpointer(t,p) hashmod(t, point2uint(p)) |
89 | | |
90 | | |
91 | | #define dummynode (&dummynode_) |
92 | | |
93 | | static const Node dummynode_ = { |
94 | | {{NULL}, LUA_VEMPTY, /* value's value and type */ |
95 | | LUA_VNIL, 0, {NULL}} /* key type, next, and key value */ |
96 | | }; |
97 | | |
98 | | |
99 | | static const TValue absentkey = {ABSTKEYCONSTANT}; |
100 | | |
101 | | |
102 | | /* |
103 | | ** Hash for integers. To allow a good hash, use the remainder operator |
104 | | ** ('%'). If integer fits as a non-negative int, compute an int |
105 | | ** remainder, which is faster. Otherwise, use an unsigned-integer |
106 | | ** remainder, which uses all bits and ensures a non-negative result. |
107 | | */ |
108 | 1.35M | static Node *hashint (const Table *t, lua_Integer i) { |
109 | 1.35M | lua_Unsigned ui = l_castS2U(i); |
110 | 1.35M | if (ui <= cast_uint(INT_MAX)) |
111 | 492k | return hashmod(t, cast_int(ui)); |
112 | 859k | else |
113 | 859k | return hashmod(t, ui); |
114 | 1.35M | } |
115 | | |
116 | | |
117 | | /* |
118 | | ** Hash for floating-point numbers. |
119 | | ** The main computation should be just |
120 | | ** n = frexp(n, &i); return (n * INT_MAX) + i |
121 | | ** but there are some numerical subtleties. |
122 | | ** In a two-complement representation, INT_MAX does not has an exact |
123 | | ** representation as a float, but INT_MIN does; because the absolute |
124 | | ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the |
125 | | ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal |
126 | | ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when |
127 | | ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with |
128 | | ** INT_MIN. |
129 | | */ |
130 | | #if !defined(l_hashfloat) |
131 | 89.8k | static int l_hashfloat (lua_Number n) { |
132 | 89.8k | int i; |
133 | 89.8k | lua_Integer ni; |
134 | 89.8k | n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN); |
135 | 89.8k | if (!lua_numbertointeger(n, &ni)) { /* is 'n' inf/-inf/NaN? */ |
136 | 2.49k | lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL)); |
137 | 2.49k | return 0; |
138 | 2.49k | } |
139 | 87.3k | else { /* normal case */ |
140 | 87.3k | unsigned int u = cast_uint(i) + cast_uint(ni); |
141 | 87.3k | return cast_int(u <= cast_uint(INT_MAX) ? u : ~u); |
142 | 87.3k | } |
143 | 89.8k | } |
144 | | #endif |
145 | | |
146 | | |
147 | | /* |
148 | | ** returns the 'main' position of an element in a table (that is, |
149 | | ** the index of its hash value). |
150 | | */ |
151 | 316k | static Node *mainpositionTV (const Table *t, const TValue *key) { |
152 | 316k | switch (ttypetag(key)) { |
153 | 55.2k | case LUA_VNUMINT: { |
154 | 55.2k | lua_Integer i = ivalue(key); |
155 | 55.2k | return hashint(t, i); |
156 | 0 | } |
157 | 89.8k | case LUA_VNUMFLT: { |
158 | 89.8k | lua_Number n = fltvalue(key); |
159 | 89.8k | return hashmod(t, l_hashfloat(n)); |
160 | 0 | } |
161 | 85.0k | case LUA_VSHRSTR: { |
162 | 85.0k | TString *ts = tsvalue(key); |
163 | 85.0k | return hashstr(t, ts); |
164 | 0 | } |
165 | 73.4k | case LUA_VLNGSTR: { |
166 | 73.4k | TString *ts = tsvalue(key); |
167 | 73.4k | return hashpow2(t, luaS_hashlongstr(ts)); |
168 | 0 | } |
169 | 10.4k | case LUA_VFALSE: |
170 | 10.4k | return hashboolean(t, 0); |
171 | 1.41k | case LUA_VTRUE: |
172 | 1.41k | return hashboolean(t, 1); |
173 | 0 | case LUA_VLIGHTUSERDATA: { |
174 | 0 | void *p = pvalue(key); |
175 | 0 | return hashpointer(t, p); |
176 | 0 | } |
177 | 0 | case LUA_VLCF: { |
178 | 0 | lua_CFunction f = fvalue(key); |
179 | 0 | return hashpointer(t, f); |
180 | 0 | } |
181 | 1.26k | default: { |
182 | 1.26k | GCObject *o = gcvalue(key); |
183 | 1.26k | return hashpointer(t, o); |
184 | 0 | } |
185 | 316k | } |
186 | 316k | } |
187 | | |
188 | | |
189 | 44.5k | l_sinline Node *mainpositionfromnode (const Table *t, Node *nd) { |
190 | 44.5k | TValue key; |
191 | 44.5k | getnodekey(cast(lua_State *, NULL), &key, nd); |
192 | 44.5k | return mainpositionTV(t, &key); |
193 | 44.5k | } |
194 | | |
195 | | |
196 | | /* |
197 | | ** Check whether key 'k1' is equal to the key in node 'n2'. This |
198 | | ** equality is raw, so there are no metamethods. Floats with integer |
199 | | ** values have been normalized, so integers cannot be equal to |
200 | | ** floats. It is assumed that 'eqshrstr' is simply pointer equality, so |
201 | | ** that short strings are handled in the default case. |
202 | | ** A true 'deadok' means to accept dead keys as equal to their original |
203 | | ** values. All dead keys are compared in the default case, by pointer |
204 | | ** identity. (Only collectable objects can produce dead keys.) Note that |
205 | | ** dead long strings are also compared by identity. |
206 | | ** Once a key is dead, its corresponding value may be collected, and |
207 | | ** then another value can be created with the same address. If this |
208 | | ** other value is given to 'next', 'equalkey' will signal a false |
209 | | ** positive. In a regular traversal, this situation should never happen, |
210 | | ** as all keys given to 'next' came from the table itself, and therefore |
211 | | ** could not have been collected. Outside a regular traversal, we |
212 | | ** have garbage in, garbage out. What is relevant is that this false |
213 | | ** positive does not break anything. (In particular, 'next' will return |
214 | | ** some other valid item on the table or nil.) |
215 | | */ |
216 | 211k | static int equalkey (const TValue *k1, const Node *n2, int deadok) { |
217 | 211k | if ((rawtt(k1) != keytt(n2)) && /* not the same variants? */ |
218 | 211k | !(deadok && keyisdead(n2) && iscollectable(k1))) |
219 | 58.1k | return 0; /* cannot be same key */ |
220 | 153k | switch (keytt(n2)) { |
221 | 8.65k | case LUA_VNIL: case LUA_VFALSE: case LUA_VTRUE: |
222 | 8.65k | return 1; |
223 | 0 | case LUA_VNUMINT: |
224 | 0 | return (ivalue(k1) == keyival(n2)); |
225 | 77.1k | case LUA_VNUMFLT: |
226 | 77.1k | return luai_numeq(fltvalue(k1), fltvalueraw(keyval(n2))); |
227 | 0 | case LUA_VLIGHTUSERDATA: |
228 | 0 | return pvalue(k1) == pvalueraw(keyval(n2)); |
229 | 0 | case LUA_VLCF: |
230 | 0 | return fvalue(k1) == fvalueraw(keyval(n2)); |
231 | 66.4k | case ctb(LUA_VLNGSTR): |
232 | 66.4k | return luaS_eqlngstr(tsvalue(k1), keystrval(n2)); |
233 | 1.13k | default: |
234 | 1.13k | return gcvalue(k1) == gcvalueraw(keyval(n2)); |
235 | 153k | } |
236 | 153k | } |
237 | | |
238 | | |
239 | | /* |
240 | | ** True if value of 'alimit' is equal to the real size of the array |
241 | | ** part of table 't'. (Otherwise, the array part must be larger than |
242 | | ** 'alimit'.) |
243 | | */ |
244 | 2.65M | #define limitequalsasize(t) (isrealasize(t) || ispow2((t)->alimit)) |
245 | | |
246 | | |
247 | | /* |
248 | | ** Returns the real size of the 'array' array |
249 | | */ |
250 | 44.1k | LUAI_FUNC unsigned int luaH_realasize (const Table *t) { |
251 | 44.1k | if (limitequalsasize(t)) |
252 | 44.1k | return t->alimit; /* this is the size */ |
253 | 0 | else { |
254 | 0 | unsigned int size = t->alimit; |
255 | | /* compute the smallest power of 2 not smaller than 'n' */ |
256 | 0 | size |= (size >> 1); |
257 | 0 | size |= (size >> 2); |
258 | 0 | size |= (size >> 4); |
259 | 0 | size |= (size >> 8); |
260 | 0 | #if (UINT_MAX >> 14) > 3 /* unsigned int has more than 16 bits */ |
261 | 0 | size |= (size >> 16); |
262 | | #if (UINT_MAX >> 30) > 3 |
263 | | size |= (size >> 32); /* unsigned int has more than 32 bits */ |
264 | | #endif |
265 | 0 | #endif |
266 | 0 | size++; |
267 | 0 | lua_assert(ispow2(size) && size/2 < t->alimit && t->alimit < size); |
268 | 0 | return size; |
269 | 0 | } |
270 | 44.1k | } |
271 | | |
272 | | |
273 | | /* |
274 | | ** Check whether real size of the array is a power of 2. |
275 | | ** (If it is not, 'alimit' cannot be changed to any other value |
276 | | ** without changing the real size.) |
277 | | */ |
278 | 0 | static int ispow2realasize (const Table *t) { |
279 | 0 | return (!isrealasize(t) || ispow2(t->alimit)); |
280 | 0 | } |
281 | | |
282 | | |
283 | 22.0k | static unsigned int setlimittosize (Table *t) { |
284 | 22.0k | t->alimit = luaH_realasize(t); |
285 | 22.0k | setrealasize(t); |
286 | 22.0k | return t->alimit; |
287 | 22.0k | } |
288 | | |
289 | | |
290 | 2.81k | #define limitasasize(t) check_exp(isrealasize(t), t->alimit) |
291 | | |
292 | | |
293 | | |
294 | | /* |
295 | | ** "Generic" get version. (Not that generic: not valid for integers, |
296 | | ** which may be in array part, nor for floats with integral values.) |
297 | | ** See explanation about 'deadok' in function 'equalkey'. |
298 | | */ |
299 | 160k | static const TValue *getgeneric (Table *t, const TValue *key, int deadok) { |
300 | 160k | Node *n = mainpositionTV(t, key); |
301 | 211k | for (;;) { /* check whether 'key' is somewhere in the chain */ |
302 | 211k | if (equalkey(key, n, deadok)) |
303 | 138k | return gval(n); /* that's it */ |
304 | 72.6k | else { |
305 | 72.6k | int nx = gnext(n); |
306 | 72.6k | if (nx == 0) |
307 | 21.5k | return &absentkey; /* not found */ |
308 | 51.0k | n += nx; |
309 | 51.0k | } |
310 | 211k | } |
311 | 160k | } |
312 | | |
313 | | |
314 | | /* |
315 | | ** returns the index for 'k' if 'k' is an appropriate key to live in |
316 | | ** the array part of a table, 0 otherwise. |
317 | | */ |
318 | 31.2k | static unsigned int arrayindex (lua_Integer k) { |
319 | 31.2k | if (l_castS2U(k) - 1u < MAXASIZE) /* 'k' in [1, MAXASIZE]? */ |
320 | 18.8k | return cast_uint(k); /* 'key' is an appropriate array index */ |
321 | 12.3k | else |
322 | 12.3k | return 0; |
323 | 31.2k | } |
324 | | |
325 | | |
326 | | /* |
327 | | ** returns the index of a 'key' for table traversals. First goes all |
328 | | ** elements in the array part, then elements in the hash part. The |
329 | | ** beginning of a traversal is signaled by 0. |
330 | | */ |
331 | | static unsigned int findindex (lua_State *L, Table *t, TValue *key, |
332 | 0 | unsigned int asize) { |
333 | 0 | unsigned int i; |
334 | 0 | if (ttisnil(key)) return 0; /* first iteration */ |
335 | 0 | i = ttisinteger(key) ? arrayindex(ivalue(key)) : 0; |
336 | 0 | if (i - 1u < asize) /* is 'key' inside array part? */ |
337 | 0 | return i; /* yes; that's the index */ |
338 | 0 | else { |
339 | 0 | const TValue *n = getgeneric(t, key, 1); |
340 | 0 | if (l_unlikely(isabstkey(n))) |
341 | 0 | luaG_runerror(L, "invalid key to 'next'"); /* key not found */ |
342 | 0 | i = cast_int(nodefromval(n) - gnode(t, 0)); /* key index in hash table */ |
343 | | /* hash elements are numbered after array ones */ |
344 | 0 | return (i + 1) + asize; |
345 | 0 | } |
346 | 0 | } |
347 | | |
348 | | |
349 | 0 | int luaH_next (lua_State *L, Table *t, StkId key) { |
350 | 0 | unsigned int asize = luaH_realasize(t); |
351 | 0 | unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */ |
352 | 0 | for (; i < asize; i++) { /* try first array part */ |
353 | 0 | if (!isempty(&t->array[i])) { /* a non-empty entry? */ |
354 | 0 | setivalue(s2v(key), i + 1); |
355 | 0 | setobj2s(L, key + 1, &t->array[i]); |
356 | 0 | return 1; |
357 | 0 | } |
358 | 0 | } |
359 | 0 | for (i -= asize; cast_int(i) < sizenode(t); i++) { /* hash part */ |
360 | 0 | if (!isempty(gval(gnode(t, i)))) { /* a non-empty entry? */ |
361 | 0 | Node *n = gnode(t, i); |
362 | 0 | getnodekey(L, s2v(key), n); |
363 | 0 | setobj2s(L, key + 1, gval(n)); |
364 | 0 | return 1; |
365 | 0 | } |
366 | 0 | } |
367 | 0 | return 0; /* no more elements */ |
368 | 0 | } |
369 | | |
370 | | |
371 | 28.4k | static void freehash (lua_State *L, Table *t) { |
372 | 28.4k | if (!isdummy(t)) |
373 | 2.83k | luaM_freearray(L, t->node, cast_sizet(sizenode(t))); |
374 | 28.4k | } |
375 | | |
376 | | |
377 | | /* |
378 | | ** {============================================================= |
379 | | ** Rehash |
380 | | ** ============================================================== |
381 | | */ |
382 | | |
383 | | /* |
384 | | ** Compute the optimal size for the array part of table 't'. 'nums' is a |
385 | | ** "count array" where 'nums[i]' is the number of integers in the table |
386 | | ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of |
387 | | ** integer keys in the table and leaves with the number of keys that |
388 | | ** will go to the array part; return the optimal size. (The condition |
389 | | ** 'twotoi > 0' in the for loop stops the loop if 'twotoi' overflows.) |
390 | | */ |
391 | 2.81k | static unsigned int computesizes (unsigned int nums[], unsigned int *pna) { |
392 | 2.81k | int i; |
393 | 2.81k | unsigned int twotoi; /* 2^i (candidate for optimal size) */ |
394 | 2.81k | unsigned int a = 0; /* number of elements smaller than 2^i */ |
395 | 2.81k | unsigned int na = 0; /* number of elements to go to array part */ |
396 | 2.81k | unsigned int optimal = 0; /* optimal size for array part */ |
397 | | /* loop while keys can fill more than half of total size */ |
398 | 2.81k | for (i = 0, twotoi = 1; |
399 | 6.72k | twotoi > 0 && *pna > twotoi / 2; |
400 | 3.90k | i++, twotoi *= 2) { |
401 | 3.90k | a += nums[i]; |
402 | 3.90k | if (a > twotoi/2) { /* more than half elements present? */ |
403 | 1.36k | optimal = twotoi; /* optimal size (till now) */ |
404 | 1.36k | na = a; /* all elements up to 'optimal' will go to array part */ |
405 | 1.36k | } |
406 | 3.90k | } |
407 | 2.81k | lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal); |
408 | 2.81k | *pna = na; |
409 | 2.81k | return optimal; |
410 | 2.81k | } |
411 | | |
412 | | |
413 | 31.2k | static int countint (lua_Integer key, unsigned int *nums) { |
414 | 31.2k | unsigned int k = arrayindex(key); |
415 | 31.2k | if (k != 0) { /* is 'key' an appropriate array index? */ |
416 | 18.8k | nums[luaO_ceillog2(k)]++; /* count as such */ |
417 | 18.8k | return 1; |
418 | 18.8k | } |
419 | 12.3k | else |
420 | 12.3k | return 0; |
421 | 31.2k | } |
422 | | |
423 | | |
424 | | /* |
425 | | ** Count keys in array part of table 't': Fill 'nums[i]' with |
426 | | ** number of keys that will go into corresponding slice and return |
427 | | ** total number of non-nil keys. |
428 | | */ |
429 | 2.81k | static unsigned int numusearray (const Table *t, unsigned int *nums) { |
430 | 2.81k | int lg; |
431 | 2.81k | unsigned int ttlg; /* 2^lg */ |
432 | 2.81k | unsigned int ause = 0; /* summation of 'nums' */ |
433 | 2.81k | unsigned int i = 1; /* count to traverse all array keys */ |
434 | 2.81k | unsigned int asize = limitasasize(t); /* real array size */ |
435 | | /* traverse each slice */ |
436 | 3.73k | for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) { |
437 | 3.73k | unsigned int lc = 0; /* counter */ |
438 | 3.73k | unsigned int lim = ttlg; |
439 | 3.73k | if (lim > asize) { |
440 | 2.81k | lim = asize; /* adjust upper limit */ |
441 | 2.81k | if (i > lim) |
442 | 2.81k | break; /* no more elements to count */ |
443 | 2.81k | } |
444 | | /* count elements in range (2^(lg - 1), 2^lg] */ |
445 | 3.16k | for (; i <= lim; i++) { |
446 | 2.24k | if (!isempty(&t->array[i-1])) |
447 | 2.07k | lc++; |
448 | 2.24k | } |
449 | 919 | nums[lg] += lc; |
450 | 919 | ause += lc; |
451 | 919 | } |
452 | 2.81k | return ause; |
453 | 2.81k | } |
454 | | |
455 | | |
456 | 2.81k | static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) { |
457 | 2.81k | int totaluse = 0; /* total number of elements */ |
458 | 2.81k | int ause = 0; /* elements added to 'nums' (can go to array part) */ |
459 | 2.81k | int i = sizenode(t); |
460 | 79.0k | while (i--) { |
461 | 76.2k | Node *n = &t->node[i]; |
462 | 76.2k | if (!isempty(gval(n))) { |
463 | 75.8k | if (keyisinteger(n)) |
464 | 30.8k | ause += countint(keyival(n), nums); |
465 | 75.8k | totaluse++; |
466 | 75.8k | } |
467 | 76.2k | } |
468 | 2.81k | *pna += ause; |
469 | 2.81k | return totaluse; |
470 | 2.81k | } |
471 | | |
472 | | |
473 | | /* |
474 | | ** Creates an array for the hash part of a table with the given |
475 | | ** size, or reuses the dummy node if size is zero. |
476 | | ** The computation for size overflow is in two steps: the first |
477 | | ** comparison ensures that the shift in the second one does not |
478 | | ** overflow. |
479 | | */ |
480 | 28.4k | static void setnodevector (lua_State *L, Table *t, unsigned int size) { |
481 | 28.4k | if (size == 0) { /* no elements to hash part? */ |
482 | 25.6k | t->node = cast(Node *, dummynode); /* use common 'dummynode' */ |
483 | 25.6k | t->lsizenode = 0; |
484 | 25.6k | t->lastfree = NULL; /* signal that it is using dummy node */ |
485 | 25.6k | } |
486 | 2.83k | else { |
487 | 2.83k | int i; |
488 | 2.83k | int lsize = luaO_ceillog2(size); |
489 | 2.83k | if (lsize > MAXHBITS || (1u << lsize) > MAXHSIZE) |
490 | 0 | luaG_runerror(L, "table overflow"); |
491 | 2.83k | size = twoto(lsize); |
492 | 2.83k | t->node = luaM_newvector(L, size, Node); |
493 | 128k | for (i = 0; i < cast_int(size); i++) { |
494 | 125k | Node *n = gnode(t, i); |
495 | 125k | gnext(n) = 0; |
496 | 125k | setnilkey(n); |
497 | 125k | setempty(gval(n)); |
498 | 125k | } |
499 | 2.83k | t->lsizenode = cast_byte(lsize); |
500 | 2.83k | t->lastfree = gnode(t, size); /* all positions are free */ |
501 | 2.83k | } |
502 | 28.4k | } |
503 | | |
504 | | |
505 | | /* |
506 | | ** (Re)insert all elements from the hash part of 'ot' into table 't'. |
507 | | */ |
508 | 19.2k | static void reinsert (lua_State *L, Table *ot, Table *t) { |
509 | 19.2k | int j; |
510 | 19.2k | int size = sizenode(ot); |
511 | 111k | for (j = 0; j < size; j++) { |
512 | 92.6k | Node *old = gnode(ot, j); |
513 | 92.6k | if (!isempty(gval(old))) { |
514 | | /* doesn't need barrier/invalidate cache, as entry was |
515 | | already present in the table */ |
516 | 75.8k | TValue k; |
517 | 75.8k | getnodekey(L, &k, old); |
518 | 75.8k | luaH_set(L, t, &k, gval(old)); |
519 | 75.8k | } |
520 | 92.6k | } |
521 | 19.2k | } |
522 | | |
523 | | |
524 | | /* |
525 | | ** Exchange the hash part of 't1' and 't2'. |
526 | | */ |
527 | 19.2k | static void exchangehashpart (Table *t1, Table *t2) { |
528 | 19.2k | lu_byte lsizenode = t1->lsizenode; |
529 | 19.2k | Node *node = t1->node; |
530 | 19.2k | Node *lastfree = t1->lastfree; |
531 | 19.2k | t1->lsizenode = t2->lsizenode; |
532 | 19.2k | t1->node = t2->node; |
533 | 19.2k | t1->lastfree = t2->lastfree; |
534 | 19.2k | t2->lsizenode = lsizenode; |
535 | 19.2k | t2->node = node; |
536 | 19.2k | t2->lastfree = lastfree; |
537 | 19.2k | } |
538 | | |
539 | | |
540 | | /* |
541 | | ** Resize table 't' for the new given sizes. Both allocations (for |
542 | | ** the hash part and for the array part) can fail, which creates some |
543 | | ** subtleties. If the first allocation, for the hash part, fails, an |
544 | | ** error is raised and that is it. Otherwise, it copies the elements from |
545 | | ** the shrinking part of the array (if it is shrinking) into the new |
546 | | ** hash. Then it reallocates the array part. If that fails, the table |
547 | | ** is in its original state; the function frees the new hash part and then |
548 | | ** raises the allocation error. Otherwise, it sets the new hash part |
549 | | ** into the table, initializes the new part of the array (if any) with |
550 | | ** nils and reinserts the elements of the old hash back into the new |
551 | | ** parts of the table. |
552 | | */ |
553 | | void luaH_resize (lua_State *L, Table *t, unsigned int newasize, |
554 | 19.2k | unsigned int nhsize) { |
555 | 19.2k | unsigned int i; |
556 | 19.2k | Table newt; /* to keep the new hash part */ |
557 | 19.2k | unsigned int oldasize = setlimittosize(t); |
558 | 19.2k | TValue *newarray; |
559 | | /* create new hash part with appropriate size into 'newt' */ |
560 | 19.2k | setnodevector(L, &newt, nhsize); |
561 | 19.2k | if (newasize < oldasize) { /* will array shrink? */ |
562 | 6 | t->alimit = newasize; /* pretend array has new size... */ |
563 | 6 | exchangehashpart(t, &newt); /* and new hash */ |
564 | | /* re-insert into the new hash the elements from vanishing slice */ |
565 | 12 | for (i = newasize; i < oldasize; i++) { |
566 | 6 | if (!isempty(&t->array[i])) |
567 | 0 | luaH_setint(L, t, i + 1, &t->array[i]); |
568 | 6 | } |
569 | 6 | t->alimit = oldasize; /* restore current size... */ |
570 | 6 | exchangehashpart(t, &newt); /* and hash (in case of errors) */ |
571 | 6 | } |
572 | | /* allocate new array */ |
573 | 19.2k | newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue); |
574 | 19.2k | if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ |
575 | 0 | freehash(L, &newt); /* release new hash part */ |
576 | 0 | luaM_error(L); /* raise error (with array unchanged) */ |
577 | 0 | } |
578 | | /* allocation ok; initialize new part of the array */ |
579 | 19.2k | exchangehashpart(t, &newt); /* 't' has the new hash ('newt' has the old) */ |
580 | 19.2k | t->array = newarray; /* set new array part */ |
581 | 19.2k | t->alimit = newasize; |
582 | 190k | for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ |
583 | 171k | setempty(&t->array[i]); |
584 | | /* re-insert elements from old hash part into new parts */ |
585 | 19.2k | reinsert(L, &newt, t); /* 'newt' now has the old hash */ |
586 | 19.2k | freehash(L, &newt); /* free old hash part */ |
587 | 19.2k | } |
588 | | |
589 | | |
590 | 8.00k | void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) { |
591 | 8.00k | int nsize = allocsizenode(t); |
592 | 8.00k | luaH_resize(L, t, nasize, nsize); |
593 | 8.00k | } |
594 | | |
595 | | /* |
596 | | ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i |
597 | | */ |
598 | 2.81k | static void rehash (lua_State *L, Table *t, const TValue *ek) { |
599 | 2.81k | unsigned int asize; /* optimal size for array part */ |
600 | 2.81k | unsigned int na; /* number of keys in the array part */ |
601 | 2.81k | unsigned int nums[MAXABITS + 1]; |
602 | 2.81k | int i; |
603 | 2.81k | int totaluse; |
604 | 92.9k | for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */ |
605 | 2.81k | setlimittosize(t); |
606 | 2.81k | na = numusearray(t, nums); /* count keys in array part */ |
607 | 2.81k | totaluse = na; /* all those keys are integer keys */ |
608 | 2.81k | totaluse += numusehash(t, nums, &na); /* count keys in hash part */ |
609 | | /* count extra key */ |
610 | 2.81k | if (ttisinteger(ek)) |
611 | 413 | na += countint(ivalue(ek), nums); |
612 | 2.81k | totaluse++; |
613 | | /* compute new size for array part */ |
614 | 2.81k | asize = computesizes(nums, &na); |
615 | | /* resize the table to new computed sizes */ |
616 | 2.81k | luaH_resize(L, t, asize, totaluse - na); |
617 | 2.81k | } |
618 | | |
619 | | |
620 | | |
621 | | /* |
622 | | ** }============================================================= |
623 | | */ |
624 | | |
625 | | |
626 | 9.19k | Table *luaH_new (lua_State *L) { |
627 | 9.19k | GCObject *o = luaC_newobj(L, LUA_VTABLE, sizeof(Table)); |
628 | 9.19k | Table *t = gco2t(o); |
629 | 9.19k | t->metatable = NULL; |
630 | 9.19k | t->flags = cast_byte(maskflags); /* table has no metamethod fields */ |
631 | 9.19k | t->array = NULL; |
632 | 9.19k | t->alimit = 0; |
633 | 9.19k | setnodevector(L, t, 0); |
634 | 9.19k | return t; |
635 | 9.19k | } |
636 | | |
637 | | |
638 | 9.19k | void luaH_free (lua_State *L, Table *t) { |
639 | 9.19k | freehash(L, t); |
640 | 9.19k | luaM_freearray(L, t->array, luaH_realasize(t)); |
641 | 9.19k | luaM_free(L, t); |
642 | 9.19k | } |
643 | | |
644 | | |
645 | 47.3k | static Node *getfreepos (Table *t) { |
646 | 47.3k | if (!isdummy(t)) { |
647 | 95.0k | while (t->lastfree > t->node) { |
648 | 92.6k | t->lastfree--; |
649 | 92.6k | if (keyisnil(t->lastfree)) |
650 | 44.5k | return t->lastfree; |
651 | 92.6k | } |
652 | 46.9k | } |
653 | 2.81k | return NULL; /* could not find a free place */ |
654 | 47.3k | } |
655 | | |
656 | | |
657 | | |
658 | | /* |
659 | | ** inserts a new key into a hash table; first, check whether key's main |
660 | | ** position is free. If not, check whether colliding node is in its main |
661 | | ** position or not: if it is not, move colliding node to an empty place and |
662 | | ** put new key in its main position; otherwise (colliding node is in its main |
663 | | ** position), new key goes to an empty position. |
664 | | */ |
665 | | static void luaH_newkey (lua_State *L, Table *t, const TValue *key, |
666 | 334k | TValue *value) { |
667 | 334k | Node *mp; |
668 | 334k | TValue aux; |
669 | 334k | if (l_unlikely(ttisnil(key))) |
670 | 0 | luaG_runerror(L, "table index is nil"); |
671 | 334k | else if (ttisfloat(key)) { |
672 | 7.36k | lua_Number f = fltvalue(key); |
673 | 7.36k | lua_Integer k; |
674 | 7.36k | if (luaV_flttointeger(f, &k, F2Ieq)) { /* does key fit in an integer? */ |
675 | 66 | setivalue(&aux, k); |
676 | 66 | key = &aux; /* insert it as an integer */ |
677 | 66 | } |
678 | 7.30k | else if (l_unlikely(luai_numisnan(f))) |
679 | 0 | luaG_runerror(L, "table index is NaN"); |
680 | 7.36k | } |
681 | 334k | if (ttisnil(value)) |
682 | 222k | return; /* do not insert nil values */ |
683 | 111k | mp = mainpositionTV(t, key); |
684 | 111k | if (!isempty(gval(mp)) || isdummy(t)) { /* main position is taken? */ |
685 | 47.3k | Node *othern; |
686 | 47.3k | Node *f = getfreepos(t); /* get a free place */ |
687 | 47.3k | if (f == NULL) { /* cannot find a free place? */ |
688 | 2.81k | rehash(L, t, key); /* grow table */ |
689 | | /* whatever called 'newkey' takes care of TM cache */ |
690 | 2.81k | luaH_set(L, t, key, value); /* insert key into grown table */ |
691 | 2.81k | return; |
692 | 2.81k | } |
693 | 44.5k | lua_assert(!isdummy(t)); |
694 | 44.5k | othern = mainpositionfromnode(t, mp); |
695 | 44.5k | if (othern != mp) { /* is colliding node out of its main position? */ |
696 | | /* yes; move colliding node into free position */ |
697 | 14.6k | while (othern + gnext(othern) != mp) /* find previous */ |
698 | 4.46k | othern += gnext(othern); |
699 | 10.2k | gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */ |
700 | 10.2k | *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */ |
701 | 10.2k | if (gnext(mp) != 0) { |
702 | 2.46k | gnext(f) += cast_int(mp - f); /* correct 'next' */ |
703 | 2.46k | gnext(mp) = 0; /* now 'mp' is free */ |
704 | 2.46k | } |
705 | 10.2k | setempty(gval(mp)); |
706 | 10.2k | } |
707 | 34.3k | else { /* colliding node is in its own main position */ |
708 | | /* new node will go into free position */ |
709 | 34.3k | if (gnext(mp) != 0) |
710 | 11.5k | gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */ |
711 | 22.7k | else lua_assert(gnext(f) == 0); |
712 | 34.3k | gnext(mp) = cast_int(f - mp); |
713 | 34.3k | mp = f; |
714 | 34.3k | } |
715 | 44.5k | } |
716 | 109k | setnodekey(L, mp, key); |
717 | 109k | luaC_barrierback(L, obj2gco(t), key); |
718 | 109k | lua_assert(isempty(gval(mp))); |
719 | 109k | setobj2t(L, gval(mp), value); |
720 | 109k | } |
721 | | |
722 | | |
723 | | /* |
724 | | ** Search function for integers. If integer is inside 'alimit', get it |
725 | | ** directly from the array part. Otherwise, if 'alimit' is not equal to |
726 | | ** the real size of the array, key still can be in the array part. In |
727 | | ** this case, try to avoid a call to 'luaH_realasize' when key is just |
728 | | ** one more than the limit (so that it can be incremented without |
729 | | ** changing the real size of the array). |
730 | | */ |
731 | 1.32M | const TValue *luaH_getint (Table *t, lua_Integer key) { |
732 | 1.32M | if (l_castS2U(key) - 1u < t->alimit) /* 'key' in [1, t->alimit]? */ |
733 | 26.3k | return &t->array[key - 1]; |
734 | 1.29M | else if (!limitequalsasize(t) && /* key still may be in the array part? */ |
735 | 1.29M | (l_castS2U(key) == t->alimit + 1 || |
736 | 0 | l_castS2U(key) - 1u < luaH_realasize(t))) { |
737 | 0 | t->alimit = cast_uint(key); /* probably '#t' is here now */ |
738 | 0 | return &t->array[key - 1]; |
739 | 0 | } |
740 | 1.29M | else { |
741 | 1.29M | Node *n = hashint(t, key); |
742 | 2.99M | for (;;) { /* check whether 'key' is somewhere in the chain */ |
743 | 2.99M | if (keyisinteger(n) && keyival(n) == key) |
744 | 811k | return gval(n); /* that's it */ |
745 | 2.18M | else { |
746 | 2.18M | int nx = gnext(n); |
747 | 2.18M | if (nx == 0) break; |
748 | 1.70M | n += nx; |
749 | 1.70M | } |
750 | 2.99M | } |
751 | 484k | return &absentkey; |
752 | 1.29M | } |
753 | 1.32M | } |
754 | | |
755 | | |
756 | | /* |
757 | | ** search function for short strings |
758 | | */ |
759 | 29.0M | const TValue *luaH_getshortstr (Table *t, TString *key) { |
760 | 29.0M | Node *n = hashstr(t, key); |
761 | 29.0M | lua_assert(key->tt == LUA_VSHRSTR); |
762 | 36.7M | for (;;) { /* check whether 'key' is somewhere in the chain */ |
763 | 36.7M | if (keyisshrstr(n) && eqshrstr(keystrval(n), key)) |
764 | 27.4M | return gval(n); /* that's it */ |
765 | 9.36M | else { |
766 | 9.36M | int nx = gnext(n); |
767 | 9.36M | if (nx == 0) |
768 | 1.61M | return &absentkey; /* not found */ |
769 | 7.74M | n += nx; |
770 | 7.74M | } |
771 | 36.7M | } |
772 | 29.0M | } |
773 | | |
774 | | |
775 | 13.5M | const TValue *luaH_getstr (Table *t, TString *key) { |
776 | 13.5M | if (key->tt == LUA_VSHRSTR) |
777 | 13.5M | return luaH_getshortstr(t, key); |
778 | 29.7k | else { /* for long strings, use generic case */ |
779 | 29.7k | TValue ko; |
780 | 29.7k | setsvalue(cast(lua_State *, NULL), &ko, key); |
781 | 29.7k | return getgeneric(t, &ko, 0); |
782 | 29.7k | } |
783 | 13.5M | } |
784 | | |
785 | | |
786 | | /* |
787 | | ** main search function |
788 | | */ |
789 | 13.4M | const TValue *luaH_get (Table *t, const TValue *key) { |
790 | 13.4M | switch (ttypetag(key)) { |
791 | 13.2M | case LUA_VSHRSTR: return luaH_getshortstr(t, tsvalue(key)); |
792 | 92.6k | case LUA_VNUMINT: return luaH_getint(t, ivalue(key)); |
793 | 0 | case LUA_VNIL: return &absentkey; |
794 | 82.0k | case LUA_VNUMFLT: { |
795 | 82.0k | lua_Integer k; |
796 | 82.0k | if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */ |
797 | 3.27k | return luaH_getint(t, k); /* use specialized version */ |
798 | | /* else... */ |
799 | 82.0k | } /* FALLTHROUGH */ |
800 | 130k | default: |
801 | 130k | return getgeneric(t, key, 0); |
802 | 13.4M | } |
803 | 13.4M | } |
804 | | |
805 | | |
806 | | /* |
807 | | ** Finish a raw "set table" operation, where 'slot' is where the value |
808 | | ** should have been (the result of a previous "get table"). |
809 | | ** Beware: when using this function you probably need to check a GC |
810 | | ** barrier and invalidate the TM cache. |
811 | | */ |
812 | | void luaH_finishset (lua_State *L, Table *t, const TValue *key, |
813 | 437k | const TValue *slot, TValue *value) { |
814 | 437k | if (isabstkey(slot)) |
815 | 334k | luaH_newkey(L, t, key, value); |
816 | 102k | else |
817 | 102k | setobj2t(L, cast(TValue *, slot), value); |
818 | 437k | } |
819 | | |
820 | | |
821 | | /* |
822 | | ** beware: when using this function you probably need to check a GC |
823 | | ** barrier and invalidate the TM cache. |
824 | | */ |
825 | 78.6k | void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) { |
826 | 78.6k | const TValue *slot = luaH_get(t, key); |
827 | 78.6k | luaH_finishset(L, t, key, slot, value); |
828 | 78.6k | } |
829 | | |
830 | | |
831 | 0 | void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { |
832 | 0 | const TValue *p = luaH_getint(t, key); |
833 | 0 | if (isabstkey(p)) { |
834 | 0 | TValue k; |
835 | 0 | setivalue(&k, key); |
836 | 0 | luaH_newkey(L, t, &k, value); |
837 | 0 | } |
838 | 0 | else |
839 | 0 | setobj2t(L, cast(TValue *, p), value); |
840 | 0 | } |
841 | | |
842 | | |
843 | | /* |
844 | | ** Try to find a boundary in the hash part of table 't'. From the |
845 | | ** caller, we know that 'j' is zero or present and that 'j + 1' is |
846 | | ** present. We want to find a larger key that is absent from the |
847 | | ** table, so that we can do a binary search between the two keys to |
848 | | ** find a boundary. We keep doubling 'j' until we get an absent index. |
849 | | ** If the doubling would overflow, we try LUA_MAXINTEGER. If it is |
850 | | ** absent, we are ready for the binary search. ('j', being max integer, |
851 | | ** is larger or equal to 'i', but it cannot be equal because it is |
852 | | ** absent while 'i' is present; so 'j > i'.) Otherwise, 'j' is a |
853 | | ** boundary. ('j + 1' cannot be a present integer key because it is |
854 | | ** not a valid integer in Lua.) |
855 | | */ |
856 | 9.64k | static lua_Unsigned hash_search (Table *t, lua_Unsigned j) { |
857 | 9.64k | lua_Unsigned i; |
858 | 9.64k | if (j == 0) j++; /* the caller ensures 'j + 1' is present */ |
859 | 384k | do { |
860 | 384k | i = j; /* 'i' is a present index */ |
861 | 384k | if (j <= l_castS2U(LUA_MAXINTEGER) / 2) |
862 | 377k | j *= 2; |
863 | 6.97k | else { |
864 | 6.97k | j = LUA_MAXINTEGER; |
865 | 6.97k | if (isempty(luaH_getint(t, j))) /* t[j] not present? */ |
866 | 6.97k | break; /* 'j' now is an absent index */ |
867 | 0 | else /* weird case */ |
868 | 0 | return j; /* well, max integer is a boundary... */ |
869 | 6.97k | } |
870 | 384k | } while (!isempty(luaH_getint(t, j))); /* repeat until an absent t[j] */ |
871 | | /* i < j && t[i] present && t[j] absent */ |
872 | 438k | while (j - i > 1u) { /* do a binary search between them */ |
873 | 428k | lua_Unsigned m = (i + j) / 2; |
874 | 428k | if (isempty(luaH_getint(t, m))) j = m; |
875 | 0 | else i = m; |
876 | 428k | } |
877 | 9.64k | return i; |
878 | 9.64k | } |
879 | | |
880 | | |
881 | | static unsigned int binsearch (const TValue *array, unsigned int i, |
882 | 0 | unsigned int j) { |
883 | 0 | while (j - i > 1u) { /* binary search */ |
884 | 0 | unsigned int m = (i + j) / 2; |
885 | 0 | if (isempty(&array[m - 1])) j = m; |
886 | 0 | else i = m; |
887 | 0 | } |
888 | 0 | return i; |
889 | 0 | } |
890 | | |
891 | | |
892 | | /* |
893 | | ** Try to find a boundary in table 't'. (A 'boundary' is an integer index |
894 | | ** such that t[i] is present and t[i+1] is absent, or 0 if t[1] is absent |
895 | | ** and 'maxinteger' if t[maxinteger] is present.) |
896 | | ** (In the next explanation, we use Lua indices, that is, with base 1. |
897 | | ** The code itself uses base 0 when indexing the array part of the table.) |
898 | | ** The code starts with 'limit = t->alimit', a position in the array |
899 | | ** part that may be a boundary. |
900 | | ** |
901 | | ** (1) If 't[limit]' is empty, there must be a boundary before it. |
902 | | ** As a common case (e.g., after 't[#t]=nil'), check whether 'limit-1' |
903 | | ** is present. If so, it is a boundary. Otherwise, do a binary search |
904 | | ** between 0 and limit to find a boundary. In both cases, try to |
905 | | ** use this boundary as the new 'alimit', as a hint for the next call. |
906 | | ** |
907 | | ** (2) If 't[limit]' is not empty and the array has more elements |
908 | | ** after 'limit', try to find a boundary there. Again, try first |
909 | | ** the special case (which should be quite frequent) where 'limit+1' |
910 | | ** is empty, so that 'limit' is a boundary. Otherwise, check the |
911 | | ** last element of the array part. If it is empty, there must be a |
912 | | ** boundary between the old limit (present) and the last element |
913 | | ** (absent), which is found with a binary search. (This boundary always |
914 | | ** can be a new limit.) |
915 | | ** |
916 | | ** (3) The last case is when there are no elements in the array part |
917 | | ** (limit == 0) or its last element (the new limit) is present. |
918 | | ** In this case, must check the hash part. If there is no hash part |
919 | | ** or 'limit+1' is absent, 'limit' is a boundary. Otherwise, call |
920 | | ** 'hash_search' to find a boundary in the hash part of the table. |
921 | | ** (In those cases, the boundary is not inside the array part, and |
922 | | ** therefore cannot be used as a new limit.) |
923 | | */ |
924 | 18.8k | lua_Unsigned luaH_getn (Table *t) { |
925 | 18.8k | unsigned int limit = t->alimit; |
926 | 18.8k | if (limit > 0 && isempty(&t->array[limit - 1])) { /* (1)? */ |
927 | | /* there must be a boundary before 'limit' */ |
928 | 0 | if (limit >= 2 && !isempty(&t->array[limit - 2])) { |
929 | | /* 'limit - 1' is a boundary; can it be a new limit? */ |
930 | 0 | if (ispow2realasize(t) && !ispow2(limit - 1)) { |
931 | 0 | t->alimit = limit - 1; |
932 | 0 | setnorealasize(t); /* now 'alimit' is not the real size */ |
933 | 0 | } |
934 | 0 | return limit - 1; |
935 | 0 | } |
936 | 0 | else { /* must search for a boundary in [0, limit] */ |
937 | 0 | unsigned int boundary = binsearch(t->array, 0, limit); |
938 | | /* can this boundary represent the real size of the array? */ |
939 | 0 | if (ispow2realasize(t) && boundary > luaH_realasize(t) / 2) { |
940 | 0 | t->alimit = boundary; /* use it as the new limit */ |
941 | 0 | setnorealasize(t); |
942 | 0 | } |
943 | 0 | return boundary; |
944 | 0 | } |
945 | 0 | } |
946 | | /* 'limit' is zero or present in table */ |
947 | 18.8k | if (!limitequalsasize(t)) { /* (2)? */ |
948 | | /* 'limit' > 0 and array has more elements after 'limit' */ |
949 | 0 | if (isempty(&t->array[limit])) /* 'limit + 1' is empty? */ |
950 | 0 | return limit; /* this is the boundary */ |
951 | | /* else, try last element in the array */ |
952 | 0 | limit = luaH_realasize(t); |
953 | 0 | if (isempty(&t->array[limit - 1])) { /* empty? */ |
954 | | /* there must be a boundary in the array after old limit, |
955 | | and it must be a valid new limit */ |
956 | 0 | unsigned int boundary = binsearch(t->array, t->alimit, limit); |
957 | 0 | t->alimit = boundary; |
958 | 0 | return boundary; |
959 | 0 | } |
960 | | /* else, new limit is present in the table; check the hash part */ |
961 | 0 | } |
962 | | /* (3) 'limit' is the last element and either is zero or present in table */ |
963 | 18.8k | lua_assert(limit == luaH_realasize(t) && |
964 | 18.8k | (limit == 0 || !isempty(&t->array[limit - 1]))); |
965 | 18.8k | if (isdummy(t) || isempty(luaH_getint(t, cast(lua_Integer, limit + 1)))) |
966 | 9.17k | return limit; /* 'limit + 1' is absent */ |
967 | 9.64k | else /* 'limit + 1' is also present */ |
968 | 9.64k | return hash_search(t, limit); |
969 | 18.8k | } |
970 | | |
971 | | |
972 | | |
973 | | #if defined(LUA_DEBUG) |
974 | | |
975 | | /* export these functions for the test library */ |
976 | | |
977 | | Node *luaH_mainposition (const Table *t, const TValue *key) { |
978 | | return mainpositionTV(t, key); |
979 | | } |
980 | | |
981 | | #endif |