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
46 #define MAXABITS	cast_int(sizeof(int) * CHAR_BIT - 1)
50 ** MAXASIZE is the maximum size of the array part. It is the minimum
60 #define MAXHBITS	(MAXABITS - 1)
64 ** MAXHSIZE is the maximum size of the hash part. It is the minimum
81 #define hashmod(t,n)	(gnode(t, ((n) % ((sizenode(t)-1)|1))))
84 #define hashstr(t,str)		hashpow2(t, (str)->hash)
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.
118 ** Hash for floating-point numbers.
122 ** In a two-complement representation, INT_MAX does not has an exact
125 ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
127 ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
134   n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN);  in l_hashfloat()
135   if (!lua_numbertointeger(n, &ni)) {  /* is 'n' inf/-inf/NaN? */  in l_hashfloat()
241 ** part of table 't'. (Otherwise, the array part must be larger than
244 #define limitequalsasize(t)	(isrealasize(t) || ispow2((t)->alimit))
252     return t->alimit;  /* this is the size */  in luaH_realasize()
254     unsigned int size = t->alimit;  in luaH_realasize()
267     lua_assert(ispow2(size) && size/2 < t->alimit && t->alimit < size);  in luaH_realasize()
279   return (!isrealasize(t) || ispow2(t->alimit));  in ispow2realasize()
284   t->alimit = luaH_realasize(t);  in setlimittosize()
286   return t->alimit;  in setlimittosize()
290 #define limitasasize(t)	check_exp(isrealasize(t), t->alimit)
296 ** which may be in array part, nor for floats with integral values.)
316 ** the array part of a table, 0 otherwise.
319   if (l_castS2U(k) - 1u < MAXASIZE)  /* 'k' in [1, MAXASIZE]? */  in arrayindex()
328 ** elements in the array part, then elements in the hash part. The
336   if (i - 1u < asize)  /* is 'key' inside array part? */  in findindex()
342     i = cast_int(nodefromval(n) - gnode(t, 0));  /* key index in hash table */  in findindex()
352   for (; i < asize; i++) {  /* try first array part */  in luaH_next()
353     if (!isempty(&t->array[i])) {  /* a non-empty entry? */  in luaH_next()
355       setobj2s(L, key + 1, &t->array[i]);  in luaH_next()
359   for (i -= asize; cast_int(i) < sizenode(t); i++) {  /* hash part */  in luaH_next()
360     if (!isempty(gval(gnode(t, i)))) {  /* a non-empty entry? */  in luaH_next()
373     luaM_freearray(L, t->node, cast_sizet(sizenode(t)));  in freehash()
384 ** Compute the optimal size for the array part of table 't'. 'nums' is a
385 ** "count array" where 'nums[i]' is the number of integers in the table
386 ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
387 ** integer keys in the table and leaves with the number of keys that
388 ** will go to the array part; return the optimal size.  (The condition
394   unsigned int a = 0;  /* number of elements smaller than 2^i */  in computesizes()
395   unsigned int na = 0;  /* number of elements to go to array part */  in computesizes()
396   unsigned int optimal = 0;  /* optimal size for array part */  in computesizes()
404       na = a;  /* all elements up to 'optimal' will go to array part */  in computesizes()
425 ** Count keys in array part of table 't': Fill 'nums[i]' with
426 ** number of keys that will go into corresponding slice and return
427 ** total number of non-nil keys.
444     /* count elements in range (2^(lg - 1), 2^lg] */  in numusearray()
446       if (!isempty(&t->array[i-1]))  in numusearray()
457   int totaluse = 0;  /* total number of elements */  in numusehash()
458   int ause = 0;  /* elements added to 'nums' (can go to array part) */  in numusehash()
460   while (i--) {  in numusehash()
461     Node *n = &t->node[i];  in numusehash()
474 ** Creates an array for the hash part of a table with the given
481   if (size == 0) {  /* no elements to hash part? */  in setnodevector()
482     t->node = cast(Node *, dummynode);  /* use common 'dummynode' */  in setnodevector()
483     t->lsizenode = 0;  in setnodevector()
484     t->lastfree = NULL;  /* signal that it is using dummy node */  in setnodevector()
492     t->node = luaM_newvector(L, size, Node);  in setnodevector()
499     t->lsizenode = cast_byte(lsize);  in setnodevector()
500     t->lastfree = gnode(t, size);  /* all positions are free */  in setnodevector()
506 ** (Re)insert all elements from the hash part of 'ot' into table 't'.
525 ** Exchange the hash part of 't1' and 't2'.
528   lu_byte lsizenode = t1->lsizenode;  in exchangehashpart()
529   Node *node = t1->node;  in exchangehashpart()
530   Node *lastfree = t1->lastfree;  in exchangehashpart()
531   t1->lsizenode = t2->lsizenode;  in exchangehashpart()
532   t1->node = t2->node;  in exchangehashpart()
533   t1->lastfree = t2->lastfree;  in exchangehashpart()
534   t2->lsizenode = lsizenode;  in exchangehashpart()
535   t2->node = node;  in exchangehashpart()
536   t2->lastfree = lastfree;  in exchangehashpart()
542 ** the hash part and for the array part) can fail, which creates some
543 ** subtleties. If the first allocation, for the hash part, fails, an
545 ** the shrinking part of the array (if it is shrinking) into the new
546 ** hash. Then it reallocates the array part.  If that fails, the table
547 ** is in its original state; the function frees the new hash part and then
548 ** raises the allocation error. Otherwise, it sets the new hash part
549 ** into the table, initializes the new part of the array (if any) with
556   Table newt;  /* to keep the new hash part */  in luaH_resize()
559   /* create new hash part with appropriate size into 'newt' */  in luaH_resize()
562     t->alimit = newasize;  /* pretend array has new size... */  in luaH_resize()
564     /* re-insert into the new hash the elements from vanishing slice */  in luaH_resize()
566       if (!isempty(&t->array[i]))  in luaH_resize()
567         luaH_setint(L, t, i + 1, &t->array[i]);  in luaH_resize()
569     t->alimit = oldasize;  /* restore current size... */  in luaH_resize()
573   newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue);  in luaH_resize()
575     freehash(L, &newt);  /* release new hash part */  in luaH_resize()
578   /* allocation ok; initialize new part of the array */  in luaH_resize()
580   t->array = newarray;  /* set new array part */  in luaH_resize()
581   t->alimit = newasize;  in luaH_resize()
583      setempty(&t->array[i]);  in luaH_resize()
584   /* re-insert elements from old hash part into new parts */  in luaH_resize()
586   freehash(L, &newt);  /* free old hash part */  in luaH_resize()
596 ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
599   unsigned int asize;  /* optimal size for array part */  in rehash()
600   unsigned int na;  /* number of keys in the array part */  in rehash()
606   na = numusearray(t, nums);  /* count keys in array part */  in rehash()
608   totaluse += numusehash(t, nums, &na);  /* count keys in hash part */  in rehash()
613   /* compute new size for array part */  in rehash()
616   luaH_resize(L, t, asize, totaluse - na);  in rehash()
629   t->metatable = NULL;  in luaH_new()
630   t->flags = cast_byte(maskflags);  /* table has no metamethod fields */  in luaH_new()
631   t->array = NULL;  in luaH_new()
632   t->alimit = 0;  in luaH_new()
640   luaM_freearray(L, t->array, luaH_realasize(t));  in luaH_free()
647     while (t->lastfree > t->node) {  in getfreepos()
648       t->lastfree--;  in getfreepos()
649       if (keyisnil(t->lastfree))  in getfreepos()
650         return t->lastfree;  in getfreepos()
698       gnext(othern) = cast_int(f - othern);  /* rechain to point to 'f' */  in luaH_newkey()
699       *f = *mp;  /* copy colliding node into free pos. (mp->next also goes) */  in luaH_newkey()
701         gnext(f) += cast_int(mp - f);  /* correct 'next' */  in luaH_newkey()
709         gnext(f) = cast_int((mp + gnext(mp)) - f);  /* chain new position */  in luaH_newkey()
711       gnext(mp) = cast_int(f - mp);  in luaH_newkey()
724 ** directly from the array part. Otherwise, if 'alimit' is not equal to
725 ** the real size of the array, key still can be in the array part. In
731   if (l_castS2U(key) - 1u < t->alimit)  /* 'key' in [1, t->alimit]? */  in luaH_getint()
732     return &t->array[key - 1];  in luaH_getint()
733   else if (!limitequalsasize(t) &&  /* key still may be in the array part? */  in luaH_getint()
734            (l_castS2U(key) == t->alimit + 1 ||  in luaH_getint()
735             l_castS2U(key) - 1u < luaH_realasize(t))) {  in luaH_getint()
736     t->alimit = cast_uint(key);  /* probably '#t' is here now */  in luaH_getint()
737     return &t->array[key - 1];  in luaH_getint()
760   lua_assert(key->tt == LUA_VSHRSTR);  in luaH_getshortstr()
775   if (key->tt == LUA_VSHRSTR)  in luaH_getstr()
843 ** Try to find a boundary in the hash part of table 't'. From the
871   while (j - i > 1u) {  /* do a binary search between them */  in hash_search()
882   while (j - i > 1u) {  /* binary search */  in binsearch()
884     if (isempty(&array[m - 1])) j = m;  in binsearch()
896 ** The code itself uses base 0 when indexing the array part of the table.)
897 ** The code starts with 'limit = t->alimit', a position in the array
898 ** part that may be a boundary.
901 ** As a common case (e.g., after 't[#t]=nil'), check whether 'limit-1'
910 ** last element of the array part. If it is empty, there must be a
915 ** (3) The last case is when there are no elements in the array part
917 ** In this case, must check the hash part. If there is no hash part
919 ** 'hash_search' to find a boundary in the hash part of the table.
920 ** (In those cases, the boundary is not inside the array part, and
924   unsigned int limit = t->alimit;  in luaH_getn()
925   if (limit > 0 && isempty(&t->array[limit - 1])) {  /* (1)? */  in luaH_getn()
927     if (limit >= 2 && !isempty(&t->array[limit - 2])) {  in luaH_getn()
928       /* 'limit - 1' is a boundary; can it be a new limit? */  in luaH_getn()
929       if (ispow2realasize(t) && !ispow2(limit - 1)) {  in luaH_getn()
930         t->alimit = limit - 1;  in luaH_getn()
933       return limit - 1;  in luaH_getn()
936       unsigned int boundary = binsearch(t->array, 0, limit);  in luaH_getn()
939         t->alimit = boundary;  /* use it as the new limit */  in luaH_getn()
948     if (isempty(&t->array[limit]))  /* 'limit + 1' is empty? */  in luaH_getn()
952     if (isempty(&t->array[limit - 1])) {  /* empty? */  in luaH_getn()
955       unsigned int boundary = binsearch(t->array, t->alimit, limit);  in luaH_getn()
956       t->alimit = boundary;  in luaH_getn()
959     /* else, new limit is present in the table; check the hash part */  in luaH_getn()
963              (limit == 0 || !isempty(&t->array[limit - 1])));  in luaH_getn()