1 /* $NetBSD: ltable.c,v 1.5 2015/10/08 13:40:16 mbalmer Exp $ */
4 ** Id: ltable.c,v 2.111 2015/06/09 14:21:13 roberto Exp
6 ** See Copyright Notice in lua.h
16 ** Implementation of tables (aka arrays, objects, or hash tables).
17 ** Tables keep its elements in two parts: an array part and a hash part.
18 ** Non-negative integer keys are all candidates to be kept in the array
19 ** part. The actual size of the array is the largest 'n' such that
20 ** more than half the slots between 1 and n are in use.
21 ** Hash uses a mix of chained scatter table with Brent's variation.
22 ** A main invariant of these tables is that, if an element is not
23 ** in its main position (i.e. the 'original' position that its hash gives
24 ** to it), then the colliding element is in its own main position.
25 ** Hence even when the load factor reaches 100%, performance remains good.
48 ** Maximum size of array part (MAXASIZE) is 2^MAXABITS. MAXABITS is
49 ** the largest integer such that MAXASIZE fits in an unsigned int.
51 #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1)
52 #define MAXASIZE (1u << MAXABITS)
55 ** Maximum size of hash part is 2^MAXHBITS. MAXHBITS is the largest
56 ** integer such that 2^MAXHBITS fits in a signed int. (Note that the
57 ** maximum number of elements in a table, 2^MAXABITS + 2^MAXHBITS, still
58 ** fits comfortably in an unsigned int.)
60 #define MAXHBITS (MAXABITS - 1)
63 #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
65 #define hashstr(t,str) hashpow2(t, (str)->hash)
66 #define hashboolean(t,p) hashpow2(t, p)
67 #define hashint(t,i) hashpow2(t, i)
71 ** for some types, it is better to avoid modulus by power of 2, as
72 ** they tend to have many 2 factors.
74 #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
77 #define hashpointer(t,p) hashmod(t, point2uint(p))
80 #define dummynode (&dummynode_)
82 #define isdummy(n) ((n) == dummynode)
84 static const Node dummynode_
= {
85 {NILCONSTANT
}, /* value */
86 {{NILCONSTANT
, 0}} /* key */
92 ** Hash for floating-point numbers.
93 ** The main computation should be just
94 ** n = frepx(n, &i); return (n * INT_MAX) + i
95 ** but there are some numerical subtleties.
96 ** In a two-complement representation, INT_MAX does not has an exact
97 ** representation as a float, but INT_MIN does; because the absolute
98 ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the
99 ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
100 ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when
101 ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
104 #if !defined(l_hashfloat)
105 static int l_hashfloat (lua_Number n
) {
108 n
= l_mathop(frexp
)(n
, &i
) * -cast_num(INT_MIN
);
109 if (!lua_numbertointeger(n
, &ni
)) { /* is 'n' inf/-inf/NaN? */
110 lua_assert(luai_numisnan(n
) || l_mathop(fabs
)(n
) == HUGE_VAL
);
113 else { /* normal case */
114 unsigned int u
= cast(unsigned int, i
) + cast(unsigned int, ni
);
115 return cast_int(u
<= cast(unsigned int, INT_MAX
) ? u
: ~u
);
122 ** returns the 'main' position of an element in a table (that is, the index
123 ** of its hash value)
125 static Node
*mainposition (const Table
*t
, const TValue
*key
) {
126 switch (ttype(key
)) {
128 return hashint(t
, ivalue(key
));
131 return hashmod(t
, l_hashfloat(fltvalue(key
)));
134 return hashstr(t
, tsvalue(key
));
136 TString
*s
= tsvalue(key
);
137 if (s
->extra
== 0) { /* no hash? */
138 s
->hash
= luaS_hash(getstr(s
), s
->u
.lnglen
, s
->hash
);
139 s
->extra
= 1; /* now it has its hash */
141 return hashstr(t
, tsvalue(key
));
144 return hashboolean(t
, bvalue(key
));
145 case LUA_TLIGHTUSERDATA
:
146 return hashpointer(t
, pvalue(key
));
148 return hashpointer(t
, fvalue(key
));
150 return hashpointer(t
, gcvalue(key
));
156 ** returns the index for 'key' if 'key' is an appropriate key to live in
157 ** the array part of the table, 0 otherwise.
159 static unsigned int arrayindex (const TValue
*key
) {
160 if (ttisinteger(key
)) {
161 lua_Integer k
= ivalue(key
);
162 if (0 < k
&& (lua_Unsigned
)k
<= MAXASIZE
)
163 return cast(unsigned int, k
); /* 'key' is an appropriate array index */
165 return 0; /* 'key' did not match some condition */
170 ** returns the index of a 'key' for table traversals. First goes all
171 ** elements in the array part, then elements in the hash part. The
172 ** beginning of a traversal is signaled by 0.
174 static unsigned int findindex (lua_State
*L
, Table
*t
, StkId key
) {
176 if (ttisnil(key
)) return 0; /* first iteration */
178 if (i
!= 0 && i
<= t
->sizearray
) /* is 'key' inside array part? */
179 return i
; /* yes; that's the index */
182 Node
*n
= mainposition(t
, key
);
183 for (;;) { /* check whether 'key' is somewhere in the chain */
184 /* key may be dead already, but it is ok to use it in 'next' */
185 if (luaV_rawequalobj(gkey(n
), key
) ||
186 (ttisdeadkey(gkey(n
)) && iscollectable(key
) &&
187 deadvalue(gkey(n
)) == gcvalue(key
))) {
188 i
= cast_int(n
- gnode(t
, 0)); /* key index in hash table */
189 /* hash elements are numbered after array ones */
190 return (i
+ 1) + t
->sizearray
;
194 luaG_runerror(L
, "invalid key to 'next'"); /* key not found */
201 int luaH_next (lua_State
*L
, Table
*t
, StkId key
) {
202 unsigned int i
= findindex(L
, t
, key
); /* find original element */
203 for (; i
< t
->sizearray
; i
++) { /* try first array part */
204 if (!ttisnil(&t
->array
[i
])) { /* a non-nil value? */
205 setivalue(key
, i
+ 1);
206 setobj2s(L
, key
+1, &t
->array
[i
]);
210 for (i
-= t
->sizearray
; cast_int(i
) < sizenode(t
); i
++) { /* hash part */
211 if (!ttisnil(gval(gnode(t
, i
)))) { /* a non-nil value? */
212 setobj2s(L
, key
, gkey(gnode(t
, i
)));
213 setobj2s(L
, key
+1, gval(gnode(t
, i
)));
217 return 0; /* no more elements */
222 ** {=============================================================
224 ** ==============================================================
228 ** Compute the optimal size for the array part of table 't'. 'nums' is a
229 ** "count array" where 'nums[i]' is the number of integers in the table
230 ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
231 ** integer keys in the table and leaves with the number of keys that
232 ** will go to the array part; return the optimal size.
234 static unsigned int computesizes (unsigned int nums
[], unsigned int *pna
) {
236 unsigned int twotoi
; /* 2^i (candidate for optimal size) */
237 unsigned int a
= 0; /* number of elements smaller than 2^i */
238 unsigned int na
= 0; /* number of elements to go to array part */
239 unsigned int optimal
= 0; /* optimal size for array part */
240 /* loop while keys can fill more than half of total size */
241 for (i
= 0, twotoi
= 1; *pna
> twotoi
/ 2; i
++, twotoi
*= 2) {
244 if (a
> twotoi
/2) { /* more than half elements present? */
245 optimal
= twotoi
; /* optimal size (till now) */
246 na
= a
; /* all elements up to 'optimal' will go to array part */
250 lua_assert((optimal
== 0 || optimal
/ 2 < na
) && na
<= optimal
);
256 static int countint (const TValue
*key
, unsigned int *nums
) {
257 unsigned int k
= arrayindex(key
);
258 if (k
!= 0) { /* is 'key' an appropriate array index? */
259 nums
[luaO_ceillog2(k
)]++; /* count as such */
268 ** Count keys in array part of table 't': Fill 'nums[i]' with
269 ** number of keys that will go into corresponding slice and return
270 ** total number of non-nil keys.
272 static unsigned int numusearray (const Table
*t
, unsigned int *nums
) {
274 unsigned int ttlg
; /* 2^lg */
275 unsigned int ause
= 0; /* summation of 'nums' */
276 unsigned int i
= 1; /* count to traverse all array keys */
277 /* traverse each slice */
278 for (lg
= 0, ttlg
= 1; lg
<= MAXABITS
; lg
++, ttlg
*= 2) {
279 unsigned int lc
= 0; /* counter */
280 unsigned int lim
= ttlg
;
281 if (lim
> t
->sizearray
) {
282 lim
= t
->sizearray
; /* adjust upper limit */
284 break; /* no more elements to count */
286 /* count elements in range (2^(lg - 1), 2^lg] */
287 for (; i
<= lim
; i
++) {
288 if (!ttisnil(&t
->array
[i
-1]))
298 static int numusehash (const Table
*t
, unsigned int *nums
, unsigned int *pna
) {
299 int totaluse
= 0; /* total number of elements */
300 int ause
= 0; /* elements added to 'nums' (can go to array part) */
303 Node
*n
= &t
->node
[i
];
304 if (!ttisnil(gval(n
))) {
305 ause
+= countint(gkey(n
), nums
);
314 static void setarrayvector (lua_State
*L
, Table
*t
, unsigned int size
) {
316 luaM_reallocvector(L
, t
->array
, t
->sizearray
, size
, TValue
);
317 for (i
=t
->sizearray
; i
<size
; i
++)
318 setnilvalue(&t
->array
[i
]);
323 static void setnodevector (lua_State
*L
, Table
*t
, unsigned int size
) {
325 if (size
== 0) { /* no elements to hash part? */
326 t
->node
= cast(Node
*, dummynode
); /* use common 'dummynode' */
331 lsize
= luaO_ceillog2(size
);
332 if (lsize
> MAXHBITS
)
333 luaG_runerror(L
, "table overflow");
335 t
->node
= luaM_newvector(L
, size
, Node
);
336 for (i
= 0; i
< (int)size
; i
++) {
337 Node
*n
= gnode(t
, i
);
339 setnilvalue(wgkey(n
));
340 setnilvalue(gval(n
));
343 t
->lsizenode
= cast_byte(lsize
);
344 t
->lastfree
= gnode(t
, size
); /* all positions are free */
348 void luaH_resize (lua_State
*L
, Table
*t
, unsigned int nasize
,
349 unsigned int nhsize
) {
352 unsigned int oldasize
= t
->sizearray
;
353 int oldhsize
= t
->lsizenode
;
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 setnodevector(L
, t
, nhsize
);
359 if (nasize
< oldasize
) { /* array part must shrink? */
360 t
->sizearray
= nasize
;
361 /* re-insert elements from vanishing slice */
362 for (i
=nasize
; i
<oldasize
; i
++) {
363 if (!ttisnil(&t
->array
[i
]))
364 luaH_setint(L
, t
, i
+ 1, &t
->array
[i
]);
367 luaM_reallocvector(L
, t
->array
, oldasize
, nasize
, TValue
);
369 /* re-insert elements from hash part */
370 for (j
= twoto(oldhsize
) - 1; j
>= 0; j
--) {
371 Node
*old
= nold
+ j
;
372 if (!ttisnil(gval(old
))) {
373 /* doesn't need barrier/invalidate cache, as entry was
374 already present in the table */
375 setobjt2t(L
, luaH_set(L
, t
, gkey(old
)), gval(old
));
379 luaM_freearray(L
, nold
, cast(size_t, twoto(oldhsize
))); /* free old hash */
383 void luaH_resizearray (lua_State
*L
, Table
*t
, unsigned int nasize
) {
384 int nsize
= isdummy(t
->node
) ? 0 : sizenode(t
);
385 luaH_resize(L
, t
, nasize
, nsize
);
389 ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
391 static void rehash (lua_State
*L
, Table
*t
, const TValue
*ek
) {
392 unsigned int asize
; /* optimal size for array part */
393 unsigned int na
; /* number of keys in the array part */
394 unsigned int nums
[MAXABITS
+ 1];
397 for (i
= 0; i
<= MAXABITS
; i
++) nums
[i
] = 0; /* reset counts */
398 na
= numusearray(t
, nums
); /* count keys in array part */
399 totaluse
= na
; /* all those keys are integer keys */
400 totaluse
+= numusehash(t
, nums
, &na
); /* count keys in hash part */
401 /* count extra key */
402 na
+= countint(ek
, nums
);
404 /* compute new size for array part */
405 asize
= computesizes(nums
, &na
);
406 /* resize the table to new computed sizes */
407 luaH_resize(L
, t
, asize
, totaluse
- na
);
413 ** }=============================================================
417 Table
*luaH_new (lua_State
*L
) {
418 GCObject
*o
= luaC_newobj(L
, LUA_TTABLE
, sizeof(Table
));
421 t
->flags
= cast_byte(~0);
424 setnodevector(L
, t
, 0);
429 void luaH_free (lua_State
*L
, Table
*t
) {
430 if (!isdummy(t
->node
))
431 luaM_freearray(L
, t
->node
, cast(size_t, sizenode(t
)));
432 luaM_freearray(L
, t
->array
, t
->sizearray
);
437 static Node
*getfreepos (Table
*t
) {
438 while (t
->lastfree
> t
->node
) {
440 if (ttisnil(gkey(t
->lastfree
)))
443 return NULL
; /* could not find a free place */
449 ** inserts a new key into a hash table; first, check whether key's main
450 ** position is free. If not, check whether colliding node is in its main
451 ** position or not: if it is not, move colliding node to an empty place and
452 ** put new key in its main position; otherwise (colliding node is in its main
453 ** position), new key goes to an empty position.
455 TValue
*luaH_newkey (lua_State
*L
, Table
*t
, const TValue
*key
) {
460 if (ttisnil(key
)) luaG_runerror(L
, "table index is nil");
462 else if (ttisfloat(key
)) {
464 if (luaV_tointeger(key
, &k
, 0)) { /* index is int? */
466 key
= &aux
; /* insert it as an integer */
468 else if (luai_numisnan(fltvalue(key
)))
469 luaG_runerror(L
, "table index is NaN");
472 mp
= mainposition(t
, key
);
473 if (!ttisnil(gval(mp
)) || isdummy(mp
)) { /* main position is taken? */
475 Node
*f
= getfreepos(t
); /* get a free place */
476 if (f
== NULL
) { /* cannot find a free place? */
477 rehash(L
, t
, key
); /* grow table */
478 /* whatever called 'newkey' takes care of TM cache and GC barrier */
479 return luaH_set(L
, t
, key
); /* insert key into grown table */
481 lua_assert(!isdummy(f
));
482 othern
= mainposition(t
, gkey(mp
));
483 if (othern
!= mp
) { /* is colliding node out of its main position? */
484 /* yes; move colliding node into free position */
485 while (othern
+ gnext(othern
) != mp
) /* find previous */
486 othern
+= gnext(othern
);
487 gnext(othern
) = cast_int(f
- othern
); /* rechain to point to 'f' */
488 *f
= *mp
; /* copy colliding node into free pos. (mp->next also goes) */
489 if (gnext(mp
) != 0) {
490 gnext(f
) += cast_int(mp
- f
); /* correct 'next' */
491 gnext(mp
) = 0; /* now 'mp' is free */
493 setnilvalue(gval(mp
));
495 else { /* colliding node is in its own main position */
496 /* new node will go into free position */
498 gnext(f
) = cast_int((mp
+ gnext(mp
)) - f
); /* chain new position */
499 else lua_assert(gnext(f
) == 0);
500 gnext(mp
) = cast_int(f
- mp
);
504 setnodekey(L
, &mp
->i_key
, key
);
505 luaC_barrierback(L
, t
, key
);
506 lua_assert(ttisnil(gval(mp
)));
512 ** search function for integers
514 const TValue
*luaH_getint (Table
*t
, lua_Integer key
) {
515 /* (1 <= key && key <= t->sizearray) */
516 if (l_castS2U(key
- 1) < t
->sizearray
)
517 return &t
->array
[key
- 1];
519 Node
*n
= hashint(t
, key
);
520 for (;;) { /* check whether 'key' is somewhere in the chain */
521 if (ttisinteger(gkey(n
)) && ivalue(gkey(n
)) == key
)
522 return gval(n
); /* that's it */
529 return luaO_nilobject
;
535 ** search function for short strings
537 const TValue
*luaH_getstr (Table
*t
, TString
*key
) {
538 Node
*n
= hashstr(t
, key
);
539 lua_assert(key
->tt
== LUA_TSHRSTR
);
540 for (;;) { /* check whether 'key' is somewhere in the chain */
541 const TValue
*k
= gkey(n
);
542 if (ttisshrstring(k
) && eqshrstr(tsvalue(k
), key
))
543 return gval(n
); /* that's it */
550 return luaO_nilobject
;
555 ** main search function
557 const TValue
*luaH_get (Table
*t
, const TValue
*key
) {
558 switch (ttype(key
)) {
559 case LUA_TSHRSTR
: return luaH_getstr(t
, tsvalue(key
));
560 case LUA_TNUMINT
: return luaH_getint(t
, ivalue(key
));
561 case LUA_TNIL
: return luaO_nilobject
;
565 if (luaV_tointeger(key
, &k
, 0)) /* index is int? */
566 return luaH_getint(t
, k
); /* use specialized version */
571 Node
*n
= mainposition(t
, key
);
572 for (;;) { /* check whether 'key' is somewhere in the chain */
573 if (luaV_rawequalobj(gkey(n
), key
))
574 return gval(n
); /* that's it */
581 return luaO_nilobject
;
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
); }