** 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. */
| 400 | ** position), new key goes to an empty position. |
| 401 | */ |
| 402 | static TValue *newkey (lua_State *L, Table *t, const TValue *key) { |
| 403 | Node *mp = mainposition(t, key); |
| 404 | if (!ttisnil(gval(mp)) || mp == dummynode) { |
| 405 | Node *othern; |
| 406 | Node *n = getfreepos(t); /* get a free place */ |
| 407 | if (n == NULL) { /* cannot find a free place? */ |
| 408 | rehash(L, t, key); /* grow table */ |
| 409 | return luaH_set(L, t, key); /* re-insert key into grown table */ |
| 410 | } |
| 411 | lua_assert(n != dummynode); |
| 412 | othern = mainposition(t, key2tval(mp)); |
| 413 | if (othern != mp) { /* is colliding node out of its main position? */ |
| 414 | /* yes; move colliding node into free position */ |
| 415 | while (gnext(othern) != mp) othern = gnext(othern); /* find previous */ |
| 416 | gnext(othern) = n; /* redo the chain with `n' in place of `mp' */ |
| 417 | *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */ |
| 418 | gnext(mp) = NULL; /* now `mp' is free */ |
| 419 | setnilvalue(gval(mp)); |
| 420 | } |
| 421 | else { /* colliding node is in its own main position */ |
| 422 | /* new node will go into free position */ |
| 423 | gnext(n) = gnext(mp); /* chain new position */ |
| 424 | gnext(mp) = n; |
| 425 | mp = n; |
| 426 | } |
| 427 | } |
| 428 | gkey(mp)->value = key->value; gkey(mp)->tt = key->tt; |
| 429 | luaC_barriert(L, t, key); |
| 430 | lua_assert(ttisnil(gval(mp))); |
| 431 | return gval(mp); |
| 432 | } |
| 433 | |
| 434 | |
| 435 | /* |
no test coverage detected