]>
git.proxmox.com Git - ceph.git/blob - ceph/src/jaegertracing/opentelemetry-cpp/third_party/prometheus-cpp/3rdparty/civetweb/src/third_party/lua-5.3.6/src/ltable.c
2 ** $Id: ltable.c,v 2.118.1.4 2018/06/08 16:22:51 roberto Exp $
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 ** Maximum size of array part (MAXASIZE) is 2^MAXABITS. MAXABITS is
44 ** the largest integer such that MAXASIZE fits in an unsigned int.
46 #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1)
47 #define MAXASIZE (1u << MAXABITS)
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.)
55 #define MAXHBITS (MAXABITS - 1)
58 #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
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)
66 ** for some types, it is better to avoid modulus by power of 2, as
67 ** they tend to have many 2 factors.
69 #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
72 #define hashpointer(t,p) hashmod(t, point2uint(p))
75 #define dummynode (&dummynode_)
77 static const Node dummynode_
= {
78 {NILCONSTANT
}, /* value */
79 {{NILCONSTANT
, 0}} /* key */
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
96 #if !defined(l_hashfloat)
97 static int l_hashfloat (lua_Number n
) {
100 n
= l_mathop(frexp
)(n
, &i
) * -cast_num(INT_MIN
);
101 if (!lua_numbertointeger(n
, &ni
)) { /* is 'n' inf/-inf/NaN? */
102 lua_assert(luai_numisnan(n
) || l_mathop(fabs
)(n
) == cast_num(HUGE_VAL
));
105 else { /* normal case */
106 unsigned int u
= cast(unsigned int, i
) + cast(unsigned int, ni
);
107 return cast_int(u
<= cast(unsigned int, INT_MAX
) ? u
: ~u
);
114 ** returns the 'main' position of an element in a table (that is, the index
115 ** of its hash value)
117 static Node
*mainposition (const Table
*t
, const TValue
*key
) {
118 switch (ttype(key
)) {
120 return hashint(t
, ivalue(key
));
122 return hashmod(t
, l_hashfloat(fltvalue(key
)));
124 return hashstr(t
, tsvalue(key
));
126 return hashpow2(t
, luaS_hashlongstr(tsvalue(key
)));
128 return hashboolean(t
, bvalue(key
));
129 case LUA_TLIGHTUSERDATA
:
130 return hashpointer(t
, pvalue(key
));
132 return hashpointer(t
, fvalue(key
));
134 lua_assert(!ttisdeadkey(key
));
135 return hashpointer(t
, gcvalue(key
));
141 ** returns the index for 'key' if 'key' is an appropriate key to live in
142 ** the array part of the table, 0 otherwise.
144 static unsigned int arrayindex (const TValue
*key
) {
145 if (ttisinteger(key
)) {
146 lua_Integer k
= ivalue(key
);
147 if (0 < k
&& (lua_Unsigned
)k
<= MAXASIZE
)
148 return cast(unsigned int, k
); /* 'key' is an appropriate array index */
150 return 0; /* 'key' did not match some condition */
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.
159 static unsigned int findindex (lua_State
*L
, Table
*t
, StkId key
) {
161 if (ttisnil(key
)) return 0; /* first iteration */
163 if (i
!= 0 && i
<= t
->sizearray
) /* is 'key' inside array part? */
164 return i
; /* yes; that's the index */
167 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 if (luaV_rawequalobj(gkey(n
), key
) ||
171 (ttisdeadkey(gkey(n
)) && iscollectable(key
) &&
172 deadvalue(gkey(n
)) == gcvalue(key
))) {
173 i
= cast_int(n
- gnode(t
, 0)); /* key index in hash table */
174 /* hash elements are numbered after array ones */
175 return (i
+ 1) + t
->sizearray
;
179 luaG_runerror(L
, "invalid key to 'next'"); /* key not found */
186 int luaH_next (lua_State
*L
, Table
*t
, StkId key
) {
187 unsigned int i
= findindex(L
, t
, key
); /* find original element */
188 for (; i
< t
->sizearray
; i
++) { /* try first array part */
189 if (!ttisnil(&t
->array
[i
])) { /* a non-nil value? */
190 setivalue(key
, i
+ 1);
191 setobj2s(L
, key
+1, &t
->array
[i
]);
195 for (i
-= t
->sizearray
; cast_int(i
) < sizenode(t
); i
++) { /* hash part */
196 if (!ttisnil(gval(gnode(t
, i
)))) { /* a non-nil value? */
197 setobj2s(L
, key
, gkey(gnode(t
, i
)));
198 setobj2s(L
, key
+1, gval(gnode(t
, i
)));
202 return 0; /* no more elements */
207 ** {=============================================================
209 ** ==============================================================
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.
219 static unsigned int computesizes (unsigned int nums
[], unsigned int *pna
) {
221 unsigned int twotoi
; /* 2^i (candidate for optimal size) */
222 unsigned int a
= 0; /* number of elements smaller than 2^i */
223 unsigned int na
= 0; /* number of elements to go to array part */
224 unsigned int optimal
= 0; /* optimal size for array part */
225 /* loop while keys can fill more than half of total size */
226 for (i
= 0, twotoi
= 1;
227 twotoi
> 0 && *pna
> twotoi
/ 2;
231 if (a
> twotoi
/2) { /* more than half elements present? */
232 optimal
= twotoi
; /* optimal size (till now) */
233 na
= a
; /* all elements up to 'optimal' will go to array part */
237 lua_assert((optimal
== 0 || optimal
/ 2 < na
) && na
<= optimal
);
243 static int countint (const TValue
*key
, unsigned int *nums
) {
244 unsigned int k
= arrayindex(key
);
245 if (k
!= 0) { /* is 'key' an appropriate array index? */
246 nums
[luaO_ceillog2(k
)]++; /* count as such */
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.
259 static unsigned int numusearray (const Table
*t
, unsigned int *nums
) {
261 unsigned int ttlg
; /* 2^lg */
262 unsigned int ause
= 0; /* summation of 'nums' */
263 unsigned int i
= 1; /* count to traverse all array keys */
264 /* traverse each slice */
265 for (lg
= 0, ttlg
= 1; lg
<= MAXABITS
; lg
++, ttlg
*= 2) {
266 unsigned int lc
= 0; /* counter */
267 unsigned int lim
= ttlg
;
268 if (lim
> t
->sizearray
) {
269 lim
= t
->sizearray
; /* adjust upper limit */
271 break; /* no more elements to count */
273 /* count elements in range (2^(lg - 1), 2^lg] */
274 for (; i
<= lim
; i
++) {
275 if (!ttisnil(&t
->array
[i
-1]))
285 static int numusehash (const Table
*t
, unsigned int *nums
, unsigned int *pna
) {
286 int totaluse
= 0; /* total number of elements */
287 int ause
= 0; /* elements added to 'nums' (can go to array part) */
290 Node
*n
= &t
->node
[i
];
291 if (!ttisnil(gval(n
))) {
292 ause
+= countint(gkey(n
), nums
);
301 static void setarrayvector (lua_State
*L
, Table
*t
, unsigned int size
) {
303 luaM_reallocvector(L
, t
->array
, t
->sizearray
, size
, TValue
);
304 for (i
=t
->sizearray
; i
<size
; i
++)
305 setnilvalue(&t
->array
[i
]);
310 static void setnodevector (lua_State
*L
, Table
*t
, unsigned int size
) {
311 if (size
== 0) { /* no elements to hash part? */
312 t
->node
= cast(Node
*, dummynode
); /* use common 'dummynode' */
314 t
->lastfree
= NULL
; /* signal that it is using dummy node */
318 int lsize
= luaO_ceillog2(size
);
319 if (lsize
> MAXHBITS
)
320 luaG_runerror(L
, "table overflow");
322 t
->node
= luaM_newvector(L
, size
, Node
);
323 for (i
= 0; i
< (int)size
; i
++) {
324 Node
*n
= gnode(t
, i
);
326 setnilvalue(wgkey(n
));
327 setnilvalue(gval(n
));
329 t
->lsizenode
= cast_byte(lsize
);
330 t
->lastfree
= gnode(t
, size
); /* all positions are free */
341 static void auxsetnode (lua_State
*L
, void *ud
) {
342 AuxsetnodeT
*asn
= cast(AuxsetnodeT
*, ud
);
343 setnodevector(L
, asn
->t
, asn
->nhsize
);
347 void luaH_resize (lua_State
*L
, Table
*t
, unsigned int nasize
,
348 unsigned int nhsize
) {
352 unsigned int oldasize
= t
->sizearray
;
353 int oldhsize
= allocsizenode(t
);
354 Node
*nold
= t
->node
; /* save old hash ... */
355 if (nasize
> oldasize
) /* array part must grow? */
356 setarrayvector(L
, t
, nasize
);
357 /* create new hash part with appropriate size */
358 asn
.t
= t
; asn
.nhsize
= nhsize
;
359 if (luaD_rawrunprotected(L
, auxsetnode
, &asn
) != LUA_OK
) { /* mem. error? */
360 setarrayvector(L
, t
, oldasize
); /* array back to its original size */
361 luaD_throw(L
, LUA_ERRMEM
); /* rethrow memory error */
363 if (nasize
< oldasize
) { /* array part must shrink? */
364 t
->sizearray
= nasize
;
365 /* re-insert elements from vanishing slice */
366 for (i
=nasize
; i
<oldasize
; i
++) {
367 if (!ttisnil(&t
->array
[i
]))
368 luaH_setint(L
, t
, i
+ 1, &t
->array
[i
]);
371 luaM_reallocvector(L
, t
->array
, oldasize
, nasize
, TValue
);
373 /* re-insert elements from hash part */
374 for (j
= oldhsize
- 1; j
>= 0; j
--) {
375 Node
*old
= nold
+ j
;
376 if (!ttisnil(gval(old
))) {
377 /* doesn't need barrier/invalidate cache, as entry was
378 already present in the table */
379 setobjt2t(L
, luaH_set(L
, t
, gkey(old
)), gval(old
));
382 if (oldhsize
> 0) /* not the dummy node? */
383 luaM_freearray(L
, nold
, cast(size_t, oldhsize
)); /* free old hash */
387 void luaH_resizearray (lua_State
*L
, Table
*t
, unsigned int nasize
) {
388 int nsize
= allocsizenode(t
);
389 luaH_resize(L
, t
, nasize
, nsize
);
393 ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
395 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];
401 for (i
= 0; i
<= MAXABITS
; i
++) nums
[i
] = 0; /* reset counts */
402 na
= numusearray(t
, nums
); /* count keys in array part */
403 totaluse
= na
; /* all those keys are integer keys */
404 totaluse
+= numusehash(t
, nums
, &na
); /* count keys in hash part */
405 /* count extra key */
406 na
+= countint(ek
, nums
);
408 /* compute new size for array part */
409 asize
= computesizes(nums
, &na
);
410 /* resize the table to new computed sizes */
411 luaH_resize(L
, t
, asize
, totaluse
- na
);
417 ** }=============================================================
421 Table
*luaH_new (lua_State
*L
) {
422 GCObject
*o
= luaC_newobj(L
, LUA_TTABLE
, sizeof(Table
));
425 t
->flags
= cast_byte(~0);
428 setnodevector(L
, t
, 0);
433 void luaH_free (lua_State
*L
, Table
*t
) {
435 luaM_freearray(L
, t
->node
, cast(size_t, sizenode(t
)));
436 luaM_freearray(L
, t
->array
, t
->sizearray
);
441 static Node
*getfreepos (Table
*t
) {
443 while (t
->lastfree
> t
->node
) {
445 if (ttisnil(gkey(t
->lastfree
)))
449 return NULL
; /* could not find a free place */
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.
461 TValue
*luaH_newkey (lua_State
*L
, Table
*t
, const TValue
*key
) {
464 if (ttisnil(key
)) luaG_runerror(L
, "table index is nil");
465 else if (ttisfloat(key
)) {
467 if (luaV_tointeger(key
, &k
, 0)) { /* does index fit in an integer? */
469 key
= &aux
; /* insert it as an integer */
471 else if (luai_numisnan(fltvalue(key
)))
472 luaG_runerror(L
, "table index is NaN");
474 mp
= mainposition(t
, key
);
475 if (!ttisnil(gval(mp
)) || isdummy(t
)) { /* main position is taken? */
477 Node
*f
= getfreepos(t
); /* get a free place */
478 if (f
== NULL
) { /* cannot find a free place? */
479 rehash(L
, t
, key
); /* grow table */
480 /* whatever called 'newkey' takes care of TM cache */
481 return luaH_set(L
, t
, key
); /* insert key into grown table */
483 lua_assert(!isdummy(t
));
484 othern
= mainposition(t
, gkey(mp
));
485 if (othern
!= mp
) { /* is colliding node out of its main position? */
486 /* yes; move colliding node into free position */
487 while (othern
+ gnext(othern
) != mp
) /* find previous */
488 othern
+= gnext(othern
);
489 gnext(othern
) = cast_int(f
- othern
); /* rechain to point to 'f' */
490 *f
= *mp
; /* copy colliding node into free pos. (mp->next also goes) */
491 if (gnext(mp
) != 0) {
492 gnext(f
) += cast_int(mp
- f
); /* correct 'next' */
493 gnext(mp
) = 0; /* now 'mp' is free */
495 setnilvalue(gval(mp
));
497 else { /* colliding node is in its own main position */
498 /* new node will go into free position */
500 gnext(f
) = cast_int((mp
+ gnext(mp
)) - f
); /* chain new position */
501 else lua_assert(gnext(f
) == 0);
502 gnext(mp
) = cast_int(f
- mp
);
506 setnodekey(L
, &mp
->i_key
, key
);
507 luaC_barrierback(L
, t
, key
);
508 lua_assert(ttisnil(gval(mp
)));
514 ** search function for integers
516 const TValue
*luaH_getint (Table
*t
, lua_Integer key
) {
517 /* (1 <= key && key <= t->sizearray) */
518 if (l_castS2U(key
) - 1 < t
->sizearray
)
519 return &t
->array
[key
- 1];
521 Node
*n
= hashint(t
, key
);
522 for (;;) { /* check whether 'key' is somewhere in the chain */
523 if (ttisinteger(gkey(n
)) && ivalue(gkey(n
)) == key
)
524 return gval(n
); /* that's it */
531 return luaO_nilobject
;
537 ** search function for short strings
539 const TValue
*luaH_getshortstr (Table
*t
, TString
*key
) {
540 Node
*n
= hashstr(t
, key
);
541 lua_assert(key
->tt
== LUA_TSHRSTR
);
542 for (;;) { /* check whether 'key' is somewhere in the chain */
543 const TValue
*k
= gkey(n
);
544 if (ttisshrstring(k
) && eqshrstr(tsvalue(k
), key
))
545 return gval(n
); /* that's it */
549 return luaO_nilobject
; /* not found */
557 ** "Generic" get version. (Not that generic: not valid for integers,
558 ** which may be in array part, nor for floats with integral values.)
560 static const TValue
*getgeneric (Table
*t
, const TValue
*key
) {
561 Node
*n
= mainposition(t
, key
);
562 for (;;) { /* check whether 'key' is somewhere in the chain */
563 if (luaV_rawequalobj(gkey(n
), key
))
564 return gval(n
); /* that's it */
568 return luaO_nilobject
; /* not found */
575 const TValue
*luaH_getstr (Table
*t
, TString
*key
) {
576 if (key
->tt
== LUA_TSHRSTR
)
577 return luaH_getshortstr(t
, key
);
578 else { /* for long strings, use generic case */
580 setsvalue(cast(lua_State
*, NULL
), &ko
, key
);
581 return getgeneric(t
, &ko
);
587 ** main search function
589 const TValue
*luaH_get (Table
*t
, const TValue
*key
) {
590 switch (ttype(key
)) {
591 case LUA_TSHRSTR
: return luaH_getshortstr(t
, tsvalue(key
));
592 case LUA_TNUMINT
: return luaH_getint(t
, ivalue(key
));
593 case LUA_TNIL
: return luaO_nilobject
;
596 if (luaV_tointeger(key
, &k
, 0)) /* index is int? */
597 return luaH_getint(t
, k
); /* use specialized version */
601 return getgeneric(t
, key
);
607 ** beware: when using this function you probably need to check a GC
608 ** barrier and invalidate the TM cache.
610 TValue
*luaH_set (lua_State
*L
, Table
*t
, const TValue
*key
) {
611 const TValue
*p
= luaH_get(t
, key
);
612 if (p
!= luaO_nilobject
)
613 return cast(TValue
*, p
);
614 else return luaH_newkey(L
, t
, key
);
618 void luaH_setint (lua_State
*L
, Table
*t
, lua_Integer key
, TValue
*value
) {
619 const TValue
*p
= luaH_getint(t
, key
);
621 if (p
!= luaO_nilobject
)
622 cell
= cast(TValue
*, p
);
626 cell
= luaH_newkey(L
, t
, &k
);
628 setobj2t(L
, cell
, value
);
632 static lua_Unsigned
unbound_search (Table
*t
, lua_Unsigned j
) {
633 lua_Unsigned i
= j
; /* i is zero or a present index */
635 /* find 'i' and 'j' such that i is present and j is not */
636 while (!ttisnil(luaH_getint(t
, j
))) {
638 if (j
> l_castS2U(LUA_MAXINTEGER
) / 2) { /* overflow? */
639 /* table was built with bad purposes: resort to linear search */
641 while (!ttisnil(luaH_getint(t
, i
))) i
++;
646 /* now do a binary search between them */
648 lua_Unsigned m
= (i
+j
)/2;
649 if (ttisnil(luaH_getint(t
, m
))) j
= m
;
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).
660 lua_Unsigned
luaH_getn (Table
*t
) {
661 unsigned int j
= t
->sizearray
;
662 if (j
> 0 && ttisnil(&t
->array
[j
- 1])) {
663 /* there is a boundary in the array part: (binary) search for it */
666 unsigned int m
= (i
+j
)/2;
667 if (ttisnil(&t
->array
[m
- 1])) j
= m
;
672 /* else must find a boundary in hash part */
673 else if (isdummy(t
)) /* hash part is empty? */
674 return j
; /* that is easy... */
675 else return unbound_search(t
, j
);
680 #if defined(LUA_DEBUG)
682 Node
*luaH_mainposition (const Table
*t
, const TValue
*key
) {
683 return mainposition(t
, key
);
686 int luaH_isdummy (const Table
*t
) { return isdummy(t
); }