Bug #81199 for Set-IntervalTree:

Thu Nov 15 09:06:54 2012 DAVEWEBB [...] cpan.org - Ticket created

Hi, I'm using Set::IntervalTree in Net::IPAddress::Filter as it's by far the smallest and fastest way I've found for dealing with large IP address filter lists. In testing I found that fetch(2^31, 2^31) reports a false positive if the tree has at least one interval, even if that interval doesn't span 2^31 The following code shows it happening. #!/usr/bin/perl use strict; use warnings; use Data::Dumper; use Set::IntervalTree; my $tree = Set::IntervalTree->new(); my $min = 1; my $max = 2; my $test = 2_147_483_648; # 2^31 - Shouldn't match but does print Dumper( $tree->fetch( $test, $test ) ); # prints [] $tree->insert( "$min - $max", $min, $max ); print Dumper( $tree->fetch( $test - 1, $test - 1 ) ); # prints [] print Dumper( $tree->fetch( $test, $test ) ); # prints [ '1 - 2' ] print Dumper( $tree->fetch( $test + 1, $test + 1 ) ); # prints [] print Dumper( $tree->fetch( $test - 1, $test + 1 ) ); # prints [] exit; My C is non-existent at best, and I couldn't spot where this bug arises. Thanks for this light and fast module. Dave

Thu Nov 15 13:17:22 2012 BENBOOTH [...] cpan.org - Correspondence added

Thanks for catching that! There was a type mismatch in the XS versus the interval_tree.h module. The XS was using 32-bit int's and the interval_tree.h module was using long's. I'm going to update the module to 0.03 today after I fix a few other things. On Thu Nov 15 09:06:54 2012, DAVEWEBB wrote: Show quoted text

> Hi, > > I'm using Set::IntervalTree in Net::IPAddress::Filter as it's by far the > smallest and fastest way I've found for dealing with large IP address > filter lists. > > In testing I found that fetch(2^31, 2^31) reports a false positive if > the tree has at least one interval, even if that interval doesn't span 2^31 > > The following code shows it happening. > > #!/usr/bin/perl > > use strict; > use warnings; > > use Data::Dumper; > use Set::IntervalTree; > > my $tree = Set::IntervalTree->new(); > my $min = 1; > my $max = 2; > my $test = 2_147_483_648; # 2^31 - Shouldn't match but does > > print Dumper( $tree->fetch( $test, $test ) ); # prints [] > > $tree->insert( "$min - $max", $min, $max ); > > print Dumper( $tree->fetch( $test - 1, $test - 1 ) ); # prints [] > print Dumper( $tree->fetch( $test, $test ) ); # prints [ '1 - > 2' ] > print Dumper( $tree->fetch( $test + 1, $test + 1 ) ); # prints [] > print Dumper( $tree->fetch( $test - 1, $test + 1 ) ); # prints [] > > > > exit; > > My C is non-existent at best, and I couldn't spot where this bug arises. > > Thanks for this light and fast module. > > Dave

Thu Nov 15 13:17:23 2012 The RT System itself - Status changed from 'new' to 'open'

Thu Nov 15 13:31:55 2012 BENBOOTH [...] cpan.org - Status changed from 'open' to 'resolved'

Fri Nov 16 11:40:37 2012 DAVEWEBB [...] cpan.org - Correspondence added

Much obliged Ben. I just tried to install 0.3 on my CentOS 6.3 box, but it failed with: cc1plus: error: unrecognized command line option "-std=c++11" I figure this is because CentOS ships with gcc version 4.4.6. I've also got gcc version 4.7.0 installed alongside it, so I changed "$CC = 'c++';" to "$CC = 'g++47';" in Makefile.PL and retried the process. It's now dying with the following: IntervalTree.c: In function ‘void boot_Set__IntervalTree(PerlInterpreter*, CV*)’: IntervalTree.c:606:5: error: unable to find string literal operator ‘operator"" SVf’ I'll have more of a play tomorrow. Cheers, Dave On Thu Nov 15 13:17:22 2012, BENBOOTH wrote: Show quoted text

> Thanks for catching that! There was a type mismatch in the XS versus > the interval_tree.h > module. The XS was using 32-bit int's and the interval_tree.h module > was using long's. I'm > going to update the module to 0.03 today after I fix a few other > things. > > On Thu Nov 15 09:06:54 2012, DAVEWEBB wrote:

> > Hi, > > > > I'm using Set::IntervalTree in Net::IPAddress::Filter as it's by far

> the

> > smallest and fastest way I've found for dealing with large IP

> address

> > filter lists. > > > > In testing I found that fetch(2^31, 2^31) reports a false positive

> if

> > the tree has at least one interval, even if that interval doesn't

> span 2^31

> > > > The following code shows it happening. > > > > #!/usr/bin/perl > > > > use strict; > > use warnings; > > > > use Data::Dumper; > > use Set::IntervalTree; > > > > my $tree = Set::IntervalTree->new(); > > my $min = 1; > > my $max = 2; > > my $test = 2_147_483_648; # 2^31 - Shouldn't match but

> does

> > > > print Dumper( $tree->fetch( $test, $test ) ); # prints [] > > > > $tree->insert( "$min - $max", $min, $max ); > > > > print Dumper( $tree->fetch( $test - 1, $test - 1 ) ); # prints [] > > print Dumper( $tree->fetch( $test, $test ) ); # prints [

> '1 -

> > 2' ] > > print Dumper( $tree->fetch( $test + 1, $test + 1 ) ); # prints [] > > print Dumper( $tree->fetch( $test - 1, $test + 1 ) ); # prints [] > > > > > > > > exit; > > > > My C is non-existent at best, and I couldn't spot where this bug

> arises.

> > > > Thanks for this light and fast module. > > > > Dave

>

Fri Nov 16 11:40:37 2012 The RT System itself - Status changed from 'resolved' to 'open'

Fri Nov 16 13:26:53 2012 benwbooth [...] gmail.com - Correspondence added

Subject:	Re: [rt.cpan.org #81199]
Date:	Fri, 16 Nov 2012 10:26:40 -0800
To:	bug-Set-IntervalTree [...] rt.cpan.org
From:	Ben Booth <benwbooth [...] gmail.com>

I finally bit the bullet and wrote a custom smart pointer wrapper class for SV values. This removes the dependency on C++11 and should allow the module to compile on older versions of GCC. I ran through the tests with valgrind and didn't notice any memory errors, but if you find any, please file a bug and I will fix it. I bumped the version number to 0.04 and have uploaded it to CPAN. Ben On Nov 16, 2012, at 8:40 AM, "Dave Webb via RT" <bug-Set-IntervalTree@rt.cpan.org> wrote: Show quoted text

> Queue: Set-IntervalTree > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=81199 > > > Much obliged Ben. > > I just tried to install 0.3 on my CentOS 6.3 box, but it failed with: > > cc1plus: error: unrecognized command line option "-std=c++11" > > I figure this is because CentOS ships with gcc version 4.4.6. I've also > got gcc version 4.7.0 installed alongside it, so I changed "$CC = > 'c++';" to "$CC = 'g++47';" in Makefile.PL and retried the process. > > It's now dying with the following: > > IntervalTree.c: In function ‘void > boot_Set__IntervalTree(PerlInterpreter*, CV*)’: > IntervalTree.c:606:5: error: unable to find string literal operator > ‘operator"" SVf’ > > I'll have more of a play tomorrow. > > Cheers, > > Dave > > On Thu Nov 15 13:17:22 2012, BENBOOTH wrote:

>> Thanks for catching that! There was a type mismatch in the XS versus >> the interval_tree.h >> module. The XS was using 32-bit int's and the interval_tree.h module >> was using long's. I'm >> going to update the module to 0.03 today after I fix a few other >> things. >> >> On Thu Nov 15 09:06:54 2012, DAVEWEBB wrote:

>>> Hi, >>> >>> I'm using Set::IntervalTree in Net::IPAddress::Filter as it's by far

>> the

>>> smallest and fastest way I've found for dealing with large IP

>> address

>>> filter lists. >>> >>> In testing I found that fetch(2^31, 2^31) reports a false positive

>> if

>>> the tree has at least one interval, even if that interval doesn't

>> span 2^31

>>> >>> The following code shows it happening. >>> >>> #!/usr/bin/perl >>> >>> use strict; >>> use warnings; >>> >>> use Data::Dumper; >>> use Set::IntervalTree; >>> >>> my $tree = Set::IntervalTree->new(); >>> my $min = 1; >>> my $max = 2; >>> my $test = 2_147_483_648; # 2^31 - Shouldn't match but

>> does

>>> >>> print Dumper( $tree->fetch( $test, $test ) ); # prints [] >>> >>> $tree->insert( "$min - $max", $min, $max ); >>> >>> print Dumper( $tree->fetch( $test - 1, $test - 1 ) ); # prints [] >>> print Dumper( $tree->fetch( $test, $test ) ); # prints [

>> '1 -

>>> 2' ] >>> print Dumper( $tree->fetch( $test + 1, $test + 1 ) ); # prints [] >>> print Dumper( $tree->fetch( $test - 1, $test + 1 ) ); # prints [] >>> >>> >>> >>> exit; >>> >>> My C is non-existent at best, and I couldn't spot where this bug

>> arises.

>>> >>> Thanks for this light and fast module. >>> >>> Dave

>>

> > >

Fri Nov 16 13:29:29 2012 BENBOOTH [...] cpan.org - Correspondence added

should be fixed in 0.04

Fri Nov 16 13:29:29 2012 BENBOOTH [...] cpan.org - Status changed from 'open' to 'resolved'

Sat Nov 17 04:06:08 2012 DAVEWEBB [...] cpan.org - Correspondence added

Thanks Ben! V0.04 installed without a hitch, and in testing appears about 30% faster than V0.02 for lookups, with about a 25% memory reduction as well! On Fri Nov 16 13:29:29 2012, BENBOOTH wrote: Show quoted text

> should be fixed in 0.04

Sat Nov 17 04:06:09 2012 The RT System itself - Status changed from 'resolved' to 'open'

Sat Nov 17 09:25:20 2012 BENBOOTH [...] cpan.org - Status changed from 'open' to 'resolved'