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
95static 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
101static 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)
119static 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*/
141static 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*/
182static 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*/
207static 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*/
241LUAI_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*/
267static int ispow2realasize (const Table *t) {
268 return (!isrealasize(t) || ispow2(t->alimit));
269}
270
271
272static 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*/
288static 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*/
307static 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*/
320static 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
338int 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
360static 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*/
380static 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
402static 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*/
418static 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
445static 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*/
469static 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*/
497static 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*/
516static 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*/
542void 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
579void 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*/
587static 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
615Table *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
627void 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
634static 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*/
654void 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*/
719const 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*/
747const 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
763const 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*/
777const 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*/
800void 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*/
813void 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
819void 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*/
844static 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
869static 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*/
912lua_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
965Node *luaH_mainposition (const Table *t, const TValue *key) {
966 return mainpositionTV(t, key);
967}
968
969int luaH_isdummy (const Table *t) { return isdummy(t); }
970
971#endif
972