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