3 ** Copyright (C) 2005-2011 Mike Pall. See Copyright Notice in luajit.h
5 ** Major portions taken verbatim or adapted from the Lua interpreter.
6 ** Copyright (C) 1994-2008 Lua.org, PUC-Rio. See Copyright Notice in lua.h
17 /* -- Object hashing ------------------------------------------------------ */
19 /* Hash values are masked with the table hash mask and used as an index. */
20 static LJ_AINLINE Node
*hashmask(const GCtab
*t
, uint32_t hash
)
22 Node
*n
= noderef(t
->node
);
23 return &n
[hash
& t
->hmask
];
26 /* String hashes are precomputed when they are interned. */
27 #define hashstr(t, s) hashmask(t, (s)->hash)
29 #define hashlohi(t, lo, hi) hashmask((t), hashrot((lo), (hi)))
30 #define hashnum(t, o) hashlohi((t), (o)->u32.lo, ((o)->u32.hi << 1))
31 #define hashptr(t, p) hashlohi((t), u32ptr(p), u32ptr(p) + HASH_BIAS)
32 #define hashgcref(t, r) hashlohi((t), gcrefu(r), gcrefu(r) + HASH_BIAS)
34 /* Hash an arbitrary key and return its anchor position in the hash table. */
35 static Node
*hashkey(const GCtab
*t
, cTValue
*key
)
37 lua_assert(!tvisint(key
));
39 return hashstr(t
, strV(key
));
40 else if (tvisnum(key
))
41 return hashnum(t
, key
);
42 else if (tvisbool(key
))
43 return hashmask(t
, boolV(key
));
45 return hashgcref(t
, key
->gcr
);
46 /* Only hash 32 bits of lightuserdata on a 64 bit CPU. Good enough? */
49 /* -- Table creation and destruction -------------------------------------- */
51 /* Create new hash part for table. */
52 static LJ_AINLINE
void newhpart(lua_State
*L
, GCtab
*t
, uint32_t hbits
)
56 lua_assert(hbits
!= 0);
57 if (hbits
> LJ_MAX_HBITS
)
58 lj_err_msg(L
, LJ_ERR_TABOV
);
60 node
= lj_mem_newvec(L
, hsize
, Node
);
61 setmref(node
->freetop
, &node
[hsize
]);
62 setmref(t
->node
, node
);
67 ** Q: Why all of these copies of t->hmask, t->node etc. to local variables?
68 ** A: Because alias analysis for C is _really_ tough.
69 ** Even state-of-the-art C compilers won't produce good code without this.
72 /* Clear hash part of table. */
73 static LJ_AINLINE
void clearhpart(GCtab
*t
)
75 uint32_t i
, hmask
= t
->hmask
;
76 Node
*node
= noderef(t
->node
);
77 lua_assert(t
->hmask
!= 0);
78 for (i
= 0; i
<= hmask
; i
++) {
80 setmref(n
->next
, NULL
);
86 /* Clear array part of table. */
87 static LJ_AINLINE
void clearapart(GCtab
*t
)
89 uint32_t i
, asize
= t
->asize
;
90 TValue
*array
= tvref(t
->array
);
91 for (i
= 0; i
< asize
; i
++)
95 /* Create a new table. Note: the slots are not initialized (yet). */
96 static GCtab
*newtab(lua_State
*L
, uint32_t asize
, uint32_t hbits
)
99 /* First try to colocate the array part. */
100 if (LJ_MAX_COLOSIZE
&& asize
> 0 && asize
<= LJ_MAX_COLOSIZE
) {
101 lua_assert((sizeof(GCtab
) & 7) == 0);
102 t
= (GCtab
*)lj_mem_newgco(L
, sizetabcolo(asize
));
104 t
->nomm
= (uint8_t)~0;
105 t
->colo
= (int8_t)asize
;
106 setmref(t
->array
, (TValue
*)((char *)t
+ sizeof(GCtab
)));
107 setgcrefnull(t
->metatable
);
110 setmref(t
->node
, &G(L
)->nilnode
);
111 } else { /* Otherwise separately allocate the array part. */
112 t
= lj_mem_newobj(L
, GCtab
);
114 t
->nomm
= (uint8_t)~0;
116 setmref(t
->array
, NULL
);
117 setgcrefnull(t
->metatable
);
118 t
->asize
= 0; /* In case the array allocation fails. */
120 setmref(t
->node
, &G(L
)->nilnode
);
122 if (asize
> LJ_MAX_ASIZE
)
123 lj_err_msg(L
, LJ_ERR_TABOV
);
124 setmref(t
->array
, lj_mem_newvec(L
, asize
, TValue
));
129 newhpart(L
, t
, hbits
);
133 /* Create a new table.
135 ** IMPORTANT NOTE: The API differs from lua_createtable()!
137 ** The array size is non-inclusive. E.g. asize=128 creates array slots
138 ** for 0..127, but not for 128. If you need slots 1..128, pass asize=129
139 ** (slot 0 is wasted in this case).
141 ** The hash size is given in hash bits. hbits=0 means no hash part.
142 ** hbits=1 creates 2 hash slots, hbits=2 creates 4 hash slots and so on.
144 GCtab
*lj_tab_new(lua_State
*L
, uint32_t asize
, uint32_t hbits
)
146 GCtab
*t
= newtab(L
, asize
, hbits
);
148 if (t
->hmask
> 0) clearhpart(t
);
153 GCtab
* LJ_FASTCALL
lj_tab_new1(lua_State
*L
, uint32_t ahsize
)
155 GCtab
*t
= newtab(L
, ahsize
& 0xffffff, ahsize
>> 24);
157 if (t
->hmask
> 0) clearhpart(t
);
162 /* Duplicate a table. */
163 GCtab
* LJ_FASTCALL
lj_tab_dup(lua_State
*L
, const GCtab
*kt
)
166 uint32_t asize
, hmask
;
167 t
= newtab(L
, kt
->asize
, kt
->hmask
> 0 ? lj_fls(kt
->hmask
)+1 : 0);
168 lua_assert(kt
->asize
== t
->asize
&& kt
->hmask
== t
->hmask
);
169 t
->nomm
= 0; /* Keys with metamethod names may be present. */
172 TValue
*array
= tvref(t
->array
);
173 TValue
*karray
= tvref(kt
->array
);
174 if (asize
< 64) { /* An inlined loop beats memcpy for < 512 bytes. */
176 for (i
= 0; i
< asize
; i
++)
177 copyTV(L
, &array
[i
], &karray
[i
]);
179 memcpy(array
, karray
, asize
*sizeof(TValue
));
185 Node
*node
= noderef(t
->node
);
186 Node
*knode
= noderef(kt
->node
);
187 ptrdiff_t d
= (char *)node
- (char *)knode
;
188 setmref(node
->freetop
, (Node
*)((char *)noderef(knode
->freetop
) + d
));
189 for (i
= 0; i
<= hmask
; i
++) {
190 Node
*kn
= &knode
[i
];
192 Node
*next
= nextnode(kn
);
193 /* Don't use copyTV here, since it asserts on a copy of a dead key. */
194 n
->val
= kn
->val
; n
->key
= kn
->key
;
195 setmref(n
->next
, next
== NULL
? next
: (Node
*)((char *)next
+ d
));
202 void LJ_FASTCALL
lj_tab_free(global_State
*g
, GCtab
*t
)
205 lj_mem_freevec(g
, noderef(t
->node
), t
->hmask
+1, Node
);
206 if (t
->asize
> 0 && LJ_MAX_COLOSIZE
&& t
->colo
<= 0)
207 lj_mem_freevec(g
, tvref(t
->array
), t
->asize
, TValue
);
208 if (LJ_MAX_COLOSIZE
&& t
->colo
)
209 lj_mem_free(g
, t
, sizetabcolo((uint32_t)t
->colo
& 0x7f));
214 /* -- Table resizing ------------------------------------------------------ */
216 /* Resize a table to fit the new array/hash part sizes. */
217 static void resizetab(lua_State
*L
, GCtab
*t
, uint32_t asize
, uint32_t hbits
)
219 Node
*oldnode
= noderef(t
->node
);
220 uint32_t oldasize
= t
->asize
;
221 uint32_t oldhmask
= t
->hmask
;
222 if (asize
> oldasize
) { /* Array part grows? */
225 if (asize
> LJ_MAX_ASIZE
)
226 lj_err_msg(L
, LJ_ERR_TABOV
);
227 if (LJ_MAX_COLOSIZE
&& t
->colo
> 0) {
228 /* A colocated array must be separated and copied. */
229 TValue
*oarray
= tvref(t
->array
);
230 array
= lj_mem_newvec(L
, asize
, TValue
);
231 t
->colo
= (int8_t)(t
->colo
| 0x80); /* Mark as separated (colo < 0). */
232 for (i
= 0; i
< oldasize
; i
++)
233 copyTV(L
, &array
[i
], &oarray
[i
]);
235 array
= (TValue
*)lj_mem_realloc(L
, tvref(t
->array
),
236 oldasize
*sizeof(TValue
), asize
*sizeof(TValue
));
238 setmref(t
->array
, array
);
240 for (i
= oldasize
; i
< asize
; i
++) /* Clear newly allocated slots. */
243 /* Create new (empty) hash part. */
245 newhpart(L
, t
, hbits
);
248 global_State
*g
= G(L
);
249 setmref(t
->node
, &g
->nilnode
);
252 if (asize
< oldasize
) { /* Array part shrinks? */
253 TValue
*array
= tvref(t
->array
);
255 t
->asize
= asize
; /* Note: This 'shrinks' even colocated arrays. */
256 for (i
= asize
; i
< oldasize
; i
++) /* Reinsert old array values. */
257 if (!tvisnil(&array
[i
]))
258 copyTV(L
, lj_tab_setinth(L
, t
, (int32_t)i
), &array
[i
]);
259 /* Physically shrink only separated arrays. */
260 if (LJ_MAX_COLOSIZE
&& t
->colo
<= 0)
261 setmref(t
->array
, lj_mem_realloc(L
, array
,
262 oldasize
*sizeof(TValue
), asize
*sizeof(TValue
)));
264 if (oldhmask
> 0) { /* Reinsert pairs from old hash part. */
267 for (i
= 0; i
<= oldhmask
; i
++) {
268 Node
*n
= &oldnode
[i
];
269 if (!tvisnil(&n
->val
))
270 copyTV(L
, lj_tab_set(L
, t
, &n
->key
), &n
->val
);
273 lj_mem_freevec(g
, oldnode
, oldhmask
+1, Node
);
277 static uint32_t countint(cTValue
*key
, uint32_t *bins
)
279 lua_assert(!tvisint(key
));
281 lua_Number nk
= numV(key
);
282 int32_t k
= lj_num2int(nk
);
283 if ((uint32_t)k
< LJ_MAX_ASIZE
&& nk
== (lua_Number
)k
) {
284 bins
[(k
> 2 ? lj_fls((uint32_t)(k
-1)) : 0)]++;
291 static uint32_t countarray(const GCtab
*t
, uint32_t *bins
)
294 if (t
->asize
== 0) return 0;
295 for (na
= i
= b
= 0; b
< LJ_MAX_ABITS
; b
++) {
296 uint32_t n
, top
= 2u << b
;
298 if (top
>= t
->asize
) {
303 array
= tvref(t
->array
);
304 for (n
= 0; i
<= top
; i
++)
305 if (!tvisnil(&array
[i
]))
313 static uint32_t counthash(const GCtab
*t
, uint32_t *bins
, uint32_t *narray
)
315 uint32_t total
, na
, i
, hmask
= t
->hmask
;
316 Node
*node
= noderef(t
->node
);
317 for (total
= na
= 0, i
= 0; i
<= hmask
; i
++) {
319 if (!tvisnil(&n
->val
)) {
320 na
+= countint(&n
->key
, bins
);
328 static uint32_t bestasize(uint32_t bins
[], uint32_t *narray
)
330 uint32_t b
, sum
, na
= 0, sz
= 0, nn
= *narray
;
331 for (b
= 0, sum
= 0; 2*nn
> (1u<<b
) && sum
!= nn
; b
++)
332 if (bins
[b
] > 0 && 2*(sum
+= bins
[b
]) > (1u<<b
)) {
340 static void rehashtab(lua_State
*L
, GCtab
*t
, cTValue
*ek
)
342 uint32_t bins
[LJ_MAX_ABITS
];
343 uint32_t total
, asize
, na
, i
;
344 for (i
= 0; i
< LJ_MAX_ABITS
; i
++) bins
[i
] = 0;
345 asize
= countarray(t
, bins
);
347 total
+= counthash(t
, bins
, &asize
);
348 asize
+= countint(ek
, bins
);
349 na
= bestasize(bins
, &asize
);
351 resizetab(L
, t
, asize
, hsize2hbits(total
));
354 void lj_tab_reasize(lua_State
*L
, GCtab
*t
, uint32_t nasize
)
356 resizetab(L
, t
, nasize
+1, t
->hmask
> 0 ? lj_fls(t
->hmask
)+1 : 0);
359 /* -- Table getters ------------------------------------------------------- */
361 cTValue
* LJ_FASTCALL
lj_tab_getinth(GCtab
*t
, int32_t key
)
365 k
.n
= (lua_Number
)key
;
368 if (tvisnum(&n
->key
) && n
->key
.n
== k
.n
)
370 } while ((n
= nextnode(n
)));
374 cTValue
*lj_tab_getstr(GCtab
*t
, GCstr
*key
)
376 Node
*n
= hashstr(t
, key
);
378 if (tvisstr(&n
->key
) && strV(&n
->key
) == key
)
380 } while ((n
= nextnode(n
)));
384 cTValue
*lj_tab_get(lua_State
*L
, GCtab
*t
, cTValue
*key
)
387 cTValue
*tv
= lj_tab_getstr(t
, strV(key
));
390 } else if (tvisint(key
)) {
391 cTValue
*tv
= lj_tab_getint(t
, intV(key
));
394 } else if (tvisnum(key
)) {
395 lua_Number nk
= numV(key
);
396 int32_t k
= lj_num2int(nk
);
397 if (nk
== (lua_Number
)k
) {
398 cTValue
*tv
= lj_tab_getint(t
, k
);
402 goto genlookup
; /* Else use the generic lookup. */
404 } else if (!tvisnil(key
)) {
409 if (lj_obj_equal(&n
->key
, key
))
411 } while ((n
= nextnode(n
)));
416 /* -- Table setters ------------------------------------------------------- */
418 /* Insert new key. Use Brent's variation to optimize the chain length. */
419 TValue
*lj_tab_newkey(lua_State
*L
, GCtab
*t
, cTValue
*key
)
421 Node
*n
= hashkey(t
, key
);
422 if (!tvisnil(&n
->val
) || t
->hmask
== 0) {
423 Node
*nodebase
= noderef(t
->node
);
424 Node
*collide
, *freenode
= noderef(nodebase
->freetop
);
425 lua_assert(freenode
>= nodebase
&& freenode
<= nodebase
+t
->hmask
+1);
427 if (freenode
== nodebase
) { /* No free node found? */
428 rehashtab(L
, t
, key
); /* Rehash table. */
429 return lj_tab_set(L
, t
, key
); /* Retry key insertion. */
431 } while (!tvisnil(&(--freenode
)->key
));
432 setmref(nodebase
->freetop
, freenode
);
433 lua_assert(freenode
!= &G(L
)->nilnode
);
434 collide
= hashkey(t
, &n
->key
);
435 if (collide
!= n
) { /* Colliding node not the main node? */
436 while (noderef(collide
->next
) != n
) /* Find predecessor. */
437 collide
= nextnode(collide
);
438 setmref(collide
->next
, freenode
); /* Relink chain. */
439 /* Copy colliding node into free node and free main node. */
440 freenode
->val
= n
->val
;
441 freenode
->key
= n
->key
;
442 freenode
->next
= n
->next
;
443 setmref(n
->next
, NULL
);
445 /* Rechain pseudo-resurrected string keys with colliding hashes. */
446 while (nextnode(freenode
)) {
447 Node
*nn
= nextnode(freenode
);
448 if (tvisstr(&nn
->key
) && !tvisnil(&nn
->val
) &&
449 hashstr(t
, strV(&nn
->key
)) == n
) {
450 freenode
->next
= nn
->next
;
452 setmref(n
->next
, nn
);
457 } else { /* Otherwise use free node. */
458 setmrefr(freenode
->next
, n
->next
); /* Insert into chain. */
459 setmref(n
->next
, freenode
);
463 n
->key
.u64
= key
->u64
;
464 if (LJ_UNLIKELY(tvismzero(&n
->key
)))
466 lj_gc_anybarriert(L
, t
);
467 lua_assert(tvisnil(&n
->val
));
471 TValue
*lj_tab_setinth(lua_State
*L
, GCtab
*t
, int32_t key
)
475 k
.n
= (lua_Number
)key
;
478 if (tvisnum(&n
->key
) && n
->key
.n
== k
.n
)
480 } while ((n
= nextnode(n
)));
481 return lj_tab_newkey(L
, t
, &k
);
484 TValue
*lj_tab_setstr(lua_State
*L
, GCtab
*t
, GCstr
*key
)
487 Node
*n
= hashstr(t
, key
);
489 if (tvisstr(&n
->key
) && strV(&n
->key
) == key
)
491 } while ((n
= nextnode(n
)));
493 return lj_tab_newkey(L
, t
, &k
);
496 TValue
*lj_tab_set(lua_State
*L
, GCtab
*t
, cTValue
*key
)
499 t
->nomm
= 0; /* Invalidate negative metamethod cache. */
501 return lj_tab_setstr(L
, t
, strV(key
));
502 } else if (tvisint(key
)) {
503 return lj_tab_setint(L
, t
, intV(key
));
504 } else if (tvisnum(key
)) {
505 lua_Number nk
= numV(key
);
506 int32_t k
= lj_num2int(nk
);
507 if (nk
== (lua_Number
)k
)
508 return lj_tab_setint(L
, t
, k
);
510 lj_err_msg(L
, LJ_ERR_NANIDX
);
511 /* Else use the generic lookup. */
512 } else if (tvisnil(key
)) {
513 lj_err_msg(L
, LJ_ERR_NILIDX
);
517 if (lj_obj_equal(&n
->key
, key
))
519 } while ((n
= nextnode(n
)));
520 return lj_tab_newkey(L
, t
, key
);
523 /* -- Table traversal ----------------------------------------------------- */
525 /* Get the traversal index of a key. */
526 static uint32_t keyindex(lua_State
*L
, GCtab
*t
, cTValue
*key
)
530 int32_t k
= intV(key
);
531 if ((uint32_t)k
< t
->asize
)
532 return (uint32_t)k
; /* Array key indexes: [0..t->asize-1] */
533 setnumV(&tmp
, (lua_Number
)k
);
535 } else if (tvisnum(key
)) {
536 lua_Number nk
= numV(key
);
537 int32_t k
= lj_num2int(nk
);
538 if ((uint32_t)k
< t
->asize
&& nk
== (lua_Number
)k
)
539 return (uint32_t)k
; /* Array key indexes: [0..t->asize-1] */
542 Node
*n
= hashkey(t
, key
);
544 if (lj_obj_equal(&n
->key
, key
))
545 return t
->asize
+ (uint32_t)(n
- noderef(t
->node
));
546 /* Hash key indexes: [t->asize..t->asize+t->nmask] */
547 } while ((n
= nextnode(n
)));
548 lj_err_msg(L
, LJ_ERR_NEXTIDX
);
549 return 0; /* unreachable */
551 return ~0u; /* A nil key starts the traversal. */
554 /* Advance to the next step in a table traversal. */
555 int lj_tab_next(lua_State
*L
, GCtab
*t
, TValue
*key
)
557 uint32_t i
= keyindex(L
, t
, key
); /* Find predecessor key index. */
558 for (i
++; i
< t
->asize
; i
++) /* First traverse the array keys. */
559 if (!tvisnil(arrayslot(t
, i
))) {
561 copyTV(L
, key
+1, arrayslot(t
, i
));
564 for (i
-= t
->asize
; i
<= t
->hmask
; i
++) { /* Then traverse the hash keys. */
565 Node
*n
= &noderef(t
->node
)[i
];
566 if (!tvisnil(&n
->val
)) {
567 copyTV(L
, key
, &n
->key
);
568 copyTV(L
, key
+1, &n
->val
);
572 return 0; /* End of traversal. */
575 /* -- Table length calculation -------------------------------------------- */
577 static MSize
unbound_search(GCtab
*t
, MSize j
)
580 MSize i
= j
; /* i is zero or a present index */
582 /* find `i' and `j' such that i is present and j is not */
583 while ((tv
= lj_tab_getint(t
, cast(int32_t, j
))) && !tvisnil(tv
)) {
586 if (j
> (MSize
)(INT_MAX
-2)) { /* overflow? */
587 /* table was built with bad purposes: resort to linear search */
589 while ((tv
= lj_tab_getint(t
, cast(int32_t, i
))) && !tvisnil(tv
)) i
++;
593 /* now do a binary search between them */
596 cTValue
*tvb
= lj_tab_getint(t
, cast(int32_t, m
));
597 if (tvb
&& !tvisnil(tvb
)) i
= m
; else j
= m
;
603 ** Try to find a boundary in table `t'. A `boundary' is an integer index
604 ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
606 MSize LJ_FASTCALL
lj_tab_len(GCtab
*t
)
608 MSize j
= (MSize
)t
->asize
;
609 if (j
> 1 && tvisnil(arrayslot(t
, j
-1))) {
613 if (tvisnil(arrayslot(t
, m
-1))) j
= m
; else i
= m
;
620 return unbound_search(t
, j
);