Line data Source code
1 : /*
2 : ** $Id: ltable.c,v 2.118.1.4 2018/06/08 16:22:51 roberto Exp $
3 : ** Lua tables (hash)
4 : ** See Copyright Notice in lua.h
5 : */
6 :
7 : #define ltable_c
8 : #define LUA_CORE
9 :
10 : #include "lprefix.h"
11 :
12 :
13 : /*
14 : ** Implementation of tables (aka arrays, objects, or hash tables).
15 : ** Tables keep its elements in two parts: an array part and a hash part.
16 : ** Non-negative integer keys are all candidates to be kept in the array
17 : ** part. The actual size of the array is the largest 'n' such that
18 : ** more than half the slots between 1 and n are in use.
19 : ** Hash uses a mix of chained scatter table with Brent's variation.
20 : ** A main invariant of these tables is that, if an element is not
21 : ** in its main position (i.e. the 'original' position that its hash gives
22 : ** to it), then the colliding element is in its own main position.
23 : ** Hence even when the load factor reaches 100%, performance remains good.
24 : */
25 :
26 : #include <math.h>
27 : #include <limits.h>
28 :
29 : #include "lua.h"
30 :
31 : #include "ldebug.h"
32 : #include "ldo.h"
33 : #include "lgc.h"
34 : #include "lmem.h"
35 : #include "lobject.h"
36 : #include "lstate.h"
37 : #include "lstring.h"
38 : #include "ltable.h"
39 : #include "lvm.h"
40 :
41 :
42 : /*
43 : ** Maximum size of array part (MAXASIZE) is 2^MAXABITS. MAXABITS is
44 : ** the largest integer such that MAXASIZE fits in an unsigned int.
45 : */
46 : #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1)
47 : #define MAXASIZE (1u << MAXABITS)
48 :
49 : /*
50 : ** Maximum size of hash part is 2^MAXHBITS. MAXHBITS is the largest
51 : ** integer such that 2^MAXHBITS fits in a signed int. (Note that the
52 : ** maximum number of elements in a table, 2^MAXABITS + 2^MAXHBITS, still
53 : ** fits comfortably in an unsigned int.)
54 : */
55 : #define MAXHBITS (MAXABITS - 1)
56 :
57 :
58 : #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
59 :
60 : #define hashstr(t,str) hashpow2(t, (str)->hash)
61 : #define hashboolean(t,p) hashpow2(t, p)
62 : #define hashint(t,i) hashpow2(t, i)
63 :
64 :
65 : /*
66 : ** for some types, it is better to avoid modulus by power of 2, as
67 : ** they tend to have many 2 factors.
68 : */
69 : #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
70 :
71 :
72 : #define hashpointer(t,p) hashmod(t, point2uint(p))
73 :
74 :
75 : #define dummynode (&dummynode_)
76 :
77 : static const Node dummynode_ = {
78 : {NILCONSTANT}, /* value */
79 : {{NILCONSTANT, 0}} /* key */
80 : };
81 :
82 :
83 : /*
84 : ** Hash for floating-point numbers.
85 : ** The main computation should be just
86 : ** n = frexp(n, &i); return (n * INT_MAX) + i
87 : ** but there are some numerical subtleties.
88 : ** In a two-complement representation, INT_MAX does not has an exact
89 : ** representation as a float, but INT_MIN does; because the absolute
90 : ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the
91 : ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
92 : ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when
93 : ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
94 : ** INT_MIN.
95 : */
96 : #if !defined(l_hashfloat)
97 541 : static int l_hashfloat (lua_Number n) {
98 : int i;
99 : lua_Integer ni;
100 541 : n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN);
101 541 : if (!lua_numbertointeger(n, &ni)) { /* is 'n' inf/-inf/NaN? */
102 : lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL));
103 1 : return 0;
104 : }
105 : else { /* normal case */
106 540 : unsigned int u = cast(unsigned int, i) + cast(unsigned int, ni);
107 540 : return cast_int(u <= cast(unsigned int, INT_MAX) ? u : ~u);
108 : }
109 : }
110 : #endif
111 :
112 :
113 : /*
114 : ** returns the 'main' position of an element in a table (that is, the index
115 : ** of its hash value)
116 : */
117 130453 : static Node *mainposition (const Table *t, const TValue *key) {
118 130453 : switch (ttype(key)) {
119 24119 : case LUA_TNUMINT:
120 24119 : return hashint(t, ivalue(key));
121 541 : case LUA_TNUMFLT:
122 541 : return hashmod(t, l_hashfloat(fltvalue(key)));
123 93761 : case LUA_TSHRSTR:
124 93761 : return hashstr(t, tsvalue(key));
125 1452 : case LUA_TLNGSTR:
126 1452 : return hashpow2(t, luaS_hashlongstr(tsvalue(key)));
127 727 : case LUA_TBOOLEAN:
128 727 : return hashboolean(t, bvalue(key));
129 9492 : case LUA_TLIGHTUSERDATA:
130 9492 : return hashpointer(t, pvalue(key));
131 5 : case LUA_TLCF:
132 5 : return hashpointer(t, fvalue(key));
133 356 : default:
134 : lua_assert(!ttisdeadkey(key));
135 356 : return hashpointer(t, gcvalue(key));
136 : }
137 : }
138 :
139 :
140 : /*
141 : ** returns the index for 'key' if 'key' is an appropriate key to live in
142 : ** the array part of the table, 0 otherwise.
143 : */
144 61352 : static unsigned int arrayindex (const TValue *key) {
145 61352 : if (ttisinteger(key)) {
146 23822 : lua_Integer k = ivalue(key);
147 23822 : if (0 < k && (lua_Unsigned)k <= MAXASIZE)
148 23813 : return cast(unsigned int, k); /* 'key' is an appropriate array index */
149 : }
150 37539 : return 0; /* 'key' did not match some condition */
151 : }
152 :
153 :
154 : /*
155 : ** returns the index of a 'key' for table traversals. First goes all
156 : ** elements in the array part, then elements in the hash part. The
157 : ** beginning of a traversal is signaled by 0.
158 : */
159 2438 : static unsigned int findindex (lua_State *L, Table *t, StkId key) {
160 : unsigned int i;
161 2438 : if (ttisnil(key)) return 0; /* first iteration */
162 2278 : i = arrayindex(key);
163 2278 : if (i != 0 && i <= t->sizearray) /* is 'key' inside array part? */
164 18 : return i; /* yes; that's the index */
165 : else {
166 : int nx;
167 2260 : Node *n = mainposition(t, key);
168 : for (;;) { /* check whether 'key' is somewhere in the chain */
169 : /* key may be dead already, but it is ok to use it in 'next' */
170 2967 : if (luaV_rawequalobj(gkey(n), key) ||
171 708 : (ttisdeadkey(gkey(n)) && iscollectable(key) &&
172 0 : deadvalue(gkey(n)) == gcvalue(key))) {
173 2259 : i = cast_int(n - gnode(t, 0)); /* key index in hash table */
174 : /* hash elements are numbered after array ones */
175 2259 : return (i + 1) + t->sizearray;
176 : }
177 708 : nx = gnext(n);
178 708 : if (nx == 0)
179 1 : luaG_runerror(L, "invalid key to 'next'"); /* key not found */
180 707 : else n += nx;
181 : }
182 : }
183 : }
184 :
185 :
186 2438 : int luaH_next (lua_State *L, Table *t, StkId key) {
187 2438 : unsigned int i = findindex(L, t, key); /* find original element */
188 2437 : for (; i < t->sizearray; i++) { /* try first array part */
189 17 : if (!ttisnil(&t->array[i])) { /* a non-nil value? */
190 17 : setivalue(key, i + 1);
191 17 : setobj2s(L, key+1, &t->array[i]);
192 17 : return 1;
193 : }
194 : }
195 3643 : for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) { /* hash part */
196 3490 : if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
197 2267 : setobj2s(L, key, gkey(gnode(t, i)));
198 2267 : setobj2s(L, key+1, gval(gnode(t, i)));
199 2267 : return 1;
200 : }
201 : }
202 153 : return 0; /* no more elements */
203 : }
204 :
205 :
206 : /*
207 : ** {=============================================================
208 : ** Rehash
209 : ** ==============================================================
210 : */
211 :
212 : /*
213 : ** Compute the optimal size for the array part of table 't'. 'nums' is a
214 : ** "count array" where 'nums[i]' is the number of integers in the table
215 : ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
216 : ** integer keys in the table and leaves with the number of keys that
217 : ** will go to the array part; return the optimal size.
218 : */
219 27938 : static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {
220 : int i;
221 : unsigned int twotoi; /* 2^i (candidate for optimal size) */
222 27938 : unsigned int a = 0; /* number of elements smaller than 2^i */
223 27938 : unsigned int na = 0; /* number of elements to go to array part */
224 27938 : unsigned int optimal = 0; /* optimal size for array part */
225 : /* loop while keys can fill more than half of total size */
226 27938 : for (i = 0, twotoi = 1;
227 88039 : twotoi > 0 && *pna > twotoi / 2;
228 60101 : i++, twotoi *= 2) {
229 60101 : if (nums[i] > 0) {
230 60065 : a += nums[i];
231 60065 : if (a > twotoi/2) { /* more than half elements present? */
232 60065 : optimal = twotoi; /* optimal size (till now) */
233 60065 : na = a; /* all elements up to 'optimal' will go to array part */
234 : }
235 : }
236 : }
237 : lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
238 27938 : *pna = na;
239 27938 : return optimal;
240 : }
241 :
242 :
243 59074 : static int countint (const TValue *key, unsigned int *nums) {
244 59074 : unsigned int k = arrayindex(key);
245 59074 : if (k != 0) { /* is 'key' an appropriate array index? */
246 23794 : nums[luaO_ceillog2(k)]++; /* count as such */
247 23794 : return 1;
248 : }
249 : else
250 35280 : return 0;
251 : }
252 :
253 :
254 : /*
255 : ** Count keys in array part of table 't': Fill 'nums[i]' with
256 : ** number of keys that will go into corresponding slice and return
257 : ** total number of non-nil keys.
258 : */
259 27938 : static unsigned int numusearray (const Table *t, unsigned int *nums) {
260 : int lg;
261 : unsigned int ttlg; /* 2^lg */
262 27938 : unsigned int ause = 0; /* summation of 'nums' */
263 27938 : unsigned int i = 1; /* count to traverse all array keys */
264 : /* traverse each slice */
265 64251 : for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
266 64251 : unsigned int lc = 0; /* counter */
267 64251 : unsigned int lim = ttlg;
268 64251 : if (lim > t->sizearray) {
269 27942 : lim = t->sizearray; /* adjust upper limit */
270 27942 : if (i > lim)
271 27938 : break; /* no more elements to count */
272 : }
273 : /* count elements in range (2^(lg - 1), 2^lg] */
274 80522 : for (; i <= lim; i++) {
275 44209 : if (!ttisnil(&t->array[i-1]))
276 44185 : lc++;
277 : }
278 36313 : nums[lg] += lc;
279 36313 : ause += lc;
280 : }
281 27938 : return ause;
282 : }
283 :
284 :
285 27938 : static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
286 27938 : int totaluse = 0; /* total number of elements */
287 27938 : int ause = 0; /* elements added to 'nums' (can go to array part) */
288 27938 : int i = sizenode(t);
289 83590 : while (i--) {
290 55652 : Node *n = &t->node[i];
291 55652 : if (!ttisnil(gval(n))) {
292 31136 : ause += countint(gkey(n), nums);
293 31136 : totaluse++;
294 : }
295 : }
296 27938 : *pna += ause;
297 27938 : return totaluse;
298 : }
299 :
300 :
301 24344 : static void setarrayvector (lua_State *L, Table *t, unsigned int size) {
302 : unsigned int i;
303 24344 : luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
304 74461 : for (i=t->sizearray; i<size; i++)
305 50117 : setnilvalue(&t->array[i]);
306 24344 : t->sizearray = size;
307 24344 : }
308 :
309 :
310 38717 : static void setnodevector (lua_State *L, Table *t, unsigned int size) {
311 38717 : if (size == 0) { /* no elements to hash part? */
312 33202 : t->node = cast(Node *, dummynode); /* use common 'dummynode' */
313 33202 : t->lsizenode = 0;
314 33202 : t->lastfree = NULL; /* signal that it is using dummy node */
315 : }
316 : else {
317 : int i;
318 5515 : int lsize = luaO_ceillog2(size);
319 5515 : if (lsize > MAXHBITS)
320 0 : luaG_runerror(L, "table overflow");
321 5515 : size = twoto(lsize);
322 5515 : t->node = luaM_newvector(L, size, Node);
323 85745 : for (i = 0; i < (int)size; i++) {
324 80230 : Node *n = gnode(t, i);
325 80230 : gnext(n) = 0;
326 80230 : setnilvalue(wgkey(n));
327 80230 : setnilvalue(gval(n));
328 : }
329 5515 : t->lsizenode = cast_byte(lsize);
330 5515 : t->lastfree = gnode(t, size); /* all positions are free */
331 : }
332 38717 : }
333 :
334 :
335 : typedef struct {
336 : Table *t;
337 : unsigned int nhsize;
338 : } AuxsetnodeT;
339 :
340 :
341 29823 : static void auxsetnode (lua_State *L, void *ud) {
342 29823 : AuxsetnodeT *asn = cast(AuxsetnodeT *, ud);
343 29823 : setnodevector(L, asn->t, asn->nhsize);
344 29823 : }
345 :
346 :
347 29823 : void luaH_resize (lua_State *L, Table *t, unsigned int nasize,
348 : unsigned int nhsize) {
349 : unsigned int i;
350 : int j;
351 : AuxsetnodeT asn;
352 29823 : unsigned int oldasize = t->sizearray;
353 29823 : int oldhsize = allocsizenode(t);
354 29823 : Node *nold = t->node; /* save old hash ... */
355 29823 : if (nasize > oldasize) /* array part must grow? */
356 24344 : setarrayvector(L, t, nasize);
357 : /* create new hash part with appropriate size */
358 29823 : asn.t = t; asn.nhsize = nhsize;
359 29823 : if (luaD_rawrunprotected(L, auxsetnode, &asn) != LUA_OK) { /* mem. error? */
360 0 : setarrayvector(L, t, oldasize); /* array back to its original size */
361 0 : luaD_throw(L, LUA_ERRMEM); /* rethrow memory error */
362 : }
363 29823 : if (nasize < oldasize) { /* array part must shrink? */
364 0 : t->sizearray = nasize;
365 : /* re-insert elements from vanishing slice */
366 0 : for (i=nasize; i<oldasize; i++) {
367 0 : if (!ttisnil(&t->array[i]))
368 0 : luaH_setint(L, t, i + 1, &t->array[i]);
369 : }
370 : /* shrink array */
371 0 : luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
372 : }
373 : /* re-insert elements from hash part */
374 60959 : for (j = oldhsize - 1; j >= 0; j--) {
375 31136 : Node *old = nold + j;
376 31136 : if (!ttisnil(gval(old))) {
377 : /* doesn't need barrier/invalidate cache, as entry was
378 : already present in the table */
379 31136 : setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));
380 : }
381 : }
382 29823 : if (oldhsize > 0) /* not the dummy node? */
383 3422 : luaM_freearray(L, nold, cast(size_t, oldhsize)); /* free old hash */
384 29823 : }
385 :
386 :
387 221 : void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) {
388 221 : int nsize = allocsizenode(t);
389 221 : luaH_resize(L, t, nasize, nsize);
390 221 : }
391 :
392 : /*
393 : ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
394 : */
395 27938 : static void rehash (lua_State *L, Table *t, const TValue *ek) {
396 : unsigned int asize; /* optimal size for array part */
397 : unsigned int na; /* number of keys in the array part */
398 : unsigned int nums[MAXABITS + 1];
399 : int i;
400 : int totaluse;
401 921954 : for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */
402 27938 : na = numusearray(t, nums); /* count keys in array part */
403 27938 : totaluse = na; /* all those keys are integer keys */
404 27938 : totaluse += numusehash(t, nums, &na); /* count keys in hash part */
405 : /* count extra key */
406 27938 : na += countint(ek, nums);
407 27938 : totaluse++;
408 : /* compute new size for array part */
409 27938 : asize = computesizes(nums, &na);
410 : /* resize the table to new computed sizes */
411 27938 : luaH_resize(L, t, asize, totaluse - na);
412 27938 : }
413 :
414 :
415 :
416 : /*
417 : ** }=============================================================
418 : */
419 :
420 :
421 8894 : Table *luaH_new (lua_State *L) {
422 8894 : GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
423 8894 : Table *t = gco2t(o);
424 8894 : t->metatable = NULL;
425 8894 : t->flags = cast_byte(~0);
426 8894 : t->array = NULL;
427 8894 : t->sizearray = 0;
428 8894 : setnodevector(L, t, 0);
429 8894 : return t;
430 : }
431 :
432 :
433 8663 : void luaH_free (lua_State *L, Table *t) {
434 8663 : if (!isdummy(t))
435 1916 : luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
436 8663 : luaM_freearray(L, t->array, t->sizearray);
437 8663 : luaM_free(L, t);
438 8663 : }
439 :
440 :
441 53967 : static Node *getfreepos (Table *t) {
442 53967 : if (!isdummy(t)) {
443 55931 : while (t->lastfree > t->node) {
444 52509 : t->lastfree--;
445 52509 : if (ttisnil(gkey(t->lastfree)))
446 26029 : return t->lastfree;
447 : }
448 : }
449 27938 : return NULL; /* could not find a free place */
450 : }
451 :
452 :
453 :
454 : /*
455 : ** inserts a new key into a hash table; first, check whether key's main
456 : ** position is free. If not, check whether colliding node is in its main
457 : ** position or not: if it is not, move colliding node to an empty place and
458 : ** put new key in its main position; otherwise (colliding node is in its main
459 : ** position), new key goes to an empty position.
460 : */
461 94573 : TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
462 : Node *mp;
463 : TValue aux;
464 94573 : if (ttisnil(key)) luaG_runerror(L, "table index is nil");
465 94571 : else if (ttisfloat(key)) {
466 : lua_Integer k;
467 221 : if (luaV_tointeger(key, &k, 0)) { /* does index fit in an integer? */
468 31 : setivalue(&aux, k);
469 31 : key = &aux; /* insert it as an integer */
470 : }
471 190 : else if (luai_numisnan(fltvalue(key)))
472 1 : luaG_runerror(L, "table index is NaN");
473 : }
474 94570 : mp = mainposition(t, key);
475 94570 : if (!ttisnil(gval(mp)) || isdummy(t)) { /* main position is taken? */
476 : Node *othern;
477 53967 : Node *f = getfreepos(t); /* get a free place */
478 53967 : if (f == NULL) { /* cannot find a free place? */
479 27938 : rehash(L, t, key); /* grow table */
480 : /* whatever called 'newkey' takes care of TM cache */
481 27938 : return luaH_set(L, t, key); /* insert key into grown table */
482 : }
483 : lua_assert(!isdummy(t));
484 26029 : othern = mainposition(t, gkey(mp));
485 26029 : if (othern != mp) { /* is colliding node out of its main position? */
486 : /* yes; move colliding node into free position */
487 6417 : while (othern + gnext(othern) != mp) /* find previous */
488 1169 : othern += gnext(othern);
489 5248 : gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */
490 5248 : *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */
491 5248 : if (gnext(mp) != 0) {
492 975 : gnext(f) += cast_int(mp - f); /* correct 'next' */
493 975 : gnext(mp) = 0; /* now 'mp' is free */
494 : }
495 5248 : setnilvalue(gval(mp));
496 : }
497 : else { /* colliding node is in its own main position */
498 : /* new node will go into free position */
499 20781 : if (gnext(mp) != 0)
500 4652 : gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */
501 : else lua_assert(gnext(f) == 0);
502 20781 : gnext(mp) = cast_int(f - mp);
503 20781 : mp = f;
504 : }
505 : }
506 66632 : setnodekey(L, &mp->i_key, key);
507 66632 : luaC_barrierback(L, t, key);
508 : lua_assert(ttisnil(gval(mp)));
509 66632 : return gval(mp);
510 : }
511 :
512 :
513 : /*
514 : ** search function for integers
515 : */
516 513516 : const TValue *luaH_getint (Table *t, lua_Integer key) {
517 : /* (1 <= key && key <= t->sizearray) */
518 513516 : if (l_castS2U(key) - 1 < t->sizearray)
519 488992 : return &t->array[key - 1];
520 : else {
521 24524 : Node *n = hashint(t, key);
522 : for (;;) { /* check whether 'key' is somewhere in the chain */
523 24562 : if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
524 86 : return gval(n); /* that's it */
525 : else {
526 24476 : int nx = gnext(n);
527 24476 : if (nx == 0) break;
528 38 : n += nx;
529 : }
530 : }
531 24438 : return luaO_nilobject;
532 : }
533 : }
534 :
535 :
536 : /*
537 : ** search function for short strings
538 : */
539 236477 : const TValue *luaH_getshortstr (Table *t, TString *key) {
540 236477 : Node *n = hashstr(t, key);
541 : lua_assert(key->tt == LUA_TSHRSTR);
542 48556 : for (;;) { /* check whether 'key' is somewhere in the chain */
543 285033 : const TValue *k = gkey(n);
544 285033 : if (ttisshrstring(k) && eqshrstr(tsvalue(k), key))
545 164497 : return gval(n); /* that's it */
546 : else {
547 120536 : int nx = gnext(n);
548 120536 : if (nx == 0)
549 71980 : return luaO_nilobject; /* not found */
550 48556 : n += nx;
551 : }
552 : }
553 : }
554 :
555 :
556 : /*
557 : ** "Generic" get version. (Not that generic: not valid for integers,
558 : ** which may be in array part, nor for floats with integral values.)
559 : */
560 7594 : static const TValue *getgeneric (Table *t, const TValue *key) {
561 7594 : Node *n = mainposition(t, key);
562 : for (;;) { /* check whether 'key' is somewhere in the chain */
563 10383 : if (luaV_rawequalobj(gkey(n), key))
564 3931 : return gval(n); /* that's it */
565 : else {
566 6452 : int nx = gnext(n);
567 6452 : if (nx == 0)
568 3663 : return luaO_nilobject; /* not found */
569 2789 : n += nx;
570 : }
571 : }
572 : }
573 :
574 :
575 25947 : const TValue *luaH_getstr (Table *t, TString *key) {
576 25947 : if (key->tt == LUA_TSHRSTR)
577 25947 : return luaH_getshortstr(t, key);
578 : else { /* for long strings, use generic case */
579 : TValue ko;
580 0 : setsvalue(cast(lua_State *, NULL), &ko, key);
581 0 : return getgeneric(t, &ko);
582 : }
583 : }
584 :
585 :
586 : /*
587 : ** main search function
588 : */
589 357187 : const TValue *luaH_get (Table *t, const TValue *key) {
590 357187 : switch (ttype(key)) {
591 201813 : case LUA_TSHRSTR: return luaH_getshortstr(t, tsvalue(key));
592 147717 : case LUA_TNUMINT: return luaH_getint(t, ivalue(key));
593 4 : case LUA_TNIL: return luaO_nilobject;
594 330 : case LUA_TNUMFLT: {
595 : lua_Integer k;
596 330 : if (luaV_tointeger(key, &k, 0)) /* index is int? */
597 59 : return luaH_getint(t, k); /* use specialized version */
598 : /* else... */
599 : } /* FALLTHROUGH */
600 : default:
601 7594 : return getgeneric(t, key);
602 : }
603 : }
604 :
605 :
606 : /*
607 : ** beware: when using this function you probably need to check a GC
608 : ** barrier and invalidate the TM cache.
609 : */
610 139550 : TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
611 139550 : const TValue *p = luaH_get(t, key);
612 139550 : if (p != luaO_nilobject)
613 88182 : return cast(TValue *, p);
614 51368 : else return luaH_newkey(L, t, key);
615 : }
616 :
617 :
618 1948 : void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
619 1948 : const TValue *p = luaH_getint(t, key);
620 : TValue *cell;
621 1948 : if (p != luaO_nilobject)
622 1691 : cell = cast(TValue *, p);
623 : else {
624 : TValue k;
625 257 : setivalue(&k, key);
626 257 : cell = luaH_newkey(L, t, &k);
627 : }
628 1948 : setobj2t(L, cell, value);
629 1948 : }
630 :
631 :
632 61 : static lua_Unsigned unbound_search (Table *t, lua_Unsigned j) {
633 61 : lua_Unsigned i = j; /* i is zero or a present index */
634 61 : j++;
635 : /* find 'i' and 'j' such that i is present and j is not */
636 62 : while (!ttisnil(luaH_getint(t, j))) {
637 1 : i = j;
638 1 : if (j > l_castS2U(LUA_MAXINTEGER) / 2) { /* overflow? */
639 : /* table was built with bad purposes: resort to linear search */
640 0 : i = 1;
641 0 : while (!ttisnil(luaH_getint(t, i))) i++;
642 0 : return i - 1;
643 : }
644 1 : j *= 2;
645 : }
646 : /* now do a binary search between them */
647 63 : while (j - i > 1) {
648 2 : lua_Unsigned m = (i+j)/2;
649 2 : if (ttisnil(luaH_getint(t, m))) j = m;
650 0 : else i = m;
651 : }
652 61 : return i;
653 : }
654 :
655 :
656 : /*
657 : ** Try to find a boundary in table 't'. A 'boundary' is an integer index
658 : ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
659 : */
660 18759 : lua_Unsigned luaH_getn (Table *t) {
661 18759 : unsigned int j = t->sizearray;
662 18759 : if (j > 0 && ttisnil(&t->array[j - 1])) {
663 : /* there is a boundary in the array part: (binary) search for it */
664 17800 : unsigned int i = 0;
665 71002 : while (j - i > 1) {
666 53202 : unsigned int m = (i+j)/2;
667 53202 : if (ttisnil(&t->array[m - 1])) j = m;
668 50627 : else i = m;
669 : }
670 17800 : return i;
671 : }
672 : /* else must find a boundary in hash part */
673 959 : else if (isdummy(t)) /* hash part is empty? */
674 898 : return j; /* that is easy... */
675 61 : else return unbound_search(t, j);
676 : }
677 :
678 :
679 :
680 : #if defined(LUA_DEBUG)
681 :
682 : Node *luaH_mainposition (const Table *t, const TValue *key) {
683 : return mainposition(t, key);
684 : }
685 :
686 : int luaH_isdummy (const Table *t) { return isdummy(t); }
687 :
688 : #endif
|
