]>
git.proxmox.com Git - ceph.git/blob - ceph/src/jaegertracing/opentelemetry-cpp/third_party/prometheus-cpp/3rdparty/civetweb/src/third_party/lua-5.4.3/src/ltable.c
4 ** See Copyright Notice in lua.h
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.
43 ** MAXABITS is the largest integer such that MAXASIZE fits in an
46 #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1)
50 ** MAXASIZE is the maximum size of the array part. It is the minimum
51 ** between 2^MAXABITS and the maximum size that, measured in bytes,
52 ** fits in a 'size_t'.
54 #define MAXASIZE luaM_limitN(1u << MAXABITS, TValue)
57 ** MAXHBITS is the largest integer such that 2^MAXHBITS fits in a
60 #define MAXHBITS (MAXABITS - 1)
64 ** MAXHSIZE is the maximum size of the hash part. It is the minimum
65 ** between 2^MAXHBITS and the maximum size such that, measured in bytes,
66 ** it fits in a 'size_t'.
68 #define MAXHSIZE luaM_limitN(1u << MAXHBITS, Node)
72 ** When the original hash value is good, hashing by a power of 2
73 ** avoids the cost of '%'.
75 #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
78 ** for other types, it is better to avoid modulo by power of 2, as
79 ** they can have many 2 factors.
81 #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
84 #define hashstr(t,str) hashpow2(t, (str)->hash)
85 #define hashboolean(t,p) hashpow2(t, p)
87 #define hashint(t,i) hashpow2(t, i)
90 #define hashpointer(t,p) hashmod(t, point2uint(p))
93 #define dummynode (&dummynode_)
95 static const Node dummynode_
= {
96 {{NULL
}, LUA_VEMPTY
, /* value's value and type */
97 LUA_VNIL
, 0, {NULL
}} /* key type, next, and key value */
101 static const TValue absentkey
= {ABSTKEYCONSTANT
};
106 ** Hash for floating-point numbers.
107 ** The main computation should be just
108 ** n = frexp(n, &i); return (n * INT_MAX) + i
109 ** but there are some numerical subtleties.
110 ** In a two-complement representation, INT_MAX does not has an exact
111 ** representation as a float, but INT_MIN does; because the absolute
112 ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the
113 ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
114 ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when
115 ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
118 #if !defined(l_hashfloat)
119 static int l_hashfloat (lua_Number n
) {
122 n
= l_mathop(frexp
)(n
, &i
) * -cast_num(INT_MIN
);
123 if (!lua_numbertointeger(n
, &ni
)) { /* is 'n' inf/-inf/NaN? */
124 lua_assert(luai_numisnan(n
) || l_mathop(fabs
)(n
) == cast_num(HUGE_VAL
));
127 else { /* normal case */
128 unsigned int u
= cast_uint(i
) + cast_uint(ni
);
129 return cast_int(u
<= cast_uint(INT_MAX
) ? u
: ~u
);
136 ** returns the 'main' position of an element in a table (that is,
137 ** the index of its hash value). The key comes broken (tag in 'ktt'
138 ** and value in 'vkl') so that we can call it on keys inserted into
141 static Node
*mainposition (const Table
*t
, int ktt
, const Value
*kvl
) {
142 switch (withvariant(ktt
)) {
144 lua_Integer key
= ivalueraw(*kvl
);
145 return hashint(t
, key
);
148 lua_Number n
= fltvalueraw(*kvl
);
149 return hashmod(t
, l_hashfloat(n
));
152 TString
*ts
= tsvalueraw(*kvl
);
153 return hashstr(t
, ts
);
156 TString
*ts
= tsvalueraw(*kvl
);
157 return hashpow2(t
, luaS_hashlongstr(ts
));
160 return hashboolean(t
, 0);
162 return hashboolean(t
, 1);
163 case LUA_VLIGHTUSERDATA
: {
164 void *p
= pvalueraw(*kvl
);
165 return hashpointer(t
, p
);
168 lua_CFunction f
= fvalueraw(*kvl
);
169 return hashpointer(t
, f
);
172 GCObject
*o
= gcvalueraw(*kvl
);
173 return hashpointer(t
, o
);
180 ** Returns the main position of an element given as a 'TValue'
182 static Node
*mainpositionTV (const Table
*t
, const TValue
*key
) {
183 return mainposition(t
, rawtt(key
), valraw(key
));
188 ** Check whether key 'k1' is equal to the key in node 'n2'. This
189 ** equality is raw, so there are no metamethods. Floats with integer
190 ** values have been normalized, so integers cannot be equal to
191 ** floats. It is assumed that 'eqshrstr' is simply pointer equality, so
192 ** that short strings are handled in the default case.
193 ** A true 'deadok' means to accept dead keys as equal to their original
194 ** values. All dead keys are compared in the default case, by pointer
195 ** identity. (Only collectable objects can produce dead keys.) Note that
196 ** dead long strings are also compared by identity.
197 ** Once a key is dead, its corresponding value may be collected, and
198 ** then another value can be created with the same address. If this
199 ** other value is given to 'next', 'equalkey' will signal a false
200 ** positive. In a regular traversal, this situation should never happen,
201 ** as all keys given to 'next' came from the table itself, and therefore
202 ** could not have been collected. Outside a regular traversal, we
203 ** have garbage in, garbage out. What is relevant is that this false
204 ** positive does not break anything. (In particular, 'next' will return
205 ** some other valid item on the table or nil.)
207 static int equalkey (const TValue
*k1
, const Node
*n2
, int deadok
) {
208 if ((rawtt(k1
) != keytt(n2
)) && /* not the same variants? */
209 !(deadok
&& keyisdead(n2
) && iscollectable(k1
)))
210 return 0; /* cannot be same key */
212 case LUA_VNIL
: case LUA_VFALSE
: case LUA_VTRUE
:
215 return (ivalue(k1
) == keyival(n2
));
217 return luai_numeq(fltvalue(k1
), fltvalueraw(keyval(n2
)));
218 case LUA_VLIGHTUSERDATA
:
219 return pvalue(k1
) == pvalueraw(keyval(n2
));
221 return fvalue(k1
) == fvalueraw(keyval(n2
));
222 case ctb(LUA_VLNGSTR
):
223 return luaS_eqlngstr(tsvalue(k1
), keystrval(n2
));
225 return gcvalue(k1
) == gcvalueraw(keyval(n2
));
231 ** True if value of 'alimit' is equal to the real size of the array
232 ** part of table 't'. (Otherwise, the array part must be larger than
235 #define limitequalsasize(t) (isrealasize(t) || ispow2((t)->alimit))
239 ** Returns the real size of the 'array' array
241 LUAI_FUNC
unsigned int luaH_realasize (const Table
*t
) {
242 if (limitequalsasize(t
))
243 return t
->alimit
; /* this is the size */
245 unsigned int size
= t
->alimit
;
246 /* compute the smallest power of 2 not smaller than 'n' */
251 size
|= (size
>> 16);
252 #if (UINT_MAX >> 30) > 3
253 size
|= (size
>> 32); /* unsigned int has more than 32 bits */
256 lua_assert(ispow2(size
) && size
/2 < t
->alimit
&& t
->alimit
< size
);
263 ** Check whether real size of the array is a power of 2.
264 ** (If it is not, 'alimit' cannot be changed to any other value
265 ** without changing the real size.)
267 static int ispow2realasize (const Table
*t
) {
268 return (!isrealasize(t
) || ispow2(t
->alimit
));
272 static unsigned int setlimittosize (Table
*t
) {
273 t
->alimit
= luaH_realasize(t
);
279 #define limitasasize(t) check_exp(isrealasize(t), t->alimit)
284 ** "Generic" get version. (Not that generic: not valid for integers,
285 ** which may be in array part, nor for floats with integral values.)
286 ** See explanation about 'deadok' in function 'equalkey'.
288 static const TValue
*getgeneric (Table
*t
, const TValue
*key
, int deadok
) {
289 Node
*n
= mainpositionTV(t
, key
);
290 for (;;) { /* check whether 'key' is somewhere in the chain */
291 if (equalkey(key
, n
, deadok
))
292 return gval(n
); /* that's it */
296 return &absentkey
; /* not found */
304 ** returns the index for 'k' if 'k' is an appropriate key to live in
305 ** the array part of a table, 0 otherwise.
307 static unsigned int arrayindex (lua_Integer k
) {
308 if (l_castS2U(k
) - 1u < MAXASIZE
) /* 'k' in [1, MAXASIZE]? */
309 return cast_uint(k
); /* 'key' is an appropriate array index */
316 ** returns the index of a 'key' for table traversals. First goes all
317 ** elements in the array part, then elements in the hash part. The
318 ** beginning of a traversal is signaled by 0.
320 static unsigned int findindex (lua_State
*L
, Table
*t
, TValue
*key
,
321 unsigned int asize
) {
323 if (ttisnil(key
)) return 0; /* first iteration */
324 i
= ttisinteger(key
) ? arrayindex(ivalue(key
)) : 0;
325 if (i
- 1u < asize
) /* is 'key' inside array part? */
326 return i
; /* yes; that's the index */
328 const TValue
*n
= getgeneric(t
, key
, 1);
329 if (l_unlikely(isabstkey(n
)))
330 luaG_runerror(L
, "invalid key to 'next'"); /* key not found */
331 i
= cast_int(nodefromval(n
) - gnode(t
, 0)); /* key index in hash table */
332 /* hash elements are numbered after array ones */
333 return (i
+ 1) + asize
;
338 int luaH_next (lua_State
*L
, Table
*t
, StkId key
) {
339 unsigned int asize
= luaH_realasize(t
);
340 unsigned int i
= findindex(L
, t
, s2v(key
), asize
); /* find original key */
341 for (; i
< asize
; i
++) { /* try first array part */
342 if (!isempty(&t
->array
[i
])) { /* a non-empty entry? */
343 setivalue(s2v(key
), i
+ 1);
344 setobj2s(L
, key
+ 1, &t
->array
[i
]);
348 for (i
-= asize
; cast_int(i
) < sizenode(t
); i
++) { /* hash part */
349 if (!isempty(gval(gnode(t
, i
)))) { /* a non-empty entry? */
350 Node
*n
= gnode(t
, i
);
351 getnodekey(L
, s2v(key
), n
);
352 setobj2s(L
, key
+ 1, gval(n
));
356 return 0; /* no more elements */
360 static void freehash (lua_State
*L
, Table
*t
) {
362 luaM_freearray(L
, t
->node
, cast_sizet(sizenode(t
)));
367 ** {=============================================================
369 ** ==============================================================
373 ** Compute the optimal size for the array part of table 't'. 'nums' is a
374 ** "count array" where 'nums[i]' is the number of integers in the table
375 ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
376 ** integer keys in the table and leaves with the number of keys that
377 ** will go to the array part; return the optimal size. (The condition
378 ** 'twotoi > 0' in the for loop stops the loop if 'twotoi' overflows.)
380 static unsigned int computesizes (unsigned int nums
[], unsigned int *pna
) {
382 unsigned int twotoi
; /* 2^i (candidate for optimal size) */
383 unsigned int a
= 0; /* number of elements smaller than 2^i */
384 unsigned int na
= 0; /* number of elements to go to array part */
385 unsigned int optimal
= 0; /* optimal size for array part */
386 /* loop while keys can fill more than half of total size */
387 for (i
= 0, twotoi
= 1;
388 twotoi
> 0 && *pna
> twotoi
/ 2;
391 if (a
> twotoi
/2) { /* more than half elements present? */
392 optimal
= twotoi
; /* optimal size (till now) */
393 na
= a
; /* all elements up to 'optimal' will go to array part */
396 lua_assert((optimal
== 0 || optimal
/ 2 < na
) && na
<= optimal
);
402 static int countint (lua_Integer key
, unsigned int *nums
) {
403 unsigned int k
= arrayindex(key
);
404 if (k
!= 0) { /* is 'key' an appropriate array index? */
405 nums
[luaO_ceillog2(k
)]++; /* count as such */
414 ** Count keys in array part of table 't': Fill 'nums[i]' with
415 ** number of keys that will go into corresponding slice and return
416 ** total number of non-nil keys.
418 static unsigned int numusearray (const Table
*t
, unsigned int *nums
) {
420 unsigned int ttlg
; /* 2^lg */
421 unsigned int ause
= 0; /* summation of 'nums' */
422 unsigned int i
= 1; /* count to traverse all array keys */
423 unsigned int asize
= limitasasize(t
); /* real array size */
424 /* traverse each slice */
425 for (lg
= 0, ttlg
= 1; lg
<= MAXABITS
; lg
++, ttlg
*= 2) {
426 unsigned int lc
= 0; /* counter */
427 unsigned int lim
= ttlg
;
429 lim
= asize
; /* adjust upper limit */
431 break; /* no more elements to count */
433 /* count elements in range (2^(lg - 1), 2^lg] */
434 for (; i
<= lim
; i
++) {
435 if (!isempty(&t
->array
[i
-1]))
445 static int numusehash (const Table
*t
, unsigned int *nums
, unsigned int *pna
) {
446 int totaluse
= 0; /* total number of elements */
447 int ause
= 0; /* elements added to 'nums' (can go to array part) */
450 Node
*n
= &t
->node
[i
];
451 if (!isempty(gval(n
))) {
453 ause
+= countint(keyival(n
), nums
);
463 ** Creates an array for the hash part of a table with the given
464 ** size, or reuses the dummy node if size is zero.
465 ** The computation for size overflow is in two steps: the first
466 ** comparison ensures that the shift in the second one does not
469 static void setnodevector (lua_State
*L
, Table
*t
, unsigned int size
) {
470 if (size
== 0) { /* no elements to hash part? */
471 t
->node
= cast(Node
*, dummynode
); /* use common 'dummynode' */
473 t
->lastfree
= NULL
; /* signal that it is using dummy node */
477 int lsize
= luaO_ceillog2(size
);
478 if (lsize
> MAXHBITS
|| (1u << lsize
) > MAXHSIZE
)
479 luaG_runerror(L
, "table overflow");
481 t
->node
= luaM_newvector(L
, size
, Node
);
482 for (i
= 0; i
< (int)size
; i
++) {
483 Node
*n
= gnode(t
, i
);
488 t
->lsizenode
= cast_byte(lsize
);
489 t
->lastfree
= gnode(t
, size
); /* all positions are free */
495 ** (Re)insert all elements from the hash part of 'ot' into table 't'.
497 static void reinsert (lua_State
*L
, Table
*ot
, Table
*t
) {
499 int size
= sizenode(ot
);
500 for (j
= 0; j
< size
; j
++) {
501 Node
*old
= gnode(ot
, j
);
502 if (!isempty(gval(old
))) {
503 /* doesn't need barrier/invalidate cache, as entry was
504 already present in the table */
506 getnodekey(L
, &k
, old
);
507 luaH_set(L
, t
, &k
, gval(old
));
514 ** Exchange the hash part of 't1' and 't2'.
516 static void exchangehashpart (Table
*t1
, Table
*t2
) {
517 lu_byte lsizenode
= t1
->lsizenode
;
518 Node
*node
= t1
->node
;
519 Node
*lastfree
= t1
->lastfree
;
520 t1
->lsizenode
= t2
->lsizenode
;
522 t1
->lastfree
= t2
->lastfree
;
523 t2
->lsizenode
= lsizenode
;
525 t2
->lastfree
= lastfree
;
530 ** Resize table 't' for the new given sizes. Both allocations (for
531 ** the hash part and for the array part) can fail, which creates some
532 ** subtleties. If the first allocation, for the hash part, fails, an
533 ** error is raised and that is it. Otherwise, it copies the elements from
534 ** the shrinking part of the array (if it is shrinking) into the new
535 ** hash. Then it reallocates the array part. If that fails, the table
536 ** is in its original state; the function frees the new hash part and then
537 ** raises the allocation error. Otherwise, it sets the new hash part
538 ** into the table, initializes the new part of the array (if any) with
539 ** nils and reinserts the elements of the old hash back into the new
540 ** parts of the table.
542 void luaH_resize (lua_State
*L
, Table
*t
, unsigned int newasize
,
543 unsigned int nhsize
) {
545 Table newt
; /* to keep the new hash part */
546 unsigned int oldasize
= setlimittosize(t
);
548 /* create new hash part with appropriate size into 'newt' */
549 setnodevector(L
, &newt
, nhsize
);
550 if (newasize
< oldasize
) { /* will array shrink? */
551 t
->alimit
= newasize
; /* pretend array has new size... */
552 exchangehashpart(t
, &newt
); /* and new hash */
553 /* re-insert into the new hash the elements from vanishing slice */
554 for (i
= newasize
; i
< oldasize
; i
++) {
555 if (!isempty(&t
->array
[i
]))
556 luaH_setint(L
, t
, i
+ 1, &t
->array
[i
]);
558 t
->alimit
= oldasize
; /* restore current size... */
559 exchangehashpart(t
, &newt
); /* and hash (in case of errors) */
561 /* allocate new array */
562 newarray
= luaM_reallocvector(L
, t
->array
, oldasize
, newasize
, TValue
);
563 if (l_unlikely(newarray
== NULL
&& newasize
> 0)) { /* allocation failed? */
564 freehash(L
, &newt
); /* release new hash part */
565 luaM_error(L
); /* raise error (with array unchanged) */
567 /* allocation ok; initialize new part of the array */
568 exchangehashpart(t
, &newt
); /* 't' has the new hash ('newt' has the old) */
569 t
->array
= newarray
; /* set new array part */
570 t
->alimit
= newasize
;
571 for (i
= oldasize
; i
< newasize
; i
++) /* clear new slice of the array */
572 setempty(&t
->array
[i
]);
573 /* re-insert elements from old hash part into new parts */
574 reinsert(L
, &newt
, t
); /* 'newt' now has the old hash */
575 freehash(L
, &newt
); /* free old hash part */
579 void luaH_resizearray (lua_State
*L
, Table
*t
, unsigned int nasize
) {
580 int nsize
= allocsizenode(t
);
581 luaH_resize(L
, t
, nasize
, nsize
);
585 ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
587 static void rehash (lua_State
*L
, Table
*t
, const TValue
*ek
) {
588 unsigned int asize
; /* optimal size for array part */
589 unsigned int na
; /* number of keys in the array part */
590 unsigned int nums
[MAXABITS
+ 1];
593 for (i
= 0; i
<= MAXABITS
; i
++) nums
[i
] = 0; /* reset counts */
595 na
= numusearray(t
, nums
); /* count keys in array part */
596 totaluse
= na
; /* all those keys are integer keys */
597 totaluse
+= numusehash(t
, nums
, &na
); /* count keys in hash part */
598 /* count extra key */
600 na
+= countint(ivalue(ek
), nums
);
602 /* compute new size for array part */
603 asize
= computesizes(nums
, &na
);
604 /* resize the table to new computed sizes */
605 luaH_resize(L
, t
, asize
, totaluse
- na
);
611 ** }=============================================================
615 Table
*luaH_new (lua_State
*L
) {
616 GCObject
*o
= luaC_newobj(L
, LUA_VTABLE
, sizeof(Table
));
619 t
->flags
= cast_byte(maskflags
); /* table has no metamethod fields */
622 setnodevector(L
, t
, 0);
627 void luaH_free (lua_State
*L
, Table
*t
) {
629 luaM_freearray(L
, t
->array
, luaH_realasize(t
));
634 static Node
*getfreepos (Table
*t
) {
636 while (t
->lastfree
> t
->node
) {
638 if (keyisnil(t
->lastfree
))
642 return NULL
; /* could not find a free place */
648 ** inserts a new key into a hash table; first, check whether key's main
649 ** position is free. If not, check whether colliding node is in its main
650 ** position or not: if it is not, move colliding node to an empty place and
651 ** put new key in its main position; otherwise (colliding node is in its main
652 ** position), new key goes to an empty position.
654 void luaH_newkey (lua_State
*L
, Table
*t
, const TValue
*key
, TValue
*value
) {
657 if (l_unlikely(ttisnil(key
)))
658 luaG_runerror(L
, "table index is nil");
659 else if (ttisfloat(key
)) {
660 lua_Number f
= fltvalue(key
);
662 if (luaV_flttointeger(f
, &k
, F2Ieq
)) { /* does key fit in an integer? */
664 key
= &aux
; /* insert it as an integer */
666 else if (l_unlikely(luai_numisnan(f
)))
667 luaG_runerror(L
, "table index is NaN");
670 return; /* do not insert nil values */
671 mp
= mainpositionTV(t
, key
);
672 if (!isempty(gval(mp
)) || isdummy(t
)) { /* main position is taken? */
674 Node
*f
= getfreepos(t
); /* get a free place */
675 if (f
== NULL
) { /* cannot find a free place? */
676 rehash(L
, t
, key
); /* grow table */
677 /* whatever called 'newkey' takes care of TM cache */
678 luaH_set(L
, t
, key
, value
); /* insert key into grown table */
681 lua_assert(!isdummy(t
));
682 othern
= mainposition(t
, keytt(mp
), &keyval(mp
));
683 if (othern
!= mp
) { /* is colliding node out of its main position? */
684 /* yes; move colliding node into free position */
685 while (othern
+ gnext(othern
) != mp
) /* find previous */
686 othern
+= gnext(othern
);
687 gnext(othern
) = cast_int(f
- othern
); /* rechain to point to 'f' */
688 *f
= *mp
; /* copy colliding node into free pos. (mp->next also goes) */
689 if (gnext(mp
) != 0) {
690 gnext(f
) += cast_int(mp
- f
); /* correct 'next' */
691 gnext(mp
) = 0; /* now 'mp' is free */
695 else { /* colliding node is in its own main position */
696 /* new node will go into free position */
698 gnext(f
) = cast_int((mp
+ gnext(mp
)) - f
); /* chain new position */
699 else lua_assert(gnext(f
) == 0);
700 gnext(mp
) = cast_int(f
- mp
);
704 setnodekey(L
, mp
, key
);
705 luaC_barrierback(L
, obj2gco(t
), key
);
706 lua_assert(isempty(gval(mp
)));
707 setobj2t(L
, gval(mp
), value
);
712 ** Search function for integers. If integer is inside 'alimit', get it
713 ** directly from the array part. Otherwise, if 'alimit' is not equal to
714 ** the real size of the array, key still can be in the array part. In
715 ** this case, try to avoid a call to 'luaH_realasize' when key is just
716 ** one more than the limit (so that it can be incremented without
717 ** changing the real size of the array).
719 const TValue
*luaH_getint (Table
*t
, lua_Integer key
) {
720 if (l_castS2U(key
) - 1u < t
->alimit
) /* 'key' in [1, t->alimit]? */
721 return &t
->array
[key
- 1];
722 else if (!limitequalsasize(t
) && /* key still may be in the array part? */
723 (l_castS2U(key
) == t
->alimit
+ 1 ||
724 l_castS2U(key
) - 1u < luaH_realasize(t
))) {
725 t
->alimit
= cast_uint(key
); /* probably '#t' is here now */
726 return &t
->array
[key
- 1];
729 Node
*n
= hashint(t
, key
);
730 for (;;) { /* check whether 'key' is somewhere in the chain */
731 if (keyisinteger(n
) && keyival(n
) == key
)
732 return gval(n
); /* that's it */
745 ** search function for short strings
747 const TValue
*luaH_getshortstr (Table
*t
, TString
*key
) {
748 Node
*n
= hashstr(t
, key
);
749 lua_assert(key
->tt
== LUA_VSHRSTR
);
750 for (;;) { /* check whether 'key' is somewhere in the chain */
751 if (keyisshrstr(n
) && eqshrstr(keystrval(n
), key
))
752 return gval(n
); /* that's it */
756 return &absentkey
; /* not found */
763 const TValue
*luaH_getstr (Table
*t
, TString
*key
) {
764 if (key
->tt
== LUA_VSHRSTR
)
765 return luaH_getshortstr(t
, key
);
766 else { /* for long strings, use generic case */
768 setsvalue(cast(lua_State
*, NULL
), &ko
, key
);
769 return getgeneric(t
, &ko
, 0);
775 ** main search function
777 const TValue
*luaH_get (Table
*t
, const TValue
*key
) {
778 switch (ttypetag(key
)) {
779 case LUA_VSHRSTR
: return luaH_getshortstr(t
, tsvalue(key
));
780 case LUA_VNUMINT
: return luaH_getint(t
, ivalue(key
));
781 case LUA_VNIL
: return &absentkey
;
784 if (luaV_flttointeger(fltvalue(key
), &k
, F2Ieq
)) /* integral index? */
785 return luaH_getint(t
, k
); /* use specialized version */
789 return getgeneric(t
, key
, 0);
795 ** Finish a raw "set table" operation, where 'slot' is where the value
796 ** should have been (the result of a previous "get table").
797 ** Beware: when using this function you probably need to check a GC
798 ** barrier and invalidate the TM cache.
800 void luaH_finishset (lua_State
*L
, Table
*t
, const TValue
*key
,
801 const TValue
*slot
, TValue
*value
) {
803 luaH_newkey(L
, t
, key
, value
);
805 setobj2t(L
, cast(TValue
*, slot
), value
);
810 ** beware: when using this function you probably need to check a GC
811 ** barrier and invalidate the TM cache.
813 void luaH_set (lua_State
*L
, Table
*t
, const TValue
*key
, TValue
*value
) {
814 const TValue
*slot
= luaH_get(t
, key
);
815 luaH_finishset(L
, t
, key
, slot
, value
);
819 void luaH_setint (lua_State
*L
, Table
*t
, lua_Integer key
, TValue
*value
) {
820 const TValue
*p
= luaH_getint(t
, key
);
824 luaH_newkey(L
, t
, &k
, value
);
827 setobj2t(L
, cast(TValue
*, p
), value
);
832 ** Try to find a boundary in the hash part of table 't'. From the
833 ** caller, we know that 'j' is zero or present and that 'j + 1' is
834 ** present. We want to find a larger key that is absent from the
835 ** table, so that we can do a binary search between the two keys to
836 ** find a boundary. We keep doubling 'j' until we get an absent index.
837 ** If the doubling would overflow, we try LUA_MAXINTEGER. If it is
838 ** absent, we are ready for the binary search. ('j', being max integer,
839 ** is larger or equal to 'i', but it cannot be equal because it is
840 ** absent while 'i' is present; so 'j > i'.) Otherwise, 'j' is a
841 ** boundary. ('j + 1' cannot be a present integer key because it is
842 ** not a valid integer in Lua.)
844 static lua_Unsigned
hash_search (Table
*t
, lua_Unsigned j
) {
846 if (j
== 0) j
++; /* the caller ensures 'j + 1' is present */
848 i
= j
; /* 'i' is a present index */
849 if (j
<= l_castS2U(LUA_MAXINTEGER
) / 2)
853 if (isempty(luaH_getint(t
, j
))) /* t[j] not present? */
854 break; /* 'j' now is an absent index */
855 else /* weird case */
856 return j
; /* well, max integer is a boundary... */
858 } while (!isempty(luaH_getint(t
, j
))); /* repeat until an absent t[j] */
859 /* i < j && t[i] present && t[j] absent */
860 while (j
- i
> 1u) { /* do a binary search between them */
861 lua_Unsigned m
= (i
+ j
) / 2;
862 if (isempty(luaH_getint(t
, m
))) j
= m
;
869 static unsigned int binsearch (const TValue
*array
, unsigned int i
,
871 while (j
- i
> 1u) { /* binary search */
872 unsigned int m
= (i
+ j
) / 2;
873 if (isempty(&array
[m
- 1])) j
= m
;
881 ** Try to find a boundary in table 't'. (A 'boundary' is an integer index
882 ** such that t[i] is present and t[i+1] is absent, or 0 if t[1] is absent
883 ** and 'maxinteger' if t[maxinteger] is present.)
884 ** (In the next explanation, we use Lua indices, that is, with base 1.
885 ** The code itself uses base 0 when indexing the array part of the table.)
886 ** The code starts with 'limit = t->alimit', a position in the array
887 ** part that may be a boundary.
889 ** (1) If 't[limit]' is empty, there must be a boundary before it.
890 ** As a common case (e.g., after 't[#t]=nil'), check whether 'limit-1'
891 ** is present. If so, it is a boundary. Otherwise, do a binary search
892 ** between 0 and limit to find a boundary. In both cases, try to
893 ** use this boundary as the new 'alimit', as a hint for the next call.
895 ** (2) If 't[limit]' is not empty and the array has more elements
896 ** after 'limit', try to find a boundary there. Again, try first
897 ** the special case (which should be quite frequent) where 'limit+1'
898 ** is empty, so that 'limit' is a boundary. Otherwise, check the
899 ** last element of the array part. If it is empty, there must be a
900 ** boundary between the old limit (present) and the last element
901 ** (absent), which is found with a binary search. (This boundary always
902 ** can be a new limit.)
904 ** (3) The last case is when there are no elements in the array part
905 ** (limit == 0) or its last element (the new limit) is present.
906 ** In this case, must check the hash part. If there is no hash part
907 ** or 'limit+1' is absent, 'limit' is a boundary. Otherwise, call
908 ** 'hash_search' to find a boundary in the hash part of the table.
909 ** (In those cases, the boundary is not inside the array part, and
910 ** therefore cannot be used as a new limit.)
912 lua_Unsigned
luaH_getn (Table
*t
) {
913 unsigned int limit
= t
->alimit
;
914 if (limit
> 0 && isempty(&t
->array
[limit
- 1])) { /* (1)? */
915 /* there must be a boundary before 'limit' */
916 if (limit
>= 2 && !isempty(&t
->array
[limit
- 2])) {
917 /* 'limit - 1' is a boundary; can it be a new limit? */
918 if (ispow2realasize(t
) && !ispow2(limit
- 1)) {
919 t
->alimit
= limit
- 1;
920 setnorealasize(t
); /* now 'alimit' is not the real size */
924 else { /* must search for a boundary in [0, limit] */
925 unsigned int boundary
= binsearch(t
->array
, 0, limit
);
926 /* can this boundary represent the real size of the array? */
927 if (ispow2realasize(t
) && boundary
> luaH_realasize(t
) / 2) {
928 t
->alimit
= boundary
; /* use it as the new limit */
934 /* 'limit' is zero or present in table */
935 if (!limitequalsasize(t
)) { /* (2)? */
936 /* 'limit' > 0 and array has more elements after 'limit' */
937 if (isempty(&t
->array
[limit
])) /* 'limit + 1' is empty? */
938 return limit
; /* this is the boundary */
939 /* else, try last element in the array */
940 limit
= luaH_realasize(t
);
941 if (isempty(&t
->array
[limit
- 1])) { /* empty? */
942 /* there must be a boundary in the array after old limit,
943 and it must be a valid new limit */
944 unsigned int boundary
= binsearch(t
->array
, t
->alimit
, limit
);
945 t
->alimit
= boundary
;
948 /* else, new limit is present in the table; check the hash part */
950 /* (3) 'limit' is the last element and either is zero or present in table */
951 lua_assert(limit
== luaH_realasize(t
) &&
952 (limit
== 0 || !isempty(&t
->array
[limit
- 1])));
953 if (isdummy(t
) || isempty(luaH_getint(t
, cast(lua_Integer
, limit
+ 1))))
954 return limit
; /* 'limit + 1' is absent */
955 else /* 'limit + 1' is also present */
956 return hash_search(t
, limit
);
961 #if defined(LUA_DEBUG)
963 /* export these functions for the test library */
965 Node
*luaH_mainposition (const Table
*t
, const TValue
*key
) {
966 return mainpositionTV(t
, key
);
969 int luaH_isdummy (const Table
*t
) { return isdummy(t
); }