Line | Branch | Decision | Exec | Source |
---|---|---|---|---|
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 | #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 | #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 | #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 | #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 | #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 | #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) | |||
82 | ||||
83 | ||||
84 | #define hashstr(t,str) hashpow2(t, (str)->hash) | |||
85 | #define hashboolean(t,p) hashpow2(t, p) | |||
86 | ||||
87 | ||||
88 | #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 | 707 | static Node *hashint (const Table *t, lua_Integer i) { | ||
109 | 707 | lua_Unsigned ui = l_castS2U(i); | ||
110 |
1/2✓ Branch 0 taken 707 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 707 times.
✗ Decision 'false' not taken.
|
707 | if (ui <= cast_uint(INT_MAX)) |
111 | 707 | return hashmod(t, cast_int(ui)); | ||
112 | else | |||
113 | ✗ | return hashmod(t, ui); | ||
114 | } | |||
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 | 151 | static int l_hashfloat (lua_Number n) { | ||
132 | int i; | |||
133 | lua_Integer ni; | |||
134 | 151 | n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN); | ||
135 |
2/4✓ Branch 0 taken 151 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 151 times.
✗ Branch 3 not taken.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 151 times.
|
151 | if (!lua_numbertointeger(n, &ni)) { /* is 'n' inf/-inf/NaN? */ |
136 | lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL)); | |||
137 | ✗ | return 0; | ||
138 | } | |||
139 | else { /* normal case */ | |||
140 | 151 | unsigned int u = cast_uint(i) + cast_uint(ni); | ||
141 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 151 times.
|
151 | return cast_int(u <= cast_uint(INT_MAX) ? u : ~u); | |
142 | } | |||
143 | } | |||
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 | 141569 | static Node *mainpositionTV (const Table *t, const TValue *key) { | ||
152 |
4/9✓ Branch 0 taken 359 times.
✓ Branch 1 taken 151 times.
✓ Branch 2 taken 140944 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 115 times.
|
141569 | switch (ttypetag(key)) { | |
153 |
1/1✓ Decision 'true' taken 359 times.
|
359 | case LUA_VNUMINT: { | |
154 | 359 | lua_Integer i = ivalue(key); | ||
155 | 359 | return hashint(t, i); | ||
156 | } | |||
157 |
1/1✓ Decision 'true' taken 151 times.
|
151 | case LUA_VNUMFLT: { | |
158 | 151 | lua_Number n = fltvalue(key); | ||
159 | 151 | return hashmod(t, l_hashfloat(n)); | ||
160 | } | |||
161 |
1/1✓ Decision 'true' taken 140944 times.
|
140944 | case LUA_VSHRSTR: { | |
162 | 140944 | TString *ts = tsvalue(key); | ||
163 | 140944 | return hashstr(t, ts); | ||
164 | } | |||
165 | ✗ | case LUA_VLNGSTR: { | ||
166 | ✗ | TString *ts = tsvalue(key); | ||
167 | ✗ | return hashpow2(t, luaS_hashlongstr(ts)); | ||
168 | } | |||
169 | ✗ | case LUA_VFALSE: | ||
170 | ✗ | return hashboolean(t, 0); | ||
171 | ✗ | case LUA_VTRUE: | ||
172 | ✗ | return hashboolean(t, 1); | ||
173 | ✗ | case LUA_VLIGHTUSERDATA: { | ||
174 | ✗ | void *p = pvalue(key); | ||
175 | ✗ | return hashpointer(t, p); | ||
176 | } | |||
177 | ✗ | case LUA_VLCF: { | ||
178 | ✗ | lua_CFunction f = fvalue(key); | ||
179 | ✗ | return hashpointer(t, f); | ||
180 | } | |||
181 |
1/1✓ Decision 'true' taken 115 times.
|
115 | default: { | |
182 | 115 | GCObject *o = gcvalue(key); | ||
183 | 115 | return hashpointer(t, o); | ||
184 | } | |||
185 | } | |||
186 | } | |||
187 | ||||
188 | ||||
189 | 36875 | l_sinline Node *mainpositionfromnode (const Table *t, Node *nd) { | ||
190 | TValue key; | |||
191 | 36875 | getnodekey(cast(lua_State *, NULL), &key, nd); | ||
192 | 36875 | return mainpositionTV(t, &key); | ||
193 | } | |||
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 | 174 | static int equalkey (const TValue *k1, const Node *n2, int deadok) { | ||
217 |
3/4✓ Branch 0 taken 128 times.
✓ Branch 1 taken 46 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 128 times.
|
2/2✓ Decision 'true' taken 128 times.
✓ Decision 'false' taken 46 times.
|
174 | if ((rawtt(k1) != keytt(n2)) && /* not the same variants? */ |
218 | ✗ | !(deadok && keyisdead(n2) && iscollectable(k1))) | ||
219 | 128 | return 0; /* cannot be same key */ | ||
220 |
2/7✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 7 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 39 times.
|
46 | switch (keytt(n2)) { | |
221 | ✗ | case LUA_VNIL: case LUA_VFALSE: case LUA_VTRUE: | ||
222 | ✗ | return 1; | ||
223 | ✗ | case LUA_VNUMINT: | ||
224 | ✗ | return (ivalue(k1) == keyival(n2)); | ||
225 |
1/1✓ Decision 'true' taken 7 times.
|
7 | case LUA_VNUMFLT: | |
226 | 7 | return luai_numeq(fltvalue(k1), fltvalueraw(keyval(n2))); | ||
227 | ✗ | case LUA_VLIGHTUSERDATA: | ||
228 | ✗ | return pvalue(k1) == pvalueraw(keyval(n2)); | ||
229 | ✗ | case LUA_VLCF: | ||
230 | ✗ | return fvalue(k1) == fvalueraw(keyval(n2)); | ||
231 | ✗ | case ctb(LUA_VLNGSTR): | ||
232 | ✗ | return luaS_eqlngstr(tsvalue(k1), keystrval(n2)); | ||
233 |
1/1✓ Decision 'true' taken 39 times.
|
39 | default: | |
234 | 39 | return gcvalue(k1) == gcvalueraw(keyval(n2)); | ||
235 | } | |||
236 | } | |||
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 | #define limitequalsasize(t) (isrealasize(t) || ispow2((t)->alimit)) | |||
245 | ||||
246 | ||||
247 | /* | |||
248 | ** Returns the real size of the 'array' array | |||
249 | */ | |||
250 | 44657 | LUAI_FUNC unsigned int luaH_realasize (const Table *t) { | ||
251 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 44657 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
1/2✓ Decision 'true' taken 44657 times.
✗ Decision 'false' not taken.
|
44657 | if (limitequalsasize(t)) |
252 | 44657 | return t->alimit; /* this is the size */ | ||
253 | else { | |||
254 | ✗ | unsigned int size = t->alimit; | ||
255 | /* compute the smallest power of 2 not smaller than 'n' */ | |||
256 | ✗ | size |= (size >> 1); | ||
257 | ✗ | size |= (size >> 2); | ||
258 | ✗ | size |= (size >> 4); | ||
259 | ✗ | size |= (size >> 8); | ||
260 | #if (UINT_MAX >> 14) > 3 /* unsigned int has more than 16 bits */ | |||
261 | ✗ | size |= (size >> 16); | ||
262 | #if (UINT_MAX >> 30) > 3 | |||
263 | size |= (size >> 32); /* unsigned int has more than 32 bits */ | |||
264 | #endif | |||
265 | #endif | |||
266 | ✗ | size++; | ||
267 | lua_assert(ispow2(size) && size/2 < t->alimit && t->alimit < size); | |||
268 | ✗ | return size; | ||
269 | } | |||
270 | } | |||
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 | ✗ | static int ispow2realasize (const Table *t) { | ||
279 | ✗ | return (!isrealasize(t) || ispow2(t->alimit)); | ||
280 | } | |||
281 | ||||
282 | ||||
283 | 25597 | static unsigned int setlimittosize (Table *t) { | ||
284 | 25597 | t->alimit = luaH_realasize(t); | ||
285 | 25597 | setrealasize(t); | ||
286 | 25597 | return t->alimit; | ||
287 | } | |||
288 | ||||
289 | ||||
290 | #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 | 147 | static const TValue *getgeneric (Table *t, const TValue *key, int deadok) { | ||
300 | 147 | Node *n = mainpositionTV(t, key); | ||
301 | for (;;) { /* check whether 'key' is somewhere in the chain */ | |||
302 |
2/2✓ Branch 1 taken 46 times.
✓ Branch 2 taken 128 times.
|
2/2✓ Decision 'true' taken 46 times.
✓ Decision 'false' taken 128 times.
|
174 | if (equalkey(key, n, deadok)) |
303 | 46 | return gval(n); /* that's it */ | ||
304 | else { | |||
305 | 128 | int nx = gnext(n); | ||
306 |
2/2✓ Branch 0 taken 101 times.
✓ Branch 1 taken 27 times.
|
2/2✓ Decision 'true' taken 101 times.
✓ Decision 'false' taken 27 times.
|
128 | if (nx == 0) |
307 | 101 | return &absentkey; /* not found */ | ||
308 | 27 | n += nx; | ||
309 | } | |||
310 | } | |||
311 | } | |||
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 | 127 | static unsigned int arrayindex (lua_Integer k) { | ||
319 |
1/2✓ Branch 0 taken 127 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 127 times.
✗ Decision 'false' not taken.
|
127 | if (l_castS2U(k) - 1u < MAXASIZE) /* 'k' in [1, MAXASIZE]? */ |
320 | 127 | return cast_uint(k); /* 'key' is an appropriate array index */ | ||
321 | else | |||
322 | ✗ | return 0; | ||
323 | } | |||
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 | unsigned int asize) { | |||
333 | unsigned int i; | |||
334 | ✗ | if (ttisnil(key)) return 0; /* first iteration */ | ||
335 | ✗ | i = ttisinteger(key) ? arrayindex(ivalue(key)) : 0; | ||
336 | ✗ | if (i - 1u < asize) /* is 'key' inside array part? */ | ||
337 | ✗ | return i; /* yes; that's the index */ | ||
338 | else { | |||
339 | ✗ | const TValue *n = getgeneric(t, key, 1); | ||
340 | ✗ | if (l_unlikely(isabstkey(n))) | ||
341 | ✗ | luaG_runerror(L, "invalid key to 'next'"); /* key not found */ | ||
342 | ✗ | i = cast_int(nodefromval(n) - gnode(t, 0)); /* key index in hash table */ | ||
343 | /* hash elements are numbered after array ones */ | |||
344 | ✗ | return (i + 1) + asize; | ||
345 | } | |||
346 | } | |||
347 | ||||
348 | ||||
349 | ✗ | int luaH_next (lua_State *L, Table *t, StkId key) { | ||
350 | ✗ | unsigned int asize = luaH_realasize(t); | ||
351 | ✗ | unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */ | ||
352 | ✗ | for (; i < asize; i++) { /* try first array part */ | ||
353 | ✗ | if (!isempty(&t->array[i])) { /* a non-empty entry? */ | ||
354 | ✗ | setivalue(s2v(key), i + 1); | ||
355 | ✗ | setobj2s(L, key + 1, &t->array[i]); | ||
356 | ✗ | return 1; | ||
357 | } | |||
358 | } | |||
359 | ✗ | for (i -= asize; cast_int(i) < sizenode(t); i++) { /* hash part */ | ||
360 | ✗ | if (!isempty(gval(gnode(t, i)))) { /* a non-empty entry? */ | ||
361 | ✗ | Node *n = gnode(t, i); | ||
362 | ✗ | getnodekey(L, s2v(key), n); | ||
363 | ✗ | setobj2s(L, key + 1, gval(n)); | ||
364 | ✗ | return 1; | ||
365 | } | |||
366 | } | |||
367 | ✗ | return 0; /* no more elements */ | ||
368 | } | |||
369 | ||||
370 | ||||
371 | 22227 | static void freehash (lua_State *L, Table *t) { | ||
372 |
2/2✓ Branch 0 taken 14600 times.
✓ Branch 1 taken 7627 times.
|
2/2✓ Decision 'true' taken 14600 times.
✓ Decision 'false' taken 7627 times.
|
22227 | if (!isdummy(t)) |
373 | 14600 | luaM_freearray(L, t->node, cast_sizet(sizenode(t))); | ||
374 | 22227 | } | ||
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 | 10583 | static unsigned int computesizes (unsigned int nums[], unsigned int *pna) { | ||
392 | int i; | |||
393 | unsigned int twotoi; /* 2^i (candidate for optimal size) */ | |||
394 | 10583 | unsigned int a = 0; /* number of elements smaller than 2^i */ | ||
395 | 10583 | unsigned int na = 0; /* number of elements to go to array part */ | ||
396 | 10583 | unsigned int optimal = 0; /* optimal size for array part */ | ||
397 | /* loop while keys can fill more than half of total size */ | |||
398 | 10583 | for (i = 0, twotoi = 1; | ||
399 |
3/4✓ Branch 0 taken 13796 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 3213 times.
✓ Branch 3 taken 10583 times.
|
13796 | twotoi > 0 && *pna > twotoi / 2; | |
400 | 3213 | i++, twotoi *= 2) { | ||
401 | 3213 | a += nums[i]; | ||
402 |
2/2✓ Branch 0 taken 3090 times.
✓ Branch 1 taken 123 times.
|
2/2✓ Decision 'true' taken 3090 times.
✓ Decision 'false' taken 123 times.
|
3213 | if (a > twotoi/2) { /* more than half elements present? */ |
403 | 3090 | optimal = twotoi; /* optimal size (till now) */ | ||
404 | 3090 | na = a; /* all elements up to 'optimal' will go to array part */ | ||
405 | } | |||
406 | } | |||
407 | lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal); | |||
408 | 10583 | *pna = na; | ||
409 | 10583 | return optimal; | ||
410 | } | |||
411 | ||||
412 | ||||
413 | 127 | static int countint (lua_Integer key, unsigned int *nums) { | ||
414 | 127 | unsigned int k = arrayindex(key); | ||
415 |
1/2✓ Branch 0 taken 127 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 127 times.
✗ Decision 'false' not taken.
|
127 | if (k != 0) { /* is 'key' an appropriate array index? */ |
416 | 127 | nums[luaO_ceillog2(k)]++; /* count as such */ | ||
417 | 127 | return 1; | ||
418 | } | |||
419 | else | |||
420 | ✗ | return 0; | ||
421 | } | |||
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 | 10583 | static unsigned int numusearray (const Table *t, unsigned int *nums) { | ||
430 | int lg; | |||
431 | unsigned int ttlg; /* 2^lg */ | |||
432 | 10583 | unsigned int ause = 0; /* summation of 'nums' */ | ||
433 | 10583 | unsigned int i = 1; /* count to traverse all array keys */ | ||
434 | 10583 | unsigned int asize = limitasasize(t); /* real array size */ | ||
435 | /* traverse each slice */ | |||
436 |
1/2✓ Branch 0 taken 13673 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 13673 times.
✗ Decision 'false' not taken.
|
13673 | for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) { |
437 | 13673 | unsigned int lc = 0; /* counter */ | ||
438 | 13673 | unsigned int lim = ttlg; | ||
439 |
2/2✓ Branch 0 taken 10583 times.
✓ Branch 1 taken 3090 times.
|
2/2✓ Decision 'true' taken 10583 times.
✓ Decision 'false' taken 3090 times.
|
13673 | if (lim > asize) { |
440 | 10583 | lim = asize; /* adjust upper limit */ | ||
441 |
1/2✓ Branch 0 taken 10583 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 10583 times.
✗ Decision 'false' not taken.
|
10583 | if (i > lim) |
442 | 10583 | break; /* no more elements to count */ | ||
443 | } | |||
444 | /* count elements in range (2^(lg - 1), 2^lg] */ | |||
445 |
2/2✓ Branch 0 taken 3090 times.
✓ Branch 1 taken 3090 times.
|
2/2✓ Decision 'true' taken 3090 times.
✓ Decision 'false' taken 3090 times.
|
6180 | for (; i <= lim; i++) { |
446 |
1/2✓ Branch 0 taken 3090 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 3090 times.
✗ Decision 'false' not taken.
|
3090 | if (!isempty(&t->array[i-1])) |
447 | 3090 | lc++; | ||
448 | } | |||
449 | 3090 | nums[lg] += lc; | ||
450 | 3090 | ause += lc; | ||
451 | } | |||
452 | 10583 | return ause; | ||
453 | } | |||
454 | ||||
455 | ||||
456 | 10583 | static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) { | ||
457 | 10583 | int totaluse = 0; /* total number of elements */ | ||
458 | 10583 | int ause = 0; /* elements added to 'nums' (can go to array part) */ | ||
459 | 10583 | int i = sizenode(t); | ||
460 |
2/2✓ Branch 0 taken 45629 times.
✓ Branch 1 taken 10583 times.
|
2/2✓ Decision 'true' taken 45629 times.
✓ Decision 'false' taken 10583 times.
|
56212 | while (i--) { |
461 | 45629 | Node *n = &t->node[i]; | ||
462 |
2/2✓ Branch 0 taken 42539 times.
✓ Branch 1 taken 3090 times.
|
2/2✓ Decision 'true' taken 42539 times.
✓ Decision 'false' taken 3090 times.
|
45629 | if (!isempty(gval(n))) { |
463 |
2/2✓ Branch 0 taken 102 times.
✓ Branch 1 taken 42437 times.
|
2/2✓ Decision 'true' taken 102 times.
✓ Decision 'false' taken 42437 times.
|
42539 | if (keyisinteger(n)) |
464 | 102 | ause += countint(keyival(n), nums); | ||
465 | 42539 | totaluse++; | ||
466 | } | |||
467 | } | |||
468 | 10583 | *pna += ause; | ||
469 | 10583 | return totaluse; | ||
470 | } | |||
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 | 22227 | static void setnodevector (lua_State *L, Table *t, unsigned int size) { | ||
481 |
2/2✓ Branch 0 taken 7627 times.
✓ Branch 1 taken 14600 times.
|
2/2✓ Decision 'true' taken 7627 times.
✓ Decision 'false' taken 14600 times.
|
22227 | if (size == 0) { /* no elements to hash part? */ |
482 | 7627 | t->node = cast(Node *, dummynode); /* use common 'dummynode' */ | ||
483 | 7627 | t->lsizenode = 0; | ||
484 | 7627 | t->lastfree = NULL; /* signal that it is using dummy node */ | ||
485 | } | |||
486 | else { | |||
487 | int i; | |||
488 | 14600 | int lsize = luaO_ceillog2(size); | ||
489 |
2/4✓ Branch 0 taken 14600 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 14600 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 14600 times.
|
14600 | if (lsize > MAXHBITS || (1u << lsize) > MAXHSIZE) |
490 | ✗ | luaG_runerror(L, "table overflow"); | ||
491 | 14600 | size = twoto(lsize); | ||
492 | 14600 | t->node = luaM_newvector(L, size, Node); | ||
493 |
2/2✓ Branch 0 taken 105472 times.
✓ Branch 1 taken 14600 times.
|
2/2✓ Decision 'true' taken 105472 times.
✓ Decision 'false' taken 14600 times.
|
120072 | for (i = 0; i < cast_int(size); i++) { |
494 | 105472 | Node *n = gnode(t, i); | ||
495 | 105472 | gnext(n) = 0; | ||
496 | 105472 | setnilkey(n); | ||
497 | 105472 | setempty(gval(n)); | ||
498 | } | |||
499 | 14600 | t->lsizenode = cast_byte(lsize); | ||
500 | 14600 | t->lastfree = gnode(t, size); /* all positions are free */ | ||
501 | } | |||
502 | 22227 | } | ||
503 | ||||
504 | ||||
505 | /* | |||
506 | ** (Re)insert all elements from the hash part of 'ot' into table 't'. | |||
507 | */ | |||
508 | 15014 | static void reinsert (lua_State *L, Table *ot, Table *t) { | ||
509 | int j; | |||
510 | 15014 | int size = sizenode(ot); | ||
511 |
2/2✓ Branch 0 taken 50060 times.
✓ Branch 1 taken 15014 times.
|
2/2✓ Decision 'true' taken 50060 times.
✓ Decision 'false' taken 15014 times.
|
65074 | for (j = 0; j < size; j++) { |
512 | 50060 | Node *old = gnode(ot, j); | ||
513 |
2/2✓ Branch 0 taken 42539 times.
✓ Branch 1 taken 7521 times.
|
2/2✓ Decision 'true' taken 42539 times.
✓ Decision 'false' taken 7521 times.
|
50060 | if (!isempty(gval(old))) { |
514 | /* doesn't need barrier/invalidate cache, as entry was | |||
515 | already present in the table */ | |||
516 | TValue k; | |||
517 | 42539 | getnodekey(L, &k, old); | ||
518 | 42539 | luaH_set(L, t, &k, gval(old)); | ||
519 | } | |||
520 | } | |||
521 | 15014 | } | ||
522 | ||||
523 | ||||
524 | /* | |||
525 | ** Exchange the hash part of 't1' and 't2'. | |||
526 | */ | |||
527 | 15014 | static void exchangehashpart (Table *t1, Table *t2) { | ||
528 | 15014 | lu_byte lsizenode = t1->lsizenode; | ||
529 | 15014 | Node *node = t1->node; | ||
530 | 15014 | Node *lastfree = t1->lastfree; | ||
531 | 15014 | t1->lsizenode = t2->lsizenode; | ||
532 | 15014 | t1->node = t2->node; | ||
533 | 15014 | t1->lastfree = t2->lastfree; | ||
534 | 15014 | t2->lsizenode = lsizenode; | ||
535 | 15014 | t2->node = node; | ||
536 | 15014 | t2->lastfree = lastfree; | ||
537 | 15014 | } | ||
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 | 15014 | void luaH_resize (lua_State *L, Table *t, unsigned int newasize, | ||
554 | unsigned int nhsize) { | |||
555 | unsigned int i; | |||
556 | Table newt; /* to keep the new hash part */ | |||
557 | 15014 | unsigned int oldasize = setlimittosize(t); | ||
558 | TValue *newarray; | |||
559 | /* create new hash part with appropriate size into 'newt' */ | |||
560 | 15014 | setnodevector(L, &newt, nhsize); | ||
561 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 15014 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 15014 times.
|
15014 | if (newasize < oldasize) { /* will array shrink? */ |
562 | ✗ | t->alimit = newasize; /* pretend array has new size... */ | ||
563 | ✗ | exchangehashpart(t, &newt); /* and new hash */ | ||
564 | /* re-insert into the new hash the elements from vanishing slice */ | |||
565 | ✗ | for (i = newasize; i < oldasize; i++) { | ||
566 | ✗ | if (!isempty(&t->array[i])) | ||
567 | ✗ | luaH_setint(L, t, i + 1, &t->array[i]); | ||
568 | } | |||
569 | ✗ | t->alimit = oldasize; /* restore current size... */ | ||
570 | ✗ | exchangehashpart(t, &newt); /* and hash (in case of errors) */ | ||
571 | } | |||
572 | /* allocate new array */ | |||
573 | 15014 | newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue); | ||
574 |
4/6✓ Branch 0 taken 13055 times.
✓ Branch 1 taken 1959 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 13055 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 15014 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 15014 times.
|
15014 | if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ |
575 | ✗ | freehash(L, &newt); /* release new hash part */ | ||
576 | ✗ | luaM_error(L); /* raise error (with array unchanged) */ | ||
577 | } | |||
578 | /* allocation ok; initialize new part of the array */ | |||
579 | 15014 | exchangehashpart(t, &newt); /* 't' has the new hash ('newt' has the old) */ | ||
580 | 15014 | t->array = newarray; /* set new array part */ | ||
581 | 15014 | t->alimit = newasize; | ||
582 |
2/2✓ Branch 0 taken 1414 times.
✓ Branch 1 taken 15014 times.
|
2/2✓ Decision 'true' taken 1414 times.
✓ Decision 'false' taken 15014 times.
|
16428 | for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ |
583 | 1414 | setempty(&t->array[i]); | ||
584 | /* re-insert elements from old hash part into new parts */ | |||
585 | 15014 | reinsert(L, &newt, t); /* 'newt' now has the old hash */ | ||
586 | 15014 | freehash(L, &newt); /* free old hash part */ | ||
587 | 15014 | } | ||
588 | ||||
589 | ||||
590 | ✗ | void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) { | ||
591 | ✗ | int nsize = allocsizenode(t); | ||
592 | ✗ | luaH_resize(L, t, nasize, nsize); | ||
593 | ✗ | } | ||
594 | ||||
595 | /* | |||
596 | ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i | |||
597 | */ | |||
598 | 10583 | static void rehash (lua_State *L, Table *t, const TValue *ek) { | ||
599 | unsigned int asize; /* optimal size for array part */ | |||
600 | unsigned int na; /* number of keys in the array part */ | |||
601 | unsigned int nums[MAXABITS + 1]; | |||
602 | int i; | |||
603 | int totaluse; | |||
604 |
2/2✓ Branch 0 taken 338656 times.
✓ Branch 1 taken 10583 times.
|
2/2✓ Decision 'true' taken 338656 times.
✓ Decision 'false' taken 10583 times.
|
349239 | for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */ |
605 | 10583 | setlimittosize(t); | ||
606 | 10583 | na = numusearray(t, nums); /* count keys in array part */ | ||
607 | 10583 | totaluse = na; /* all those keys are integer keys */ | ||
608 | 10583 | totaluse += numusehash(t, nums, &na); /* count keys in hash part */ | ||
609 | /* count extra key */ | |||
610 |
2/2✓ Branch 0 taken 25 times.
✓ Branch 1 taken 10558 times.
|
2/2✓ Decision 'true' taken 25 times.
✓ Decision 'false' taken 10558 times.
|
10583 | if (ttisinteger(ek)) |
611 | 25 | na += countint(ivalue(ek), nums); | ||
612 | 10583 | totaluse++; | ||
613 | /* compute new size for array part */ | |||
614 | 10583 | asize = computesizes(nums, &na); | ||
615 | /* resize the table to new computed sizes */ | |||
616 | 10583 | luaH_resize(L, t, asize, totaluse - na); | ||
617 | 10583 | } | ||
618 | ||||
619 | ||||
620 | ||||
621 | /* | |||
622 | ** }============================================================= | |||
623 | */ | |||
624 | ||||
625 | ||||
626 | 7213 | Table *luaH_new (lua_State *L) { | ||
627 | 7213 | GCObject *o = luaC_newobj(L, LUA_VTABLE, sizeof(Table)); | ||
628 | 7213 | Table *t = gco2t(o); | ||
629 | 7213 | t->metatable = NULL; | ||
630 | 7213 | t->flags = cast_byte(maskflags); /* table has no metamethod fields */ | ||
631 | 7213 | t->array = NULL; | ||
632 | 7213 | t->alimit = 0; | ||
633 | 7213 | setnodevector(L, t, 0); | ||
634 | 7213 | return t; | ||
635 | } | |||
636 | ||||
637 | ||||
638 | 7213 | void luaH_free (lua_State *L, Table *t) { | ||
639 | 7213 | freehash(L, t); | ||
640 | 7213 | luaM_freearray(L, t->array, luaH_realasize(t)); | ||
641 | 7213 | luaM_free(L, t); | ||
642 | 7213 | } | ||
643 | ||||
644 | ||||
645 | 47458 | static Node *getfreepos (Table *t) { | ||
646 |
2/2✓ Branch 0 taken 44368 times.
✓ Branch 1 taken 3090 times.
|
2/2✓ Decision 'true' taken 44368 times.
✓ Decision 'false' taken 3090 times.
|
47458 | if (!isdummy(t)) { |
647 |
2/2✓ Branch 0 taken 75373 times.
✓ Branch 1 taken 7493 times.
|
2/2✓ Decision 'true' taken 75373 times.
✓ Decision 'false' taken 7493 times.
|
82866 | while (t->lastfree > t->node) { |
648 | 75373 | t->lastfree--; | ||
649 |
2/2✓ Branch 0 taken 36875 times.
✓ Branch 1 taken 38498 times.
|
2/2✓ Decision 'true' taken 36875 times.
✓ Decision 'false' taken 38498 times.
|
75373 | if (keyisnil(t->lastfree)) |
650 | 36875 | return t->lastfree; | ||
651 | } | |||
652 | } | |||
653 | 10583 | return NULL; /* could not find a free place */ | ||
654 | } | |||
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 | 104547 | void luaH_newkey (lua_State *L, Table *t, const TValue *key, TValue *value) { | ||
666 | Node *mp; | |||
667 | TValue aux; | |||
668 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 104547 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 104547 times.
|
104547 | if (l_unlikely(ttisnil(key))) |
669 | ✗ | luaG_runerror(L, "table index is nil"); | ||
670 |
2/2✓ Branch 0 taken 68 times.
✓ Branch 1 taken 104479 times.
|
2/2✓ Decision 'true' taken 68 times.
✓ Decision 'false' taken 104479 times.
|
104547 | else if (ttisfloat(key)) { |
671 | 68 | lua_Number f = fltvalue(key); | ||
672 | lua_Integer k; | |||
673 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 68 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 68 times.
|
68 | if (luaV_flttointeger(f, &k, F2Ieq)) { /* does key fit in an integer? */ |
674 | ✗ | setivalue(&aux, k); | ||
675 | ✗ | key = &aux; /* insert it as an integer */ | ||
676 | } | |||
677 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 68 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 68 times.
|
68 | else if (l_unlikely(luai_numisnan(f))) |
678 | ✗ | luaG_runerror(L, "table index is NaN"); | ||
679 | } | |||
680 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 104547 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 104547 times.
|
104547 | if (ttisnil(value)) |
681 | 10583 | return; /* do not insert nil values */ | ||
682 | 104547 | mp = mainpositionTV(t, key); | ||
683 |
4/4✓ Branch 0 taken 60179 times.
✓ Branch 1 taken 44368 times.
✓ Branch 2 taken 3090 times.
✓ Branch 3 taken 57089 times.
|
2/2✓ Decision 'true' taken 47458 times.
✓ Decision 'false' taken 57089 times.
|
104547 | if (!isempty(gval(mp)) || isdummy(t)) { /* main position is taken? */ |
684 | Node *othern; | |||
685 | 47458 | Node *f = getfreepos(t); /* get a free place */ | ||
686 |
2/2✓ Branch 0 taken 10583 times.
✓ Branch 1 taken 36875 times.
|
2/2✓ Decision 'true' taken 10583 times.
✓ Decision 'false' taken 36875 times.
|
47458 | if (f == NULL) { /* cannot find a free place? */ |
687 | 10583 | rehash(L, t, key); /* grow table */ | ||
688 | /* whatever called 'newkey' takes care of TM cache */ | |||
689 | 10583 | luaH_set(L, t, key, value); /* insert key into grown table */ | ||
690 | 10583 | return; | ||
691 | } | |||
692 | lua_assert(!isdummy(t)); | |||
693 | 36875 | othern = mainpositionfromnode(t, mp); | ||
694 |
2/2✓ Branch 0 taken 7906 times.
✓ Branch 1 taken 28969 times.
|
2/2✓ Decision 'true' taken 7906 times.
✓ Decision 'false' taken 28969 times.
|
36875 | if (othern != mp) { /* is colliding node out of its main position? */ |
695 | /* yes; move colliding node into free position */ | |||
696 |
2/2✓ Branch 0 taken 1636 times.
✓ Branch 1 taken 7906 times.
|
2/2✓ Decision 'true' taken 1636 times.
✓ Decision 'false' taken 7906 times.
|
9542 | while (othern + gnext(othern) != mp) /* find previous */ |
697 | 1636 | othern += gnext(othern); | ||
698 | 7906 | gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */ | ||
699 | 7906 | *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */ | ||
700 |
2/2✓ Branch 0 taken 1333 times.
✓ Branch 1 taken 6573 times.
|
2/2✓ Decision 'true' taken 1333 times.
✓ Decision 'false' taken 6573 times.
|
7906 | if (gnext(mp) != 0) { |
701 | 1333 | gnext(f) += cast_int(mp - f); /* correct 'next' */ | ||
702 | 1333 | gnext(mp) = 0; /* now 'mp' is free */ | ||
703 | } | |||
704 | 7906 | setempty(gval(mp)); | ||
705 | } | |||
706 | else { /* colliding node is in its own main position */ | |||
707 | /* new node will go into free position */ | |||
708 |
2/2✓ Branch 0 taken 6315 times.
✓ Branch 1 taken 22654 times.
|
2/2✓ Decision 'true' taken 6315 times.
✓ Decision 'false' taken 22654 times.
|
28969 | if (gnext(mp) != 0) |
709 | 6315 | gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */ | ||
710 | else lua_assert(gnext(f) == 0); | |||
711 | 28969 | gnext(mp) = cast_int(f - mp); | ||
712 | 28969 | mp = f; | ||
713 | } | |||
714 | } | |||
715 | 93964 | setnodekey(L, mp, key); | ||
716 |
3/6✓ Branch 0 taken 93670 times.
✓ Branch 1 taken 294 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 93670 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
|
93964 | luaC_barrierback(L, obj2gco(t), key); | |
717 | lua_assert(isempty(gval(mp))); | |||
718 | 93964 | setobj2t(L, gval(mp), value); | ||
719 | } | |||
720 | ||||
721 | ||||
722 | /* | |||
723 | ** Search function for integers. If integer is inside 'alimit', get it | |||
724 | ** directly from the array part. Otherwise, if 'alimit' is not equal to | |||
725 | ** the real size of the array, key still can be in the array part. In | |||
726 | ** this case, try to avoid a call to 'luaH_realasize' when key is just | |||
727 | ** one more than the limit (so that it can be incremented without | |||
728 | ** changing the real size of the array). | |||
729 | */ | |||
730 | 390 | const TValue *luaH_getint (Table *t, lua_Integer key) { | ||
731 |
2/2✓ Branch 0 taken 42 times.
✓ Branch 1 taken 348 times.
|
2/2✓ Decision 'true' taken 42 times.
✓ Decision 'false' taken 348 times.
|
390 | if (l_castS2U(key) - 1u < t->alimit) /* 'key' in [1, t->alimit]? */ |
732 | 42 | return &t->array[key - 1]; | ||
733 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 348 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 348 times.
|
348 | else if (!limitequalsasize(t) && /* key still may be in the array part? */ |
734 | ✗ | (l_castS2U(key) == t->alimit + 1 || | ||
735 | ✗ | l_castS2U(key) - 1u < luaH_realasize(t))) { | ||
736 | ✗ | t->alimit = cast_uint(key); /* probably '#t' is here now */ | ||
737 | ✗ | return &t->array[key - 1]; | ||
738 | } | |||
739 | else { | |||
740 | 348 | Node *n = hashint(t, key); | ||
741 | for (;;) { /* check whether 'key' is somewhere in the chain */ | |||
742 |
4/4✓ Branch 0 taken 69 times.
✓ Branch 1 taken 349 times.
✓ Branch 2 taken 36 times.
✓ Branch 3 taken 33 times.
|
2/2✓ Decision 'true' taken 36 times.
✓ Decision 'false' taken 382 times.
|
418 | if (keyisinteger(n) && keyival(n) == key) |
743 | 36 | return gval(n); /* that's it */ | ||
744 | else { | |||
745 | 382 | int nx = gnext(n); | ||
746 |
2/2✓ Branch 0 taken 312 times.
✓ Branch 1 taken 70 times.
|
2/2✓ Decision 'true' taken 312 times.
✓ Decision 'false' taken 70 times.
|
382 | if (nx == 0) break; |
747 | 70 | n += nx; | ||
748 | } | |||
749 | } | |||
750 | 312 | return &absentkey; | ||
751 | } | |||
752 | } | |||
753 | ||||
754 | ||||
755 | /* | |||
756 | ** search function for short strings | |||
757 | */ | |||
758 | 127734 | const TValue *luaH_getshortstr (Table *t, TString *key) { | ||
759 | 127734 | Node *n = hashstr(t, key); | ||
760 | lua_assert(key->tt == LUA_VSHRSTR); | |||
761 | for (;;) { /* check whether 'key' is somewhere in the chain */ | |||
762 |
4/4✓ Branch 0 taken 86679 times.
✓ Branch 1 taken 61971 times.
✓ Branch 2 taken 17365 times.
✓ Branch 3 taken 69314 times.
|
2/2✓ Decision 'true' taken 17365 times.
✓ Decision 'false' taken 131285 times.
|
148650 | if (keyisshrstr(n) && eqshrstr(keystrval(n), key)) |
763 | 17365 | return gval(n); /* that's it */ | ||
764 | else { | |||
765 | 131285 | int nx = gnext(n); | ||
766 |
2/2✓ Branch 0 taken 110369 times.
✓ Branch 1 taken 20916 times.
|
2/2✓ Decision 'true' taken 110369 times.
✓ Decision 'false' taken 20916 times.
|
131285 | if (nx == 0) |
767 | 110369 | return &absentkey; /* not found */ | ||
768 | 20916 | n += nx; | ||
769 | } | |||
770 | } | |||
771 | } | |||
772 | ||||
773 | ||||
774 | 62241 | const TValue *luaH_getstr (Table *t, TString *key) { | ||
775 |
1/2✓ Branch 0 taken 62241 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 62241 times.
✗ Decision 'false' not taken.
|
62241 | if (key->tt == LUA_VSHRSTR) |
776 | 62241 | return luaH_getshortstr(t, key); | ||
777 | else { /* for long strings, use generic case */ | |||
778 | TValue ko; | |||
779 | ✗ | setsvalue(cast(lua_State *, NULL), &ko, key); | ||
780 | ✗ | return getgeneric(t, &ko, 0); | ||
781 | } | |||
782 | } | |||
783 | ||||
784 | ||||
785 | /* | |||
786 | ** main search function | |||
787 | */ | |||
788 | 60428 | const TValue *luaH_get (Table *t, const TValue *key) { | ||
789 |
4/5✓ Branch 0 taken 59936 times.
✓ Branch 1 taken 294 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 126 times.
✓ Branch 4 taken 72 times.
|
60428 | switch (ttypetag(key)) { | |
790 |
1/1✓ Decision 'true' taken 59936 times.
|
59936 | case LUA_VSHRSTR: return luaH_getshortstr(t, tsvalue(key)); | |
791 |
1/1✓ Decision 'true' taken 294 times.
|
294 | case LUA_VNUMINT: return luaH_getint(t, ivalue(key)); | |
792 | ✗ | case LUA_VNIL: return &absentkey; | ||
793 |
1/1✓ Decision 'true' taken 126 times.
|
126 | case LUA_VNUMFLT: { | |
794 | lua_Integer k; | |||
795 |
2/2✓ Branch 1 taken 51 times.
✓ Branch 2 taken 75 times.
|
2/2✓ Decision 'true' taken 51 times.
✓ Decision 'false' taken 75 times.
|
126 | if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */ |
796 | 51 | return luaH_getint(t, k); /* use specialized version */ | ||
797 | /* else... */ | |||
798 | } /* FALLTHROUGH */ | |||
799 | default: | |||
800 |
1/1✓ Decision 'true' taken 147 times.
|
147 | return getgeneric(t, key, 0); | |
801 | } | |||
802 | } | |||
803 | ||||
804 | ||||
805 | /* | |||
806 | ** Finish a raw "set table" operation, where 'slot' is where the value | |||
807 | ** should have been (the result of a previous "get table"). | |||
808 | ** Beware: when using this function you probably need to check a GC | |||
809 | ** barrier and invalidate the TM cache. | |||
810 | */ | |||
811 | 105629 | void luaH_finishset (lua_State *L, Table *t, const TValue *key, | ||
812 | const TValue *slot, TValue *value) { | |||
813 |
2/2✓ Branch 0 taken 104547 times.
✓ Branch 1 taken 1082 times.
|
2/2✓ Decision 'true' taken 104547 times.
✓ Decision 'false' taken 1082 times.
|
105629 | if (isabstkey(slot)) |
814 | 104547 | luaH_newkey(L, t, key, value); | ||
815 | else | |||
816 | 1082 | setobj2t(L, cast(TValue *, slot), value); | ||
817 | 105629 | } | ||
818 | ||||
819 | ||||
820 | /* | |||
821 | ** beware: when using this function you probably need to check a GC | |||
822 | ** barrier and invalidate the TM cache. | |||
823 | */ | |||
824 | 53122 | void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) { | ||
825 | 53122 | const TValue *slot = luaH_get(t, key); | ||
826 | 53122 | luaH_finishset(L, t, key, slot, value); | ||
827 | 53122 | } | ||
828 | ||||
829 | ||||
830 | ✗ | void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { | ||
831 | ✗ | const TValue *p = luaH_getint(t, key); | ||
832 | ✗ | if (isabstkey(p)) { | ||
833 | TValue k; | |||
834 | ✗ | setivalue(&k, key); | ||
835 | ✗ | luaH_newkey(L, t, &k, value); | ||
836 | } | |||
837 | else | |||
838 | ✗ | setobj2t(L, cast(TValue *, p), value); | ||
839 | ✗ | } | ||
840 | ||||
841 | ||||
842 | /* | |||
843 | ** Try to find a boundary in the hash part of table 't'. From the | |||
844 | ** caller, we know that 'j' is zero or present and that 'j + 1' is | |||
845 | ** present. We want to find a larger key that is absent from the | |||
846 | ** table, so that we can do a binary search between the two keys to | |||
847 | ** find a boundary. We keep doubling 'j' until we get an absent index. | |||
848 | ** If the doubling would overflow, we try LUA_MAXINTEGER. If it is | |||
849 | ** absent, we are ready for the binary search. ('j', being max integer, | |||
850 | ** is larger or equal to 'i', but it cannot be equal because it is | |||
851 | ** absent while 'i' is present; so 'j > i'.) Otherwise, 'j' is a | |||
852 | ** boundary. ('j + 1' cannot be a present integer key because it is | |||
853 | ** not a valid integer in Lua.) | |||
854 | */ | |||
855 | ✗ | static lua_Unsigned hash_search (Table *t, lua_Unsigned j) { | ||
856 | lua_Unsigned i; | |||
857 | ✗ | if (j == 0) j++; /* the caller ensures 'j + 1' is present */ | ||
858 | do { | |||
859 | ✗ | i = j; /* 'i' is a present index */ | ||
860 | ✗ | if (j <= l_castS2U(LUA_MAXINTEGER) / 2) | ||
861 | ✗ | j *= 2; | ||
862 | else { | |||
863 | ✗ | j = LUA_MAXINTEGER; | ||
864 | ✗ | if (isempty(luaH_getint(t, j))) /* t[j] not present? */ | ||
865 | ✗ | break; /* 'j' now is an absent index */ | ||
866 | else /* weird case */ | |||
867 | ✗ | return j; /* well, max integer is a boundary... */ | ||
868 | } | |||
869 | ✗ | } while (!isempty(luaH_getint(t, j))); /* repeat until an absent t[j] */ | ||
870 | /* i < j && t[i] present && t[j] absent */ | |||
871 | ✗ | while (j - i > 1u) { /* do a binary search between them */ | ||
872 | ✗ | lua_Unsigned m = (i + j) / 2; | ||
873 | ✗ | if (isempty(luaH_getint(t, m))) j = m; | ||
874 | ✗ | else i = m; | ||
875 | } | |||
876 | ✗ | return i; | ||
877 | } | |||
878 | ||||
879 | ||||
880 | ✗ | static unsigned int binsearch (const TValue *array, unsigned int i, | ||
881 | unsigned int j) { | |||
882 | ✗ | while (j - i > 1u) { /* binary search */ | ||
883 | ✗ | unsigned int m = (i + j) / 2; | ||
884 | ✗ | if (isempty(&array[m - 1])) j = m; | ||
885 | ✗ | else i = m; | ||
886 | } | |||
887 | ✗ | return i; | ||
888 | } | |||
889 | ||||
890 | ||||
891 | /* | |||
892 | ** Try to find a boundary in table 't'. (A 'boundary' is an integer index | |||
893 | ** such that t[i] is present and t[i+1] is absent, or 0 if t[1] is absent | |||
894 | ** and 'maxinteger' if t[maxinteger] is present.) | |||
895 | ** (In the next explanation, we use Lua indices, that is, with base 1. | |||
896 | ** The code itself uses base 0 when indexing the array part of the table.) | |||
897 | ** The code starts with 'limit = t->alimit', a position in the array | |||
898 | ** part that may be a boundary. | |||
899 | ** | |||
900 | ** (1) If 't[limit]' is empty, there must be a boundary before it. | |||
901 | ** As a common case (e.g., after 't[#t]=nil'), check whether 'limit-1' | |||
902 | ** is present. If so, it is a boundary. Otherwise, do a binary search | |||
903 | ** between 0 and limit to find a boundary. In both cases, try to | |||
904 | ** use this boundary as the new 'alimit', as a hint for the next call. | |||
905 | ** | |||
906 | ** (2) If 't[limit]' is not empty and the array has more elements | |||
907 | ** after 'limit', try to find a boundary there. Again, try first | |||
908 | ** the special case (which should be quite frequent) where 'limit+1' | |||
909 | ** is empty, so that 'limit' is a boundary. Otherwise, check the | |||
910 | ** last element of the array part. If it is empty, there must be a | |||
911 | ** boundary between the old limit (present) and the last element | |||
912 | ** (absent), which is found with a binary search. (This boundary always | |||
913 | ** can be a new limit.) | |||
914 | ** | |||
915 | ** (3) The last case is when there are no elements in the array part | |||
916 | ** (limit == 0) or its last element (the new limit) is present. | |||
917 | ** In this case, must check the hash part. If there is no hash part | |||
918 | ** or 'limit+1' is absent, 'limit' is a boundary. Otherwise, call | |||
919 | ** 'hash_search' to find a boundary in the hash part of the table. | |||
920 | ** (In those cases, the boundary is not inside the array part, and | |||
921 | ** therefore cannot be used as a new limit.) | |||
922 | */ | |||
923 | ✗ | lua_Unsigned luaH_getn (Table *t) { | ||
924 | ✗ | unsigned int limit = t->alimit; | ||
925 | ✗ | if (limit > 0 && isempty(&t->array[limit - 1])) { /* (1)? */ | ||
926 | /* there must be a boundary before 'limit' */ | |||
927 | ✗ | if (limit >= 2 && !isempty(&t->array[limit - 2])) { | ||
928 | /* 'limit - 1' is a boundary; can it be a new limit? */ | |||
929 | ✗ | if (ispow2realasize(t) && !ispow2(limit - 1)) { | ||
930 | ✗ | t->alimit = limit - 1; | ||
931 | ✗ | setnorealasize(t); /* now 'alimit' is not the real size */ | ||
932 | } | |||
933 | ✗ | return limit - 1; | ||
934 | } | |||
935 | else { /* must search for a boundary in [0, limit] */ | |||
936 | ✗ | unsigned int boundary = binsearch(t->array, 0, limit); | ||
937 | /* can this boundary represent the real size of the array? */ | |||
938 | ✗ | if (ispow2realasize(t) && boundary > luaH_realasize(t) / 2) { | ||
939 | ✗ | t->alimit = boundary; /* use it as the new limit */ | ||
940 | ✗ | setnorealasize(t); | ||
941 | } | |||
942 | ✗ | return boundary; | ||
943 | } | |||
944 | } | |||
945 | /* 'limit' is zero or present in table */ | |||
946 | ✗ | if (!limitequalsasize(t)) { /* (2)? */ | ||
947 | /* 'limit' > 0 and array has more elements after 'limit' */ | |||
948 | ✗ | if (isempty(&t->array[limit])) /* 'limit + 1' is empty? */ | ||
949 | ✗ | return limit; /* this is the boundary */ | ||
950 | /* else, try last element in the array */ | |||
951 | ✗ | limit = luaH_realasize(t); | ||
952 | ✗ | if (isempty(&t->array[limit - 1])) { /* empty? */ | ||
953 | /* there must be a boundary in the array after old limit, | |||
954 | and it must be a valid new limit */ | |||
955 | ✗ | unsigned int boundary = binsearch(t->array, t->alimit, limit); | ||
956 | ✗ | t->alimit = boundary; | ||
957 | ✗ | return boundary; | ||
958 | } | |||
959 | /* else, new limit is present in the table; check the hash part */ | |||
960 | } | |||
961 | /* (3) 'limit' is the last element and either is zero or present in table */ | |||
962 | lua_assert(limit == luaH_realasize(t) && | |||
963 | (limit == 0 || !isempty(&t->array[limit - 1]))); | |||
964 | ✗ | if (isdummy(t) || isempty(luaH_getint(t, cast(lua_Integer, limit + 1)))) | ||
965 | ✗ | return limit; /* 'limit + 1' is absent */ | ||
966 | else /* 'limit + 1' is also present */ | |||
967 | ✗ | return hash_search(t, limit); | ||
968 | } | |||
969 | ||||
970 | ||||
971 | ||||
972 | #if defined(LUA_DEBUG) | |||
973 | ||||
974 | /* export these functions for the test library */ | |||
975 | ||||
976 | Node *luaH_mainposition (const Table *t, const TValue *key) { | |||
977 | return mainpositionTV(t, key); | |||
978 | } | |||
979 | ||||
980 | #endif | |||
981 |