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