bugGuile - Bugs: bug #22022, hashx-set! and -ref

 
 

bug #22022: hashx-set! and -ref

Submitter:  Gregory Marton <gremio>
Submitted:  Mon 14 Jan 2008 10:40:04 PM UTC
   
 
Category:  None Severity:  3 - Normal
Item Group:  None Status:  Fixed
Privacy:  Public Assigned to:  None
Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Sun 07 Dec 2008 04:51:29 PM UTC, comment #5: 

Grem's copyright assignment has now been processed, so his additional hashtable tests have been committed.

Neil Jerram <ossau>
Group administrator
Tue 29 Jan 2008 10:28:47 PM UTC, comment #4: 

(For the bug record...  The following has already been discussed on-list, but I don't know how to prevent savannah from CC'ing this to bug-guile.) Have committed (on 2008-01-18) a test and fix for the segfault.  Other failed test have been agreed to be invalid, as discussed below.  Will commit other, passing tests from Gregory Marton once copyright papers are in place.

Neil Jerram <ossau>
Group administrator
Thu 17 Jan 2008 10:45:57 PM UTC, comment #3: 

And here are all the remaining ones.  I've added a (pk ...) in each case, so the output from make check shows what the actual hash?-ref value was.

;;; (#f)
FAIL: hash.test: auto-resizing hashx: (equal? (quote eq) (pk (hashq-ref table 4)))

;;; (#f)
FAIL: hash.test: auto-resizing hashx: (equal? (quote equal) (pk (hashx-ref hash equal? table 1/32)))

;;; (#f)
FAIL: hash.test: auto-resizing hashx: (equal? (quote eqv) (pk (hashx-ref hashv eqv? table 1/33)))

;;; (#f)
FAIL: hash.test: auto-resizing hashx: (equal? (quote eq) (pk (hashx-ref hashq eq? table 34)))

These cases, together with the neighbouring ones that happen to pass, are actually out of scope, because the manual says (5.6.12.2 Hash Table Reference):

-----------manual------------
Like the association list functions, the hash table functions come in
several varieties, according to the equality test used for the keys.
Plain `hash-' functions use `equal?', `hashq-' functions use `eq?',
`hashv-' functions use `eqv?', and the `hashx-' functions use an
application supplied test.

   A single `make-hash-table' creates a hash table suitable for use
with any set of functions, but it's imperative that just one set is
then used consistently, or results will be unpredictable.
-----------manual------------

The rationale for this is what happens when a hash table is resized.  When that happens, the new hash buckets (vector indices) are recalculated, for all existing entries in the table, using the hash function that was specified on the call that caused the resize.  If that hash function is different from the hash that is later used to try to query particular entries, Guile can look in the wrong bucket, and the expected entry won't be found.

There's another case, too, where a rehash is done following GC, using a hash function that was stored at some point in the hashtable data structure.  But I haven't got right into that, because I think we already have enough to rule these test cases invalid.

What do you think?

Neil Jerram <ossau>
Group administrator
Thu 17 Jan 2008 09:57:36 PM UTC, comment #2: 

Another one:

   (pass-if (equal? "#<hash-table 34/61>"
    (with-output-to-string (lambda () (write table)))))))

Actual output here has 33 instead of 34.  I believe 33 is correct, because the additions to the hash table run from 2 up to 34, not from 1 up to 34.

Agree?

Neil Jerram <ossau>
Group administrator
Thu 17 Jan 2008 09:52:17 PM UTC, comment #1: 

I think I have a fix for the segfault, but now I'm seeing several other test failures.  Here's one...

 (pass-if (let ((table (make-hash-table)))
    (hashx-set! (lambda (k v) 1) assoc table 'foo 'bar)
    (equal?
     'bar (hashx-ref (lambda (k v) 1) assoc table 'baz))))

This one is wrong, isn't it?  It sets an entry with key 'foo, then queries the entry with key 'baz.  So the result, correctly, is #f.  What was your intention here?

Neil Jerram <ossau>
Group administrator
Mon 14 Jan 2008 10:40:04 PM UTC, original submission:  

Hashing using ones own hash functions does not survive a hash resize.

If the assoc function returns #t, a segfault or bus error results.

A patch to the test suite demonstrating these and testing a few other things is attached.

As an enhancement request, it would be nice for the common case to be able to pass a hash-function argument and assoc to make-hash-table or to have a (make-hashx-table hash assoc [size]), and in either case to remember the hash function so that resize works correctly.

Thanks,
Grem

Gregory Marton <gremio>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #14801:  hash.test.patch added by gremio (7KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by ossau (Posted a comment)
  • -email is unavailable- added by gremio (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2008-01-29 ossau StatusNone Fixed
        Open/ClosedOpen Closed
    2008-01-14 gremio Attached File- Added hash.test.patch, #14801

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code