| Line | Branch | Decision | Exec | Source |
|---|---|---|---|---|
| 1 | /* | |||
| 2 | ** $Id: ltable.c $ | |||
| 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 | ** MAXABITS is the largest integer such that MAXASIZE fits in an | |||
| 44 | ** unsigned int. | |||
| 45 | */ | |||
| 46 | #define MAXABITS cast_int(sizeof(int) * CHAR_BIT - 1) | |||
| 47 | ||||
| 48 | ||||
| 49 | /* | |||
| 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'. | |||
| 53 | */ | |||
| 54 | #define MAXASIZE luaM_limitN(1u << MAXABITS, TValue) | |||
| 55 | ||||
| 56 | /* | |||
| 57 | ** MAXHBITS is the largest integer such that 2^MAXHBITS fits in a | |||
| 58 | ** signed int. | |||
| 59 | */ | |||
| 60 | #define MAXHBITS (MAXABITS - 1) | |||
| 61 | ||||
| 62 | ||||
| 63 | /* | |||
| 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'. | |||
| 67 | */ | |||
| 68 | #define MAXHSIZE luaM_limitN(1u << MAXHBITS, Node) | |||
| 69 | ||||
| 70 | ||||
| 71 | /* | |||
| 72 | ** When the original hash value is good, hashing by a power of 2 | |||
| 73 | ** avoids the cost of '%'. | |||
| 74 | */ | |||
| 75 | #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) | |||
| 76 | ||||
| 77 | /* | |||
| 78 | ** for other types, it is better to avoid modulo by power of 2, as | |||
| 79 | ** they can have many 2 factors. | |||
| 80 | */ | |||
| 81 | #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) | |||
| 82 | ||||
| 83 | ||||
| 84 | #define hashstr(t,str) hashpow2(t, (str)->hash) | |||
| 85 | #define hashboolean(t,p) hashpow2(t, p) | |||
| 86 | ||||
| 87 | ||||
| 88 | #define hashpointer(t,p) hashmod(t, point2uint(p)) | |||
| 89 | ||||
| 90 | ||||
| 91 | #define dummynode (&dummynode_) | |||
| 92 | ||||
| 93 | static const Node dummynode_ = { | |||
| 94 | {{NULL}, LUA_VEMPTY, /* value's value and type */ | |||
| 95 | LUA_VNIL, 0, {NULL}} /* key type, next, and key value */ | |||
| 96 | }; | |||
| 97 | ||||
| 98 | ||||
| 99 | static const TValue absentkey = {ABSTKEYCONSTANT}; | |||
| 100 | ||||
| 101 | ||||
| 102 | /* | |||
| 103 | ** Hash for integers. To allow a good hash, use the remainder operator | |||
| 104 | ** ('%'). If integer fits as a non-negative int, compute an int | |||
| 105 | ** remainder, which is faster. Otherwise, use an unsigned-integer | |||
| 106 | ** remainder, which uses all bits and ensures a non-negative result. | |||
| 107 | */ | |||
| 108 | 704 | static Node *hashint (const Table *t, lua_Integer i) { | ||
| 109 | 704 | lua_Unsigned ui = l_castS2U(i); | ||
| 110 |
1/2✓ Branch 0 taken 704 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 704 times.
✗ Decision 'false' not taken.
|
704 | if (ui <= cast_uint(INT_MAX)) |
| 111 | 704 | return hashmod(t, cast_int(ui)); | ||
| 112 | else | |||
| 113 | ✗ | return hashmod(t, ui); | ||
| 114 | } | |||
| 115 | ||||
| 116 | ||||
| 117 | /* | |||
| 118 | ** Hash for floating-point numbers. | |||
| 119 | ** The main computation should be just | |||
| 120 | ** n = frexp(n, &i); return (n * INT_MAX) + i | |||
| 121 | ** but there are some numerical subtleties. | |||
| 122 | ** In a two-complement representation, INT_MAX does not has an exact | |||
| 123 | ** representation as a float, but INT_MIN does; because the absolute | |||
| 124 | ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the | |||
| 125 | ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal | |||
| 126 | ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when | |||
| 127 | ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with | |||
| 128 | ** INT_MIN. | |||
| 129 | */ | |||
| 130 | #if !defined(l_hashfloat) | |||
| 131 | 156 | static int l_hashfloat (lua_Number n) { | ||
| 132 | int i; | |||
| 133 | lua_Integer ni; | |||
| 134 | 156 | n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN); | ||
| 135 |
2/4✓ Branch 0 taken 156 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 156 times.
✗ Branch 3 not taken.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 156 times.
|
156 | if (!lua_numbertointeger(n, &ni)) { /* is 'n' inf/-inf/NaN? */ |
| 136 | lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL)); | |||
| 137 | ✗ | return 0; | ||
| 138 | } | |||
| 139 | else { /* normal case */ | |||
| 140 | 156 | unsigned int u = cast_uint(i) + cast_uint(ni); | ||
| 141 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 156 times.
|
156 | return cast_int(u <= cast_uint(INT_MAX) ? u : ~u); | |
| 142 | } | |||
| 143 | } | |||
| 144 | #endif | |||
| 145 | ||||
| 146 | ||||
| 147 | /* | |||
| 148 | ** returns the 'main' position of an element in a table (that is, | |||
| 149 | ** the index of its hash value). | |||
| 150 | */ | |||
| 151 | 136331 | static Node *mainpositionTV (const Table *t, const TValue *key) { | ||
| 152 |
4/9✓ Branch 0 taken 356 times.
✓ Branch 1 taken 156 times.
✓ Branch 2 taken 135703 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 116 times.
|
136331 | switch (ttypetag(key)) { | |
| 153 |
1/1✓ Decision 'true' taken 356 times.
|
356 | case LUA_VNUMINT: { | |
| 154 | 356 | lua_Integer i = ivalue(key); | ||
| 155 | 356 | return hashint(t, i); | ||
| 156 | } | |||
| 157 |
1/1✓ Decision 'true' taken 156 times.
|
156 | case LUA_VNUMFLT: { | |
| 158 | 156 | lua_Number n = fltvalue(key); | ||
| 159 | 156 | return hashmod(t, l_hashfloat(n)); | ||
| 160 | } | |||
| 161 |
1/1✓ Decision 'true' taken 135703 times.
|
135703 | case LUA_VSHRSTR: { | |
| 162 | 135703 | TString *ts = tsvalue(key); | ||
| 163 | 135703 | return hashstr(t, ts); | ||
| 164 | } | |||
| 165 | ✗ | case LUA_VLNGSTR: { | ||
| 166 | ✗ | TString *ts = tsvalue(key); | ||
| 167 | ✗ | return hashpow2(t, luaS_hashlongstr(ts)); | ||
| 168 | } | |||
| 169 | ✗ | case LUA_VFALSE: | ||
| 170 | ✗ | return hashboolean(t, 0); | ||
| 171 | ✗ | case LUA_VTRUE: | ||
| 172 | ✗ | return hashboolean(t, 1); | ||
| 173 | ✗ | case LUA_VLIGHTUSERDATA: { | ||
| 174 | ✗ | void *p = pvalue(key); | ||
| 175 | ✗ | return hashpointer(t, p); | ||
| 176 | } | |||
| 177 | ✗ | case LUA_VLCF: { | ||
| 178 | ✗ | lua_CFunction f = fvalue(key); | ||
| 179 | ✗ | return hashpointer(t, f); | ||
| 180 | } | |||
| 181 |
1/1✓ Decision 'true' taken 116 times.
|
116 | default: { | |
| 182 | 116 | GCObject *o = gcvalue(key); | ||
| 183 | 116 | return hashpointer(t, o); | ||
| 184 | } | |||
| 185 | } | |||
| 186 | } | |||
| 187 | ||||
| 188 | ||||
| 189 | 35333 | l_sinline Node *mainpositionfromnode (const Table *t, Node *nd) { | ||
| 190 | TValue key; | |||
| 191 | 35333 | getnodekey(cast(lua_State *, NULL), &key, nd); | ||
| 192 | 35333 | return mainpositionTV(t, &key); | ||
| 193 | } | |||
| 194 | ||||
| 195 | ||||
| 196 | /* | |||
| 197 | ** Check whether key 'k1' is equal to the key in node 'n2'. This | |||
| 198 | ** equality is raw, so there are no metamethods. Floats with integer | |||
| 199 | ** values have been normalized, so integers cannot be equal to | |||
| 200 | ** floats. It is assumed that 'eqshrstr' is simply pointer equality, so | |||
| 201 | ** that short strings are handled in the default case. | |||
| 202 | ** A true 'deadok' means to accept dead keys as equal to their original | |||
| 203 | ** values. All dead keys are compared in the default case, by pointer | |||
| 204 | ** identity. (Only collectable objects can produce dead keys.) Note that | |||
| 205 | ** dead long strings are also compared by identity. | |||
| 206 | ** Once a key is dead, its corresponding value may be collected, and | |||
| 207 | ** then another value can be created with the same address. If this | |||
| 208 | ** other value is given to 'next', 'equalkey' will signal a false | |||
| 209 | ** positive. In a regular traversal, this situation should never happen, | |||
| 210 | ** as all keys given to 'next' came from the table itself, and therefore | |||
| 211 | ** could not have been collected. Outside a regular traversal, we | |||
| 212 | ** have garbage in, garbage out. What is relevant is that this false | |||
| 213 | ** positive does not break anything. (In particular, 'next' will return | |||
| 214 | ** some other valid item on the table or nil.) | |||
| 215 | */ | |||
| 216 | 170 | static int equalkey (const TValue *k1, const Node *n2, int deadok) { | ||
| 217 |
3/4✓ Branch 0 taken 123 times.
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 123 times.
|
2/2✓ Decision 'true' taken 123 times.
✓ Decision 'false' taken 47 times.
|
170 | if ((rawtt(k1) != keytt(n2)) && /* not the same variants? */ |
| 218 | ✗ | !(deadok && keyisdead(n2) && iscollectable(k1))) | ||
| 219 | 123 | return 0; /* cannot be same key */ | ||
| 220 |
2/7✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 39 times.
|
47 | switch (keytt(n2)) { | |
| 221 | ✗ | case LUA_VNIL: case LUA_VFALSE: case LUA_VTRUE: | ||
| 222 | ✗ | return 1; | ||
| 223 | ✗ | case LUA_VNUMINT: | ||
| 224 | ✗ | return (ivalue(k1) == keyival(n2)); | ||
| 225 |
1/1✓ Decision 'true' taken 8 times.
|
8 | case LUA_VNUMFLT: | |
| 226 | 8 | return luai_numeq(fltvalue(k1), fltvalueraw(keyval(n2))); | ||
| 227 | ✗ | case LUA_VLIGHTUSERDATA: | ||
| 228 | ✗ | return pvalue(k1) == pvalueraw(keyval(n2)); | ||
| 229 | ✗ | case LUA_VLCF: | ||
| 230 | ✗ | return fvalue(k1) == fvalueraw(keyval(n2)); | ||
| 231 | ✗ | case ctb(LUA_VLNGSTR): | ||
| 232 | ✗ | return luaS_eqlngstr(tsvalue(k1), keystrval(n2)); | ||
| 233 |
1/1✓ Decision 'true' taken 39 times.
|
39 | default: | |
| 234 | 39 | return gcvalue(k1) == gcvalueraw(keyval(n2)); | ||
| 235 | } | |||
| 236 | } | |||
| 237 | ||||
| 238 | ||||
| 239 | /* | |||
| 240 | ** True if value of 'alimit' is equal to the real size of the array | |||
| 241 | ** part of table 't'. (Otherwise, the array part must be larger than | |||
| 242 | ** 'alimit'.) | |||
| 243 | */ | |||
| 244 | #define limitequalsasize(t) (isrealasize(t) || ispow2((t)->alimit)) | |||
| 245 | ||||
| 246 | ||||
| 247 | /* | |||
| 248 | ** Returns the real size of the 'array' array | |||
| 249 | */ | |||
| 250 | 42965 | LUAI_FUNC unsigned int luaH_realasize (const Table *t) { | ||
| 251 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 42965 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
1/2✓ Decision 'true' taken 42965 times.
✗ Decision 'false' not taken.
|
42965 | if (limitequalsasize(t)) |
| 252 | 42965 | return t->alimit; /* this is the size */ | ||
| 253 | else { | |||
| 254 | ✗ | unsigned int size = t->alimit; | ||
| 255 | /* compute the smallest power of 2 not smaller than 'n' */ | |||
| 256 | ✗ | size |= (size >> 1); | ||
| 257 | ✗ | size |= (size >> 2); | ||
| 258 | ✗ | size |= (size >> 4); | ||
| 259 | ✗ | size |= (size >> 8); | ||
| 260 | #if (UINT_MAX >> 14) > 3 /* unsigned int has more than 16 bits */ | |||
| 261 | ✗ | size |= (size >> 16); | ||
| 262 | #if (UINT_MAX >> 30) > 3 | |||
| 263 | size |= (size >> 32); /* unsigned int has more than 32 bits */ | |||
| 264 | #endif | |||
| 265 | #endif | |||
| 266 | ✗ | size++; | ||
| 267 | lua_assert(ispow2(size) && size/2 < t->alimit && t->alimit < size); | |||
| 268 | ✗ | return size; | ||
| 269 | } | |||
| 270 | } | |||
| 271 | ||||
| 272 | ||||
| 273 | /* | |||
| 274 | ** Check whether real size of the array is a power of 2. | |||
| 275 | ** (If it is not, 'alimit' cannot be changed to any other value | |||
| 276 | ** without changing the real size.) | |||
| 277 | */ | |||
| 278 | ✗ | static int ispow2realasize (const Table *t) { | ||
| 279 | ✗ | return (!isrealasize(t) || ispow2(t->alimit)); | ||
| 280 | } | |||
| 281 | ||||
| 282 | ||||
| 283 | 24637 | static unsigned int setlimittosize (Table *t) { | ||
| 284 | 24637 | t->alimit = luaH_realasize(t); | ||
| 285 | 24637 | setrealasize(t); | ||
| 286 | 24637 | return t->alimit; | ||
| 287 | } | |||
| 288 | ||||
| 289 | ||||
| 290 | #define limitasasize(t) check_exp(isrealasize(t), t->alimit) | |||
| 291 | ||||
| 292 | ||||
| 293 | ||||
| 294 | /* | |||
| 295 | ** "Generic" get version. (Not that generic: not valid for integers, | |||
| 296 | ** which may be in array part, nor for floats with integral values.) | |||
| 297 | ** See explanation about 'deadok' in function 'equalkey'. | |||
| 298 | */ | |||
| 299 | 147 | static const TValue *getgeneric (Table *t, const TValue *key, int deadok) { | ||
| 300 | 147 | Node *n = mainpositionTV(t, key); | ||
| 301 | for (;;) { /* check whether 'key' is somewhere in the chain */ | |||
| 302 |
2/2✓ Branch 1 taken 46 times.
✓ Branch 2 taken 124 times.
|
2/2✓ Decision 'true' taken 46 times.
✓ Decision 'false' taken 124 times.
|
170 | if (equalkey(key, n, deadok)) |
| 303 | 46 | return gval(n); /* that's it */ | ||
| 304 | else { | |||
| 305 | 124 | int nx = gnext(n); | ||
| 306 |
2/2✓ Branch 0 taken 101 times.
✓ Branch 1 taken 23 times.
|
2/2✓ Decision 'true' taken 101 times.
✓ Decision 'false' taken 23 times.
|
124 | if (nx == 0) |
| 307 | 101 | return &absentkey; /* not found */ | ||
| 308 | 23 | n += nx; | ||
| 309 | } | |||
| 310 | } | |||
| 311 | } | |||
| 312 | ||||
| 313 | ||||
| 314 | /* | |||
| 315 | ** returns the index for 'k' if 'k' is an appropriate key to live in | |||
| 316 | ** the array part of a table, 0 otherwise. | |||
| 317 | */ | |||
| 318 | 127 | static unsigned int arrayindex (lua_Integer k) { | ||
| 319 |
1/2✓ Branch 0 taken 127 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 127 times.
✗ Decision 'false' not taken.
|
127 | if (l_castS2U(k) - 1u < MAXASIZE) /* 'k' in [1, MAXASIZE]? */ |
| 320 | 127 | return cast_uint(k); /* 'key' is an appropriate array index */ | ||
| 321 | else | |||
| 322 | ✗ | return 0; | ||
| 323 | } | |||
| 324 | ||||
| 325 | ||||
| 326 | /* | |||
| 327 | ** returns the index of a 'key' for table traversals. First goes all | |||
| 328 | ** elements in the array part, then elements in the hash part. The | |||
| 329 | ** beginning of a traversal is signaled by 0. | |||
| 330 | */ | |||
| 331 | ✗ | static unsigned int findindex (lua_State *L, Table *t, TValue *key, | ||
| 332 | unsigned int asize) { | |||
| 333 | unsigned int i; | |||
| 334 | ✗ | if (ttisnil(key)) return 0; /* first iteration */ | ||
| 335 | ✗ | i = ttisinteger(key) ? arrayindex(ivalue(key)) : 0; | ||
| 336 | ✗ | if (i - 1u < asize) /* is 'key' inside array part? */ | ||
| 337 | ✗ | return i; /* yes; that's the index */ | ||
| 338 | else { | |||
| 339 | ✗ | const TValue *n = getgeneric(t, key, 1); | ||
| 340 | ✗ | if (l_unlikely(isabstkey(n))) | ||
| 341 | ✗ | luaG_runerror(L, "invalid key to 'next'"); /* key not found */ | ||
| 342 | ✗ | i = cast_int(nodefromval(n) - gnode(t, 0)); /* key index in hash table */ | ||
| 343 | /* hash elements are numbered after array ones */ | |||
| 344 | ✗ | return (i + 1) + asize; | ||
| 345 | } | |||
| 346 | } | |||
| 347 | ||||
| 348 | ||||
| 349 | ✗ | int luaH_next (lua_State *L, Table *t, StkId key) { | ||
| 350 | ✗ | unsigned int asize = luaH_realasize(t); | ||
| 351 | ✗ | unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */ | ||
| 352 | ✗ | for (; i < asize; i++) { /* try first array part */ | ||
| 353 | ✗ | if (!isempty(&t->array[i])) { /* a non-empty entry? */ | ||
| 354 | ✗ | setivalue(s2v(key), i + 1); | ||
| 355 | ✗ | setobj2s(L, key + 1, &t->array[i]); | ||
| 356 | ✗ | return 1; | ||
| 357 | } | |||
| 358 | } | |||
| 359 | ✗ | for (i -= asize; cast_int(i) < sizenode(t); i++) { /* hash part */ | ||
| 360 | ✗ | if (!isempty(gval(gnode(t, i)))) { /* a non-empty entry? */ | ||
| 361 | ✗ | Node *n = gnode(t, i); | ||
| 362 | ✗ | getnodekey(L, s2v(key), n); | ||
| 363 | ✗ | setobj2s(L, key + 1, gval(n)); | ||
| 364 | ✗ | return 1; | ||
| 365 | } | |||
| 366 | } | |||
| 367 | ✗ | return 0; /* no more elements */ | ||
| 368 | } | |||
| 369 | ||||
| 370 | ||||
| 371 | 21387 | static void freehash (lua_State *L, Table *t) { | ||
| 372 |
2/2✓ Branch 0 taken 14048 times.
✓ Branch 1 taken 7339 times.
|
2/2✓ Decision 'true' taken 14048 times.
✓ Decision 'false' taken 7339 times.
|
21387 | if (!isdummy(t)) |
| 373 | 14048 | luaM_freearray(L, t->node, cast_sizet(sizenode(t))); | ||
| 374 | 21387 | } | ||
| 375 | ||||
| 376 | ||||
| 377 | /* | |||
| 378 | ** {============================================================= | |||
| 379 | ** Rehash | |||
| 380 | ** ============================================================== | |||
| 381 | */ | |||
| 382 | ||||
| 383 | /* | |||
| 384 | ** Compute the optimal size for the array part of table 't'. 'nums' is a | |||
| 385 | ** "count array" where 'nums[i]' is the number of integers in the table | |||
| 386 | ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of | |||
| 387 | ** integer keys in the table and leaves with the number of keys that | |||
| 388 | ** will go to the array part; return the optimal size. (The condition | |||
| 389 | ** 'twotoi > 0' in the for loop stops the loop if 'twotoi' overflows.) | |||
| 390 | */ | |||
| 391 | 10187 | static unsigned int computesizes (unsigned int nums[], unsigned int *pna) { | ||
| 392 | int i; | |||
| 393 | unsigned int twotoi; /* 2^i (candidate for optimal size) */ | |||
| 394 | 10187 | unsigned int a = 0; /* number of elements smaller than 2^i */ | ||
| 395 | 10187 | unsigned int na = 0; /* number of elements to go to array part */ | ||
| 396 | 10187 | unsigned int optimal = 0; /* optimal size for array part */ | ||
| 397 | /* loop while keys can fill more than half of total size */ | |||
| 398 | 10187 | for (i = 0, twotoi = 1; | ||
| 399 |
3/4✓ Branch 0 taken 13280 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 3093 times.
✓ Branch 3 taken 10187 times.
|
13280 | twotoi > 0 && *pna > twotoi / 2; | |
| 400 | 3093 | i++, twotoi *= 2) { | ||
| 401 | 3093 | a += nums[i]; | ||
| 402 |
2/2✓ Branch 0 taken 2970 times.
✓ Branch 1 taken 123 times.
|
2/2✓ Decision 'true' taken 2970 times.
✓ Decision 'false' taken 123 times.
|
3093 | if (a > twotoi/2) { /* more than half elements present? */ |
| 403 | 2970 | optimal = twotoi; /* optimal size (till now) */ | ||
| 404 | 2970 | na = a; /* all elements up to 'optimal' will go to array part */ | ||
| 405 | } | |||
| 406 | } | |||
| 407 | lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal); | |||
| 408 | 10187 | *pna = na; | ||
| 409 | 10187 | return optimal; | ||
| 410 | } | |||
| 411 | ||||
| 412 | ||||
| 413 | 127 | static int countint (lua_Integer key, unsigned int *nums) { | ||
| 414 | 127 | unsigned int k = arrayindex(key); | ||
| 415 |
1/2✓ Branch 0 taken 127 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 127 times.
✗ Decision 'false' not taken.
|
127 | if (k != 0) { /* is 'key' an appropriate array index? */ |
| 416 | 127 | nums[luaO_ceillog2(k)]++; /* count as such */ | ||
| 417 | 127 | return 1; | ||
| 418 | } | |||
| 419 | else | |||
| 420 | ✗ | return 0; | ||
| 421 | } | |||
| 422 | ||||
| 423 | ||||
| 424 | /* | |||
| 425 | ** Count keys in array part of table 't': Fill 'nums[i]' with | |||
| 426 | ** number of keys that will go into corresponding slice and return | |||
| 427 | ** total number of non-nil keys. | |||
| 428 | */ | |||
| 429 | 10187 | static unsigned int numusearray (const Table *t, unsigned int *nums) { | ||
| 430 | int lg; | |||
| 431 | unsigned int ttlg; /* 2^lg */ | |||
| 432 | 10187 | unsigned int ause = 0; /* summation of 'nums' */ | ||
| 433 | 10187 | unsigned int i = 1; /* count to traverse all array keys */ | ||
| 434 | 10187 | unsigned int asize = limitasasize(t); /* real array size */ | ||
| 435 | /* traverse each slice */ | |||
| 436 |
1/2✓ Branch 0 taken 13157 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 13157 times.
✗ Decision 'false' not taken.
|
13157 | for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) { |
| 437 | 13157 | unsigned int lc = 0; /* counter */ | ||
| 438 | 13157 | unsigned int lim = ttlg; | ||
| 439 |
2/2✓ Branch 0 taken 10187 times.
✓ Branch 1 taken 2970 times.
|
2/2✓ Decision 'true' taken 10187 times.
✓ Decision 'false' taken 2970 times.
|
13157 | if (lim > asize) { |
| 440 | 10187 | lim = asize; /* adjust upper limit */ | ||
| 441 |
1/2✓ Branch 0 taken 10187 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 10187 times.
✗ Decision 'false' not taken.
|
10187 | if (i > lim) |
| 442 | 10187 | break; /* no more elements to count */ | ||
| 443 | } | |||
| 444 | /* count elements in range (2^(lg - 1), 2^lg] */ | |||
| 445 |
2/2✓ Branch 0 taken 2970 times.
✓ Branch 1 taken 2970 times.
|
2/2✓ Decision 'true' taken 2970 times.
✓ Decision 'false' taken 2970 times.
|
5940 | for (; i <= lim; i++) { |
| 446 |
1/2✓ Branch 0 taken 2970 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 2970 times.
✗ Decision 'false' not taken.
|
2970 | if (!isempty(&t->array[i-1])) |
| 447 | 2970 | lc++; | ||
| 448 | } | |||
| 449 | 2970 | nums[lg] += lc; | ||
| 450 | 2970 | ause += lc; | ||
| 451 | } | |||
| 452 | 10187 | return ause; | ||
| 453 | } | |||
| 454 | ||||
| 455 | ||||
| 456 | 10187 | static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) { | ||
| 457 | 10187 | int totaluse = 0; /* total number of elements */ | ||
| 458 | 10187 | int ause = 0; /* elements added to 'nums' (can go to array part) */ | ||
| 459 | 10187 | int i = sizenode(t); | ||
| 460 |
2/2✓ Branch 0 taken 44129 times.
✓ Branch 1 taken 10187 times.
|
2/2✓ Decision 'true' taken 44129 times.
✓ Decision 'false' taken 10187 times.
|
54316 | while (i--) { |
| 461 | 44129 | Node *n = &t->node[i]; | ||
| 462 |
2/2✓ Branch 0 taken 41159 times.
✓ Branch 1 taken 2970 times.
|
2/2✓ Decision 'true' taken 41159 times.
✓ Decision 'false' taken 2970 times.
|
44129 | if (!isempty(gval(n))) { |
| 463 |
2/2✓ Branch 0 taken 102 times.
✓ Branch 1 taken 41057 times.
|
2/2✓ Decision 'true' taken 102 times.
✓ Decision 'false' taken 41057 times.
|
41159 | if (keyisinteger(n)) |
| 464 | 102 | ause += countint(keyival(n), nums); | ||
| 465 | 41159 | totaluse++; | ||
| 466 | } | |||
| 467 | } | |||
| 468 | 10187 | *pna += ause; | ||
| 469 | 10187 | return totaluse; | ||
| 470 | } | |||
| 471 | ||||
| 472 | ||||
| 473 | /* | |||
| 474 | ** Creates an array for the hash part of a table with the given | |||
| 475 | ** size, or reuses the dummy node if size is zero. | |||
| 476 | ** The computation for size overflow is in two steps: the first | |||
| 477 | ** comparison ensures that the shift in the second one does not | |||
| 478 | ** overflow. | |||
| 479 | */ | |||
| 480 | 21387 | static void setnodevector (lua_State *L, Table *t, unsigned int size) { | ||
| 481 |
2/2✓ Branch 0 taken 7339 times.
✓ Branch 1 taken 14048 times.
|
2/2✓ Decision 'true' taken 7339 times.
✓ Decision 'false' taken 14048 times.
|
21387 | if (size == 0) { /* no elements to hash part? */ |
| 482 | 7339 | t->node = cast(Node *, dummynode); /* use common 'dummynode' */ | ||
| 483 | 7339 | t->lsizenode = 0; | ||
| 484 | 7339 | t->lastfree = NULL; /* signal that it is using dummy node */ | ||
| 485 | } | |||
| 486 | else { | |||
| 487 | int i; | |||
| 488 | 14048 | int lsize = luaO_ceillog2(size); | ||
| 489 |
2/4✓ Branch 0 taken 14048 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 14048 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 14048 times.
|
14048 | if (lsize > MAXHBITS || (1u << lsize) > MAXHSIZE) |
| 490 | ✗ | luaG_runerror(L, "table overflow"); | ||
| 491 | 14048 | size = twoto(lsize); | ||
| 492 | 14048 | t->node = luaM_newvector(L, size, Node); | ||
| 493 |
2/2✓ Branch 0 taken 101920 times.
✓ Branch 1 taken 14048 times.
|
2/2✓ Decision 'true' taken 101920 times.
✓ Decision 'false' taken 14048 times.
|
115968 | for (i = 0; i < cast_int(size); i++) { |
| 494 | 101920 | Node *n = gnode(t, i); | ||
| 495 | 101920 | gnext(n) = 0; | ||
| 496 | 101920 | setnilkey(n); | ||
| 497 | 101920 | setempty(gval(n)); | ||
| 498 | } | |||
| 499 | 14048 | t->lsizenode = cast_byte(lsize); | ||
| 500 | 14048 | t->lastfree = gnode(t, size); /* all positions are free */ | ||
| 501 | } | |||
| 502 | 21387 | } | ||
| 503 | ||||
| 504 | ||||
| 505 | /* | |||
| 506 | ** (Re)insert all elements from the hash part of 'ot' into table 't'. | |||
| 507 | */ | |||
| 508 | 14450 | static void reinsert (lua_State *L, Table *ot, Table *t) { | ||
| 509 | int j; | |||
| 510 | 14450 | int size = sizenode(ot); | ||
| 511 |
2/2✓ Branch 0 taken 48392 times.
✓ Branch 1 taken 14450 times.
|
2/2✓ Decision 'true' taken 48392 times.
✓ Decision 'false' taken 14450 times.
|
62842 | for (j = 0; j < size; j++) { |
| 512 | 48392 | Node *old = gnode(ot, j); | ||
| 513 |
2/2✓ Branch 0 taken 41159 times.
✓ Branch 1 taken 7233 times.
|
2/2✓ Decision 'true' taken 41159 times.
✓ Decision 'false' taken 7233 times.
|
48392 | if (!isempty(gval(old))) { |
| 514 | /* doesn't need barrier/invalidate cache, as entry was | |||
| 515 | already present in the table */ | |||
| 516 | TValue k; | |||
| 517 | 41159 | getnodekey(L, &k, old); | ||
| 518 | 41159 | luaH_set(L, t, &k, gval(old)); | ||
| 519 | } | |||
| 520 | } | |||
| 521 | 14450 | } | ||
| 522 | ||||
| 523 | ||||
| 524 | /* | |||
| 525 | ** Exchange the hash part of 't1' and 't2'. | |||
| 526 | */ | |||
| 527 | 14450 | static void exchangehashpart (Table *t1, Table *t2) { | ||
| 528 | 14450 | lu_byte lsizenode = t1->lsizenode; | ||
| 529 | 14450 | Node *node = t1->node; | ||
| 530 | 14450 | Node *lastfree = t1->lastfree; | ||
| 531 | 14450 | t1->lsizenode = t2->lsizenode; | ||
| 532 | 14450 | t1->node = t2->node; | ||
| 533 | 14450 | t1->lastfree = t2->lastfree; | ||
| 534 | 14450 | t2->lsizenode = lsizenode; | ||
| 535 | 14450 | t2->node = node; | ||
| 536 | 14450 | t2->lastfree = lastfree; | ||
| 537 | 14450 | } | ||
| 538 | ||||
| 539 | ||||
| 540 | /* | |||
| 541 | ** Resize table 't' for the new given sizes. Both allocations (for | |||
| 542 | ** the hash part and for the array part) can fail, which creates some | |||
| 543 | ** subtleties. If the first allocation, for the hash part, fails, an | |||
| 544 | ** error is raised and that is it. Otherwise, it copies the elements from | |||
| 545 | ** the shrinking part of the array (if it is shrinking) into the new | |||
| 546 | ** hash. Then it reallocates the array part. If that fails, the table | |||
| 547 | ** is in its original state; the function frees the new hash part and then | |||
| 548 | ** raises the allocation error. Otherwise, it sets the new hash part | |||
| 549 | ** into the table, initializes the new part of the array (if any) with | |||
| 550 | ** nils and reinserts the elements of the old hash back into the new | |||
| 551 | ** parts of the table. | |||
| 552 | */ | |||
| 553 | 14450 | void luaH_resize (lua_State *L, Table *t, unsigned int newasize, | ||
| 554 | unsigned int nhsize) { | |||
| 555 | unsigned int i; | |||
| 556 | Table newt; /* to keep the new hash part */ | |||
| 557 | 14450 | unsigned int oldasize = setlimittosize(t); | ||
| 558 | TValue *newarray; | |||
| 559 | /* create new hash part with appropriate size into 'newt' */ | |||
| 560 | 14450 | setnodevector(L, &newt, nhsize); | ||
| 561 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 14450 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 14450 times.
|
14450 | if (newasize < oldasize) { /* will array shrink? */ |
| 562 | ✗ | t->alimit = newasize; /* pretend array has new size... */ | ||
| 563 | ✗ | exchangehashpart(t, &newt); /* and new hash */ | ||
| 564 | /* re-insert into the new hash the elements from vanishing slice */ | |||
| 565 | ✗ | for (i = newasize; i < oldasize; i++) { | ||
| 566 | ✗ | if (!isempty(&t->array[i])) | ||
| 567 | ✗ | luaH_setint(L, t, i + 1, &t->array[i]); | ||
| 568 | } | |||
| 569 | ✗ | t->alimit = oldasize; /* restore current size... */ | ||
| 570 | ✗ | exchangehashpart(t, &newt); /* and hash (in case of errors) */ | ||
| 571 | } | |||
| 572 | /* allocate new array */ | |||
| 573 | 14450 | newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue); | ||
| 574 |
4/6✓ Branch 0 taken 12563 times.
✓ Branch 1 taken 1887 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12563 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 14450 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 14450 times.
|
14450 | if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ |
| 575 | ✗ | freehash(L, &newt); /* release new hash part */ | ||
| 576 | ✗ | luaM_error(L); /* raise error (with array unchanged) */ | ||
| 577 | } | |||
| 578 | /* allocation ok; initialize new part of the array */ | |||
| 579 | 14450 | exchangehashpart(t, &newt); /* 't' has the new hash ('newt' has the old) */ | ||
| 580 | 14450 | t->array = newarray; /* set new array part */ | ||
| 581 | 14450 | t->alimit = newasize; | ||
| 582 |
2/2✓ Branch 0 taken 1390 times.
✓ Branch 1 taken 14450 times.
|
2/2✓ Decision 'true' taken 1390 times.
✓ Decision 'false' taken 14450 times.
|
15840 | for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ |
| 583 | 1390 | setempty(&t->array[i]); | ||
| 584 | /* re-insert elements from old hash part into new parts */ | |||
| 585 | 14450 | reinsert(L, &newt, t); /* 'newt' now has the old hash */ | ||
| 586 | 14450 | freehash(L, &newt); /* free old hash part */ | ||
| 587 | 14450 | } | ||
| 588 | ||||
| 589 | ||||
| 590 | ✗ | void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) { | ||
| 591 | ✗ | int nsize = allocsizenode(t); | ||
| 592 | ✗ | luaH_resize(L, t, nasize, nsize); | ||
| 593 | ✗ | } | ||
| 594 | ||||
| 595 | /* | |||
| 596 | ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i | |||
| 597 | */ | |||
| 598 | 10187 | static void rehash (lua_State *L, Table *t, const TValue *ek) { | ||
| 599 | unsigned int asize; /* optimal size for array part */ | |||
| 600 | unsigned int na; /* number of keys in the array part */ | |||
| 601 | unsigned int nums[MAXABITS + 1]; | |||
| 602 | int i; | |||
| 603 | int totaluse; | |||
| 604 |
2/2✓ Branch 0 taken 325984 times.
✓ Branch 1 taken 10187 times.
|
2/2✓ Decision 'true' taken 325984 times.
✓ Decision 'false' taken 10187 times.
|
336171 | for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */ |
| 605 | 10187 | setlimittosize(t); | ||
| 606 | 10187 | na = numusearray(t, nums); /* count keys in array part */ | ||
| 607 | 10187 | totaluse = na; /* all those keys are integer keys */ | ||
| 608 | 10187 | totaluse += numusehash(t, nums, &na); /* count keys in hash part */ | ||
| 609 | /* count extra key */ | |||
| 610 |
2/2✓ Branch 0 taken 25 times.
✓ Branch 1 taken 10162 times.
|
2/2✓ Decision 'true' taken 25 times.
✓ Decision 'false' taken 10162 times.
|
10187 | if (ttisinteger(ek)) |
| 611 | 25 | na += countint(ivalue(ek), nums); | ||
| 612 | 10187 | totaluse++; | ||
| 613 | /* compute new size for array part */ | |||
| 614 | 10187 | asize = computesizes(nums, &na); | ||
| 615 | /* resize the table to new computed sizes */ | |||
| 616 | 10187 | luaH_resize(L, t, asize, totaluse - na); | ||
| 617 | 10187 | } | ||
| 618 | ||||
| 619 | ||||
| 620 | ||||
| 621 | /* | |||
| 622 | ** }============================================================= | |||
| 623 | */ | |||
| 624 | ||||
| 625 | ||||
| 626 | 6937 | Table *luaH_new (lua_State *L) { | ||
| 627 | 6937 | GCObject *o = luaC_newobj(L, LUA_VTABLE, sizeof(Table)); | ||
| 628 | 6937 | Table *t = gco2t(o); | ||
| 629 | 6937 | t->metatable = NULL; | ||
| 630 | 6937 | t->flags = cast_byte(maskflags); /* table has no metamethod fields */ | ||
| 631 | 6937 | t->array = NULL; | ||
| 632 | 6937 | t->alimit = 0; | ||
| 633 | 6937 | setnodevector(L, t, 0); | ||
| 634 | 6937 | return t; | ||
| 635 | } | |||
| 636 | ||||
| 637 | ||||
| 638 | 6937 | void luaH_free (lua_State *L, Table *t) { | ||
| 639 | 6937 | freehash(L, t); | ||
| 640 | 6937 | luaM_freearray(L, t->array, luaH_realasize(t)); | ||
| 641 | 6937 | luaM_free(L, t); | ||
| 642 | 6937 | } | ||
| 643 | ||||
| 644 | ||||
| 645 | 45520 | static Node *getfreepos (Table *t) { | ||
| 646 |
2/2✓ Branch 0 taken 42550 times.
✓ Branch 1 taken 2970 times.
|
2/2✓ Decision 'true' taken 42550 times.
✓ Decision 'false' taken 2970 times.
|
45520 | if (!isdummy(t)) { |
| 647 |
2/2✓ Branch 0 taken 72606 times.
✓ Branch 1 taken 7217 times.
|
2/2✓ Decision 'true' taken 72606 times.
✓ Decision 'false' taken 7217 times.
|
79823 | while (t->lastfree > t->node) { |
| 648 | 72606 | t->lastfree--; | ||
| 649 |
2/2✓ Branch 0 taken 35333 times.
✓ Branch 1 taken 37273 times.
|
2/2✓ Decision 'true' taken 35333 times.
✓ Decision 'false' taken 37273 times.
|
72606 | if (keyisnil(t->lastfree)) |
| 650 | 35333 | return t->lastfree; | ||
| 651 | } | |||
| 652 | } | |||
| 653 | 10187 | return NULL; /* could not find a free place */ | ||
| 654 | } | |||
| 655 | ||||
| 656 | ||||
| 657 | ||||
| 658 | /* | |||
| 659 | ** inserts a new key into a hash table; first, check whether key's main | |||
| 660 | ** position is free. If not, check whether colliding node is in its main | |||
| 661 | ** position or not: if it is not, move colliding node to an empty place and | |||
| 662 | ** put new key in its main position; otherwise (colliding node is in its main | |||
| 663 | ** position), new key goes to an empty position. | |||
| 664 | */ | |||
| 665 | 100851 | void luaH_newkey (lua_State *L, Table *t, const TValue *key, TValue *value) { | ||
| 666 | Node *mp; | |||
| 667 | TValue aux; | |||
| 668 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 100851 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 100851 times.
|
100851 | if (l_unlikely(ttisnil(key))) |
| 669 | ✗ | luaG_runerror(L, "table index is nil"); | ||
| 670 |
2/2✓ Branch 0 taken 68 times.
✓ Branch 1 taken 100783 times.
|
2/2✓ Decision 'true' taken 68 times.
✓ Decision 'false' taken 100783 times.
|
100851 | else if (ttisfloat(key)) { |
| 671 | 68 | lua_Number f = fltvalue(key); | ||
| 672 | lua_Integer k; | |||
| 673 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 68 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 68 times.
|
68 | if (luaV_flttointeger(f, &k, F2Ieq)) { /* does key fit in an integer? */ |
| 674 | ✗ | setivalue(&aux, k); | ||
| 675 | ✗ | key = &aux; /* insert it as an integer */ | ||
| 676 | } | |||
| 677 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 68 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 68 times.
|
68 | else if (l_unlikely(luai_numisnan(f))) |
| 678 | ✗ | luaG_runerror(L, "table index is NaN"); | ||
| 679 | } | |||
| 680 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 100851 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 100851 times.
|
100851 | if (ttisnil(value)) |
| 681 | 10187 | return; /* do not insert nil values */ | ||
| 682 | 100851 | mp = mainpositionTV(t, key); | ||
| 683 |
4/4✓ Branch 0 taken 58301 times.
✓ Branch 1 taken 42550 times.
✓ Branch 2 taken 2970 times.
✓ Branch 3 taken 55331 times.
|
2/2✓ Decision 'true' taken 45520 times.
✓ Decision 'false' taken 55331 times.
|
100851 | if (!isempty(gval(mp)) || isdummy(t)) { /* main position is taken? */ |
| 684 | Node *othern; | |||
| 685 | 45520 | Node *f = getfreepos(t); /* get a free place */ | ||
| 686 |
2/2✓ Branch 0 taken 10187 times.
✓ Branch 1 taken 35333 times.
|
2/2✓ Decision 'true' taken 10187 times.
✓ Decision 'false' taken 35333 times.
|
45520 | if (f == NULL) { /* cannot find a free place? */ |
| 687 | 10187 | rehash(L, t, key); /* grow table */ | ||
| 688 | /* whatever called 'newkey' takes care of TM cache */ | |||
| 689 | 10187 | luaH_set(L, t, key, value); /* insert key into grown table */ | ||
| 690 | 10187 | return; | ||
| 691 | } | |||
| 692 | lua_assert(!isdummy(t)); | |||
| 693 | 35333 | othern = mainpositionfromnode(t, mp); | ||
| 694 |
2/2✓ Branch 0 taken 7578 times.
✓ Branch 1 taken 27755 times.
|
2/2✓ Decision 'true' taken 7578 times.
✓ Decision 'false' taken 27755 times.
|
35333 | if (othern != mp) { /* is colliding node out of its main position? */ |
| 695 | /* yes; move colliding node into free position */ | |||
| 696 |
2/2✓ Branch 0 taken 1545 times.
✓ Branch 1 taken 7578 times.
|
2/2✓ Decision 'true' taken 1545 times.
✓ Decision 'false' taken 7578 times.
|
9123 | while (othern + gnext(othern) != mp) /* find previous */ |
| 697 | 1545 | othern += gnext(othern); | ||
| 698 | 7578 | gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */ | ||
| 699 | 7578 | *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */ | ||
| 700 |
2/2✓ Branch 0 taken 1226 times.
✓ Branch 1 taken 6352 times.
|
2/2✓ Decision 'true' taken 1226 times.
✓ Decision 'false' taken 6352 times.
|
7578 | if (gnext(mp) != 0) { |
| 701 | 1226 | gnext(f) += cast_int(mp - f); /* correct 'next' */ | ||
| 702 | 1226 | gnext(mp) = 0; /* now 'mp' is free */ | ||
| 703 | } | |||
| 704 | 7578 | setempty(gval(mp)); | ||
| 705 | } | |||
| 706 | else { /* colliding node is in its own main position */ | |||
| 707 | /* new node will go into free position */ | |||
| 708 |
2/2✓ Branch 0 taken 5887 times.
✓ Branch 1 taken 21868 times.
|
2/2✓ Decision 'true' taken 5887 times.
✓ Decision 'false' taken 21868 times.
|
27755 | if (gnext(mp) != 0) |
| 709 | 5887 | gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */ | ||
| 710 | else lua_assert(gnext(f) == 0); | |||
| 711 | 27755 | gnext(mp) = cast_int(f - mp); | ||
| 712 | 27755 | mp = f; | ||
| 713 | } | |||
| 714 | } | |||
| 715 | 90664 | setnodekey(L, mp, key); | ||
| 716 |
3/6✓ Branch 0 taken 90370 times.
✓ Branch 1 taken 294 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 90370 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
|
90664 | luaC_barrierback(L, obj2gco(t), key); | |
| 717 | lua_assert(isempty(gval(mp))); | |||
| 718 | 90664 | setobj2t(L, gval(mp), value); | ||
| 719 | } | |||
| 720 | ||||
| 721 | ||||
| 722 | /* | |||
| 723 | ** Search function for integers. If integer is inside 'alimit', get it | |||
| 724 | ** directly from the array part. Otherwise, if 'alimit' is not equal to | |||
| 725 | ** the real size of the array, key still can be in the array part. In | |||
| 726 | ** this case, try to avoid a call to 'luaH_realasize' when key is just | |||
| 727 | ** one more than the limit (so that it can be incremented without | |||
| 728 | ** changing the real size of the array). | |||
| 729 | */ | |||
| 730 | 390 | const TValue *luaH_getint (Table *t, lua_Integer key) { | ||
| 731 |
2/2✓ Branch 0 taken 42 times.
✓ Branch 1 taken 348 times.
|
2/2✓ Decision 'true' taken 42 times.
✓ Decision 'false' taken 348 times.
|
390 | if (l_castS2U(key) - 1u < t->alimit) /* 'key' in [1, t->alimit]? */ |
| 732 | 42 | return &t->array[key - 1]; | ||
| 733 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 348 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 348 times.
|
348 | else if (!limitequalsasize(t) && /* key still may be in the array part? */ |
| 734 | ✗ | (l_castS2U(key) == t->alimit + 1 || | ||
| 735 | ✗ | l_castS2U(key) - 1u < luaH_realasize(t))) { | ||
| 736 | ✗ | t->alimit = cast_uint(key); /* probably '#t' is here now */ | ||
| 737 | ✗ | return &t->array[key - 1]; | ||
| 738 | } | |||
| 739 | else { | |||
| 740 | 348 | Node *n = hashint(t, key); | ||
| 741 | for (;;) { /* check whether 'key' is somewhere in the chain */ | |||
| 742 |
4/4✓ Branch 0 taken 70 times.
✓ Branch 1 taken 337 times.
✓ Branch 2 taken 36 times.
✓ Branch 3 taken 34 times.
|
2/2✓ Decision 'true' taken 36 times.
✓ Decision 'false' taken 371 times.
|
407 | if (keyisinteger(n) && keyival(n) == key) |
| 743 | 36 | return gval(n); /* that's it */ | ||
| 744 | else { | |||
| 745 | 371 | int nx = gnext(n); | ||
| 746 |
2/2✓ Branch 0 taken 312 times.
✓ Branch 1 taken 59 times.
|
2/2✓ Decision 'true' taken 312 times.
✓ Decision 'false' taken 59 times.
|
371 | if (nx == 0) break; |
| 747 | 59 | n += nx; | ||
| 748 | } | |||
| 749 | } | |||
| 750 | 312 | return &absentkey; | ||
| 751 | } | |||
| 752 | } | |||
| 753 | ||||
| 754 | ||||
| 755 | /* | |||
| 756 | ** search function for short strings | |||
| 757 | */ | |||
| 758 | 123342 | const TValue *luaH_getshortstr (Table *t, TString *key) { | ||
| 759 | 123342 | Node *n = hashstr(t, key); | ||
| 760 | lua_assert(key->tt == LUA_VSHRSTR); | |||
| 761 | for (;;) { /* check whether 'key' is somewhere in the chain */ | |||
| 762 |
4/4✓ Branch 0 taken 82706 times.
✓ Branch 1 taken 60021 times.
✓ Branch 2 taken 16909 times.
✓ Branch 3 taken 65797 times.
|
2/2✓ Decision 'true' taken 16909 times.
✓ Decision 'false' taken 125818 times.
|
142727 | if (keyisshrstr(n) && eqshrstr(keystrval(n), key)) |
| 763 | 16909 | return gval(n); /* that's it */ | ||
| 764 | else { | |||
| 765 | 125818 | int nx = gnext(n); | ||
| 766 |
2/2✓ Branch 0 taken 106433 times.
✓ Branch 1 taken 19385 times.
|
2/2✓ Decision 'true' taken 106433 times.
✓ Decision 'false' taken 19385 times.
|
125818 | if (nx == 0) |
| 767 | 106433 | return &absentkey; /* not found */ | ||
| 768 | 19385 | n += nx; | ||
| 769 | } | |||
| 770 | } | |||
| 771 | } | |||
| 772 | ||||
| 773 | ||||
| 774 | 60009 | const TValue *luaH_getstr (Table *t, TString *key) { | ||
| 775 |
1/2✓ Branch 0 taken 60009 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 60009 times.
✗ Decision 'false' not taken.
|
60009 | if (key->tt == LUA_VSHRSTR) |
| 776 | 60009 | return luaH_getshortstr(t, key); | ||
| 777 | else { /* for long strings, use generic case */ | |||
| 778 | TValue ko; | |||
| 779 | ✗ | setsvalue(cast(lua_State *, NULL), &ko, key); | ||
| 780 | ✗ | return getgeneric(t, &ko, 0); | ||
| 781 | } | |||
| 782 | } | |||
| 783 | ||||
| 784 | ||||
| 785 | /* | |||
| 786 | ** main search function | |||
| 787 | */ | |||
| 788 | 58424 | const TValue *luaH_get (Table *t, const TValue *key) { | ||
| 789 |
4/5✓ Branch 0 taken 57932 times.
✓ Branch 1 taken 294 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 126 times.
✓ Branch 4 taken 72 times.
|
58424 | switch (ttypetag(key)) { | |
| 790 |
1/1✓ Decision 'true' taken 57932 times.
|
57932 | case LUA_VSHRSTR: return luaH_getshortstr(t, tsvalue(key)); | |
| 791 |
1/1✓ Decision 'true' taken 294 times.
|
294 | case LUA_VNUMINT: return luaH_getint(t, ivalue(key)); | |
| 792 | ✗ | case LUA_VNIL: return &absentkey; | ||
| 793 |
1/1✓ Decision 'true' taken 126 times.
|
126 | case LUA_VNUMFLT: { | |
| 794 | lua_Integer k; | |||
| 795 |
2/2✓ Branch 1 taken 51 times.
✓ Branch 2 taken 75 times.
|
2/2✓ Decision 'true' taken 51 times.
✓ Decision 'false' taken 75 times.
|
126 | if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */ |
| 796 | 51 | return luaH_getint(t, k); /* use specialized version */ | ||
| 797 | /* else... */ | |||
| 798 | } /* FALLTHROUGH */ | |||
| 799 | default: | |||
| 800 |
1/1✓ Decision 'true' taken 147 times.
|
147 | return getgeneric(t, key, 0); | |
| 801 | } | |||
| 802 | } | |||
| 803 | ||||
| 804 | ||||
| 805 | /* | |||
| 806 | ** Finish a raw "set table" operation, where 'slot' is where the value | |||
| 807 | ** should have been (the result of a previous "get table"). | |||
| 808 | ** Beware: when using this function you probably need to check a GC | |||
| 809 | ** barrier and invalidate the TM cache. | |||
| 810 | */ | |||
| 811 | 101921 | void luaH_finishset (lua_State *L, Table *t, const TValue *key, | ||
| 812 | const TValue *slot, TValue *value) { | |||
| 813 |
2/2✓ Branch 0 taken 100851 times.
✓ Branch 1 taken 1070 times.
|
2/2✓ Decision 'true' taken 100851 times.
✓ Decision 'false' taken 1070 times.
|
101921 | if (isabstkey(slot)) |
| 814 | 100851 | luaH_newkey(L, t, key, value); | ||
| 815 | else | |||
| 816 | 1070 | setobj2t(L, cast(TValue *, slot), value); | ||
| 817 | 101921 | } | ||
| 818 | ||||
| 819 | ||||
| 820 | /* | |||
| 821 | ** beware: when using this function you probably need to check a GC | |||
| 822 | ** barrier and invalidate the TM cache. | |||
| 823 | */ | |||
| 824 | 51346 | void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) { | ||
| 825 | 51346 | const TValue *slot = luaH_get(t, key); | ||
| 826 | 51346 | luaH_finishset(L, t, key, slot, value); | ||
| 827 | 51346 | } | ||
| 828 | ||||
| 829 | ||||
| 830 | ✗ | void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { | ||
| 831 | ✗ | const TValue *p = luaH_getint(t, key); | ||
| 832 | ✗ | if (isabstkey(p)) { | ||
| 833 | TValue k; | |||
| 834 | ✗ | setivalue(&k, key); | ||
| 835 | ✗ | luaH_newkey(L, t, &k, value); | ||
| 836 | } | |||
| 837 | else | |||
| 838 | ✗ | setobj2t(L, cast(TValue *, p), value); | ||
| 839 | ✗ | } | ||
| 840 | ||||
| 841 | ||||
| 842 | /* | |||
| 843 | ** Try to find a boundary in the hash part of table 't'. From the | |||
| 844 | ** caller, we know that 'j' is zero or present and that 'j + 1' is | |||
| 845 | ** present. We want to find a larger key that is absent from the | |||
| 846 | ** table, so that we can do a binary search between the two keys to | |||
| 847 | ** find a boundary. We keep doubling 'j' until we get an absent index. | |||
| 848 | ** If the doubling would overflow, we try LUA_MAXINTEGER. If it is | |||
| 849 | ** absent, we are ready for the binary search. ('j', being max integer, | |||
| 850 | ** is larger or equal to 'i', but it cannot be equal because it is | |||
| 851 | ** absent while 'i' is present; so 'j > i'.) Otherwise, 'j' is a | |||
| 852 | ** boundary. ('j + 1' cannot be a present integer key because it is | |||
| 853 | ** not a valid integer in Lua.) | |||
| 854 | */ | |||
| 855 | ✗ | static lua_Unsigned hash_search (Table *t, lua_Unsigned j) { | ||
| 856 | lua_Unsigned i; | |||
| 857 | ✗ | if (j == 0) j++; /* the caller ensures 'j + 1' is present */ | ||
| 858 | do { | |||
| 859 | ✗ | i = j; /* 'i' is a present index */ | ||
| 860 | ✗ | if (j <= l_castS2U(LUA_MAXINTEGER) / 2) | ||
| 861 | ✗ | j *= 2; | ||
| 862 | else { | |||
| 863 | ✗ | j = LUA_MAXINTEGER; | ||
| 864 | ✗ | if (isempty(luaH_getint(t, j))) /* t[j] not present? */ | ||
| 865 | ✗ | break; /* 'j' now is an absent index */ | ||
| 866 | else /* weird case */ | |||
| 867 | ✗ | return j; /* well, max integer is a boundary... */ | ||
| 868 | } | |||
| 869 | ✗ | } while (!isempty(luaH_getint(t, j))); /* repeat until an absent t[j] */ | ||
| 870 | /* i < j && t[i] present && t[j] absent */ | |||
| 871 | ✗ | while (j - i > 1u) { /* do a binary search between them */ | ||
| 872 | ✗ | lua_Unsigned m = (i + j) / 2; | ||
| 873 | ✗ | if (isempty(luaH_getint(t, m))) j = m; | ||
| 874 | ✗ | else i = m; | ||
| 875 | } | |||
| 876 | ✗ | return i; | ||
| 877 | } | |||
| 878 | ||||
| 879 | ||||
| 880 | ✗ | static unsigned int binsearch (const TValue *array, unsigned int i, | ||
| 881 | unsigned int j) { | |||
| 882 | ✗ | while (j - i > 1u) { /* binary search */ | ||
| 883 | ✗ | unsigned int m = (i + j) / 2; | ||
| 884 | ✗ | if (isempty(&array[m - 1])) j = m; | ||
| 885 | ✗ | else i = m; | ||
| 886 | } | |||
| 887 | ✗ | return i; | ||
| 888 | } | |||
| 889 | ||||
| 890 | ||||
| 891 | /* | |||
| 892 | ** Try to find a boundary in table 't'. (A 'boundary' is an integer index | |||
| 893 | ** such that t[i] is present and t[i+1] is absent, or 0 if t[1] is absent | |||
| 894 | ** and 'maxinteger' if t[maxinteger] is present.) | |||
| 895 | ** (In the next explanation, we use Lua indices, that is, with base 1. | |||
| 896 | ** The code itself uses base 0 when indexing the array part of the table.) | |||
| 897 | ** The code starts with 'limit = t->alimit', a position in the array | |||
| 898 | ** part that may be a boundary. | |||
| 899 | ** | |||
| 900 | ** (1) If 't[limit]' is empty, there must be a boundary before it. | |||
| 901 | ** As a common case (e.g., after 't[#t]=nil'), check whether 'limit-1' | |||
| 902 | ** is present. If so, it is a boundary. Otherwise, do a binary search | |||
| 903 | ** between 0 and limit to find a boundary. In both cases, try to | |||
| 904 | ** use this boundary as the new 'alimit', as a hint for the next call. | |||
| 905 | ** | |||
| 906 | ** (2) If 't[limit]' is not empty and the array has more elements | |||
| 907 | ** after 'limit', try to find a boundary there. Again, try first | |||
| 908 | ** the special case (which should be quite frequent) where 'limit+1' | |||
| 909 | ** is empty, so that 'limit' is a boundary. Otherwise, check the | |||
| 910 | ** last element of the array part. If it is empty, there must be a | |||
| 911 | ** boundary between the old limit (present) and the last element | |||
| 912 | ** (absent), which is found with a binary search. (This boundary always | |||
| 913 | ** can be a new limit.) | |||
| 914 | ** | |||
| 915 | ** (3) The last case is when there are no elements in the array part | |||
| 916 | ** (limit == 0) or its last element (the new limit) is present. | |||
| 917 | ** In this case, must check the hash part. If there is no hash part | |||
| 918 | ** or 'limit+1' is absent, 'limit' is a boundary. Otherwise, call | |||
| 919 | ** 'hash_search' to find a boundary in the hash part of the table. | |||
| 920 | ** (In those cases, the boundary is not inside the array part, and | |||
| 921 | ** therefore cannot be used as a new limit.) | |||
| 922 | */ | |||
| 923 | ✗ | lua_Unsigned luaH_getn (Table *t) { | ||
| 924 | ✗ | unsigned int limit = t->alimit; | ||
| 925 | ✗ | if (limit > 0 && isempty(&t->array[limit - 1])) { /* (1)? */ | ||
| 926 | /* there must be a boundary before 'limit' */ | |||
| 927 | ✗ | if (limit >= 2 && !isempty(&t->array[limit - 2])) { | ||
| 928 | /* 'limit - 1' is a boundary; can it be a new limit? */ | |||
| 929 | ✗ | if (ispow2realasize(t) && !ispow2(limit - 1)) { | ||
| 930 | ✗ | t->alimit = limit - 1; | ||
| 931 | ✗ | setnorealasize(t); /* now 'alimit' is not the real size */ | ||
| 932 | } | |||
| 933 | ✗ | return limit - 1; | ||
| 934 | } | |||
| 935 | else { /* must search for a boundary in [0, limit] */ | |||
| 936 | ✗ | unsigned int boundary = binsearch(t->array, 0, limit); | ||
| 937 | /* can this boundary represent the real size of the array? */ | |||
| 938 | ✗ | if (ispow2realasize(t) && boundary > luaH_realasize(t) / 2) { | ||
| 939 | ✗ | t->alimit = boundary; /* use it as the new limit */ | ||
| 940 | ✗ | setnorealasize(t); | ||
| 941 | } | |||
| 942 | ✗ | return boundary; | ||
| 943 | } | |||
| 944 | } | |||
| 945 | /* 'limit' is zero or present in table */ | |||
| 946 | ✗ | if (!limitequalsasize(t)) { /* (2)? */ | ||
| 947 | /* 'limit' > 0 and array has more elements after 'limit' */ | |||
| 948 | ✗ | if (isempty(&t->array[limit])) /* 'limit + 1' is empty? */ | ||
| 949 | ✗ | return limit; /* this is the boundary */ | ||
| 950 | /* else, try last element in the array */ | |||
| 951 | ✗ | limit = luaH_realasize(t); | ||
| 952 | ✗ | if (isempty(&t->array[limit - 1])) { /* empty? */ | ||
| 953 | /* there must be a boundary in the array after old limit, | |||
| 954 | and it must be a valid new limit */ | |||
| 955 | ✗ | unsigned int boundary = binsearch(t->array, t->alimit, limit); | ||
| 956 | ✗ | t->alimit = boundary; | ||
| 957 | ✗ | return boundary; | ||
| 958 | } | |||
| 959 | /* else, new limit is present in the table; check the hash part */ | |||
| 960 | } | |||
| 961 | /* (3) 'limit' is the last element and either is zero or present in table */ | |||
| 962 | lua_assert(limit == luaH_realasize(t) && | |||
| 963 | (limit == 0 || !isempty(&t->array[limit - 1]))); | |||
| 964 | ✗ | if (isdummy(t) || isempty(luaH_getint(t, cast(lua_Integer, limit + 1)))) | ||
| 965 | ✗ | return limit; /* 'limit + 1' is absent */ | ||
| 966 | else /* 'limit + 1' is also present */ | |||
| 967 | ✗ | return hash_search(t, limit); | ||
| 968 | } | |||
| 969 | ||||
| 970 | ||||
| 971 | ||||
| 972 | #if defined(LUA_DEBUG) | |||
| 973 | ||||
| 974 | /* export these functions for the test library */ | |||
| 975 | ||||
| 976 | Node *luaH_mainposition (const Table *t, const TValue *key) { | |||
| 977 | return mainpositionTV(t, key); | |||
| 978 | } | |||
| 979 | ||||
| 980 | #endif | |||
| 981 |