** 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. Return 0 if ** could not insert key (could not find
| 857 | ** could not insert key (could not find a free space). |
| 858 | */ |
| 859 | static int insertkey (Table *t, const TValue *key, TValue *value) { |
| 860 | Node *mp = mainpositionTV(t, key); |
| 861 | /* table cannot already contain the key */ |
| 862 | lua_assert(isabstkey(getgeneric(t, key, 0))); |
| 863 | if (!isempty(gval(mp)) || isdummy(t)) { /* main position is taken? */ |
| 864 | Node *othern; |
| 865 | Node *f = getfreepos(t); /* get a free place */ |
| 866 | if (f == NULL) /* cannot find a free place? */ |
| 867 | return 0; |
| 868 | lua_assert(!isdummy(t)); |
| 869 | othern = mainpositionfromnode(t, mp); |
| 870 | if (othern != mp) { /* is colliding node out of its main position? */ |
| 871 | /* yes; move colliding node into free position */ |
| 872 | while (othern + gnext(othern) != mp) /* find previous */ |
| 873 | othern += gnext(othern); |
| 874 | gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */ |
| 875 | *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */ |
| 876 | if (gnext(mp) != 0) { |
| 877 | gnext(f) += cast_int(mp - f); /* correct 'next' */ |
| 878 | gnext(mp) = 0; /* now 'mp' is free */ |
| 879 | } |
| 880 | setempty(gval(mp)); |
| 881 | } |
| 882 | else { /* colliding node is in its own main position */ |
| 883 | /* new node will go into free position */ |
| 884 | if (gnext(mp) != 0) |
| 885 | gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */ |
| 886 | else lua_assert(gnext(f) == 0); |
| 887 | gnext(mp) = cast_int(f - mp); |
| 888 | mp = f; |
| 889 | } |
| 890 | } |
| 891 | setnodekey(mp, key); |
| 892 | lua_assert(isempty(gval(mp))); |
| 893 | setobj2t(cast(lua_State *, 0), gval(mp), value); |
| 894 | return 1; |
| 895 | } |
| 896 | |
| 897 | |
| 898 | /* |
no test coverage detected