robertdavidgraham/masscan — pull request #131 by vlad902 (2014-11-24 05:43:31+00:00)
Title: Make loading IP lists exponentially faster

Currently, loading many IP ranges from a file (e.g. if you're taking the output of a previous scan for another scan) will take a very long time because the rangelist_add_range function scans over the entire (sorted) range list instead of doing a binary search. By updating the function to use binary search, it becomes possible to quickly load millions of IP ranges efficiently. For example, loading 100k IPs takes 0.1s instead of 4s, and loading 400k IPs takes 0.7s instead of 130s.

The regression tests pass with this commit and I've tested the range merging logic with several inputs to confirm the outputs are equivalent to the old logic.

Commit message:
Inserting entries into a range list currently requires exponential time
with relation to the number of entries in the list. Instead of doing a
linear search over a sorted list, do a binary search instead.