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