Efficient searching through IP address range in file?

From: Mike Hunson (mike_at_nospammingallowed.com)
Date: 01/30/05

  • Next message: Ian Woods: "Re: Efficient algorithm for finding duplicates in 56-bit number" 
    Date: Sat, 29 Jan 2005 15:59:21 -0800

    Hi,

    I'm looking for a way to look through a file of IP ranges in an efficient
    manner.
    I do not have a CS background but am trying to learn different search
    strategies, etc. Just ordered a copy of an algorithms book.

    Basically, we have a file of IP ranges. Since an IP can be represented as
    either a string (xxx.xxx.xxx.xxx) or as a number (4 bytes) we represent it
    as a number.

    so an IP range might be:
    0x12345678 - 0x12356666

    this would be represented in the file as just 8 bytes where the first four
    are the starting point, the final four are the ending point, and the final
    two are the designation code. So 10 bytes per line.

    Now, we have an IP address that falls into this range, say 0x12345765

    The total file size is about 1 megabyte, and I'd like to find the first
    match. What is the best way to do this? I know the answer is probably to
    index the file, but I'm not sure how to do this. Assign a hash code based
    on the first byte of the IP range? But then do I need to actually sort my 1
    MB file first?

    Thanks in advance,

    Mike

  • Next message: Ian Woods: "Re: Efficient algorithm for finding duplicates in 56-bit number"