diff options
Diffstat (limited to 'src/lj_tab.c')
-rw-r--r-- | src/lj_tab.c | 618 |
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. */ | ||
29 | static 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. */ | ||
38 | static 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. */ | ||
54 | static 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. */ | ||
75 | static 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. */ | ||
89 | static 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). */ | ||
98 | static 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 | */ | ||
155 | GCtab *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. */ | ||
164 | GCtab *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. */ | ||
203 | void 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. */ | ||
223 | static 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 | |||
284 | static 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 | |||
297 | static 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 | |||
319 | static 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 | |||
334 | static 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 | |||
346 | static 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 | |||
359 | void 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 | |||
366 | cTValue *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 | |||
379 | cTValue *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 | |||
389 | cTValue *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 | |||
419 | static 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 | */ | ||
439 | TValue *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 | |||
474 | TValue *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 | |||
487 | TValue *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 | |||
499 | TValue *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. */ | ||
527 | static 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. */ | ||
551 | int 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 | |||
573 | static 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 | */ | ||
602 | MSize 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 | |||