public inbox for glibc-bugs@sourceware.org help / color / mirror / Atom feed
* [Bug libc/6966] New: hsearch almost always probes the same index when using the secondary hash @ 2008-10-19 1:30 bugzilla at bsb dot me dot uk 2008-10-19 1:34 ` [Bug libc/6966] " bugzilla at bsb dot me dot uk 2008-11-01 15:39 ` drepper at redhat dot com 0 siblings, 2 replies; 4+ messages in thread From: bugzilla at bsb dot me dot uk @ 2008-10-19 1:30 UTC (permalink / raw) To: glibc-bugs hsearch references Kunth vol. 3 6.4 on "open addressing" but the code does implement the algorithm from Knuth. Instead of generating the second hash from the first, the code generates the second hash from the first index. Because this hash is then used to step the index, the result is that the first index generated is (almost) always the same. This partly defeats the purpose of using a secondary hash. I say "almost" because it happens for all but 2 of the possible index values in any given table. For example, in a table of size 11, all secondary probes will start at index 10 unless the inital hash produced 9 or 10. This was reported on news:comp.lang.c by James Dow Allen and I decided to check on it. I have a simple patch but I am not sure of the procedure for posting patches to glibc. -- Summary: hsearch almost always probes the same index when using the secondary hash Product: glibc Version: 2.8 Status: NEW Severity: minor Priority: P3 Component: libc AssignedTo: drepper at redhat dot com ReportedBy: bugzilla at bsb dot me dot uk CC: glibc-bugs at sources dot redhat dot com http://sourceware.org/bugzilla/show_bug.cgi?id=6966 ------- You are receiving this mail because: ------- You are on the CC list for the bug, or are watching someone who is. ^ permalink raw reply [flat|nested] 4+ messages in thread
* [Bug libc/6966] hsearch almost always probes the same index when using the secondary hash 2008-10-19 1:30 [Bug libc/6966] New: hsearch almost always probes the same index when using the secondary hash bugzilla at bsb dot me dot uk @ 2008-10-19 1:34 ` bugzilla at bsb dot me dot uk 2008-11-01 15:39 ` drepper at redhat dot com 1 sibling, 0 replies; 4+ messages in thread From: bugzilla at bsb dot me dot uk @ 2008-10-19 1:34 UTC (permalink / raw) To: glibc-bugs ------- Additional Comments From bugzilla at bsb dot me dot uk 2008-10-19 01:33 ------- Created an attachment (id=3006) --> (http://sourceware.org/bugzilla/attachment.cgi?id=3006&action=view) Suggested fix. The patch suggests two related changes. First, that idx be set from hval without reducing havl % htab->size. hval2 can now be derived from hval without generating the same probe sequence all the time. Secondly, a new variable must be used to detect the wrap-around, since hval no longer contains the initial value of idx. -- http://sourceware.org/bugzilla/show_bug.cgi?id=6966 ------- You are receiving this mail because: ------- You are on the CC list for the bug, or are watching someone who is. ^ permalink raw reply [flat|nested] 4+ messages in thread
* [Bug libc/6966] hsearch almost always probes the same index when using the secondary hash 2008-10-19 1:30 [Bug libc/6966] New: hsearch almost always probes the same index when using the secondary hash bugzilla at bsb dot me dot uk 2008-10-19 1:34 ` [Bug libc/6966] " bugzilla at bsb dot me dot uk @ 2008-11-01 15:39 ` drepper at redhat dot com 1 sibling, 0 replies; 4+ messages in thread From: drepper at redhat dot com @ 2008-11-01 15:39 UTC (permalink / raw) To: glibc-bugs ------- Additional Comments From drepper at redhat dot com 2008-11-01 15:37 ------- Applied to cvs. -- What |Removed |Added ---------------------------------------------------------------------------- Status|NEW |RESOLVED Resolution| |FIXED http://sourceware.org/bugzilla/show_bug.cgi?id=6966 ------- You are receiving this mail because: ------- You are on the CC list for the bug, or are watching someone who is. ^ permalink raw reply [flat|nested] 4+ messages in thread
[parent not found: <bug-6966-131@http.sourceware.org/bugzilla/>]
* [Bug libc/6966] hsearch almost always probes the same index when using the secondary hash [not found] <bug-6966-131@http.sourceware.org/bugzilla/> @ 2014-07-02 6:15 ` fweimer at redhat dot com 0 siblings, 0 replies; 4+ messages in thread From: fweimer at redhat dot com @ 2014-07-02 6:15 UTC (permalink / raw) To: glibc-bugs https://sourceware.org/bugzilla/show_bug.cgi?id=6966 Florian Weimer <fweimer at redhat dot com> changed: What |Removed |Added ---------------------------------------------------------------------------- Flags| |security- -- You are receiving this mail because: You are on the CC list for the bug. ^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2014-07-02 6:15 UTC | newest] Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2008-10-19 1:30 [Bug libc/6966] New: hsearch almost always probes the same index when using the secondary hash bugzilla at bsb dot me dot uk 2008-10-19 1:34 ` [Bug libc/6966] " bugzilla at bsb dot me dot uk 2008-11-01 15:39 ` drepper at redhat dot com [not found] <bug-6966-131@http.sourceware.org/bugzilla/> 2014-07-02 6:15 ` fweimer at redhat dot com
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).