Bug#493064: libtree-redblack-perl: broken insert with custom comparison function
Soules, Craig
craig.soules at hp.com
Thu Jul 31 06:17:17 UTC 2008
Package: libtree-redblack-perl
Version: 0.3-6
Severity: important
Tags: upstream patch
Forwarded: http://rt.cpan.org/Ticket/Display.html?id=19431
[dam: I am resending this as a proper bug report]
Hello,
There's a serious flaw in this RedBlack.pm implementation. Specifically, on line 140:
140: if ($this->{'cmp'} ? $this->{'cmp'}->($key, $node->key) < 0
141: : $key lt $parent->key) {
142: $parent->left($node);
If you are using a custom compare function, it needs to compare $key
to $parent->key, not $node->key. This causes errors in insertion,
which makes the tree completely useless.
Hopefully someone can fix this in a future release!
Thanks,
Craig
This is reported[1] upstream two years ago and the report has a patch.
I am going to apply it and upload soon.
[1] http://rt.cpan.org/Ticket/Display.html?id=19431
Thanks for the headsup,
dam
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
Url : http://lists.alioth.debian.org/pipermail/pkg-perl-maintainers/attachments/20080731/400cd2b7/attachment.pgp
More information about the pkg-perl-maintainers
mailing list