3 ** Copyright (C) 2005-2014 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
!= 0 && 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
);
152 /* The API of this function conforms to lua_createtable(). */
153 GCtab
*lj_tab_new_ah(lua_State
*L
, int32_t a
, int32_t h
)
155 return lj_tab_new(L
, (uint32_t)(a
> 0 ? a
+1 : 0), hsize2hbits(h
));
159 GCtab
* LJ_FASTCALL
lj_tab_new1(lua_State
*L
, uint32_t ahsize
)
161 GCtab
*t
= newtab(L
, ahsize
& 0xffffff, ahsize
>> 24);
163 if (t
->hmask
> 0) clearhpart(t
);
168 /* Duplicate a table. */
169 GCtab
* LJ_FASTCALL
lj_tab_dup(lua_State
*L
, const GCtab
*kt
)
172 uint32_t asize
, hmask
;
173 t
= newtab(L
, kt
->asize
, kt
->hmask
> 0 ? lj_fls(kt
->hmask
)+1 : 0);
174 lua_assert(kt
->asize
== t
->asize
&& kt
->hmask
== t
->hmask
);
175 t
->nomm
= 0; /* Keys with metamethod names may be present. */
178 TValue
*array
= tvref(t
->array
);
179 TValue
*karray
= tvref(kt
->array
);
180 if (asize
< 64) { /* An inlined loop beats memcpy for < 512 bytes. */
182 for (i
= 0; i
< asize
; i
++)
183 copyTV(L
, &array
[i
], &karray
[i
]);
185 memcpy(array
, karray
, asize
*sizeof(TValue
));
191 Node
*node
= noderef(t
->node
);
192 Node
*knode
= noderef(kt
->node
);
193 ptrdiff_t d
= (char *)node
- (char *)knode
;
194 setmref(node
->freetop
, (Node
*)((char *)noderef(knode
->freetop
) + d
));
195 for (i
= 0; i
<= hmask
; i
++) {
196 Node
*kn
= &knode
[i
];
198 Node
*next
= nextnode(kn
);
199 /* Don't use copyTV here, since it asserts on a copy of a dead key. */
200 n
->val
= kn
->val
; n
->key
= kn
->key
;
201 setmref(n
->next
, next
== NULL
? next
: (Node
*)((char *)next
+ d
));
208 void LJ_FASTCALL
lj_tab_clear(GCtab
*t
)
212 Node
*node
= noderef(t
->node
);
213 setmref(node
->freetop
, &node
[t
->hmask
+1]);
219 void LJ_FASTCALL
lj_tab_free(global_State
*g
, GCtab
*t
)
222 lj_mem_freevec(g
, noderef(t
->node
), t
->hmask
+1, Node
);
223 if (t
->asize
> 0 && LJ_MAX_COLOSIZE
!= 0 && t
->colo
<= 0)
224 lj_mem_freevec(g
, tvref(t
->array
), t
->asize
, TValue
);
225 if (LJ_MAX_COLOSIZE
!= 0 && t
->colo
)
226 lj_mem_free(g
, t
, sizetabcolo((uint32_t)t
->colo
& 0x7f));
231 /* -- Table resizing ------------------------------------------------------ */
233 /* Resize a table to fit the new array/hash part sizes. */
234 static void resizetab(lua_State
*L
, GCtab
*t
, uint32_t asize
, uint32_t hbits
)
236 Node
*oldnode
= noderef(t
->node
);
237 uint32_t oldasize
= t
->asize
;
238 uint32_t oldhmask
= t
->hmask
;
239 if (asize
> oldasize
) { /* Array part grows? */
242 if (asize
> LJ_MAX_ASIZE
)
243 lj_err_msg(L
, LJ_ERR_TABOV
);
244 if (LJ_MAX_COLOSIZE
!= 0 && t
->colo
> 0) {
245 /* A colocated array must be separated and copied. */
246 TValue
*oarray
= tvref(t
->array
);
247 array
= lj_mem_newvec(L
, asize
, TValue
);
248 t
->colo
= (int8_t)(t
->colo
| 0x80); /* Mark as separated (colo < 0). */
249 for (i
= 0; i
< oldasize
; i
++)
250 copyTV(L
, &array
[i
], &oarray
[i
]);
252 array
= (TValue
*)lj_mem_realloc(L
, tvref(t
->array
),
253 oldasize
*sizeof(TValue
), asize
*sizeof(TValue
));
255 setmref(t
->array
, array
);
257 for (i
= oldasize
; i
< asize
; i
++) /* Clear newly allocated slots. */
260 /* Create new (empty) hash part. */
262 newhpart(L
, t
, hbits
);
265 global_State
*g
= G(L
);
266 setmref(t
->node
, &g
->nilnode
);
269 if (asize
< oldasize
) { /* Array part shrinks? */
270 TValue
*array
= tvref(t
->array
);
272 t
->asize
= asize
; /* Note: This 'shrinks' even colocated arrays. */
273 for (i
= asize
; i
< oldasize
; i
++) /* Reinsert old array values. */
274 if (!tvisnil(&array
[i
]))
275 copyTV(L
, lj_tab_setinth(L
, t
, (int32_t)i
), &array
[i
]);
276 /* Physically shrink only separated arrays. */
277 if (LJ_MAX_COLOSIZE
!= 0 && t
->colo
<= 0)
278 setmref(t
->array
, lj_mem_realloc(L
, array
,
279 oldasize
*sizeof(TValue
), asize
*sizeof(TValue
)));
281 if (oldhmask
> 0) { /* Reinsert pairs from old hash part. */
284 for (i
= 0; i
<= oldhmask
; i
++) {
285 Node
*n
= &oldnode
[i
];
286 if (!tvisnil(&n
->val
))
287 copyTV(L
, lj_tab_set(L
, t
, &n
->key
), &n
->val
);
290 lj_mem_freevec(g
, oldnode
, oldhmask
+1, Node
);
294 static uint32_t countint(cTValue
*key
, uint32_t *bins
)
296 lua_assert(!tvisint(key
));
298 lua_Number nk
= numV(key
);
299 int32_t k
= lj_num2int(nk
);
300 if ((uint32_t)k
< LJ_MAX_ASIZE
&& nk
== (lua_Number
)k
) {
301 bins
[(k
> 2 ? lj_fls((uint32_t)(k
-1)) : 0)]++;
308 static uint32_t countarray(const GCtab
*t
, uint32_t *bins
)
311 if (t
->asize
== 0) return 0;
312 for (na
= i
= b
= 0; b
< LJ_MAX_ABITS
; b
++) {
313 uint32_t n
, top
= 2u << b
;
315 if (top
>= t
->asize
) {
320 array
= tvref(t
->array
);
321 for (n
= 0; i
<= top
; i
++)
322 if (!tvisnil(&array
[i
]))
330 static uint32_t counthash(const GCtab
*t
, uint32_t *bins
, uint32_t *narray
)
332 uint32_t total
, na
, i
, hmask
= t
->hmask
;
333 Node
*node
= noderef(t
->node
);
334 for (total
= na
= 0, i
= 0; i
<= hmask
; i
++) {
336 if (!tvisnil(&n
->val
)) {
337 na
+= countint(&n
->key
, bins
);
345 static uint32_t bestasize(uint32_t bins
[], uint32_t *narray
)
347 uint32_t b
, sum
, na
= 0, sz
= 0, nn
= *narray
;
348 for (b
= 0, sum
= 0; 2*nn
> (1u<<b
) && sum
!= nn
; b
++)
349 if (bins
[b
] > 0 && 2*(sum
+= bins
[b
]) > (1u<<b
)) {
357 static void rehashtab(lua_State
*L
, GCtab
*t
, cTValue
*ek
)
359 uint32_t bins
[LJ_MAX_ABITS
];
360 uint32_t total
, asize
, na
, i
;
361 for (i
= 0; i
< LJ_MAX_ABITS
; i
++) bins
[i
] = 0;
362 asize
= countarray(t
, bins
);
364 total
+= counthash(t
, bins
, &asize
);
365 asize
+= countint(ek
, bins
);
366 na
= bestasize(bins
, &asize
);
368 resizetab(L
, t
, asize
, hsize2hbits(total
));
372 void lj_tab_rehash(lua_State
*L
, GCtab
*t
)
374 rehashtab(L
, t
, niltv(L
));
378 void lj_tab_reasize(lua_State
*L
, GCtab
*t
, uint32_t nasize
)
380 resizetab(L
, t
, nasize
+1, t
->hmask
> 0 ? lj_fls(t
->hmask
)+1 : 0);
383 /* -- Table getters ------------------------------------------------------- */
385 cTValue
* LJ_FASTCALL
lj_tab_getinth(GCtab
*t
, int32_t key
)
389 k
.n
= (lua_Number
)key
;
392 if (tvisnum(&n
->key
) && n
->key
.n
== k
.n
)
394 } while ((n
= nextnode(n
)));
398 cTValue
*lj_tab_getstr(GCtab
*t
, GCstr
*key
)
400 Node
*n
= hashstr(t
, key
);
402 if (tvisstr(&n
->key
) && strV(&n
->key
) == key
)
404 } while ((n
= nextnode(n
)));
408 cTValue
*lj_tab_get(lua_State
*L
, GCtab
*t
, cTValue
*key
)
411 cTValue
*tv
= lj_tab_getstr(t
, strV(key
));
414 } else if (tvisint(key
)) {
415 cTValue
*tv
= lj_tab_getint(t
, intV(key
));
418 } else if (tvisnum(key
)) {
419 lua_Number nk
= numV(key
);
420 int32_t k
= lj_num2int(nk
);
421 if (nk
== (lua_Number
)k
) {
422 cTValue
*tv
= lj_tab_getint(t
, k
);
426 goto genlookup
; /* Else use the generic lookup. */
428 } else if (!tvisnil(key
)) {
433 if (lj_obj_equal(&n
->key
, key
))
435 } while ((n
= nextnode(n
)));
440 /* -- Table setters ------------------------------------------------------- */
442 /* Insert new key. Use Brent's variation to optimize the chain length. */
443 TValue
*lj_tab_newkey(lua_State
*L
, GCtab
*t
, cTValue
*key
)
445 Node
*n
= hashkey(t
, key
);
446 if (!tvisnil(&n
->val
) || t
->hmask
== 0) {
447 Node
*nodebase
= noderef(t
->node
);
448 Node
*collide
, *freenode
= noderef(nodebase
->freetop
);
449 lua_assert(freenode
>= nodebase
&& freenode
<= nodebase
+t
->hmask
+1);
451 if (freenode
== nodebase
) { /* No free node found? */
452 rehashtab(L
, t
, key
); /* Rehash table. */
453 return lj_tab_set(L
, t
, key
); /* Retry key insertion. */
455 } while (!tvisnil(&(--freenode
)->key
));
456 setmref(nodebase
->freetop
, freenode
);
457 lua_assert(freenode
!= &G(L
)->nilnode
);
458 collide
= hashkey(t
, &n
->key
);
459 if (collide
!= n
) { /* Colliding node not the main node? */
460 while (noderef(collide
->next
) != n
) /* Find predecessor. */
461 collide
= nextnode(collide
);
462 setmref(collide
->next
, freenode
); /* Relink chain. */
463 /* Copy colliding node into free node and free main node. */
464 freenode
->val
= n
->val
;
465 freenode
->key
= n
->key
;
466 freenode
->next
= n
->next
;
467 setmref(n
->next
, NULL
);
469 /* Rechain pseudo-resurrected string keys with colliding hashes. */
470 while (nextnode(freenode
)) {
471 Node
*nn
= nextnode(freenode
);
472 if (tvisstr(&nn
->key
) && !tvisnil(&nn
->val
) &&
473 hashstr(t
, strV(&nn
->key
)) == n
) {
474 freenode
->next
= nn
->next
;
476 setmref(n
->next
, nn
);
481 } else { /* Otherwise use free node. */
482 setmrefr(freenode
->next
, n
->next
); /* Insert into chain. */
483 setmref(n
->next
, freenode
);
487 n
->key
.u64
= key
->u64
;
488 if (LJ_UNLIKELY(tvismzero(&n
->key
)))
490 lj_gc_anybarriert(L
, t
);
491 lua_assert(tvisnil(&n
->val
));
495 TValue
*lj_tab_setinth(lua_State
*L
, GCtab
*t
, int32_t key
)
499 k
.n
= (lua_Number
)key
;
502 if (tvisnum(&n
->key
) && n
->key
.n
== k
.n
)
504 } while ((n
= nextnode(n
)));
505 return lj_tab_newkey(L
, t
, &k
);
508 TValue
*lj_tab_setstr(lua_State
*L
, GCtab
*t
, GCstr
*key
)
511 Node
*n
= hashstr(t
, key
);
513 if (tvisstr(&n
->key
) && strV(&n
->key
) == key
)
515 } while ((n
= nextnode(n
)));
517 return lj_tab_newkey(L
, t
, &k
);
520 TValue
*lj_tab_set(lua_State
*L
, GCtab
*t
, cTValue
*key
)
523 t
->nomm
= 0; /* Invalidate negative metamethod cache. */
525 return lj_tab_setstr(L
, t
, strV(key
));
526 } else if (tvisint(key
)) {
527 return lj_tab_setint(L
, t
, intV(key
));
528 } else if (tvisnum(key
)) {
529 lua_Number nk
= numV(key
);
530 int32_t k
= lj_num2int(nk
);
531 if (nk
== (lua_Number
)k
)
532 return lj_tab_setint(L
, t
, k
);
534 lj_err_msg(L
, LJ_ERR_NANIDX
);
535 /* Else use the generic lookup. */
536 } else if (tvisnil(key
)) {
537 lj_err_msg(L
, LJ_ERR_NILIDX
);
541 if (lj_obj_equal(&n
->key
, key
))
543 } while ((n
= nextnode(n
)));
544 return lj_tab_newkey(L
, t
, key
);
547 /* -- Table traversal ----------------------------------------------------- */
549 /* Get the traversal index of a key. */
550 static uint32_t keyindex(lua_State
*L
, GCtab
*t
, cTValue
*key
)
554 int32_t k
= intV(key
);
555 if ((uint32_t)k
< t
->asize
)
556 return (uint32_t)k
; /* Array key indexes: [0..t->asize-1] */
557 setnumV(&tmp
, (lua_Number
)k
);
559 } else if (tvisnum(key
)) {
560 lua_Number nk
= numV(key
);
561 int32_t k
= lj_num2int(nk
);
562 if ((uint32_t)k
< t
->asize
&& nk
== (lua_Number
)k
)
563 return (uint32_t)k
; /* Array key indexes: [0..t->asize-1] */
566 Node
*n
= hashkey(t
, key
);
568 if (lj_obj_equal(&n
->key
, key
))
569 return t
->asize
+ (uint32_t)(n
- noderef(t
->node
));
570 /* Hash key indexes: [t->asize..t->asize+t->nmask] */
571 } while ((n
= nextnode(n
)));
572 if (key
->u32
.hi
== 0xfffe7fff) /* ITERN was despecialized while running. */
573 return key
->u32
.lo
- 1;
574 lj_err_msg(L
, LJ_ERR_NEXTIDX
);
575 return 0; /* unreachable */
577 return ~0u; /* A nil key starts the traversal. */
580 /* Advance to the next step in a table traversal. */
581 int lj_tab_next(lua_State
*L
, GCtab
*t
, TValue
*key
)
583 uint32_t i
= keyindex(L
, t
, key
); /* Find predecessor key index. */
584 for (i
++; i
< t
->asize
; i
++) /* First traverse the array keys. */
585 if (!tvisnil(arrayslot(t
, i
))) {
587 copyTV(L
, key
+1, arrayslot(t
, i
));
590 for (i
-= t
->asize
; i
<= t
->hmask
; i
++) { /* Then traverse the hash keys. */
591 Node
*n
= &noderef(t
->node
)[i
];
592 if (!tvisnil(&n
->val
)) {
593 copyTV(L
, key
, &n
->key
);
594 copyTV(L
, key
+1, &n
->val
);
598 return 0; /* End of traversal. */
601 /* -- Table length calculation -------------------------------------------- */
603 static MSize
unbound_search(GCtab
*t
, MSize j
)
606 MSize i
= j
; /* i is zero or a present index */
608 /* find `i' and `j' such that i is present and j is not */
609 while ((tv
= lj_tab_getint(t
, (int32_t)j
)) && !tvisnil(tv
)) {
612 if (j
> (MSize
)(INT_MAX
-2)) { /* overflow? */
613 /* table was built with bad purposes: resort to linear search */
615 while ((tv
= lj_tab_getint(t
, (int32_t)i
)) && !tvisnil(tv
)) i
++;
619 /* now do a binary search between them */
622 cTValue
*tvb
= lj_tab_getint(t
, (int32_t)m
);
623 if (tvb
&& !tvisnil(tvb
)) i
= m
; else j
= m
;
629 ** Try to find a boundary in table `t'. A `boundary' is an integer index
630 ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
632 MSize LJ_FASTCALL
lj_tab_len(GCtab
*t
)
634 MSize j
= (MSize
)t
->asize
;
635 if (j
> 1 && tvisnil(arrayslot(t
, j
-1))) {
639 if (tvisnil(arrayslot(t
, m
-1))) j
= m
; else i
= m
;
646 return unbound_search(t
, j
);