2 ** $Id: ltable.c,v 2.117 2015/11/19 19:16:22 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 #define isdummy(n) ((n) == dummynode)
79 static const Node dummynode_ = {
80 {NILCONSTANT}, /* value */
81 {{NILCONSTANT, 0}} /* key */
86 ** Hash for floating-point numbers.
87 ** The main computation should be just
88 ** n = frexp(n, &i); return (n * INT_MAX) + i
89 ** but there are some numerical subtleties.
90 ** In a two-complement representation, INT_MAX does not has an exact
91 ** representation as a float, but INT_MIN does; because the absolute
92 ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the
93 ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
94 ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when
95 ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
98 #if !defined(l_hashfloat)
99 static int l_hashfloat (lua_Number n) {
102 n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN);
103 if (!lua_numbertointeger(n, &ni)) { /* is 'n' inf/-inf/NaN? */
104 lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL));
107 else { /* normal case */
108 unsigned int u = cast(unsigned int, i) + cast(unsigned int, ni);
109 return cast_int(u <= cast(unsigned int, INT_MAX) ? u : ~u);
116 ** returns the 'main' position of an element in a table (that is, the index
117 ** of its hash value)
119 static Node *mainposition (const Table *t, const TValue *key) {
120 switch (ttype(key)) {
122 return hashint(t, ivalue(key));
124 return hashmod(t, l_hashfloat(fltvalue(key)));
126 return hashstr(t, tsvalue(key));
128 return hashpow2(t, luaS_hashlongstr(tsvalue(key)));
130 return hashboolean(t, bvalue(key));
131 case LUA_TLIGHTUSERDATA:
132 return hashpointer(t, pvalue(key));
134 return hashpointer(t, fvalue(key));
136 lua_assert(!ttisdeadkey(key));
137 return hashpointer(t, gcvalue(key));
143 ** returns the index for 'key' if 'key' is an appropriate key to live in
144 ** the array part of the table, 0 otherwise.
146 static unsigned int arrayindex (const TValue *key) {
147 if (ttisinteger(key)) {
148 lua_Integer k = ivalue(key);
149 if (0 < k && (lua_Unsigned)k <= MAXASIZE)
150 return cast(unsigned int, k); /* 'key' is an appropriate array index */
152 return 0; /* 'key' did not match some condition */
157 ** returns the index of a 'key' for table traversals. First goes all
158 ** elements in the array part, then elements in the hash part. The
159 ** beginning of a traversal is signaled by 0.
161 static unsigned int findindex (lua_State *L, Table *t, StkId key) {
163 if (ttisnil(key)) return 0; /* first iteration */
165 if (i != 0 && i <= t->sizearray) /* is 'key' inside array part? */
166 return i; /* yes; that's the index */
169 Node *n = mainposition(t, key);
170 for (;;) { /* check whether 'key' is somewhere in the chain */
171 /* key may be dead already, but it is ok to use it in 'next' */
172 if (luaV_rawequalobj(gkey(n), key) ||
173 (ttisdeadkey(gkey(n)) && iscollectable(key) &&
174 deadvalue(gkey(n)) == gcvalue(key))) {
175 i = cast_int(n - gnode(t, 0)); /* key index in hash table */
176 /* hash elements are numbered after array ones */
177 return (i + 1) + t->sizearray;
181 luaG_runerror(L, "invalid key to 'next'"); /* key not found */
188 int luaH_next (lua_State *L, Table *t, StkId key) {
189 unsigned int i = findindex(L, t, key); /* find original element */
190 for (; i < t->sizearray; i++) { /* try first array part */
191 if (!ttisnil(&t->array[i])) { /* a non-nil value? */
192 setivalue(key, i + 1);
193 setobj2s(L, key+1, &t->array[i]);
197 for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) { /* hash part */
198 if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
199 setobj2s(L, key, gkey(gnode(t, i)));
200 setobj2s(L, key+1, gval(gnode(t, i)));
204 return 0; /* no more elements */
209 ** {=============================================================
211 ** ==============================================================
215 ** Compute the optimal size for the array part of table 't'. 'nums' is a
216 ** "count array" where 'nums[i]' is the number of integers in the table
217 ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
218 ** integer keys in the table and leaves with the number of keys that
219 ** will go to the array part; return the optimal size.
221 static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {
223 unsigned int twotoi; /* 2^i (candidate for optimal size) */
224 unsigned int a = 0; /* number of elements smaller than 2^i */
225 unsigned int na = 0; /* number of elements to go to array part */
226 unsigned int optimal = 0; /* optimal size for array part */
227 /* loop while keys can fill more than half of total size */
228 for (i = 0, twotoi = 1; *pna > twotoi / 2; i++, 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) {
312 if (size == 0) { /* no elements to hash part? */
313 t->node = cast(Node *, dummynode); /* use common 'dummynode' */
318 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));
330 t->lsizenode = cast_byte(lsize);
331 t->lastfree = gnode(t, size); /* all positions are free */
335 void luaH_resize (lua_State *L, Table *t, unsigned int nasize,
336 unsigned int nhsize) {
339 unsigned int oldasize = t->sizearray;
340 int oldhsize = t->lsizenode;
341 Node *nold = t->node; /* save old hash ... */
342 if (nasize > oldasize) /* array part must grow? */
343 setarrayvector(L, t, nasize);
344 /* create new hash part with appropriate size */
345 setnodevector(L, t, nhsize);
346 if (nasize < oldasize) { /* array part must shrink? */
347 t->sizearray = nasize;
348 /* re-insert elements from vanishing slice */
349 for (i=nasize; i<oldasize; i++) {
350 if (!ttisnil(&t->array[i]))
351 luaH_setint(L, t, i + 1, &t->array[i]);
354 luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
356 /* re-insert elements from hash part */
357 for (j = twoto(oldhsize) - 1; j >= 0; j--) {
358 Node *old = nold + j;
359 if (!ttisnil(gval(old))) {
360 /* doesn't need barrier/invalidate cache, as entry was
361 already present in the table */
362 setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));
366 luaM_freearray(L, nold, cast(size_t, twoto(oldhsize))); /* free old hash */
370 void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) {
371 int nsize = isdummy(t->node) ? 0 : sizenode(t);
372 luaH_resize(L, t, nasize, nsize);
376 ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
378 static void rehash (lua_State *L, Table *t, const TValue *ek) {
379 unsigned int asize; /* optimal size for array part */
380 unsigned int na; /* number of keys in the array part */
381 unsigned int nums[MAXABITS + 1];
384 for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */
385 na = numusearray(t, nums); /* count keys in array part */
386 totaluse = na; /* all those keys are integer keys */
387 totaluse += numusehash(t, nums, &na); /* count keys in hash part */
388 /* count extra key */
389 na += countint(ek, nums);
391 /* compute new size for array part */
392 asize = computesizes(nums, &na);
393 /* resize the table to new computed sizes */
394 luaH_resize(L, t, asize, totaluse - na);
400 ** }=============================================================
404 Table *luaH_new (lua_State *L) {
405 GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
408 t->flags = cast_byte(~0);
411 setnodevector(L, t, 0);
416 void luaH_free (lua_State *L, Table *t) {
417 if (!isdummy(t->node))
418 luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
419 luaM_freearray(L, t->array, t->sizearray);
424 static Node *getfreepos (Table *t) {
425 while (t->lastfree > t->node) {
427 if (ttisnil(gkey(t->lastfree)))
430 return NULL; /* could not find a free place */
436 ** inserts a new key into a hash table; first, check whether key's main
437 ** position is free. If not, check whether colliding node is in its main
438 ** position or not: if it is not, move colliding node to an empty place and
439 ** put new key in its main position; otherwise (colliding node is in its main
440 ** position), new key goes to an empty position.
442 TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
445 if (ttisnil(key)) luaG_runerror(L, "table index is nil");
446 else if (ttisfloat(key)) {
448 if (luaV_tointeger(key, &k, 0)) { /* index is int? */
450 key = &aux; /* insert it as an integer */
452 else if (luai_numisnan(fltvalue(key)))
453 luaG_runerror(L, "table index is NaN");
455 mp = mainposition(t, key);
456 if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */
458 Node *f = getfreepos(t); /* get a free place */
459 if (f == NULL) { /* cannot find a free place? */
460 rehash(L, t, key); /* grow table */
461 /* whatever called 'newkey' takes care of TM cache */
462 return luaH_set(L, t, key); /* insert key into grown table */
464 lua_assert(!isdummy(f));
465 othern = mainposition(t, gkey(mp));
466 if (othern != mp) { /* is colliding node out of its main position? */
467 /* yes; move colliding node into free position */
468 while (othern + gnext(othern) != mp) /* find previous */
469 othern += gnext(othern);
470 gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */
471 *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */
472 if (gnext(mp) != 0) {
473 gnext(f) += cast_int(mp - f); /* correct 'next' */
474 gnext(mp) = 0; /* now 'mp' is free */
476 setnilvalue(gval(mp));
478 else { /* colliding node is in its own main position */
479 /* new node will go into free position */
481 gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */
482 else lua_assert(gnext(f) == 0);
483 gnext(mp) = cast_int(f - mp);
487 setnodekey(L, &mp->i_key, key);
488 luaC_barrierback(L, t, key);
489 lua_assert(ttisnil(gval(mp)));
495 ** search function for integers
497 const TValue *luaH_getint (Table *t, lua_Integer key) {
498 /* (1 <= key && key <= t->sizearray) */
499 if (l_castS2U(key) - 1 < t->sizearray)
500 return &t->array[key - 1];
502 Node *n = hashint(t, key);
503 for (;;) { /* check whether 'key' is somewhere in the chain */
504 if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
505 return gval(n); /* that's it */
512 return luaO_nilobject;
518 ** search function for short strings
520 const TValue *luaH_getshortstr (Table *t, TString *key) {
521 Node *n = hashstr(t, key);
522 lua_assert(key->tt == LUA_TSHRSTR);
523 for (;;) { /* check whether 'key' is somewhere in the chain */
524 const TValue *k = gkey(n);
525 if (ttisshrstring(k) && eqshrstr(tsvalue(k), key))
526 return gval(n); /* that's it */
530 return luaO_nilobject; /* not found */
538 ** "Generic" get version. (Not that generic: not valid for integers,
539 ** which may be in array part, nor for floats with integral values.)
541 static const TValue *getgeneric (Table *t, const TValue *key) {
542 Node *n = mainposition(t, key);
543 for (;;) { /* check whether 'key' is somewhere in the chain */
544 if (luaV_rawequalobj(gkey(n), key))
545 return gval(n); /* that's it */
549 return luaO_nilobject; /* not found */
556 const TValue *luaH_getstr (Table *t, TString *key) {
557 if (key->tt == LUA_TSHRSTR)
558 return luaH_getshortstr(t, key);
559 else { /* for long strings, use generic case */
561 setsvalue(cast(lua_State *, NULL), &ko, key);
562 return getgeneric(t, &ko);
568 ** main search function
570 const TValue *luaH_get (Table *t, const TValue *key) {
571 switch (ttype(key)) {
572 case LUA_TSHRSTR: return luaH_getshortstr(t, tsvalue(key));
573 case LUA_TNUMINT: return luaH_getint(t, ivalue(key));
574 case LUA_TNIL: return luaO_nilobject;
577 if (luaV_tointeger(key, &k, 0)) /* index is int? */
578 return luaH_getint(t, k); /* use specialized version */
582 return getgeneric(t, key);
588 ** beware: when using this function you probably need to check a GC
589 ** barrier and invalidate the TM cache.
591 TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
592 const TValue *p = luaH_get(t, key);
593 if (p != luaO_nilobject)
594 return cast(TValue *, p);
595 else return luaH_newkey(L, t, key);
599 void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
600 const TValue *p = luaH_getint(t, key);
602 if (p != luaO_nilobject)
603 cell = cast(TValue *, p);
607 cell = luaH_newkey(L, t, &k);
609 setobj2t(L, cell, value);
613 static int unbound_search (Table *t, unsigned int j) {
614 unsigned int i = j; /* i is zero or a present index */
616 /* find 'i' and 'j' such that i is present and j is not */
617 while (!ttisnil(luaH_getint(t, j))) {
619 if (j > cast(unsigned int, MAX_INT)/2) { /* overflow? */
620 /* table was built with bad purposes: resort to linear search */
622 while (!ttisnil(luaH_getint(t, i))) i++;
627 /* now do a binary search between them */
629 unsigned int m = (i+j)/2;
630 if (ttisnil(luaH_getint(t, m))) j = m;
638 ** Try to find a boundary in table 't'. A 'boundary' is an integer index
639 ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
641 int luaH_getn (Table *t) {
642 unsigned int j = t->sizearray;
643 if (j > 0 && ttisnil(&t->array[j - 1])) {
644 /* there is a boundary in the array part: (binary) search for it */
647 unsigned int m = (i+j)/2;
648 if (ttisnil(&t->array[m - 1])) j = m;
653 /* else must find a boundary in hash part */
654 else if (isdummy(t->node)) /* hash part is empty? */
655 return j; /* that is easy... */
656 else return unbound_search(t, j);
661 #if defined(LUA_DEBUG)
663 Node *luaH_mainposition (const Table *t, const TValue *key) {
664 return mainposition(t, key);
667 int luaH_isdummy (Node *n) { return isdummy(n); }