How to store IP address list in C# List to make it searchable for subnets too?

Question

Hello,

how should I correctly store IP address list with addresses which are subnets to make it searchable?

There are two examples:

1. I have IP address 1.2.3.4 and in my C# List there is 1.2.3.4 entry so here we have no problems.

2. I have IP address 3.4.5.6 and in my C# List I have subnet 3.4.0.0/24. Here is my problem.

How to store IP subnet in List to cover second example?

Thanks

Answer 1

Don't store it in a list - store it in a structure such as a Dictionary instead, where the key is the IP address, and the value is the subnet address.

Answer 2

I would prefer to create a specialized structure (class) to store all these information together. Probably in near future you would like to extend it to store ipv6 beside ipv4, and maybe some more data (metric, gateway, etc).

Answer 3

Define a class that stores an IPAddress and the prefix length:

public class IPAddressWithPrefixLength
{
    public IPAddress IPAddress { get; }
    public int PrefixLength { get; }
}

Then override Equals and GetHashCode such that only the first PrefixLength bits of IPAddress.GetAddressBytes() are taken into consideration (and, of course, the IPAddress type).

You can then use this class to store subnet prefixes in a List<T> or use them as keys of a Dictionary<K,V>:

var subnets = new List<IPAddressWithPrefixLength>
{
    new IPAddressWithPrefixLength(IPAddress.Parse("1.2.3.4"), 32),
    new IPAddressWithPrefixLength(IPAddress.Parse("3.4.0.0"), 16),
};

var ipawpl = new IPAddressWithPrefixLength(IPAddress.Parse("3.4.5.6"), 16);

Console.WriteLine(subnets.Contains(ipawpl)); // prints "True"

This works with IPv6 addresses, too.

Answer 4

I could use a binary tree with boolean labels on the nodes. Using the standard notation in which 0 is the left child and 1 the right child, 1.2.3.4 would be stored by putting true at 00000001000000100000001100000100 (the binary representation of that address) in the tree - and false at all nodes between the root and this. Conversely, 3.4.0.0/16 would be stored with a true at 0000001100000100 (the first 16 bits of the binary representation of 3.4.0.0).

When you are given an address to test, just go down the tree according to the bits of that address : if you reach a node a true, the address is in the list. If you reach the end of a branch, the address is not in the list.

For instance, if looking up 3.4.123.48, you'd go down 16 levels in the tree before reaching true, meaning that this address is in the list. But looking up 129.199.195.13, you'd know from the first 1 bit in that address that it is not part of the list.

I'm not sure how important it is to you to use the List type to store those addresses, so this may not help ; OTOH, once you've implemented a basic binary tree with labels, this should have better asymptotic performance characteristics than a .Net List.

Answer 5

At the end of this answer you will find a complete implementation of a structure to represent a IPV4 address.

Here is really simple example of usage:-

List<IPV4Address> list = new List<IPV4Address>();
list.Add(IPV4Address.FromString("3.4.0.0", 24));
var x = IPV4Address.FromString("3.4.0.6");
foreach (var addr in list.Where(a => a.Contains(x)))
  Console.WriteLine(addr);

The value "3.4.0.0/255.255.255.0" is displayed inthe console since 3.4.0.6 is found in the 3.4.0.0/24 subnet. Assuming list is full of various subnets and x could contain any address then this:-

var result = list.Where(a => a.Contains(x))
    .OrderByDescending(a => a.Mask)
    .FirstOrDefault();

will select the most specific subnet for that contains x.

public struct IPV4Address
{
  private UInt32 _Value;
  private UInt32 _Mask;

  public UInt32 Value
  {
    get { return _Value; }
    private set { _Value = value; }
  }

  public UInt32 Mask
  {
    get { return _Mask; }
    private set { _Mask = value; }
  }

  public static IPV4Address FromString(string address)
  {
    return FromString(address, 32);
  }

  public static IPV4Address FromString(string address, int maskLength)
  {
    string[] parts = address.Split('.');
    UInt32 value = ((UInt32.Parse(parts[0]) << 24) +
      ((UInt32.Parse(parts[1])) << 16) +
      ((UInt32.Parse(parts[2])) << 8) +
      UInt32.Parse(parts[3]));

    return new IPV4Address(value, maskLength);
  }

  public IPV4Address(UInt32 value)
  {
    _Value = value;
    _Mask = int.MaxValue;
  }

  public IPV4Address(UInt32 value, int maskLength)
  {
    if (maskLength < 0 || maskLength > 32)
      throw new ArgumentOutOfRangeException("maskLength", "Must be 0 to 32");

    _Value = value;
    if (maskLength == 32)
      _Mask = UInt32.MaxValue;
    else
      _Mask = ~(UInt32)((1 << (32 - maskLength))-1);

    if ((_Value & _Mask) != _Value)
      throw new ArgumentException("Address value must be contained in mask");
  }

  public bool Contains(IPV4Address address)
  {
    if ((Mask & address.Mask) == Mask)
    {
      return (address.Value & Mask) == Value;
    }
    return false;
  }

  public override string ToString()
  {
    string result = String.Format("{0}.{1}.{2}.{3}", (_Value >> 24), 
      (_Value >> 16) & 0xFF, 
      (_Value >> 8) & 0xFF, 
      _Value & 0xFF);

    if (_Mask != UInt32.MaxValue)
      result += "/" + String.Format("{0}.{1}.{2}.{3}", (_Mask >> 24),
      (_Mask >> 16) & 0xFF,
      (_Mask >> 8) & 0xFF,
      _Mask & 0xFF);

    return result;
  }
}