Slplit IPv4 адрес минимального и максимального диапазона

Question

Использование Lua Как разбить заданный IP-адрес, чтобы получить минимальный и максимальный диапазон, например:

94.19.21.119 

У меня есть CSV-файл, как это:

18087936,18153471,"AU" 
18153472,18219007,"JP" 
18219008,18350079,"IN" 
18350080,18874367,"CN" 

то будет читать 3 таблицы и CSV является мин, макс, код страны:

IPfrom = {} 
IPto = {} 
IPCountry = {} 

они получают заселена, как это:

IPfrom[18087936] = L 
IPto[L] = 18153471 
IPCountry[L] = "AU" 

с L является номером строки io.read то, что Im то пытается сделать, это получить минимальный диапазон, так что я могу без зацикливания чек, если он существует, то, если он этот ключ имеет индекс максимальный диапазон, и если ip находится в пределах min/max, я получаю код страны. Вероятно, это отличный способ сделать что-то, кроме таблиц более 100000 записей, поэтому цикл занимает некоторое время.

Answer 1

Возможно, что-то вроде следующего будет работать для вас: использование

-- 
-- Converts an IPv4 address into its integer value 
-- 
function iptoint(ip) 
    local ipint = 0 
    local iter = string.gmatch(ip, "%d+") 
    for i = 3, 0, -1 do 
     local piece = tonumber(iter()) 
     if piece == nil or piece < 0 or piece > 255 then 
      return nil 
     end 
     ipint = bit32.bor(ipint, bit32.lshift(piece, 8 * i)) 
    end 
    return ipint 
end 

-- 
-- Looks up an IPv4 address in a multidimensional table, with the entries: 
-- {start_address, end_address, country} 
-- and returns the matching country 
-- 
function iptocountry(ip, tbl) 
    local ipint = iptoint(ip) 
    if ipint == nil then 
     return nil 
    end 
    for _,v in pairs(tbl) do 
     if ipint >= v[1] and ipint <= v[2] then 
      return v[3] 
     end 
    end 
    return nil 
end 

Пример:

local countries = { 
    {16777216, 17367039, "US"}, 
    {1578300000, 1678300000, "CAN"} 
    -- ... rest of entries loaded from CSV file 
} 

local ip = "94.19.21.119" 
print (iptocountry(ip, countries)) -- prints CAN 

Answer 2

Хэш таблица (основной тип в Lua) даст вам O (N). Массив (таблица без отверстий с индексами от someMinAddr до someMaxAddr) даст вам O (1), но использует значительный объем памяти. Бинарный поиск через правильно отсортированную структурированную таблицу может дать вам O (log N), который, пожалуй, стоит 100000 адресов. Я полагаю, вы могли бы иметь структуру, как это:

IPfrom = { 
    {line=L1, addFrom=from1, addrTo=to1, c=country1}, 
    {line=L2, addFrom=from2, addrTo=to2, c=country2}, 
    {line=L3, addFrom=from3, addrTo=to3, c=country3}, 
    {line=L4, addFrom=from4, addrTo=to4, c=country4}, 
    ... 
} 

, потому что я не вижу смысла разделения полей в и страны от другой информации, просто означает больше таблицы поиска. В любом случае, если вы действительно хотите, чтобы отделить их следующее не влияет:

-- init: 
create table from CSV file 
sort IPFrom on addFrom field 

-- as many times as required: 
function findIP(addr) 
    is addr smaller than IPfrom[middle].addrTo3? 
    if yes, is addr smaller than IPfrom[middle of middle]? 
     etc 
end 

Это рекурсивная, так что если вы структурировать его правильно, вы можете использовать хвостовые вызовы и не беспокоиться о переполнении стека (;), что-то вроде

function findIPRecurs(addr, ipTbl, indxMin, indxMax) 
    local middle = (indxMin + indxMax)/2 
    local midAddr = ipTbl[middle].addrFrom 
    if addr < midAddr then 
     return findIPRecurs(addr, ipTbl, indxMin, middle) 
    else if addr > midAddr then 
     return findIPRecurs(addr, ipTbl, middle, indxMax) 
    else -- have entry: 
     return middle 
    end 
end 

function findIP(addr) 
    return findIPRecurs(addr, ipTbl, 1, #ipTbl) 
end 

Я не проверял это, поэтому может быть какое-то исправление, но вы получите эту идею. Это будет использовать ту же память, что и метод O (N), но для больших массивов будет значительно быстрее; гораздо меньше памяти, чем метод O (1), и, вероятно, приемлемо медленнее.