libstdc++/7057: Operator== on hashtables doesn't appear to work correctly (patch included)

libstdc++/7057: Operator== on hashtables doesn't appear to work correctly (patch included)

[steev]

>Number:         7057
>Category:       libstdc++
>Synopsis:       Operator== on hashtables doesn't appear to work correctly (patch included)
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Mon Jun 17 09:56:00 PDT 2002
>Closed-Date:
>Last-Modified:
>Originator:     Steev Wilcox
>Release:        3.1
>Organization:
>Environment:
Solaris 8
>Description:
The operator== on hashtables in stl_hashtable.h compares the two tables for exact equivalence - the list in each bin must have the same entries in the same order.  This will generally fail, because the keys in a hashtable aren't ordered by definition, so the lists are in an effectively random order.  The equality operator on x==y needs to check each element in x's list for being in y's list, and also check that there are the same number of elements in each (that's necessary and sufficient).

I've included a patch for this, in file stl_hashtable_h_diff in archive gccbug3.tar.gz.  There's also a C++ file hashtest.cpp which shows the comparison failing under the library shipped with GCC 3.1, and shows it working with this patch.  The software that we're developing also works with this patch applied.  I can't post this patch directly, because (1) I don't have time to exhaustively it, although we've done some testing, and (2) my mail server is blocked from posting to GCC mailing lists. :-(

Please email me if the attachment doesn't get added by the web page.

Regards and thanks, Steev
>How-To-Repeat:
Create two hash-tables, one in the reverse order of the other, but with the same data.  Sometimes the == operator works on these, sometimes it doesn't.  File hashtest.cpp in the attached .tar.gz file shows this with 10 string->int hashmaps of 10 entries each.
>Fix:
Apply stl_hashtable_h_diff to ext/stl_hashtable.h
It's just an algorithm change.
>Release-Note:
>Audit-Trail:
>Unformatted:
----gnatsweb-attachment----
Content-Type: application/x-gzip-compressed; name="gccbug3.tar.gz"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="gccbug3.tar.gz"

H4sIAFERDj0AA+1XS2/jNhDOtQb8H2a3aCL5KSlOXES2LwV66GK3hy56CbYCLdORYpkyRCoN6vV/
71CkXnl4u0A32QM/IBIznBl+oxmS44jwSFAuRuFud/KN4LiOM51MThzHcacXnnzjSL8d59yduifO
9MI5n7jOZOKgvjdx3RNwvhWhJnIuSAZwwgWld0f0UG29fglCL4sfYxYm+YrCLE65yCjZLrqdWoii
mN20RPRejCOsmmBLdq2JkItVEi9R1u3kHM2AkS3lOxJSwCn/sTQIblgehPf3vrR5Qg7dzr7bAYhZ
EjP0Ev9DAwHF6oqZFaaMCwgjkvWA21K3MADIGY9vGF1BkuKakQ9KvE4zsKK540OP+9Dvc7s0AIhg
Dhe9CPpyTgkP6pVRkWdMr29FdjF7kKQBBN3uEiLoLEwI5/BxgcFmeahozj5Cb9FgpSNIdzQjIs0s
WweAampwilFAMSxZ7cvVMxozQbMd/huEhIuZcrawuO0rogdfGshRi1ibUZXSL5JSmnBaMqqpNDPA
R6EcWnbN4sGHaa/f9P2SLHR63AHokdfmtSNxNsNpKW/yUml0F1iV68hvyjwp46XsOf5Nv6e7Oogy
vzoY6d3ajdZxxoUNfxWe8X9OUX9lN8tRRlbUXrejfGFZwB+4uizfImop2JKYWbbeP0XVS2mMOlj7
MczAle9+334QqtzWukYGaLEA4h+ZXOpJ9byjIUauvmRTayGDFpQJDpYkWoZT0bpVtG6RlpzHkSYG
9e7UdVDuzIb1RllvdFCbyrZhjfbQn8MZOcPtbWWErSwbfgLv0q78HcpBSfb69hN63pINDWRIFh/c
2u1z4asCINcNxyrR0n9TqLJdMSqDK5I7BBf/bqvJZe1u85S7zQN3mnK8BusNWATmc1jadh1zLmA2
g7e/kjjBU5OoWnkrZbF8ULZKtCeacPrI7vd3R2yKtXWhO6p8X/viMyjARRLInS3IMqFBFKzi/7/L
kf3f5fP9nzd1yv7PmXoe6rkT7ABN//cS6PV6MM55Nk7SkCRj3cyNb/r94d35WPZ67QpJk9Uo+uF9
yuC3nIE7Bffyyr24upiAh5nsDIfDr3H3yJX389W5p1z12oBlmibV7Tqf69u1cjUL/iTJIHhHpSFc
us7g0nNAWtYntb6ig4Cp41oOZviMhDsK3gfLPNxQwUdSzbJld4gK2B/qoy74kK5oD9XDPHPRwUO7
a9T+5D+h7Gll77Hym/omA790fXpa2pUjd7hA0zuSyFNbzZUSv7rgimVrcpUZw88+aDKpzOWMXdnv
D+W1g1eEdvT5s9av1fQxviZ4C6jFD80eGTuqQnwAKKqhyMT5FHA8/P4zMR7DLxENN8DxxwgklN2I
CNI1JDEX/AvZeuVM9MsAPqR/4w8iGUTK6BnH65pui96LZBRbChARhRQfmTYp4jn+Lato/WfjsrW3
vX6D2rDBOs3ZqjJqcS2X/m8JKm3qr+v5R75lqb5vGNaf8/n9ZDf0961FH4SiCr2psMSfz5um6FCN
61HRfzVdNRd8KqOH43vstS8QAwMDAwMDAwMDAwMDAwMDAwMDAwOD7xL/AtOHzpMAKAAA

Re: libstdc++/7057: Operator== on hashtables doesn't appear to work correctly (patch included)

[bkoz]

Synopsis: Operator== on hashtables doesn't appear to work correctly (patch included)

State-Changed-From-To: feedback->closed
State-Changed-By: bkoz
State-Changed-When: Thu Jul  4 09:59:50 2002
State-Changed-Why:
    Fix in.

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=7057

Re: libstdc++/7057: Operator== on hashtables doesn't appear to work correctly (patch included)

[bkoz]

Synopsis: Operator== on hashtables doesn't appear to work correctly (patch included)

Responsible-Changed-From-To: unassigned->bkoz
Responsible-Changed-By: bkoz
Responsible-Changed-When: Wed Jul  3 17:50:07 2002
Responsible-Changed-Why:
    Mine.
State-Changed-From-To: open->feedback
State-Changed-By: bkoz
State-Changed-When: Wed Jul  3 17:50:07 2002
State-Changed-Why:
    This is in now, thanks!
    
    -benjamin

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=7057