** inserts a new key into a hash table; first, check whether key's main ** position is free. If not, check whether colliding node is in its main ** position or not: if it is not, move colliding node to an empty place and ** put new key in its main position; otherwise (colliding node is in its main ** position), new key goes to an empty position. */
| 430 | ** position), new key goes to an empty position. |
| 431 | */ |
| 432 | static TValue *newkey (lua_State *L, Table *t, const TValue *key) { |
| 433 | Node *mp = mainposition(t, key); |
| 434 | if (!ttisnil(gval(mp)) || mp == dummynode) { |
| 435 | Node *othern; |
| 436 | Node *n = getfreepos(t); /* get a free place */ |
| 437 | if (n == NULL) { /* cannot find a free place? */ |
| 438 | rehash(L, t, key); /* grow table */ |
| 439 | return luaH_set(L, t, key); /* re-insert key into grown table */ |
| 440 | } |
| 441 | lua_assert(n != dummynode); |
| 442 | othern = mainposition(t, key2tval(mp)); |
| 443 | if (othern != mp) { /* is colliding node out of its main position? */ |
| 444 | /* yes; move colliding node into free position */ |
| 445 | while (gnext(othern) != mp) othern = gnext(othern); /* find previous */ |
| 446 | gnext(othern) = n; /* redo the chain with `n' in place of `mp' */ |
| 447 | *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */ |
| 448 | gnext(mp) = NULL; /* now `mp' is free */ |
| 449 | setnilvalue(gval(mp)); |
| 450 | } |
| 451 | else { /* colliding node is in its own main position */ |
| 452 | /* new node will go into free position */ |
| 453 | gnext(n) = gnext(mp); /* chain new position */ |
| 454 | gnext(mp) = n; |
| 455 | mp = n; |
| 456 | } |
| 457 | } |
| 458 | gkey(mp)->value = key->value; gkey(mp)->tt = key->tt; |
| 459 | luaC_barriert(L, t, key); |
| 460 | lua_assert(ttisnil(gval(mp))); |
| 461 | return gval(mp); |
| 462 | } |
| 463 | |
| 464 | |
| 465 | /* |
no test coverage detected