Idea: binary decision diagram for --exclude list

[David Fifield <david () bamsoftware com>]

The code behind our --exclude list is basically a list of
representations of target patterns. The time taken to determine if an
address should be excluded is proportional to the length of the exclude
list. This has actually been a problem for some people with very large
exclude lists.

I think it's worth looking into implementing the exclude list using a
binary decision diagram. This data structure is like a decision tree but
common subtrees are linked together to save space. It would offer O(1)
membership tests, no matter the length of the exclude list. BDDs are
described in the Art of Computer Programming volume 4A and in this
Wikipedia article:
        https://en.wikipedia.org/wiki/Binary_decision_diagram
I found this paper the discusses using BDDs to represent routing tables:
        
http://140.116.82.38/members/html/phd/jengjian/pdf/High-Speed%20IP%20Routing%20With%20Binary%20Decision%20Diagrams%20Based%20Hardware%20Address%20Lookup%20Engine.pdf

David Fifield
_______________________________________________
Sent through the dev mailing list
http://nmap.org/mailman/listinfo/dev
Archived at http://seclists.org/nmap-dev/