2 ** $Id: ltable.c,v 2.32 2006/01/18 11:49:02 roberto Exp $
4 ** See Copyright Notice in lua.h
9 ** Implementation of tables (aka arrays, objects, or hash tables).
10 ** Tables keep its elements in two parts: an array part and a hash part.
11 ** Non-negative integer keys are all candidates to be kept in the array
12 ** part. The actual size of the array is the largest `n' such that at
13 ** least half the slots between 0 and n are in use.
14 ** Hash uses a mix of chained scatter table with Brent's variation.
15 ** A main invariant of these tables is that, if an element is not
16 ** in its main position (i.e. the `original' position that its hash gives
17 ** to it), then the colliding element is in its own main position.
18 ** Hence even when the load factor reaches 100%, performance remains good.
39 ** max size of array part is 2^MAXBITS
44 #define MAXBITS (LUAI_BITSINT-2)
47 #define MAXASIZE (1 << MAXBITS)
50 #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
52 #define hashstr(t,str) hashpow2(t, (str)->tsv.hash)
53 #define hashboolean(t,p) hashpow2(t, p)
57 ** for some types, it is better to avoid modulus by power of 2, as
58 ** they tend to have many 2 factors.
60 #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
63 #define hashpointer(t,p) hashmod(t, IntPoint(p))
67 ** number of ints inside a lua_Number
69 #define numints cast_int(sizeof(lua_Number)/sizeof(int))
73 #define dummynode (&dummynode_)
75 static const Node dummynode_
= {
76 {{NULL
}, LUA_TNIL
}, /* value */
77 {{{NULL
}, LUA_TNIL
, NULL
}} /* key */
82 ** hash for lua_Numbers
84 static Node
*hashnum (const Table
*t
, lua_Number n
) {
85 unsigned int a
[numints
];
87 n
+= 1; /* normalize number (avoid -0) */
88 lua_assert(sizeof(a
) <= sizeof(n
));
89 memcpy(a
, &n
, sizeof(a
));
90 for (i
= 1; i
< numints
; i
++) a
[0] += a
[i
];
91 return hashmod(t
, a
[0]);
97 ** returns the `main' position of an element in a table (that is, the index
100 static Node
*mainposition (const Table
*t
, const TValue
*key
) {
101 switch (ttype(key
)) {
103 return hashnum(t
, nvalue(key
));
105 return hashstr(t
, rawtsvalue(key
));
107 return hashboolean(t
, bvalue(key
));
108 case LUA_TLIGHTUSERDATA
:
109 return hashpointer(t
, pvalue(key
));
111 return hashpointer(t
, gcvalue(key
));
117 ** returns the index for `key' if `key' is an appropriate key to live in
118 ** the array part of the table, -1 otherwise.
120 static int arrayindex (const TValue
*key
) {
121 if (ttisnumber(key
)) {
122 lua_Number n
= nvalue(key
);
124 lua_number2int(k
, n
);
125 if (luai_numeq(cast_num(k
), n
))
128 return -1; /* `key' did not match some condition */
133 ** returns the index of a `key' for table traversals. First goes all
134 ** elements in the array part, then elements in the hash part. The
135 ** beginning of a traversal is signalled by -1.
137 static int findindex (lua_State
*L
, Table
*t
, StkId key
) {
139 if (ttisnil(key
)) return -1; /* first iteration */
141 if (0 < i
&& i
<= t
->sizearray
) /* is `key' inside array part? */
142 return i
-1; /* yes; that's the index (corrected to C) */
144 Node
*n
= mainposition(t
, key
);
145 do { /* check whether `key' is somewhere in the chain */
146 /* key may be dead already, but it is ok to use it in `next' */
147 if (luaO_rawequalObj(key2tval(n
), key
) ||
148 (ttype(gkey(n
)) == LUA_TDEADKEY
&& iscollectable(key
) &&
149 gcvalue(gkey(n
)) == gcvalue(key
))) {
150 i
= cast_int(n
- gnode(t
, 0)); /* key index in hash table */
151 /* hash elements are numbered after array ones */
152 return i
+ t
->sizearray
;
156 luaG_runerror(L
, "invalid key to " LUA_QL("next")); /* key not found */
157 return 0; /* to avoid warnings */
162 int luaH_next (lua_State
*L
, Table
*t
, StkId key
) {
163 int i
= findindex(L
, t
, key
); /* find original element */
164 for (i
++; i
< t
->sizearray
; i
++) { /* try first array part */
165 if (!ttisnil(&t
->array
[i
])) { /* a non-nil value? */
166 setnvalue(key
, cast_num(i
+1));
167 setobj2s(L
, key
+1, &t
->array
[i
]);
171 for (i
-= t
->sizearray
; i
< sizenode(t
); i
++) { /* then hash part */
172 if (!ttisnil(gval(gnode(t
, i
)))) { /* a non-nil value? */
173 setobj2s(L
, key
, key2tval(gnode(t
, i
)));
174 setobj2s(L
, key
+1, gval(gnode(t
, i
)));
178 return 0; /* no more elements */
183 ** {=============================================================
185 ** ==============================================================
189 static int computesizes (int nums
[], int *narray
) {
191 int twotoi
; /* 2^i */
192 int a
= 0; /* number of elements smaller than 2^i */
193 int na
= 0; /* number of elements to go to array part */
194 int n
= 0; /* optimal size for array part */
195 for (i
= 0, twotoi
= 1; twotoi
/2 < *narray
; i
++, twotoi
*= 2) {
198 if (a
> twotoi
/2) { /* more than half elements present? */
199 n
= twotoi
; /* optimal size (till now) */
200 na
= a
; /* all elements smaller than n will go to array part */
203 if (a
== *narray
) break; /* all elements already counted */
206 lua_assert(*narray
/2 <= na
&& na
<= *narray
);
211 static int countint (const TValue
*key
, int *nums
) {
212 int k
= arrayindex(key
);
213 if (0 < k
&& k
<= MAXASIZE
) { /* is `key' an appropriate array index? */
214 nums
[ceillog2(k
)]++; /* count as such */
222 static int numusearray (const Table
*t
, int *nums
) {
225 int ause
= 0; /* summation of `nums' */
226 int i
= 1; /* count to traverse all array keys */
227 for (lg
=0, ttlg
=1; lg
<=MAXBITS
; lg
++, ttlg
*=2) { /* for each slice */
228 int lc
= 0; /* counter */
230 if (lim
> t
->sizearray
) {
231 lim
= t
->sizearray
; /* adjust upper limit */
233 break; /* no more elements to count */
235 /* count elements in range (2^(lg-1), 2^lg] */
236 for (; i
<= lim
; i
++) {
237 if (!ttisnil(&t
->array
[i
-1]))
247 static int numusehash (const Table
*t
, int *nums
, int *pnasize
) {
248 int totaluse
= 0; /* total number of elements */
249 int ause
= 0; /* summation of `nums' */
252 Node
*n
= &t
->node
[i
];
253 if (!ttisnil(gval(n
))) {
254 ause
+= countint(key2tval(n
), nums
);
263 static void setarrayvector (lua_State
*L
, Table
*t
, int size
) {
265 luaM_reallocvector(L
, t
->array
, t
->sizearray
, size
, TValue
);
266 for (i
=t
->sizearray
; i
<size
; i
++)
267 setnilvalue(&t
->array
[i
]);
272 static void setnodevector (lua_State
*L
, Table
*t
, int size
) {
274 if (size
== 0) { /* no elements to hash part? */
275 t
->node
= cast(Node
*, dummynode
); /* use common `dummynode' */
280 lsize
= ceillog2(size
);
282 luaG_runerror(L
, "table overflow");
284 t
->node
= luaM_newvector(L
, size
, Node
);
285 for (i
=0; i
<size
; i
++) {
286 Node
*n
= gnode(t
, i
);
288 setnilvalue(gkey(n
));
289 setnilvalue(gval(n
));
292 t
->lsizenode
= cast_byte(lsize
);
293 t
->lastfree
= gnode(t
, size
); /* all positions are free */
297 static void resize (lua_State
*L
, Table
*t
, int nasize
, int nhsize
) {
299 int oldasize
= t
->sizearray
;
300 int oldhsize
= t
->lsizenode
;
301 Node
*nold
= t
->node
; /* save old hash ... */
302 if (nasize
> oldasize
) /* array part must grow? */
303 setarrayvector(L
, t
, nasize
);
304 /* create new hash part with appropriate size */
305 setnodevector(L
, t
, nhsize
);
306 if (nasize
< oldasize
) { /* array part must shrink? */
307 t
->sizearray
= nasize
;
308 /* re-insert elements from vanishing slice */
309 for (i
=nasize
; i
<oldasize
; i
++) {
310 if (!ttisnil(&t
->array
[i
]))
311 setobjt2t(L
, luaH_setnum(L
, t
, i
+1), &t
->array
[i
]);
314 luaM_reallocvector(L
, t
->array
, oldasize
, nasize
, TValue
);
316 /* re-insert elements from hash part */
317 for (i
= twoto(oldhsize
) - 1; i
>= 0; i
--) {
319 if (!ttisnil(gval(old
)))
320 setobjt2t(L
, luaH_set(L
, t
, key2tval(old
)), gval(old
));
322 if (nold
!= dummynode
)
323 luaM_freearray(L
, nold
, twoto(oldhsize
), Node
); /* free old array */
327 void luaH_resizearray (lua_State
*L
, Table
*t
, int nasize
) {
328 int nsize
= (t
->node
== dummynode
) ? 0 : sizenode(t
);
329 resize(L
, t
, nasize
, nsize
);
333 static void rehash (lua_State
*L
, Table
*t
, const TValue
*ek
) {
335 int nums
[MAXBITS
+1]; /* nums[i] = number of keys between 2^(i-1) and 2^i */
338 for (i
=0; i
<=MAXBITS
; i
++) nums
[i
] = 0; /* reset counts */
339 nasize
= numusearray(t
, nums
); /* count keys in array part */
340 totaluse
= nasize
; /* all those keys are integer keys */
341 totaluse
+= numusehash(t
, nums
, &nasize
); /* count keys in hash part */
342 /* count extra key */
343 nasize
+= countint(ek
, nums
);
345 /* compute new size for array part */
346 na
= computesizes(nums
, &nasize
);
347 /* resize the table to new computed sizes */
348 resize(L
, t
, nasize
, totaluse
- na
);
354 ** }=============================================================
358 Table
*luaH_new (lua_State
*L
, int narray
, int nhash
) {
359 Table
*t
= luaM_new(L
, Table
);
360 luaC_link(L
, obj2gco(t
), LUA_TTABLE
);
362 t
->flags
= cast_byte(~0);
363 /* temporary values (kept only if some malloc fails) */
367 t
->node
= cast(Node
*, dummynode
);
368 setarrayvector(L
, t
, narray
);
369 setnodevector(L
, t
, nhash
);
374 void luaH_free (lua_State
*L
, Table
*t
) {
375 if (t
->node
!= dummynode
)
376 luaM_freearray(L
, t
->node
, sizenode(t
), Node
);
377 luaM_freearray(L
, t
->array
, t
->sizearray
, TValue
);
382 static Node
*getfreepos (Table
*t
) {
383 while (t
->lastfree
-- > t
->node
) {
384 if (ttisnil(gkey(t
->lastfree
)))
387 return NULL
; /* could not find a free place */
393 ** inserts a new key into a hash table; first, check whether key's main
394 ** position is free. If not, check whether colliding node is in its main
395 ** position or not: if it is not, move colliding node to an empty place and
396 ** put new key in its main position; otherwise (colliding node is in its main
397 ** position), new key goes to an empty position.
399 static TValue
*newkey (lua_State
*L
, Table
*t
, const TValue
*key
) {
400 Node
*mp
= mainposition(t
, key
);
401 if (!ttisnil(gval(mp
)) || mp
== dummynode
) {
403 Node
*n
= getfreepos(t
); /* get a free place */
404 if (n
== NULL
) { /* cannot find a free place? */
405 rehash(L
, t
, key
); /* grow table */
406 return luaH_set(L
, t
, key
); /* re-insert key into grown table */
408 lua_assert(n
!= dummynode
);
409 othern
= mainposition(t
, key2tval(mp
));
410 if (othern
!= mp
) { /* is colliding node out of its main position? */
411 /* yes; move colliding node into free position */
412 while (gnext(othern
) != mp
) othern
= gnext(othern
); /* find previous */
413 gnext(othern
) = n
; /* redo the chain with `n' in place of `mp' */
414 *n
= *mp
; /* copy colliding node into free pos. (mp->next also goes) */
415 gnext(mp
) = NULL
; /* now `mp' is free */
416 setnilvalue(gval(mp
));
418 else { /* colliding node is in its own main position */
419 /* new node will go into free position */
420 gnext(n
) = gnext(mp
); /* chain new position */
425 gkey(mp
)->value
= key
->value
; gkey(mp
)->tt
= key
->tt
;
426 luaC_barriert(L
, t
, key
);
427 lua_assert(ttisnil(gval(mp
)));
433 ** search function for integers
435 const TValue
*luaH_getnum (Table
*t
, int key
) {
436 /* (1 <= key && key <= t->sizearray) */
437 if (cast(unsigned int, key
-1) < cast(unsigned int, t
->sizearray
))
438 return &t
->array
[key
-1];
440 lua_Number nk
= cast_num(key
);
441 Node
*n
= hashnum(t
, nk
);
442 do { /* check whether `key' is somewhere in the chain */
443 if (ttisnumber(gkey(n
)) && luai_numeq(nvalue(gkey(n
)), nk
))
444 return gval(n
); /* that's it */
447 return luaO_nilobject
;
453 ** search function for strings
455 const TValue
*luaH_getstr (Table
*t
, TString
*key
) {
456 Node
*n
= hashstr(t
, key
);
457 do { /* check whether `key' is somewhere in the chain */
458 if (ttisstring(gkey(n
)) && rawtsvalue(gkey(n
)) == key
)
459 return gval(n
); /* that's it */
462 return luaO_nilobject
;
467 ** main search function
469 const TValue
*luaH_get (Table
*t
, const TValue
*key
) {
470 switch (ttype(key
)) {
471 case LUA_TNIL
: return luaO_nilobject
;
472 case LUA_TSTRING
: return luaH_getstr(t
, rawtsvalue(key
));
475 lua_Number n
= nvalue(key
);
476 lua_number2int(k
, n
);
477 if (luai_numeq(cast_num(k
), nvalue(key
))) /* index is int? */
478 return luaH_getnum(t
, k
); /* use specialized version */
479 /* else go through */
482 Node
*n
= mainposition(t
, key
);
483 do { /* check whether `key' is somewhere in the chain */
484 if (luaO_rawequalObj(key2tval(n
), key
))
485 return gval(n
); /* that's it */
488 return luaO_nilobject
;
494 TValue
*luaH_set (lua_State
*L
, Table
*t
, const TValue
*key
) {
495 const TValue
*p
= luaH_get(t
, key
);
497 if (p
!= luaO_nilobject
)
498 return cast(TValue
*, p
);
500 if (ttisnil(key
)) luaG_runerror(L
, "table index is nil");
501 else if (ttisnumber(key
) && luai_numisnan(nvalue(key
)))
502 luaG_runerror(L
, "table index is NaN");
503 return newkey(L
, t
, key
);
508 TValue
*luaH_setnum (lua_State
*L
, Table
*t
, int key
) {
509 const TValue
*p
= luaH_getnum(t
, key
);
510 if (p
!= luaO_nilobject
)
511 return cast(TValue
*, p
);
514 setnvalue(&k
, cast_num(key
));
515 return newkey(L
, t
, &k
);
520 TValue
*luaH_setstr (lua_State
*L
, Table
*t
, TString
*key
) {
521 const TValue
*p
= luaH_getstr(t
, key
);
522 if (p
!= luaO_nilobject
)
523 return cast(TValue
*, p
);
526 setsvalue(L
, &k
, key
);
527 return newkey(L
, t
, &k
);
532 static int unbound_search (Table
*t
, unsigned int j
) {
533 unsigned int i
= j
; /* i is zero or a present index */
535 /* find `i' and `j' such that i is present and j is not */
536 while (!ttisnil(luaH_getnum(t
, j
))) {
539 if (j
> cast(unsigned int, MAX_INT
)) { /* overflow? */
540 /* table was built with bad purposes: resort to linear search */
542 while (!ttisnil(luaH_getnum(t
, i
))) i
++;
546 /* now do a binary search between them */
548 unsigned int m
= (i
+j
)/2;
549 if (ttisnil(luaH_getnum(t
, m
))) j
= m
;
557 ** Try to find a boundary in table `t'. A `boundary' is an integer index
558 ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
560 int luaH_getn (Table
*t
) {
561 unsigned int j
= t
->sizearray
;
562 if (j
> 0 && ttisnil(&t
->array
[j
- 1])) {
563 /* there is a boundary in the array part: (binary) search for it */
566 unsigned int m
= (i
+j
)/2;
567 if (ttisnil(&t
->array
[m
- 1])) j
= m
;
572 /* else must find a boundary in hash part */
573 else if (t
->node
== dummynode
) /* hash part is empty? */
574 return j
; /* that is easy... */
575 else return unbound_search(t
, j
);
580 #if defined(LUA_DEBUG)
582 Node
*luaH_mainposition (const Table
*t
, const TValue
*key
) {
583 return mainposition(t
, key
);
586 int luaH_isdummy (Node
*n
) { return n
== dummynode
; }