CIDR lookup

bench.rb

require 'benchmark'
require "./cidr.rb"

def generate_random_ip(cidr=false)
    4.times.map{rand(256)}.join(".") + (cidr ? "/" + (rand(8) + 16).to_s : "")
end

def generate_random_suite(count, cidr_count, ip_count)
    count.times.map{
        {
            :cidrs => cidr_count.times.map{ generate_random_ip(true) },
            :ips   => ip_count.times.map{ generate_random_ip },
            :addr  => {},
        }
    }
end

testcase_count, cidr_count, ip_count = 100, 1000, 1000
puts "# Test cases: % 6d" % testcase_count
puts "# CIDRs     : % 6d" % cidr_count
puts "# IPs       : % 6d" % ip_count
puts

random_suite = generate_random_suite(testcase_count, cidr_count, ip_count)

# setup
random_suite.each {|c|
    trie = c[:addr][:trie] = TrieAddr.new
    c[:cidrs].each {|cidr| trie.add(cidr) }

    regexp = c[:addr][:regexp] = RegexpAddr.new
    c[:cidrs].each {|cidr| regexp.add(cidr) }
}

# bench
Benchmark.bm 10 do |r|
    r.report "Trie" do
        random_suite.each {|c|
            addr = c[:addr][:trie]
            c[:ips].each {|ip| addr.match(ip) }
        }
    end
    r.report "Regexp" do
        random_suite.each {|c|
            addr = c[:addr][:regexp]
            c[:ips].each {|ip| addr.match(ip) }
        }
    end
end

cidr.rb

class TrieAddr
  def self.generate_leaf
    leaf = Array.new(256);
    leaf.fill(leaf);
    return leaf
  end

  REJECT  = self.generate_leaf
  FULFILL = self.generate_leaf

  def initialize
    @root = Array.new(256, REJECT)
  end

  def add(cidr)
    ip, length = cidr.split('/', 2)
    length = (length || 32).to_i
    s = ip.split(".", 4).map {|o| o.to_i}

    netmask = ~((1 << (32 - length)) - 1) & 0xffffffff
    nip = (s[0] << 24) + (s[1] << 16) + (s[2] << 8) + s[3]
    nip &= netmask

    cur = @root
    while length > 8 do
      octet = (nip >> 24) & 0xff
      return self if cur[octet].equal?(FULFILL)
      if !cur[octet] || cur[octet].equal?(REJECT)
        cur[octet] = Array.new(256, REJECT)
      end
      cur = cur[octet]
      nip <<= 8
      length -= 8
    end
    lower = (nip >> 24) & 0xff
    upper = lower + (1 << (8 - length)) - 1;
    cur.fill(FULFILL, lower..upper)
    return self
  end

  def match(ip)
    s = ip.split(".", 4).map {|o| o.to_i}
    ! @root[s[0]][s[1]][s[2]][s[3]].equal?(REJECT)
  end
end

# thin wrapper of https://github.com/kaihar4/mruby-ipaddress_matcher
class RegexpAddr
  def initialize
    @regexps = []
  end
  def add(cidr)
    @regexps << IPAddressMatcher::CIDR.new(cidr).to_regexp
  end
  def match(ip)
    return @regexps.any? {|regexp| ip =~ regexp }
  end
end

result

# Test cases:    100
# CIDRs     :   1000
# IPs       :   1000

                 user     system      total        real
Trie         0.470000   0.010000   0.480000 (  0.498401)
Regexp      42.790000   0.180000  42.970000 ( 43.772412)