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