2 ** $Id: ltable.c,v 2.118.1.4 2018/06/08 16:22:51 roberto Exp $
4 ** See Copyright Notice in lua.h
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.
43 ** Maximum size of array part (MAXASIZE) is 2^MAXABITS. MAXABITS is
44 ** the largest integer such that MAXASIZE fits in an unsigned int.
46 #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1)
47 #define MAXASIZE (1u << MAXABITS)
50 ** Maximum size of hash part is 2^MAXHBITS. MAXHBITS is the largest
51 ** integer such that 2^MAXHBITS fits in a signed int. (Note that the
52 ** maximum number of elements in a table, 2^MAXABITS + 2^MAXHBITS, still
53 ** fits comfortably in an unsigned int.)
55 #define MAXHBITS (MAXABITS - 1)
58 #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
60 #define hashstr(t,str) hashpow2(t, (str)->hash)
61 #define hashboolean(t,p) hashpow2(t, p)
62 #define hashint(t,i) hashpow2(t, i)
66 ** for some types, it is better to avoid modulus by power of 2, as
67 ** they tend to have many 2 factors.
69 #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
72 #define hashpointer(t,p) hashmod(t, point2uint(p))
75 #define dummynode (&dummynode_)
77 static const Node dummynode_ = {
78 {NILCONSTANT}, /* value */
79 {{NILCONSTANT, 0}} /* key */
84 ** Hash for floating-point numbers.
85 ** The main computation should be just
86 ** n = frexp(n, &i); return (n * INT_MAX) + i
87 ** but there are some numerical subtleties.
88 ** In a two-complement representation, INT_MAX does not has an exact
89 ** representation as a float, but INT_MIN does; because the absolute
90 ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the
91 ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
92 ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when
93 ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
96 #if !defined(l_hashfloat)
97 static int l_hashfloat (lua_Number n) {
100 n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN);
101 if (!lua_numbertointeger(n, &ni)) { /* is 'n' inf/-inf/NaN? */
102 lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL));
105 else { /* normal case */
106 unsigned int u = cast(unsigned int, i) + cast(unsigned int, ni);
107 return cast_int(u <= cast(unsigned int, INT_MAX) ? u : ~u);
114 ** returns the 'main' position of an element in a table (that is, the index
115 ** of its hash value)
117 static Node *mainposition (const Table *t, const TValue *key) {
118 switch (ttype(key)) {
120 return hashint(t, ivalue(key));
122 return hashmod(t, l_hashfloat(fltvalue(key)));
124 return hashstr(t, tsvalue(key));
126 return hashpow2(t, luaS_hashlongstr(tsvalue(key)));
128 return hashboolean(t, bvalue(key));
129 case LUA_TLIGHTUSERDATA:
130 return hashpointer(t, pvalue(key));
132 return hashpointer(t, fvalue(key));
134 lua_assert(!ttisdeadkey(key));
135 return hashpointer(t, gcvalue(key));
141 ** returns the index for 'key' if 'key' is an appropriate key to live in
142 ** the array part of the table, 0 otherwise.
144 static unsigned int arrayindex (const TValue *key) {
145 if (ttisinteger(key)) {
146 lua_Integer k = ivalue(key);
147 if (0 < k && (lua_Unsigned)k <= MAXASIZE)
148 return cast(unsigned int, k); /* 'key' is an appropriate array index */
150 return 0; /* 'key' did not match some condition */
155 ** returns the index of a 'key' for table traversals. First goes all
156 ** elements in the array part, then elements in the hash part. The
157 ** beginning of a traversal is signaled by 0.
159 static unsigned int findindex (lua_State *L, Table *t, StkId key) {
161 if (ttisnil(key)) return 0; /* first iteration */
163 if (i != 0 && i <= t->sizearray) /* is 'key' inside array part? */
164 return i; /* yes; that's the index */
167 Node *n = mainposition(t, key);
168 for (;;) { /* check whether 'key' is somewhere in the chain */
169 /* key may be dead already, but it is ok to use it in 'next' */
170 if (luaV_rawequalobj(gkey(n), key) ||
171 (ttisdeadkey(gkey(n)) && iscollectable(key) &&
172 deadvalue(gkey(n)) == gcvalue(key))) {
173 i = cast_int(n - gnode(t, 0)); /* key index in hash table */
174 /* hash elements are numbered after array ones */
175 return (i + 1) + t->sizearray;
179 luaG_runerror(L, "invalid key to 'next'"); /* key not found */
186 int luaH_next (lua_State *L, Table *t, StkId key) {
187 unsigned int i = findindex(L, t, key); /* find original element */
188 for (; i < t->sizearray; i++) { /* try first array part */
189 if (!ttisnil(&t->array[i])) { /* a non-nil value? */
190 setivalue(key, i + 1);
191 setobj2s(L, key+1, &t->array[i]);
195 for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) { /* hash part */
196 if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
197 setobj2s(L, key, gkey(gnode(t, i)));
198 setobj2s(L, key+1, gval(gnode(t, i)));
202 return 0; /* no more elements */
207 ** {=============================================================
209 ** ==============================================================
213 ** Compute the optimal size for the array part of table 't'. 'nums' is a
214 ** "count array" where 'nums[i]' is the number of integers in the table
215 ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
216 ** integer keys in the table and leaves with the number of keys that
217 ** will go to the array part; return the optimal size.
219 static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {
221 unsigned int twotoi; /* 2^i (candidate for optimal size) */
222 unsigned int a = 0; /* number of elements smaller than 2^i */
223 unsigned int na = 0; /* number of elements to go to array part */
224 unsigned int optimal = 0; /* optimal size for array part */
225 /* loop while keys can fill more than half of total size */
226 for (i = 0, twotoi = 1;
227 twotoi > 0 && *pna > twotoi / 2;
231 if (a > twotoi/2) { /* more than half elements present? */
232 optimal = twotoi; /* optimal size (till now) */
233 na = a; /* all elements up to 'optimal' will go to array part */
237 lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
243 static int countint (const TValue *key, unsigned int *nums) {
244 unsigned int k = arrayindex(key);
245 if (k != 0) { /* is 'key' an appropriate array index? */
246 nums[luaO_ceillog2(k)]++; /* count as such */
255 ** Count keys in array part of table 't': Fill 'nums[i]' with
256 ** number of keys that will go into corresponding slice and return
257 ** total number of non-nil keys.
259 static unsigned int numusearray (const Table *t, unsigned int *nums) {
261 unsigned int ttlg; /* 2^lg */
262 unsigned int ause = 0; /* summation of 'nums' */
263 unsigned int i = 1; /* count to traverse all array keys */
264 /* traverse each slice */
265 for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
266 unsigned int lc = 0; /* counter */
267 unsigned int lim = ttlg;
268 if (lim > t->sizearray) {
269 lim = t->sizearray; /* adjust upper limit */
271 break; /* no more elements to count */
273 /* count elements in range (2^(lg - 1), 2^lg] */
274 for (; i <= lim; i++) {
275 if (!ttisnil(&t->array[i-1]))
285 static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
286 int totaluse = 0; /* total number of elements */
287 int ause = 0; /* elements added to 'nums' (can go to array part) */
290 Node *n = &t->node[i];
291 if (!ttisnil(gval(n))) {
292 ause += countint(gkey(n), nums);
301 static void setarrayvector (lua_State *L, Table *t, unsigned int size) {
303 luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
304 for (i=t->sizearray; i<size; i++)
305 setnilvalue(&t->array[i]);
310 static void setnodevector (lua_State *L, Table *t, unsigned int size) {
311 if (size == 0) { /* no elements to hash part? */
312 t->node = cast(Node *, dummynode); /* use common 'dummynode' */
314 t->lastfree = NULL; /* signal that it is using dummy node */
318 int lsize = luaO_ceillog2(size);
319 if (lsize > MAXHBITS)
320 luaG_runerror(L, "table overflow");
322 t->node = luaM_newvector(L, size, Node);
323 for (i = 0; i < (int)size; i++) {
324 Node *n = gnode(t, i);
326 setnilvalue(wgkey(n));
327 setnilvalue(gval(n));
329 t->lsizenode = cast_byte(lsize);
330 t->lastfree = gnode(t, size); /* all positions are free */
341 static void auxsetnode (lua_State *L, void *ud) {
342 AuxsetnodeT *asn = cast(AuxsetnodeT *, ud);
343 setnodevector(L, asn->t, asn->nhsize);
347 void luaH_resize (lua_State *L, Table *t, unsigned int nasize,
348 unsigned int nhsize) {
352 unsigned int oldasize = t->sizearray;
353 int oldhsize = allocsizenode(t);
354 Node *nold = t->node; /* save old hash ... */
355 if (nasize > oldasize) /* array part must grow? */
356 setarrayvector(L, t, nasize);
357 /* create new hash part with appropriate size */
358 asn.t = t; asn.nhsize = nhsize;
359 if (luaD_rawrunprotected(L, auxsetnode, &asn) != LUA_OK) { /* mem. error? */
360 setarrayvector(L, t, oldasize); /* array back to its original size */
361 luaD_throw(L, LUA_ERRMEM); /* rethrow memory error */
363 if (nasize < oldasize) { /* array part must shrink? */
364 t->sizearray = nasize;
365 /* re-insert elements from vanishing slice */
366 for (i=nasize; i<oldasize; i++) {
367 if (!ttisnil(&t->array[i]))
368 luaH_setint(L, t, i + 1, &t->array[i]);
371 luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
373 /* re-insert elements from hash part */
374 for (j = oldhsize - 1; j >= 0; j--) {
375 Node *old = nold + j;
376 if (!ttisnil(gval(old))) {
377 /* doesn't need barrier/invalidate cache, as entry was
378 already present in the table */
379 setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));
382 if (oldhsize > 0) /* not the dummy node? */
383 luaM_freearray(L, nold, cast(size_t, oldhsize)); /* free old hash */
387 void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) {
388 int nsize = allocsizenode(t);
389 luaH_resize(L, t, nasize, nsize);
393 ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
395 static void rehash (lua_State *L, Table *t, const TValue *ek) {
396 unsigned int asize; /* optimal size for array part */
397 unsigned int na; /* number of keys in the array part */
398 unsigned int nums[MAXABITS + 1];
401 for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */
402 na = numusearray(t, nums); /* count keys in array part */
403 totaluse = na; /* all those keys are integer keys */
404 totaluse += numusehash(t, nums, &na); /* count keys in hash part */
405 /* count extra key */
406 na += countint(ek, nums);
408 /* compute new size for array part */
409 asize = computesizes(nums, &na);
410 /* resize the table to new computed sizes */
411 luaH_resize(L, t, asize, totaluse - na);
417 ** }=============================================================
421 Table *luaH_new (lua_State *L) {
422 GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
425 t->flags = cast_byte(~0);
428 setnodevector(L, t, 0);
433 void luaH_free (lua_State *L, Table *t) {
435 luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
436 luaM_freearray(L, t->array, t->sizearray);
441 static Node *getfreepos (Table *t) {
443 while (t->lastfree > t->node) {
445 if (ttisnil(gkey(t->lastfree)))
449 return NULL; /* could not find a free place */
455 ** inserts a new key into a hash table; first, check whether key's main
456 ** position is free. If not, check whether colliding node is in its main
457 ** position or not: if it is not, move colliding node to an empty place and
458 ** put new key in its main position; otherwise (colliding node is in its main
459 ** position), new key goes to an empty position.
461 TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
464 if (ttisnil(key)) luaG_runerror(L, "table index is nil");
465 else if (ttisfloat(key)) {
467 if (luaV_tointeger(key, &k, 0)) { /* does index fit in an integer? */
469 key = &aux; /* insert it as an integer */
471 else if (luai_numisnan(fltvalue(key)))
472 luaG_runerror(L, "table index is NaN");
474 mp = mainposition(t, key);
475 if (!ttisnil(gval(mp)) || isdummy(t)) { /* main position is taken? */
477 Node *f = getfreepos(t); /* get a free place */
478 if (f == NULL) { /* cannot find a free place? */
479 rehash(L, t, key); /* grow table */
480 /* whatever called 'newkey' takes care of TM cache */
481 return luaH_set(L, t, key); /* insert key into grown table */
483 lua_assert(!isdummy(t));
484 othern = mainposition(t, gkey(mp));
485 if (othern != mp) { /* is colliding node out of its main position? */
486 /* yes; move colliding node into free position */
487 while (othern + gnext(othern) != mp) /* find previous */
488 othern += gnext(othern);
489 gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */
490 *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */
491 if (gnext(mp) != 0) {
492 gnext(f) += cast_int(mp - f); /* correct 'next' */
493 gnext(mp) = 0; /* now 'mp' is free */
495 setnilvalue(gval(mp));
497 else { /* colliding node is in its own main position */
498 /* new node will go into free position */
500 gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */
501 else lua_assert(gnext(f) == 0);
502 gnext(mp) = cast_int(f - mp);
506 setnodekey(L, &mp->i_key, key);
507 luaC_barrierback(L, t, key);
508 lua_assert(ttisnil(gval(mp)));
514 ** search function for integers
516 const TValue *luaH_getint (Table *t, lua_Integer key) {
517 /* (1 <= key && key <= t->sizearray) */
518 if (l_castS2U(key) - 1 < t->sizearray)
519 return &t->array[key - 1];
521 Node *n = hashint(t, key);
522 for (;;) { /* check whether 'key' is somewhere in the chain */
523 if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
524 return gval(n); /* that's it */
531 return luaO_nilobject;
537 ** search function for short strings
539 const TValue *luaH_getshortstr (Table *t, TString *key) {
540 Node *n = hashstr(t, key);
541 lua_assert(key->tt == LUA_TSHRSTR);
542 for (;;) { /* check whether 'key' is somewhere in the chain */
543 const TValue *k = gkey(n);
544 if (ttisshrstring(k) && eqshrstr(tsvalue(k), key))
545 return gval(n); /* that's it */
549 return luaO_nilobject; /* not found */
557 ** "Generic" get version. (Not that generic: not valid for integers,
558 ** which may be in array part, nor for floats with integral values.)
560 static const TValue *getgeneric (Table *t, const TValue *key) {
561 Node *n = mainposition(t, key);
562 for (;;) { /* check whether 'key' is somewhere in the chain */
563 if (luaV_rawequalobj(gkey(n), key))
564 return gval(n); /* that's it */
568 return luaO_nilobject; /* not found */
575 const TValue *luaH_getstr (Table *t, TString *key) {
576 if (key->tt == LUA_TSHRSTR)
577 return luaH_getshortstr(t, key);
578 else { /* for long strings, use generic case */
580 setsvalue(cast(lua_State *, NULL), &ko, key);
581 return getgeneric(t, &ko);
587 ** main search function
589 const TValue *luaH_get (Table *t, const TValue *key) {
590 switch (ttype(key)) {
591 case LUA_TSHRSTR: return luaH_getshortstr(t, tsvalue(key));
592 case LUA_TNUMINT: return luaH_getint(t, ivalue(key));
593 case LUA_TNIL: return luaO_nilobject;
596 if (luaV_tointeger(key, &k, 0)) /* index is int? */
597 return luaH_getint(t, k); /* use specialized version */
601 return getgeneric(t, key);
607 ** beware: when using this function you probably need to check a GC
608 ** barrier and invalidate the TM cache.
610 TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
611 const TValue *p = luaH_get(t, key);
612 if (p != luaO_nilobject)
613 return cast(TValue *, p);
614 else return luaH_newkey(L, t, key);
618 void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
619 const TValue *p = luaH_getint(t, key);
621 if (p != luaO_nilobject)
622 cell = cast(TValue *, p);
626 cell = luaH_newkey(L, t, &k);
628 setobj2t(L, cell, value);
632 static lua_Unsigned unbound_search (Table *t, lua_Unsigned j) {
633 lua_Unsigned i = j; /* i is zero or a present index */
635 /* find 'i' and 'j' such that i is present and j is not */
636 while (!ttisnil(luaH_getint(t, j))) {
638 if (j > l_castS2U(LUA_MAXINTEGER) / 2) { /* overflow? */
639 /* table was built with bad purposes: resort to linear search */
641 while (!ttisnil(luaH_getint(t, i))) i++;
646 /* now do a binary search between them */
648 lua_Unsigned m = (i+j)/2;
649 if (ttisnil(luaH_getint(t, m))) j = m;
657 ** Try to find a boundary in table 't'. A 'boundary' is an integer index
658 ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
660 lua_Unsigned luaH_getn (Table *t) {
661 unsigned int j = t->sizearray;
662 if (j > 0 && ttisnil(&t->array[j - 1])) {
663 /* there is a boundary in the array part: (binary) search for it */
666 unsigned int m = (i+j)/2;
667 if (ttisnil(&t->array[m - 1])) j = m;
672 /* else must find a boundary in hash part */
673 else if (isdummy(t)) /* hash part is empty? */
674 return j; /* that is easy... */
675 else return unbound_search(t, j);
680 #if defined(LUA_DEBUG)
682 Node *luaH_mainposition (const Table *t, const TValue *key) {
683 return mainposition(t, key);
686 int luaH_isdummy (const Table *t) { return isdummy(t); }