module Irc class NetmaskDb # helper backend class: generic nested radix tree class Tree attr_reader :pre, :chi def initialize(pre = '', chi = Hash.new) @pre = pre @chi = chi end def add(val, *prefs) str = prefs.shift or raise 'empty prefs' @pre = str if @chi.empty? n = 0 @pre.size.times do break if @pre[n] != str[n] n += 1 end rest = str.slice(n .. -1) if n != @pre.size prest = @pre.slice!(n .. -1) pc = prest.slice! 0 @chi = {pc => Tree.new(prest, @chi)} end c = rest.slice!(0) if c (@chi[c] ||= Tree.new).add(val, rest, *prefs) else if prefs.empty? (@chi[''] ||= Array.new).push val else (@chi[''] ||= Tree.new).add(val, *prefs) end end end def empty? @chi.empty? end def remove(*prefs, &block) str = prefs.shift or raise 'empty prefs?' return nil unless @pre.empty? or str.index(@pre) == 0 c = str.slice(@pre.size) || '' return nil unless @chi.include? c if c == '' if prefs.empty? @chi[c].reject!(&block) else @chi[c].remove(*prefs, &block) end else @chi[c].remove(str.slice((@pre.size + 1) .. -1), *prefs, &block) end @chi.delete(c) if @chi[c].empty? if @chi.size == 1 k = @chi.keys.shift return nil if k == '' @pre << k << @chi[k].pre @chi = @chi[k].chi end end def find(*prefs) str = prefs.shift or raise 'empty prefs?' self.find_helper(str, *prefs) + self.find_helper(str.reverse, *prefs) end protected def find_helper(*prefs) str = prefs.shift or raise 'empty prefs?' return [] unless @pre.empty? or str.index(@pre) == 0 # puts "#{self.inspect}: #{str} == #{@pre} pfx matched" if !@chi.include? '' matches = [] elsif Array === @chi[''] matches = @chi[''] else matches = @chi[''].find(*prefs) end c = str.slice(@pre.size) more = [] if c and @chi.include?(c) more = @chi[c].find_helper(str.slice((@pre.size + 1) .. -1), *prefs) end return more + matches end end # api wrapper for netmasks def initialize @tree = Tree.new end def cook_component(str) s = (str && !str.empty?) ? str : '*' l = s.index(/[\?\*]/) if l l2 = s.size - s.rindex(/[\?\*]/) - 1 if l2 > l s = s.reverse l = l2 end return (l > 0) ? s.slice(0 .. (l - 1)) : '' else return s end end def mask2keys(m) [m.host, m.user, m.nick].map { |c| cook_component(c) } end def add(user, *masks) masks.each do |m| debug "adding user #{user} with mask #{m}" @tree.add([user, m], *mask2keys(m)) end end def remove(user, mask) debug "trying to remove user #{user} with mask #{mask}" @tree.remove(*mask2keys(mask)) do |val| val[0] == user and val[1].fullform == mask.fullform end end def metric(iu, bu, mask) ret = nil if iu.matches? mask ret = iu.fullform.length - mask.fullform.length ret += 10 if bu.transient? end return ret end def find(iu) debug "find(#{iu.fullform})" matches = @tree.find(iu.host, iu.user, iu.nick).uniq.map do |val| m = metric(iu, *val) m ? [val[0], m] : nil end.compact.sort { |a, b| a[1] <=> a[1] } debug "matches: " + (matches.map do |m| "#{m[0].username}: [#{m[1]}]" end.join(', ')) return matches.empty? ? nil : matches[0][0] end end end