1 /*
2 ** Table handling.
3 ** Copyright (C) 2005-2017 Mike Pall. See Copyright Notice in luajit.h
4 **
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
7 */
8
9 #define lj_tab_c
10 #define LUA_CORE
11
12 #include "lj_obj.h"
13 #include "lj_gc.h"
14 #include "lj_err.h"
15 #include "lj_tab.h"
16
17 /* -- Object hashing ------------------------------------------------------ */
18
19 /* Hash values are masked with the table hash mask and used as an index. */
hashmask(const GCtab * t,uint32_t hash)20 static LJ_AINLINE Node *hashmask(const GCtab *t, uint32_t hash)
21 {
22 Node *n = noderef(t->node);
23 return &n[hash & t->hmask];
24 }
25
26 /* String hashes are precomputed when they are interned. */
27 #define hashstr(t, s) hashmask(t, (s)->hash)
28
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 #if LJ_GC64
32 #define hashgcref(t, r) \
33 hashlohi((t), (uint32_t)gcrefu(r), (uint32_t)(gcrefu(r) >> 32))
34 #else
35 #define hashgcref(t, r) hashlohi((t), gcrefu(r), gcrefu(r) + HASH_BIAS)
36 #endif
37
38 /* Hash an arbitrary key and return its anchor position in the hash table. */
hashkey(const GCtab * t,cTValue * key)39 static Node *hashkey(const GCtab *t, cTValue *key)
40 {
41 lua_assert(!tvisint(key));
42 if (tvisstr(key))
43 return hashstr(t, strV(key));
44 else if (tvisnum(key))
45 return hashnum(t, key);
46 else if (tvisbool(key))
47 return hashmask(t, boolV(key));
48 else
49 return hashgcref(t, key->gcr);
50 /* Only hash 32 bits of lightuserdata on a 64 bit CPU. Good enough? */
51 }
52
53 /* -- Table creation and destruction -------------------------------------- */
54
55 /* Create new hash part for table. */
newhpart(lua_State * L,GCtab * t,uint32_t hbits)56 static LJ_AINLINE void newhpart(lua_State *L, GCtab *t, uint32_t hbits)
57 {
58 uint32_t hsize;
59 Node *node;
60 lua_assert(hbits != 0);
61 if (hbits > LJ_MAX_HBITS)
62 lj_err_msg(L, LJ_ERR_TABOV);
63 hsize = 1u << hbits;
64 node = lj_mem_newvec(L, hsize, Node);
65 setmref(t->node, node);
66 setfreetop(t, node, &node[hsize]);
67 t->hmask = hsize-1;
68 }
69
70 /*
71 ** Q: Why all of these copies of t->hmask, t->node etc. to local variables?
72 ** A: Because alias analysis for C is _really_ tough.
73 ** Even state-of-the-art C compilers won't produce good code without this.
74 */
75
76 /* Clear hash part of table. */
clearhpart(GCtab * t)77 static LJ_AINLINE void clearhpart(GCtab *t)
78 {
79 uint32_t i, hmask = t->hmask;
80 Node *node = noderef(t->node);
81 lua_assert(t->hmask != 0);
82 for (i = 0; i <= hmask; i++) {
83 Node *n = &node[i];
84 setmref(n->next, NULL);
85 setnilV(&n->key);
86 setnilV(&n->val);
87 }
88 }
89
90 /* Clear array part of table. */
clearapart(GCtab * t)91 static LJ_AINLINE void clearapart(GCtab *t)
92 {
93 uint32_t i, asize = t->asize;
94 TValue *array = tvref(t->array);
95 for (i = 0; i < asize; i++)
96 setnilV(&array[i]);
97 }
98
99 /* Create a new table. Note: the slots are not initialized (yet). */
newtab(lua_State * L,uint32_t asize,uint32_t hbits)100 static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
101 {
102 GCtab *t;
103 /* First try to colocate the array part. */
104 if (LJ_MAX_COLOSIZE != 0 && asize > 0 && asize <= LJ_MAX_COLOSIZE) {
105 Node *nilnode;
106 lua_assert((sizeof(GCtab) & 7) == 0);
107 t = (GCtab *)lj_mem_newgco(L, sizetabcolo(asize));
108 t->gct = ~LJ_TTAB;
109 t->nomm = (uint8_t)~0;
110 t->colo = (int8_t)asize;
111 setmref(t->array, (TValue *)((char *)t + sizeof(GCtab)));
112 setgcrefnull(t->metatable);
113 t->asize = asize;
114 t->hmask = 0;
115 nilnode = &G(L)->nilnode;
116 setmref(t->node, nilnode);
117 #if LJ_GC64
118 setmref(t->freetop, nilnode);
119 #endif
120 } else { /* Otherwise separately allocate the array part. */
121 Node *nilnode;
122 t = lj_mem_newobj(L, GCtab);
123 t->gct = ~LJ_TTAB;
124 t->nomm = (uint8_t)~0;
125 t->colo = 0;
126 setmref(t->array, NULL);
127 setgcrefnull(t->metatable);
128 t->asize = 0; /* In case the array allocation fails. */
129 t->hmask = 0;
130 nilnode = &G(L)->nilnode;
131 setmref(t->node, nilnode);
132 #if LJ_GC64
133 setmref(t->freetop, nilnode);
134 #endif
135 if (asize > 0) {
136 if (asize > LJ_MAX_ASIZE)
137 lj_err_msg(L, LJ_ERR_TABOV);
138 setmref(t->array, lj_mem_newvec(L, asize, TValue));
139 t->asize = asize;
140 }
141 }
142 if (hbits)
143 newhpart(L, t, hbits);
144 return t;
145 }
146
147 /* Create a new table.
148 **
149 ** IMPORTANT NOTE: The API differs from lua_createtable()!
150 **
151 ** The array size is non-inclusive. E.g. asize=128 creates array slots
152 ** for 0..127, but not for 128. If you need slots 1..128, pass asize=129
153 ** (slot 0 is wasted in this case).
154 **
155 ** The hash size is given in hash bits. hbits=0 means no hash part.
156 ** hbits=1 creates 2 hash slots, hbits=2 creates 4 hash slots and so on.
157 */
lj_tab_new(lua_State * L,uint32_t asize,uint32_t hbits)158 GCtab *lj_tab_new(lua_State *L, uint32_t asize, uint32_t hbits)
159 {
160 GCtab *t = newtab(L, asize, hbits);
161 clearapart(t);
162 if (t->hmask > 0) clearhpart(t);
163 return t;
164 }
165
166 /* The API of this function conforms to lua_createtable(). */
lj_tab_new_ah(lua_State * L,int32_t a,int32_t h)167 GCtab *lj_tab_new_ah(lua_State *L, int32_t a, int32_t h)
168 {
169 return lj_tab_new(L, (uint32_t)(a > 0 ? a+1 : 0), hsize2hbits(h));
170 }
171
172 #if LJ_HASJIT
lj_tab_new1(lua_State * L,uint32_t ahsize)173 GCtab * LJ_FASTCALL lj_tab_new1(lua_State *L, uint32_t ahsize)
174 {
175 GCtab *t = newtab(L, ahsize & 0xffffff, ahsize >> 24);
176 clearapart(t);
177 if (t->hmask > 0) clearhpart(t);
178 return t;
179 }
180 #endif
181
182 /* Duplicate a table. */
lj_tab_dup(lua_State * L,const GCtab * kt)183 GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
184 {
185 GCtab *t;
186 uint32_t asize, hmask;
187 t = newtab(L, kt->asize, kt->hmask > 0 ? lj_fls(kt->hmask)+1 : 0);
188 lua_assert(kt->asize == t->asize && kt->hmask == t->hmask);
189 t->nomm = 0; /* Keys with metamethod names may be present. */
190 asize = kt->asize;
191 if (asize > 0) {
192 TValue *array = tvref(t->array);
193 TValue *karray = tvref(kt->array);
194 if (asize < 64) { /* An inlined loop beats memcpy for < 512 bytes. */
195 uint32_t i;
196 for (i = 0; i < asize; i++)
197 copyTV(L, &array[i], &karray[i]);
198 } else {
199 memcpy(array, karray, asize*sizeof(TValue));
200 }
201 }
202 hmask = kt->hmask;
203 if (hmask > 0) {
204 uint32_t i;
205 Node *node = noderef(t->node);
206 Node *knode = noderef(kt->node);
207 ptrdiff_t d = (char *)node - (char *)knode;
208 setfreetop(t, node, (Node *)((char *)getfreetop(kt, knode) + d));
209 for (i = 0; i <= hmask; i++) {
210 Node *kn = &knode[i];
211 Node *n = &node[i];
212 Node *next = nextnode(kn);
213 /* Don't use copyTV here, since it asserts on a copy of a dead key. */
214 n->val = kn->val; n->key = kn->key;
215 setmref(n->next, next == NULL? next : (Node *)((char *)next + d));
216 }
217 }
218 return t;
219 }
220
221 /* Clear a table. */
lj_tab_clear(GCtab * t)222 void LJ_FASTCALL lj_tab_clear(GCtab *t)
223 {
224 clearapart(t);
225 if (t->hmask > 0) {
226 Node *node = noderef(t->node);
227 setfreetop(t, node, &node[t->hmask+1]);
228 clearhpart(t);
229 }
230 }
231
232 /* Free a table. */
lj_tab_free(global_State * g,GCtab * t)233 void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t)
234 {
235 if (t->hmask > 0)
236 lj_mem_freevec(g, noderef(t->node), t->hmask+1, Node);
237 if (t->asize > 0 && LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
238 lj_mem_freevec(g, tvref(t->array), t->asize, TValue);
239 if (LJ_MAX_COLOSIZE != 0 && t->colo)
240 lj_mem_free(g, t, sizetabcolo((uint32_t)t->colo & 0x7f));
241 else
242 lj_mem_freet(g, t);
243 }
244
245 /* -- Table resizing ------------------------------------------------------ */
246
247 /* Resize a table to fit the new array/hash part sizes. */
lj_tab_resize(lua_State * L,GCtab * t,uint32_t asize,uint32_t hbits)248 void lj_tab_resize(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
249 {
250 Node *oldnode = noderef(t->node);
251 uint32_t oldasize = t->asize;
252 uint32_t oldhmask = t->hmask;
253 if (asize > oldasize) { /* Array part grows? */
254 TValue *array;
255 uint32_t i;
256 if (asize > LJ_MAX_ASIZE)
257 lj_err_msg(L, LJ_ERR_TABOV);
258 if (LJ_MAX_COLOSIZE != 0 && t->colo > 0) {
259 /* A colocated array must be separated and copied. */
260 TValue *oarray = tvref(t->array);
261 array = lj_mem_newvec(L, asize, TValue);
262 t->colo = (int8_t)(t->colo | 0x80); /* Mark as separated (colo < 0). */
263 for (i = 0; i < oldasize; i++)
264 copyTV(L, &array[i], &oarray[i]);
265 } else {
266 array = (TValue *)lj_mem_realloc(L, tvref(t->array),
267 oldasize*sizeof(TValue), asize*sizeof(TValue));
268 }
269 setmref(t->array, array);
270 t->asize = asize;
271 for (i = oldasize; i < asize; i++) /* Clear newly allocated slots. */
272 setnilV(&array[i]);
273 }
274 /* Create new (empty) hash part. */
275 if (hbits) {
276 newhpart(L, t, hbits);
277 clearhpart(t);
278 } else {
279 global_State *g = G(L);
280 setmref(t->node, &g->nilnode);
281 #if LJ_GC64
282 setmref(t->freetop, &g->nilnode);
283 #endif
284 t->hmask = 0;
285 }
286 if (asize < oldasize) { /* Array part shrinks? */
287 TValue *array = tvref(t->array);
288 uint32_t i;
289 t->asize = asize; /* Note: This 'shrinks' even colocated arrays. */
290 for (i = asize; i < oldasize; i++) /* Reinsert old array values. */
291 if (!tvisnil(&array[i]))
292 copyTV(L, lj_tab_setinth(L, t, (int32_t)i), &array[i]);
293 /* Physically shrink only separated arrays. */
294 if (LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
295 setmref(t->array, lj_mem_realloc(L, array,
296 oldasize*sizeof(TValue), asize*sizeof(TValue)));
297 }
298 if (oldhmask > 0) { /* Reinsert pairs from old hash part. */
299 global_State *g;
300 uint32_t i;
301 for (i = 0; i <= oldhmask; i++) {
302 Node *n = &oldnode[i];
303 if (!tvisnil(&n->val))
304 copyTV(L, lj_tab_set(L, t, &n->key), &n->val);
305 }
306 g = G(L);
307 lj_mem_freevec(g, oldnode, oldhmask+1, Node);
308 }
309 }
310
countint(cTValue * key,uint32_t * bins)311 static uint32_t countint(cTValue *key, uint32_t *bins)
312 {
313 lua_assert(!tvisint(key));
314 if (tvisnum(key)) {
315 lua_Number nk = numV(key);
316 int32_t k = lj_num2int(nk);
317 if ((uint32_t)k < LJ_MAX_ASIZE && nk == (lua_Number)k) {
318 bins[(k > 2 ? lj_fls((uint32_t)(k-1)) : 0)]++;
319 return 1;
320 }
321 }
322 return 0;
323 }
324
countarray(const GCtab * t,uint32_t * bins)325 static uint32_t countarray(const GCtab *t, uint32_t *bins)
326 {
327 uint32_t na, b, i;
328 if (t->asize == 0) return 0;
329 for (na = i = b = 0; b < LJ_MAX_ABITS; b++) {
330 uint32_t n, top = 2u << b;
331 TValue *array;
332 if (top >= t->asize) {
333 top = t->asize-1;
334 if (i > top)
335 break;
336 }
337 array = tvref(t->array);
338 for (n = 0; i <= top; i++)
339 if (!tvisnil(&array[i]))
340 n++;
341 bins[b] += n;
342 na += n;
343 }
344 return na;
345 }
346
counthash(const GCtab * t,uint32_t * bins,uint32_t * narray)347 static uint32_t counthash(const GCtab *t, uint32_t *bins, uint32_t *narray)
348 {
349 uint32_t total, na, i, hmask = t->hmask;
350 Node *node = noderef(t->node);
351 for (total = na = 0, i = 0; i <= hmask; i++) {
352 Node *n = &node[i];
353 if (!tvisnil(&n->val)) {
354 na += countint(&n->key, bins);
355 total++;
356 }
357 }
358 *narray += na;
359 return total;
360 }
361
bestasize(uint32_t bins[],uint32_t * narray)362 static uint32_t bestasize(uint32_t bins[], uint32_t *narray)
363 {
364 uint32_t b, sum, na = 0, sz = 0, nn = *narray;
365 for (b = 0, sum = 0; 2*nn > (1u<<b) && sum != nn; b++)
366 if (bins[b] > 0 && 2*(sum += bins[b]) > (1u<<b)) {
367 sz = (2u<<b)+1;
368 na = sum;
369 }
370 *narray = sz;
371 return na;
372 }
373
rehashtab(lua_State * L,GCtab * t,cTValue * ek)374 static void rehashtab(lua_State *L, GCtab *t, cTValue *ek)
375 {
376 uint32_t bins[LJ_MAX_ABITS];
377 uint32_t total, asize, na, i;
378 for (i = 0; i < LJ_MAX_ABITS; i++) bins[i] = 0;
379 asize = countarray(t, bins);
380 total = 1 + asize;
381 total += counthash(t, bins, &asize);
382 asize += countint(ek, bins);
383 na = bestasize(bins, &asize);
384 total -= na;
385 lj_tab_resize(L, t, asize, hsize2hbits(total));
386 }
387
388 #if LJ_HASFFI
lj_tab_rehash(lua_State * L,GCtab * t)389 void lj_tab_rehash(lua_State *L, GCtab *t)
390 {
391 rehashtab(L, t, niltv(L));
392 }
393 #endif
394
lj_tab_reasize(lua_State * L,GCtab * t,uint32_t nasize)395 void lj_tab_reasize(lua_State *L, GCtab *t, uint32_t nasize)
396 {
397 lj_tab_resize(L, t, nasize+1, t->hmask > 0 ? lj_fls(t->hmask)+1 : 0);
398 }
399
400 /* -- Table getters ------------------------------------------------------- */
401
lj_tab_getinth(GCtab * t,int32_t key)402 cTValue * LJ_FASTCALL lj_tab_getinth(GCtab *t, int32_t key)
403 {
404 TValue k;
405 Node *n;
406 k.n = (lua_Number)key;
407 n = hashnum(t, &k);
408 do {
409 if (tvisnum(&n->key) && n->key.n == k.n)
410 return &n->val;
411 } while ((n = nextnode(n)));
412 return NULL;
413 }
414
lj_tab_getstr(GCtab * t,GCstr * key)415 cTValue *lj_tab_getstr(GCtab *t, GCstr *key)
416 {
417 Node *n = hashstr(t, key);
418 do {
419 if (tvisstr(&n->key) && strV(&n->key) == key)
420 return &n->val;
421 } while ((n = nextnode(n)));
422 return NULL;
423 }
424
lj_tab_get(lua_State * L,GCtab * t,cTValue * key)425 cTValue *lj_tab_get(lua_State *L, GCtab *t, cTValue *key)
426 {
427 if (tvisstr(key)) {
428 cTValue *tv = lj_tab_getstr(t, strV(key));
429 if (tv)
430 return tv;
431 } else if (tvisint(key)) {
432 cTValue *tv = lj_tab_getint(t, intV(key));
433 if (tv)
434 return tv;
435 } else if (tvisnum(key)) {
436 lua_Number nk = numV(key);
437 int32_t k = lj_num2int(nk);
438 if (nk == (lua_Number)k) {
439 cTValue *tv = lj_tab_getint(t, k);
440 if (tv)
441 return tv;
442 } else {
443 goto genlookup; /* Else use the generic lookup. */
444 }
445 } else if (!tvisnil(key)) {
446 Node *n;
447 genlookup:
448 n = hashkey(t, key);
449 do {
450 if (lj_obj_equal(&n->key, key))
451 return &n->val;
452 } while ((n = nextnode(n)));
453 }
454 return niltv(L);
455 }
456
457 /* -- Table setters ------------------------------------------------------- */
458
459 /* Insert new key. Use Brent's variation to optimize the chain length. */
lj_tab_newkey(lua_State * L,GCtab * t,cTValue * key)460 TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
461 {
462 Node *n = hashkey(t, key);
463 if (!tvisnil(&n->val) || t->hmask == 0) {
464 Node *nodebase = noderef(t->node);
465 Node *collide, *freenode = getfreetop(t, nodebase);
466 lua_assert(freenode >= nodebase && freenode <= nodebase+t->hmask+1);
467 do {
468 if (freenode == nodebase) { /* No free node found? */
469 rehashtab(L, t, key); /* Rehash table. */
470 return lj_tab_set(L, t, key); /* Retry key insertion. */
471 }
472 } while (!tvisnil(&(--freenode)->key));
473 setfreetop(t, nodebase, freenode);
474 lua_assert(freenode != &G(L)->nilnode);
475 collide = hashkey(t, &n->key);
476 if (collide != n) { /* Colliding node not the main node? */
477 while (noderef(collide->next) != n) /* Find predecessor. */
478 collide = nextnode(collide);
479 setmref(collide->next, freenode); /* Relink chain. */
480 /* Copy colliding node into free node and free main node. */
481 freenode->val = n->val;
482 freenode->key = n->key;
483 freenode->next = n->next;
484 setmref(n->next, NULL);
485 setnilV(&n->val);
486 /* Rechain pseudo-resurrected string keys with colliding hashes. */
487 while (nextnode(freenode)) {
488 Node *nn = nextnode(freenode);
489 if (tvisstr(&nn->key) && !tvisnil(&nn->val) &&
490 hashstr(t, strV(&nn->key)) == n) {
491 freenode->next = nn->next;
492 nn->next = n->next;
493 setmref(n->next, nn);
494 } else {
495 freenode = nn;
496 }
497 }
498 } else { /* Otherwise use free node. */
499 setmrefr(freenode->next, n->next); /* Insert into chain. */
500 setmref(n->next, freenode);
501 n = freenode;
502 }
503 }
504 n->key.u64 = key->u64;
505 if (LJ_UNLIKELY(tvismzero(&n->key)))
506 n->key.u64 = 0;
507 lj_gc_anybarriert(L, t);
508 lua_assert(tvisnil(&n->val));
509 return &n->val;
510 }
511
lj_tab_setinth(lua_State * L,GCtab * t,int32_t key)512 TValue *lj_tab_setinth(lua_State *L, GCtab *t, int32_t key)
513 {
514 TValue k;
515 Node *n;
516 k.n = (lua_Number)key;
517 n = hashnum(t, &k);
518 do {
519 if (tvisnum(&n->key) && n->key.n == k.n)
520 return &n->val;
521 } while ((n = nextnode(n)));
522 return lj_tab_newkey(L, t, &k);
523 }
524
lj_tab_setstr(lua_State * L,GCtab * t,GCstr * key)525 TValue *lj_tab_setstr(lua_State *L, GCtab *t, GCstr *key)
526 {
527 TValue k;
528 Node *n = hashstr(t, key);
529 do {
530 if (tvisstr(&n->key) && strV(&n->key) == key)
531 return &n->val;
532 } while ((n = nextnode(n)));
533 setstrV(L, &k, key);
534 return lj_tab_newkey(L, t, &k);
535 }
536
lj_tab_set(lua_State * L,GCtab * t,cTValue * key)537 TValue *lj_tab_set(lua_State *L, GCtab *t, cTValue *key)
538 {
539 Node *n;
540 t->nomm = 0; /* Invalidate negative metamethod cache. */
541 if (tvisstr(key)) {
542 return lj_tab_setstr(L, t, strV(key));
543 } else if (tvisint(key)) {
544 return lj_tab_setint(L, t, intV(key));
545 } else if (tvisnum(key)) {
546 lua_Number nk = numV(key);
547 int32_t k = lj_num2int(nk);
548 if (nk == (lua_Number)k)
549 return lj_tab_setint(L, t, k);
550 if (tvisnan(key))
551 lj_err_msg(L, LJ_ERR_NANIDX);
552 /* Else use the generic lookup. */
553 } else if (tvisnil(key)) {
554 lj_err_msg(L, LJ_ERR_NILIDX);
555 }
556 n = hashkey(t, key);
557 do {
558 if (lj_obj_equal(&n->key, key))
559 return &n->val;
560 } while ((n = nextnode(n)));
561 return lj_tab_newkey(L, t, key);
562 }
563
564 /* -- Table traversal ----------------------------------------------------- */
565
566 /* Get the traversal index of a key. */
keyindex(lua_State * L,GCtab * t,cTValue * key)567 static uint32_t keyindex(lua_State *L, GCtab *t, cTValue *key)
568 {
569 TValue tmp;
570 if (tvisint(key)) {
571 int32_t k = intV(key);
572 if ((uint32_t)k < t->asize)
573 return (uint32_t)k; /* Array key indexes: [0..t->asize-1] */
574 setnumV(&tmp, (lua_Number)k);
575 key = &tmp;
576 } else if (tvisnum(key)) {
577 lua_Number nk = numV(key);
578 int32_t k = lj_num2int(nk);
579 if ((uint32_t)k < t->asize && nk == (lua_Number)k)
580 return (uint32_t)k; /* Array key indexes: [0..t->asize-1] */
581 }
582 if (!tvisnil(key)) {
583 Node *n = hashkey(t, key);
584 do {
585 if (lj_obj_equal(&n->key, key))
586 return t->asize + (uint32_t)(n - noderef(t->node));
587 /* Hash key indexes: [t->asize..t->asize+t->nmask] */
588 } while ((n = nextnode(n)));
589 if (key->u32.hi == 0xfffe7fff) /* ITERN was despecialized while running. */
590 return key->u32.lo - 1;
591 lj_err_msg(L, LJ_ERR_NEXTIDX);
592 return 0; /* unreachable */
593 }
594 return ~0u; /* A nil key starts the traversal. */
595 }
596
597 /* Advance to the next step in a table traversal. */
lj_tab_next(lua_State * L,GCtab * t,TValue * key)598 int lj_tab_next(lua_State *L, GCtab *t, TValue *key)
599 {
600 uint32_t i = keyindex(L, t, key); /* Find predecessor key index. */
601 for (i++; i < t->asize; i++) /* First traverse the array keys. */
602 if (!tvisnil(arrayslot(t, i))) {
603 setintV(key, i);
604 copyTV(L, key+1, arrayslot(t, i));
605 return 1;
606 }
607 for (i -= t->asize; i <= t->hmask; i++) { /* Then traverse the hash keys. */
608 Node *n = &noderef(t->node)[i];
609 if (!tvisnil(&n->val)) {
610 copyTV(L, key, &n->key);
611 copyTV(L, key+1, &n->val);
612 return 1;
613 }
614 }
615 return 0; /* End of traversal. */
616 }
617
618 /* -- Table length calculation -------------------------------------------- */
619
unbound_search(GCtab * t,MSize j)620 static MSize unbound_search(GCtab *t, MSize j)
621 {
622 cTValue *tv;
623 MSize i = j; /* i is zero or a present index */
624 j++;
625 /* find `i' and `j' such that i is present and j is not */
626 while ((tv = lj_tab_getint(t, (int32_t)j)) && !tvisnil(tv)) {
627 i = j;
628 j *= 2;
629 if (j > (MSize)(INT_MAX-2)) { /* overflow? */
630 /* table was built with bad purposes: resort to linear search */
631 i = 1;
632 while ((tv = lj_tab_getint(t, (int32_t)i)) && !tvisnil(tv)) i++;
633 return i - 1;
634 }
635 }
636 /* now do a binary search between them */
637 while (j - i > 1) {
638 MSize m = (i+j)/2;
639 cTValue *tvb = lj_tab_getint(t, (int32_t)m);
640 if (tvb && !tvisnil(tvb)) i = m; else j = m;
641 }
642 return i;
643 }
644
645 /*
646 ** Try to find a boundary in table `t'. A `boundary' is an integer index
647 ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
648 */
lj_tab_len(GCtab * t)649 MSize LJ_FASTCALL lj_tab_len(GCtab *t)
650 {
651 MSize j = (MSize)t->asize;
652 if (j > 1 && tvisnil(arrayslot(t, j-1))) {
653 MSize i = 1;
654 while (j - i > 1) {
655 MSize m = (i+j)/2;
656 if (tvisnil(arrayslot(t, m-1))) j = m; else i = m;
657 }
658 return i-1;
659 }
660 if (j) j--;
661 if (t->hmask <= 0)
662 return j;
663 return unbound_search(t, j);
664 }
665
666