1 /* 2 ** $Id: ltable.c,v 2.72 2012/09/11 19:37:16 roberto Exp $ 3 ** Lua tables (hash) 4 ** See Copyright Notice in lua.h 5 */ 6 7 8 /* 9 ** Implementation of tables (aka arrays, objects, or hash tables). 10 ** Tables keep its elements in two parts: an array part and a hash part. 11 ** Non-negative integer keys are all candidates to be kept in the array 12 ** part. The actual size of the array is the largest `n' such that at 13 ** least half the slots between 0 and n are in use. 14 ** Hash uses a mix of chained scatter table with Brent's variation. 15 ** A main invariant of these tables is that, if an element is not 16 ** in its main position (i.e. the `original' position that its hash gives 17 ** to it), then the colliding element is in its own main position. 18 ** Hence even when the load factor reaches 100%, performance remains good. 19 */ 20 21 #include <string.h> 22 23 #define ltable_c 24 #define LUA_CORE 25 26 #include "lua.h" 27 28 #include "ldebug.h" 29 #include "ldo.h" 30 #include "lgc.h" 31 #include "lmem.h" 32 #include "lobject.h" 33 #include "lstate.h" 34 #include "lstring.h" 35 #include "ltable.h" 36 #include "lvm.h" 37 38 39 /* 40 ** max size of array part is 2^MAXBITS 41 */ 42 #if LUAI_BITSINT >= 32 43 #define MAXBITS 30 44 #else 45 #define MAXBITS (LUAI_BITSINT-2) 46 #endif 47 48 #define MAXASIZE (1 << MAXBITS) 49 50 51 #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) 52 53 #define hashstr(t,str) hashpow2(t, (str)->tsv.hash) 54 #define hashboolean(t,p) hashpow2(t, p) 55 56 57 /* 58 ** for some types, it is better to avoid modulus by power of 2, as 59 ** they tend to have many 2 factors. 60 */ 61 #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) 62 63 64 #define hashpointer(t,p) hashmod(t, IntPoint(p)) 65 66 67 #define dummynode (&dummynode_) 68 69 #define isdummy(n) ((n) == dummynode) 70 71 static const Node dummynode_ = { 72 {NILCONSTANT}, /* value */ 73 {{NILCONSTANT, NULL}} /* key */ 74 }; 75 76 77 /* 78 ** hash for lua_Numbers 79 */ 80 static Node *hashnum (const Table *t, lua_Number n) { 81 int i; 82 luai_hashnum(i, n); 83 if (i < 0) { 84 if (cast(unsigned int, i) == 0u - i) /* use unsigned to avoid overflows */ 85 i = 0; /* handle INT_MIN */ 86 i = -i; /* must be a positive value */ 87 } 88 return hashmod(t, i); 89 } 90 91 92 93 /* 94 ** returns the `main' position of an element in a table (that is, the index 95 ** of its hash value) 96 */ 97 static Node *mainposition (const Table *t, const TValue *key) { 98 switch (ttype(key)) { 99 case LUA_TNUMBER: 100 return hashnum(t, nvalue(key)); 101 case LUA_TLNGSTR: { 102 TString *s = rawtsvalue(key); 103 if (s->tsv.extra == 0) { /* no hash? */ 104 s->tsv.hash = luaS_hash(getstr(s), s->tsv.len, s->tsv.hash); 105 s->tsv.extra = 1; /* now it has its hash */ 106 } 107 return hashstr(t, rawtsvalue(key)); 108 } 109 case LUA_TSHRSTR: 110 return hashstr(t, rawtsvalue(key)); 111 case LUA_TBOOLEAN: 112 return hashboolean(t, bvalue(key)); 113 case LUA_TLIGHTUSERDATA: 114 return hashpointer(t, pvalue(key)); 115 case LUA_TLCF: 116 return hashpointer(t, fvalue(key)); 117 default: 118 return hashpointer(t, gcvalue(key)); 119 } 120 } 121 122 123 /* 124 ** returns the index for `key' if `key' is an appropriate key to live in 125 ** the array part of the table, -1 otherwise. 126 */ 127 static int arrayindex (const TValue *key) { 128 if (ttisnumber(key)) { 129 lua_Number n = nvalue(key); 130 int k; 131 lua_number2int(k, n); 132 if (luai_numeq(cast_num(k), n)) 133 return k; 134 } 135 return -1; /* `key' did not match some condition */ 136 } 137 138 139 /* 140 ** returns the index of a `key' for table traversals. First goes all 141 ** elements in the array part, then elements in the hash part. The 142 ** beginning of a traversal is signaled by -1. 143 */ 144 static int findindex (lua_State *L, Table *t, StkId key) { 145 int i; 146 if (ttisnil(key)) return -1; /* first iteration */ 147 i = arrayindex(key); 148 if (0 < i && i <= t->sizearray) /* is `key' inside array part? */ 149 return i-1; /* yes; that's the index (corrected to C) */ 150 else { 151 Node *n = mainposition(t, key); 152 for (;;) { /* check whether `key' is somewhere in the chain */ 153 /* key may be dead already, but it is ok to use it in `next' */ 154 if (luaV_rawequalobj(gkey(n), key) || 155 (ttisdeadkey(gkey(n)) && iscollectable(key) && 156 deadvalue(gkey(n)) == gcvalue(key))) { 157 i = cast_int(n - gnode(t, 0)); /* key index in hash table */ 158 /* hash elements are numbered after array ones */ 159 return i + t->sizearray; 160 } 161 else n = gnext(n); 162 if (n == NULL) 163 luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */ 164 } 165 } 166 } 167 168 169 int luaH_next (lua_State *L, Table *t, StkId key) { 170 int i = findindex(L, t, key); /* find original element */ 171 for (i++; i < t->sizearray; i++) { /* try first array part */ 172 if (!ttisnil(&t->array[i])) { /* a non-nil value? */ 173 setnvalue(key, cast_num(i+1)); 174 setobj2s(L, key+1, &t->array[i]); 175 return 1; 176 } 177 } 178 for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */ 179 if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */ 180 setobj2s(L, key, gkey(gnode(t, i))); 181 setobj2s(L, key+1, gval(gnode(t, i))); 182 return 1; 183 } 184 } 185 return 0; /* no more elements */ 186 } 187 188 189 /* 190 ** {============================================================= 191 ** Rehash 192 ** ============================================================== 193 */ 194 195 196 static int computesizes (int nums[], int *narray) { 197 int i; 198 int twotoi; /* 2^i */ 199 int a = 0; /* number of elements smaller than 2^i */ 200 int na = 0; /* number of elements to go to array part */ 201 int n = 0; /* optimal size for array part */ 202 for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) { 203 if (nums[i] > 0) { 204 a += nums[i]; 205 if (a > twotoi/2) { /* more than half elements present? */ 206 n = twotoi; /* optimal size (till now) */ 207 na = a; /* all elements smaller than n will go to array part */ 208 } 209 } 210 if (a == *narray) break; /* all elements already counted */ 211 } 212 *narray = n; 213 lua_assert(*narray/2 <= na && na <= *narray); 214 return na; 215 } 216 217 218 static int countint (const TValue *key, int *nums) { 219 int k = arrayindex(key); 220 if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ 221 nums[luaO_ceillog2(k)]++; /* count as such */ 222 return 1; 223 } 224 else 225 return 0; 226 } 227 228 229 static int numusearray (const Table *t, int *nums) { 230 int lg; 231 int ttlg; /* 2^lg */ 232 int ause = 0; /* summation of `nums' */ 233 int i = 1; /* count to traverse all array keys */ 234 for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) { /* for each slice */ 235 int lc = 0; /* counter */ 236 int lim = ttlg; 237 if (lim > t->sizearray) { 238 lim = t->sizearray; /* adjust upper limit */ 239 if (i > lim) 240 break; /* no more elements to count */ 241 } 242 /* count elements in range (2^(lg-1), 2^lg] */ 243 for (; i <= lim; i++) { 244 if (!ttisnil(&t->array[i-1])) 245 lc++; 246 } 247 nums[lg] += lc; 248 ause += lc; 249 } 250 return ause; 251 } 252 253 254 static int numusehash (const Table *t, int *nums, int *pnasize) { 255 int totaluse = 0; /* total number of elements */ 256 int ause = 0; /* summation of `nums' */ 257 int i = sizenode(t); 258 while (i--) { 259 Node *n = &t->node[i]; 260 if (!ttisnil(gval(n))) { 261 ause += countint(gkey(n), nums); 262 totaluse++; 263 } 264 } 265 *pnasize += ause; 266 return totaluse; 267 } 268 269 270 static void setarrayvector (lua_State *L, Table *t, int size) { 271 int i; 272 luaM_reallocvector(L, t->array, t->sizearray, size, TValue); 273 for (i=t->sizearray; i<size; i++) 274 setnilvalue(&t->array[i]); 275 t->sizearray = size; 276 } 277 278 279 static void setnodevector (lua_State *L, Table *t, int size) { 280 int lsize; 281 if (size == 0) { /* no elements to hash part? */ 282 t->node = cast(Node *, dummynode); /* use common `dummynode' */ 283 lsize = 0; 284 } 285 else { 286 int i; 287 lsize = luaO_ceillog2(size); 288 if (lsize > MAXBITS) 289 luaG_runerror(L, "table overflow"); 290 size = twoto(lsize); 291 t->node = luaM_newvector(L, size, Node); 292 for (i=0; i<size; i++) { 293 Node *n = gnode(t, i); 294 gnext(n) = NULL; 295 setnilvalue(gkey(n)); 296 setnilvalue(gval(n)); 297 } 298 } 299 t->lsizenode = cast_byte(lsize); 300 t->lastfree = gnode(t, size); /* all positions are free */ 301 } 302 303 304 void luaH_resize (lua_State *L, Table *t, int nasize, int nhsize) { 305 int i; 306 int oldasize = t->sizearray; 307 int oldhsize = t->lsizenode; 308 Node *nold = t->node; /* save old hash ... */ 309 if (nasize > oldasize) /* array part must grow? */ 310 setarrayvector(L, t, nasize); 311 /* create new hash part with appropriate size */ 312 setnodevector(L, t, nhsize); 313 if (nasize < oldasize) { /* array part must shrink? */ 314 t->sizearray = nasize; 315 /* re-insert elements from vanishing slice */ 316 for (i=nasize; i<oldasize; i++) { 317 if (!ttisnil(&t->array[i])) 318 luaH_setint(L, t, i + 1, &t->array[i]); 319 } 320 /* shrink array */ 321 luaM_reallocvector(L, t->array, oldasize, nasize, TValue); 322 } 323 /* re-insert elements from hash part */ 324 for (i = twoto(oldhsize) - 1; i >= 0; i--) { 325 Node *old = nold+i; 326 if (!ttisnil(gval(old))) { 327 /* doesn't need barrier/invalidate cache, as entry was 328 already present in the table */ 329 setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old)); 330 } 331 } 332 if (!isdummy(nold)) 333 luaM_freearray(L, nold, cast(size_t, twoto(oldhsize))); /* free old array */ 334 } 335 336 337 void luaH_resizearray (lua_State *L, Table *t, int nasize) { 338 int nsize = isdummy(t->node) ? 0 : sizenode(t); 339 luaH_resize(L, t, nasize, nsize); 340 } 341 342 343 static void rehash (lua_State *L, Table *t, const TValue *ek) { 344 int nasize, na; 345 int nums[MAXBITS+1]; /* nums[i] = number of keys with 2^(i-1) < k <= 2^i */ 346 int i; 347 int totaluse; 348 for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* reset counts */ 349 nasize = numusearray(t, nums); /* count keys in array part */ 350 totaluse = nasize; /* all those keys are integer keys */ 351 totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */ 352 /* count extra key */ 353 nasize += countint(ek, nums); 354 totaluse++; 355 /* compute new size for array part */ 356 na = computesizes(nums, &nasize); 357 /* resize the table to new computed sizes */ 358 luaH_resize(L, t, nasize, totaluse - na); 359 } 360 361 362 363 /* 364 ** }============================================================= 365 */ 366 367 368 Table *luaH_new (lua_State *L) { 369 Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h; 370 t->metatable = NULL; 371 t->flags = cast_byte(~0); 372 t->array = NULL; 373 t->sizearray = 0; 374 setnodevector(L, t, 0); 375 return t; 376 } 377 378 379 void luaH_free (lua_State *L, Table *t) { 380 if (!isdummy(t->node)) 381 luaM_freearray(L, t->node, cast(size_t, sizenode(t))); 382 luaM_freearray(L, t->array, t->sizearray); 383 luaM_free(L, t); 384 } 385 386 387 static Node *getfreepos (Table *t) { 388 while (t->lastfree > t->node) { 389 t->lastfree--; 390 if (ttisnil(gkey(t->lastfree))) 391 return t->lastfree; 392 } 393 return NULL; /* could not find a free place */ 394 } 395 396 397 398 /* 399 ** inserts a new key into a hash table; first, check whether key's main 400 ** position is free. If not, check whether colliding node is in its main 401 ** position or not: if it is not, move colliding node to an empty place and 402 ** put new key in its main position; otherwise (colliding node is in its main 403 ** position), new key goes to an empty position. 404 */ 405 TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) { 406 Node *mp; 407 if (ttisnil(key)) luaG_runerror(L, "table index is nil"); 408 else if (ttisnumber(key) && luai_numisnan(L, nvalue(key))) 409 luaG_runerror(L, "table index is NaN"); 410 mp = mainposition(t, key); 411 if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */ 412 Node *othern; 413 Node *n = getfreepos(t); /* get a free place */ 414 if (n == NULL) { /* cannot find a free place? */ 415 rehash(L, t, key); /* grow table */ 416 /* whatever called 'newkey' take care of TM cache and GC barrier */ 417 return luaH_set(L, t, key); /* insert key into grown table */ 418 } 419 lua_assert(!isdummy(n)); 420 othern = mainposition(t, gkey(mp)); 421 if (othern != mp) { /* is colliding node out of its main position? */ 422 /* yes; move colliding node into free position */ 423 while (gnext(othern) != mp) othern = gnext(othern); /* find previous */ 424 gnext(othern) = n; /* redo the chain with `n' in place of `mp' */ 425 *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */ 426 gnext(mp) = NULL; /* now `mp' is free */ 427 setnilvalue(gval(mp)); 428 } 429 else { /* colliding node is in its own main position */ 430 /* new node will go into free position */ 431 gnext(n) = gnext(mp); /* chain new position */ 432 gnext(mp) = n; 433 mp = n; 434 } 435 } 436 setobj2t(L, gkey(mp), key); 437 luaC_barrierback(L, obj2gco(t), key); 438 lua_assert(ttisnil(gval(mp))); 439 return gval(mp); 440 } 441 442 443 /* 444 ** search function for integers 445 */ 446 const TValue *luaH_getint (Table *t, int key) { 447 /* (1 <= key && key <= t->sizearray) */ 448 if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) 449 return &t->array[key-1]; 450 else { 451 lua_Number nk = cast_num(key); 452 Node *n = hashnum(t, nk); 453 do { /* check whether `key' is somewhere in the chain */ 454 if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk)) 455 return gval(n); /* that's it */ 456 else n = gnext(n); 457 } while (n); 458 return luaO_nilobject; 459 } 460 } 461 462 463 /* 464 ** search function for short strings 465 */ 466 const TValue *luaH_getstr (Table *t, TString *key) { 467 Node *n = hashstr(t, key); 468 lua_assert(key->tsv.tt == LUA_TSHRSTR); 469 do { /* check whether `key' is somewhere in the chain */ 470 if (ttisshrstring(gkey(n)) && eqshrstr(rawtsvalue(gkey(n)), key)) 471 return gval(n); /* that's it */ 472 else n = gnext(n); 473 } while (n); 474 return luaO_nilobject; 475 } 476 477 478 /* 479 ** main search function 480 */ 481 const TValue *luaH_get (Table *t, const TValue *key) { 482 switch (ttype(key)) { 483 case LUA_TSHRSTR: return luaH_getstr(t, rawtsvalue(key)); 484 case LUA_TNIL: return luaO_nilobject; 485 case LUA_TNUMBER: { 486 int k; 487 lua_Number n = nvalue(key); 488 lua_number2int(k, n); 489 if (luai_numeq(cast_num(k), n)) /* index is int? */ 490 return luaH_getint(t, k); /* use specialized version */ 491 /* else go through */ 492 } 493 default: { 494 Node *n = mainposition(t, key); 495 do { /* check whether `key' is somewhere in the chain */ 496 if (luaV_rawequalobj(gkey(n), key)) 497 return gval(n); /* that's it */ 498 else n = gnext(n); 499 } while (n); 500 return luaO_nilobject; 501 } 502 } 503 } 504 505 506 /* 507 ** beware: when using this function you probably need to check a GC 508 ** barrier and invalidate the TM cache. 509 */ 510 TValue *luaH_set (lua_State *L, Table *t, const TValue *key) { 511 const TValue *p = luaH_get(t, key); 512 if (p != luaO_nilobject) 513 return cast(TValue *, p); 514 else return luaH_newkey(L, t, key); 515 } 516 517 518 void luaH_setint (lua_State *L, Table *t, int key, TValue *value) { 519 const TValue *p = luaH_getint(t, key); 520 TValue *cell; 521 if (p != luaO_nilobject) 522 cell = cast(TValue *, p); 523 else { 524 TValue k; 525 setnvalue(&k, cast_num(key)); 526 cell = luaH_newkey(L, t, &k); 527 } 528 setobj2t(L, cell, value); 529 } 530 531 532 static int unbound_search (Table *t, unsigned int j) { 533 unsigned int i = j; /* i is zero or a present index */ 534 j++; 535 /* find `i' and `j' such that i is present and j is not */ 536 while (!ttisnil(luaH_getint(t, j))) { 537 i = j; 538 j *= 2; 539 if (j > cast(unsigned int, MAX_INT)) { /* overflow? */ 540 /* table was built with bad purposes: resort to linear search */ 541 i = 1; 542 while (!ttisnil(luaH_getint(t, i))) i++; 543 return i - 1; 544 } 545 } 546 /* now do a binary search between them */ 547 while (j - i > 1) { 548 unsigned int m = (i+j)/2; 549 if (ttisnil(luaH_getint(t, m))) j = m; 550 else i = m; 551 } 552 return i; 553 } 554 555 556 /* 557 ** Try to find a boundary in table `t'. A `boundary' is an integer index 558 ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil). 559 */ 560 int luaH_getn (Table *t) { 561 unsigned int j = t->sizearray; 562 if (j > 0 && ttisnil(&t->array[j - 1])) { 563 /* there is a boundary in the array part: (binary) search for it */ 564 unsigned int i = 0; 565 while (j - i > 1) { 566 unsigned int m = (i+j)/2; 567 if (ttisnil(&t->array[m - 1])) j = m; 568 else i = m; 569 } 570 return i; 571 } 572 /* else must find a boundary in hash part */ 573 else if (isdummy(t->node)) /* hash part is empty? */ 574 return j; /* that is easy... */ 575 else return unbound_search(t, j); 576 } 577 578 579 580 #if defined(LUA_DEBUG) 581 582 Node *luaH_mainposition (const Table *t, const TValue *key) { 583 return mainposition(t, key); 584 } 585 586 int luaH_isdummy (Node *n) { return isdummy(n); } 587 588 #endif 589
