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