search

aaronkaplan / py-radix

Automatically exported from code.google.com/p/py-radix
Other
0 stars 0 forks source link

Radix.search_best() method not considering masklen when returning results #4

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
What steps will reproduce the problem?

1. Create a radix tree and 

>>> import radix
>>> rtree = radix.Radix()

2. Populate it with a few nodes to illustrate the problem:
>>> rtree.add('0.0.0.0/0')
<radix.RadixNode object at 0xb7710ca0>
>>> rtree.add('10.0.0.0/8')
<radix.RadixNode object at 0xb7710cf0>
>>> rtree.add('10.0.0.0/16')
<radix.RadixNode object at 0xb7710d40>
>>> rtree.add('10.0.0.0/24')
<radix.RadixNode object at 0xb7710d90>
>>> rtree.search_best('10.0.0.0/20')
<radix.RadixNode object at 0xb7710d90>
>>> rtree.search_best('10.0.0.0/20').prefix
'10.0.0.0/24'

3. Confirm the list of prefixes in the tree:

>>> rtree.prefixes()
['0.0.0.0/0', '10.0.0.0/8', '10.0.0.0/16', '10.0.0.0/24']

What is the expected output? What do you see instead?

Using the tree above, if you perform a search_best for '10.0.0.0/20', observe 
that the result is '10.0.0.0/24':

>>> rtree.search_best('10.0.0.0/20').prefix
'10.0.0.0/24'

or

>>> rtree.search_best('10.0.0.0', masklen=20).prefix
'10.0.0.0/24'

The expected result is '10.0.0.0/16'. It seems as if search_best() is not 
including the masklen when checking the tree.

What version of the product are you using? On what operating system?

version 0.5 
Linux (Ubuntu 10.10 LTS, kernel 2.6.32; CentOS 5.6, kernel 2.6.18)

Please provide any additional information below.

Here are a few more examples that the results seem to be inconsistent/confusing:

Correct:
>>> rtree.search_best('10.0.1.0').prefix
'10.0.0.0/16'
>>> rtree.search_best('10.0.2.0/23').prefix
'10.0.0.0/16'

Incorrect:
>>> rtree.search_best('10.0.0.0/23').prefix
'10.0.0.0/24'

Thanks in advance for looking into this.

Original issue reported on code.google.com by jat...@gmail.com on 7 Oct 2011 at 4:42

GoogleCodeExporter commented 9 years ago 
See revision ac92f2249e68. I'm not sure when a new version of py-radix will be 
released, though.

Original comment by clint.he...@gmail.com on 1 Dec 2011 at 2:32

GoogleCodeExporter commented 9 years ago 
Awesome, thanks. I'll have a look! :)

Original comment by jat...@gmail.com on 1 Dec 2011 at 4:44