** 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. ** ** The Value field is left unconstruct
| 894 | ** The Value field is left unconstructed. |
| 895 | */ |
| 896 | Node *NewKey(const KT key) |
| 897 | { |
| 898 | Node *mp = MainPosition(key); |
| 899 | if (!mp->IsNil()) |
| 900 | { |
| 901 | Node *othern; |
| 902 | Node *n = GetFreePos(); /* get a free place */ |
| 903 | if (n == NULL) /* cannot find a free place? */ |
| 904 | { |
| 905 | Rehash(); /* grow table */ |
| 906 | return NewKey(key); /* re-insert key into grown table */ |
| 907 | } |
| 908 | othern = MainPosition(mp->Pair.Key); |
| 909 | if (othern != mp) /* is colliding node out of its main position? */ |
| 910 | { /* yes; move colliding node into free position */ |
| 911 | while (othern->Next != mp) /* find previous */ |
| 912 | { |
| 913 | othern = othern->Next; |
| 914 | } |
| 915 | othern->Next = n; /* redo the chain with 'n' in place of 'mp' */ |
| 916 | CopyNode(n, mp); /* copy colliding node into free pos. (mp->Next also goes) */ |
| 917 | mp->Next = NULL; /* now 'mp' is free */ |
| 918 | } |
| 919 | else /* colliding node is in its own main position */ |
| 920 | { /* new node will go into free position */ |
| 921 | n->Next = mp->Next; /* chain new position */ |
| 922 | mp->Next = n; |
| 923 | mp = n; |
| 924 | } |
| 925 | } |
| 926 | else |
| 927 | { |
| 928 | mp->Next = NULL; |
| 929 | } |
| 930 | ++NumUsed; |
| 931 | ::new(&mp->Pair.Key) KT(key); |
| 932 | return mp; |
| 933 | } |
| 934 | |
| 935 | void DelKey(const KT key) |
| 936 | { |