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