aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/luajit-2.0/src/lj_tab.c
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/luajit-2.0/src/lj_tab.c')
-rw-r--r--libraries/luajit-2.0/src/lj_tab.c622
1 files changed, 0 insertions, 622 deletions
diff --git a/libraries/luajit-2.0/src/lj_tab.c b/libraries/luajit-2.0/src/lj_tab.c
deleted file mode 100644
index cd200f0..0000000
--- a/libraries/luajit-2.0/src/lj_tab.c
+++ /dev/null
@@ -1,622 +0,0 @@
1/*
2** Table handling.
3** Copyright (C) 2005-2011 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. */
20static 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#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)
33
34/* Hash an arbitrary key and return its anchor position in the hash table. */
35static Node *hashkey(const GCtab *t, cTValue *key)
36{
37 lua_assert(!tvisint(key));
38 if (tvisstr(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));
44 else
45 return hashgcref(t, key->gcr);
46 /* Only hash 32 bits of lightuserdata on a 64 bit CPU. Good enough? */
47}
48
49/* -- Table creation and destruction -------------------------------------- */
50
51/* Create new hash part for table. */
52static LJ_AINLINE void newhpart(lua_State *L, GCtab *t, uint32_t hbits)
53{
54 uint32_t hsize;
55 Node *node;
56 lua_assert(hbits != 0);
57 if (hbits > LJ_MAX_HBITS)
58 lj_err_msg(L, LJ_ERR_TABOV);
59 hsize = 1u << hbits;
60 node = lj_mem_newvec(L, hsize, Node);
61 setmref(node->freetop, &node[hsize]);
62 setmref(t->node, node);
63 t->hmask = hsize-1;
64}
65
66/*
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.
70*/
71
72/* Clear hash part of table. */
73static LJ_AINLINE void clearhpart(GCtab *t)
74{
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++) {
79 Node *n = &node[i];
80 setmref(n->next, NULL);
81 setnilV(&n->key);
82 setnilV(&n->val);
83 }
84}
85
86/* Clear array part of table. */
87static LJ_AINLINE void clearapart(GCtab *t)
88{
89 uint32_t i, asize = t->asize;
90 TValue *array = tvref(t->array);
91 for (i = 0; i < asize; i++)
92 setnilV(&array[i]);
93}
94
95/* Create a new table. Note: the slots are not initialized (yet). */
96static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
97{
98 GCtab *t;
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));
103 t->gct = ~LJ_TTAB;
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);
108 t->asize = asize;
109 t->hmask = 0;
110 setmref(t->node, &G(L)->nilnode);
111 } else { /* Otherwise separately allocate the array part. */
112 t = lj_mem_newobj(L, GCtab);
113 t->gct = ~LJ_TTAB;
114 t->nomm = (uint8_t)~0;
115 t->colo = 0;
116 setmref(t->array, NULL);
117 setgcrefnull(t->metatable);
118 t->asize = 0; /* In case the array allocation fails. */
119 t->hmask = 0;
120 setmref(t->node, &G(L)->nilnode);
121 if (asize > 0) {
122 if (asize > LJ_MAX_ASIZE)
123 lj_err_msg(L, LJ_ERR_TABOV);
124 setmref(t->array, lj_mem_newvec(L, asize, TValue));
125 t->asize = asize;
126 }
127 }
128 if (hbits)
129 newhpart(L, t, hbits);
130 return t;
131}
132
133/* Create a new table.
134**
135** IMPORTANT NOTE: The API differs from lua_createtable()!
136**
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).
140**
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.
143*/
144GCtab *lj_tab_new(lua_State *L, uint32_t asize, uint32_t hbits)
145{
146 GCtab *t = newtab(L, asize, hbits);
147 clearapart(t);
148 if (t->hmask > 0) clearhpart(t);
149 return t;
150}
151
152#if LJ_HASJIT
153GCtab * LJ_FASTCALL lj_tab_new1(lua_State *L, uint32_t ahsize)
154{
155 GCtab *t = newtab(L, ahsize & 0xffffff, ahsize >> 24);
156 clearapart(t);
157 if (t->hmask > 0) clearhpart(t);
158 return t;
159}
160#endif
161
162/* Duplicate a table. */
163GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
164{
165 GCtab *t;
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. */
170 asize = kt->asize;
171 if (asize > 0) {
172 TValue *array = tvref(t->array);
173 TValue *karray = tvref(kt->array);
174 if (asize < 64) { /* An inlined loop beats memcpy for < 512 bytes. */
175 uint32_t i;
176 for (i = 0; i < asize; i++)
177 copyTV(L, &array[i], &karray[i]);
178 } else {
179 memcpy(array, karray, asize*sizeof(TValue));
180 }
181 }
182 hmask = kt->hmask;
183 if (hmask > 0) {
184 uint32_t i;
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];
191 Node *n = &node[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));
196 }
197 }
198 return t;
199}
200
201/* Free a table. */
202void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t)
203{
204 if (t->hmask > 0)
205 lj_mem_freevec(g, noderef(t->node), t->hmask+1, Node);
206 if (t->asize > 0 && LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
207 lj_mem_freevec(g, tvref(t->array), t->asize, TValue);
208 if (LJ_MAX_COLOSIZE != 0 && t->colo)
209 lj_mem_free(g, t, sizetabcolo((uint32_t)t->colo & 0x7f));
210 else
211 lj_mem_freet(g, t);
212}
213
214/* -- Table resizing ------------------------------------------------------ */
215
216/* Resize a table to fit the new array/hash part sizes. */
217static void resizetab(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
218{
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? */
223 TValue *array;
224 uint32_t i;
225 if (asize > LJ_MAX_ASIZE)
226 lj_err_msg(L, LJ_ERR_TABOV);
227 if (LJ_MAX_COLOSIZE != 0 && 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]);
234 } else {
235 array = (TValue *)lj_mem_realloc(L, tvref(t->array),
236 oldasize*sizeof(TValue), asize*sizeof(TValue));
237 }
238 setmref(t->array, array);
239 t->asize = asize;
240 for (i = oldasize; i < asize; i++) /* Clear newly allocated slots. */
241 setnilV(&array[i]);
242 }
243 /* Create new (empty) hash part. */
244 if (hbits) {
245 newhpart(L, t, hbits);
246 clearhpart(t);
247 } else {
248 global_State *g = G(L);
249 setmref(t->node, &g->nilnode);
250 t->hmask = 0;
251 }
252 if (asize < oldasize) { /* Array part shrinks? */
253 TValue *array = tvref(t->array);
254 uint32_t i;
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 != 0 && t->colo <= 0)
261 setmref(t->array, lj_mem_realloc(L, array,
262 oldasize*sizeof(TValue), asize*sizeof(TValue)));
263 }
264 if (oldhmask > 0) { /* Reinsert pairs from old hash part. */
265 global_State *g;
266 uint32_t i;
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);
271 }
272 g = G(L);
273 lj_mem_freevec(g, oldnode, oldhmask+1, Node);
274 }
275}
276
277static uint32_t countint(cTValue *key, uint32_t *bins)
278{
279 lua_assert(!tvisint(key));
280 if (tvisnum(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)]++;
285 return 1;
286 }
287 }
288 return 0;
289}
290
291static uint32_t countarray(const GCtab *t, uint32_t *bins)
292{
293 uint32_t na, b, i;
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;
297 TValue *array;
298 if (top >= t->asize) {
299 top = t->asize-1;
300 if (i > top)
301 break;
302 }
303 array = tvref(t->array);
304 for (n = 0; i <= top; i++)
305 if (!tvisnil(&array[i]))
306 n++;
307 bins[b] += n;
308 na += n;
309 }
310 return na;
311}
312
313static uint32_t counthash(const GCtab *t, uint32_t *bins, uint32_t *narray)
314{
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++) {
318 Node *n = &node[i];
319 if (!tvisnil(&n->val)) {
320 na += countint(&n->key, bins);
321 total++;
322 }
323 }
324 *narray += na;
325 return total;
326}
327
328static uint32_t bestasize(uint32_t bins[], uint32_t *narray)
329{
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)) {
333 sz = (2u<<b)+1;
334 na = sum;
335 }
336 *narray = sz;
337 return na;
338}
339
340static void rehashtab(lua_State *L, GCtab *t, cTValue *ek)
341{
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);
346 total = 1 + asize;
347 total += counthash(t, bins, &asize);
348 asize += countint(ek, bins);
349 na = bestasize(bins, &asize);
350 total -= na;
351 resizetab(L, t, asize, hsize2hbits(total));
352}
353
354void lj_tab_reasize(lua_State *L, GCtab *t, uint32_t nasize)
355{
356 resizetab(L, t, nasize+1, t->hmask > 0 ? lj_fls(t->hmask)+1 : 0);
357}
358
359/* -- Table getters ------------------------------------------------------- */
360
361cTValue * LJ_FASTCALL lj_tab_getinth(GCtab *t, int32_t key)
362{
363 TValue k;
364 Node *n;
365 k.n = (lua_Number)key;
366 n = hashnum(t, &k);
367 do {
368 if (tvisnum(&n->key) && n->key.n == k.n)
369 return &n->val;
370 } while ((n = nextnode(n)));
371 return NULL;
372}
373
374cTValue *lj_tab_getstr(GCtab *t, GCstr *key)
375{
376 Node *n = hashstr(t, key);
377 do {
378 if (tvisstr(&n->key) && strV(&n->key) == key)
379 return &n->val;
380 } while ((n = nextnode(n)));
381 return NULL;
382}
383
384cTValue *lj_tab_get(lua_State *L, GCtab *t, cTValue *key)
385{
386 if (tvisstr(key)) {
387 cTValue *tv = lj_tab_getstr(t, strV(key));
388 if (tv)
389 return tv;
390 } else if (tvisint(key)) {
391 cTValue *tv = lj_tab_getint(t, intV(key));
392 if (tv)
393 return tv;
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);
399 if (tv)
400 return tv;
401 } else {
402 goto genlookup; /* Else use the generic lookup. */
403 }
404 } else if (!tvisnil(key)) {
405 Node *n;
406 genlookup:
407 n = hashkey(t, key);
408 do {
409 if (lj_obj_equal(&n->key, key))
410 return &n->val;
411 } while ((n = nextnode(n)));
412 }
413 return niltv(L);
414}
415
416/* -- Table setters ------------------------------------------------------- */
417
418/* Insert new key. Use Brent's variation to optimize the chain length. */
419TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
420{
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);
426 do {
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. */
430 }
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);
444 setnilV(&n->val);
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;
451 nn->next = n->next;
452 setmref(n->next, nn);
453 } else {
454 freenode = nn;
455 }
456 }
457 } else { /* Otherwise use free node. */
458 setmrefr(freenode->next, n->next); /* Insert into chain. */
459 setmref(n->next, freenode);
460 n = freenode;
461 }
462 }
463 n->key.u64 = key->u64;
464 if (LJ_UNLIKELY(tvismzero(&n->key)))
465 n->key.u64 = 0;
466 lj_gc_anybarriert(L, t);
467 lua_assert(tvisnil(&n->val));
468 return &n->val;
469}
470
471TValue *lj_tab_setinth(lua_State *L, GCtab *t, int32_t key)
472{
473 TValue k;
474 Node *n;
475 k.n = (lua_Number)key;
476 n = hashnum(t, &k);
477 do {
478 if (tvisnum(&n->key) && n->key.n == k.n)
479 return &n->val;
480 } while ((n = nextnode(n)));
481 return lj_tab_newkey(L, t, &k);
482}
483
484TValue *lj_tab_setstr(lua_State *L, GCtab *t, GCstr *key)
485{
486 TValue k;
487 Node *n = hashstr(t, key);
488 do {
489 if (tvisstr(&n->key) && strV(&n->key) == key)
490 return &n->val;
491 } while ((n = nextnode(n)));
492 setstrV(L, &k, key);
493 return lj_tab_newkey(L, t, &k);
494}
495
496TValue *lj_tab_set(lua_State *L, GCtab *t, cTValue *key)
497{
498 Node *n;
499 t->nomm = 0; /* Invalidate negative metamethod cache. */
500 if (tvisstr(key)) {
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);
509 if (tvisnan(key))
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);
514 }
515 n = hashkey(t, key);
516 do {
517 if (lj_obj_equal(&n->key, key))
518 return &n->val;
519 } while ((n = nextnode(n)));
520 return lj_tab_newkey(L, t, key);
521}
522
523/* -- Table traversal ----------------------------------------------------- */
524
525/* Get the traversal index of a key. */
526static uint32_t keyindex(lua_State *L, GCtab *t, cTValue *key)
527{
528 TValue tmp;
529 if (tvisint(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);
534 key = &tmp;
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] */
540 }
541 if (!tvisnil(key)) {
542 Node *n = hashkey(t, key);
543 do {
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 */
550 }
551 return ~0u; /* A nil key starts the traversal. */
552}
553
554/* Advance to the next step in a table traversal. */
555int lj_tab_next(lua_State *L, GCtab *t, TValue *key)
556{
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))) {
560 setintV(key, i);
561 copyTV(L, key+1, arrayslot(t, i));
562 return 1;
563 }
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);
569 return 1;
570 }
571 }
572 return 0; /* End of traversal. */
573}
574
575/* -- Table length calculation -------------------------------------------- */
576
577static MSize unbound_search(GCtab *t, MSize j)
578{
579 cTValue *tv;
580 MSize i = j; /* i is zero or a present index */
581 j++;
582 /* find `i' and `j' such that i is present and j is not */
583 while ((tv = lj_tab_getint(t, (int32_t)j)) && !tvisnil(tv)) {
584 i = j;
585 j *= 2;
586 if (j > (MSize)(INT_MAX-2)) { /* overflow? */
587 /* table was built with bad purposes: resort to linear search */
588 i = 1;
589 while ((tv = lj_tab_getint(t, (int32_t)i)) && !tvisnil(tv)) i++;
590 return i - 1;
591 }
592 }
593 /* now do a binary search between them */
594 while (j - i > 1) {
595 MSize m = (i+j)/2;
596 cTValue *tvb = lj_tab_getint(t, (int32_t)m);
597 if (tvb && !tvisnil(tvb)) i = m; else j = m;
598 }
599 return i;
600}
601
602/*
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).
605*/
606MSize LJ_FASTCALL lj_tab_len(GCtab *t)
607{
608 MSize j = (MSize)t->asize;
609 if (j > 1 && tvisnil(arrayslot(t, j-1))) {
610 MSize i = 1;
611 while (j - i > 1) {
612 MSize m = (i+j)/2;
613 if (tvisnil(arrayslot(t, m-1))) j = m; else i = m;
614 }
615 return i-1;
616 }
617 if (j) j--;
618 if (t->hmask <= 0)
619 return j;
620 return unbound_search(t, j);
621}
622
generated by cgit v1.1 at 2024-07-01 04:25:12 +0000