MPS issue job003820

TitleScheme interpreter table_set is wrong
Assigned userGareth Rees
DescriptionIn the example Scheme interpreter, the functions for setting a key in a table (table_set and table_try_set) do not check for staleness in the case that the key was not found in the table. This is wrong: the key might already be in the table, but hashed under its old address. Adding the key under the hash for its new address results in the key being present twice in the table, violating the invariant for hash tables, and causing trouble at the next rehash.

Here's an interaction illustrating the problem:

    > (define ht (make-eq-hashtable))
    > (hashtable-set! ht 'a 1)
    > (gc)
    > (hashtable-set! ht 'a 2)
    > ht
    #[hashtable (a 2) (a 1)]

At this point the hashtable incorrectly has two entries for the key 'a.

    > (gc)
    > (hashtable-ref ht 'a #f)
    Assertion failed: (b->key == NULL), function table_rehash, file scheme.c, line 932.
AnalysisAdd an isstale() test if the key is not found in the table. Make sure the documentation [1] [2] is updated.
How foundinspection
Evidence[1] <>
[2] <>
Created byGareth Rees
Created on2014-05-27 15:14:24
Last modified byGareth Rees
Last modified on2014-09-29 20:28:56
History2014-05-27 GDR Created.


Change Effect Date User Description
187079 closed 2014-09-28 23:32:37 Gareth Rees Must test a key for staleness with respect to a location dependency before setting it (not just before looking it up or deleting it).