diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/luajit-2.0/src/lj_tab.c | 622 |
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. */ | ||
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 | #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. */ | ||
35 | static 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. */ | ||
52 | static 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. */ | ||
73 | static 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. */ | ||
87 | static 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). */ | ||
96 | static 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 | */ | ||
144 | GCtab *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 | ||
153 | GCtab * 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. */ | ||
163 | GCtab * 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. */ | ||
202 | void 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. */ | ||
217 | static 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 | |||
277 | static 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 | |||
291 | static 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 | |||
313 | static 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 | |||
328 | static 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 | |||
340 | static 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 | |||
354 | void 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 | |||
361 | cTValue * 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 | |||
374 | cTValue *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 | |||
384 | cTValue *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. */ | ||
419 | TValue *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 | |||
471 | TValue *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 | |||
484 | TValue *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 | |||
496 | TValue *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. */ | ||
526 | static 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. */ | ||
555 | int 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 | |||
577 | static 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 | */ | ||
606 | MSize 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 | |||