The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

форумы  помощь  поиск  регистрация  майллист  ВХОД  слежка  RSS
"Проверка на принадлежность адреса сети: как?"
Вариант для распечатки Архивированная нить - только для чтения! 
Пред. тема | След. тема 
Форумы Программирование под UNIX (Public)
Изначальное сообщение [Проследить за развитием треда]

"Проверка на принадлежность адреса сети: как?"
Сообщение от borik_ints emailИскать по авторуВ закладки(ok) on 23-Сен-04, 21:17  (MSK)
Имеется задача: необходимо проверить, принадлежит ли данный адрес указанной подсети. В данный момент делаю следующее:

Создание массива адресов:
...
cl_subnets_len++;
if ((cl_subnets_new=realloc(cl_subnets, cl_subnets_len*sizeof(struct tcl_subnet))))
  cl_subnets=cl_subnets_new;
else error(1,"get_client_cf: can't allocate memory at %s:%d!",__FILE__,__LINE__);
cl_subnets[cl_subnets_len-1].cl_id=i;
if ((cl_subnets[cl_subnets_len-1].subnet_len=inet_net_pton(AF_INET,
wrk_str,&(cl_subnets[cl_subnets_len-1].subnet),sizeof(struct in_addr))) == -1)
  cl_subnets_len--;
...

Потом проверка, принадлежит ли адрес одному из элементов массива:

int
get_cl_id(session_ip)
struct in_addr session_ip;
{
register int i;
if (!cl_subnets) return -1;
for (i=0;(i<cl_subnets_len);i++)
if (inet_netof(session_ip) == inet_netof(cl_subnets[i].subnet.s_addr))
  break;
if (i==cl_subnets_len) return -1;
return cl_subnets[i].cl_id;
}

Однако мучают меня сомнения, что это правильно, хотя бы потому, что struct in_addr не имеет в себе разграничителя сеть/хост (по крайней мере, я не нашел). По какому принципу отделяются сети от хостов?

Уверен, что какие-то функции реализуют необходимые мне действия. Только подскажите, какие именно. А надо мне, повторюсь, проверить принадлежность хоста сети.

PS: забыл, адреса в конфиге записаны в виде xxx.xxx.xxx.xxx/yy

  Рекомендовать в FAQ | Cообщить модератору | Наверх

 Оглавление

Индекс форумов | Темы | Пред. тема | След. тема
Сообщения по теме

1. "Проверка на принадлежность адреса сети: как?"
Сообщение от dimus Искать по авторуВ закладки(??) on 24-Сен-04, 10:17  (MSK)
Эти yy - это битовая маска, которая указывает на то, сколько бит из всего IP адреса используются для определения сети. Например:
192.168.0.0/24
Значит, что 192.168.0 - сеть (3 байта по 8 бит = 24 бита)
Последний байт адресует хост. В сети 256 машин
192.168.0.0/26
192.168.0 + еще 2 бита из последнего байта - сеть.
оставшиеся 6 бит - хост. Соответственно в 1 сети у нас 64 машины
192.168.0.0 - 192.168.0.63 - первая сеть
192.168.0.64 - 192.168.0.127 - вторая сеть и т.д.
Используя старый добрый оператор & можно быстро и эффективно решить проблему. Никаких циклов не надо.
  Рекомендовать в FAQ | Cообщить модератору | Наверх

2. "Проверка на принадлежность адреса сети: как?"
Сообщение от borik_ints emailИскать по авторуВ закладки(ok) on 24-Сен-04, 11:39  (MSK)
Как именно организуетс маска подсети, мне известно, но все равно спасибо за разъяснение :)
>Используя старый добрый оператор & можно быстро и эффективно решить проблему. Никаких
>циклов не надо.

Во первых: на разных платформах порядок байтов в struct in_addr разный, а из манов я так и не вынес, какой надо юзать для обеспечения кроссплатформенности :(

Во-вторых: мне надо каждый раз создавать накладываемую маску разной длинны, как ее создать? воспользоваться потом оператором & проблемы не составит...

то есть, мне нужно на 192.168.21.15 наложить маску /21, а на 197.185.16.11 - /24. При помощи чего мне эти маски создавать?

ЗЫ: циклы использовались для создания массива сетей, а не определения маски :)

  Рекомендовать в FAQ | Cообщить модератору | Наверх

3. "Проверка на принадлежность адреса сети: как?"
Сообщение от klalafuda emailИскать по авторуВ закладки on 24-Сен-04, 11:55  (MSK)
>Во первых: на разных платформах порядок байтов в struct in_addr разный, а
>из манов я так и не вынес, какой надо юзать для
>обеспечения кроссплатформенности :(

http://www.opengroup.org/onlinepubs/009695399/basedefs/netinet/in.h.html#tag_13_32

---cut---
The <netinet/in.h> header shall define the sockaddr_in structure that includes at least the following members:

sa_family_t     sin_family   AF_INET.
in_port_t       sin_port     Port number.
struct in_addr  sin_addr     IP address.

The sin_port and sin_addr members shall be in network byte order.
---cut---

-> в сетевом порядке (что вполне логично). если же ваша пталформа это делает как-то иначе, это ее персональные сексуальные трудности :)

// wbr

  Рекомендовать в FAQ | Cообщить модератору | Наверх

4. "Проверка на принадлежность адреса сети: как?"
Сообщение от klalafuda emailИскать по авторуВ закладки on 24-Сен-04, 11:58  (MSK)
>Во первых: на разных платформах порядок байтов в struct in_addr разный, а
>из манов я так и не вынес, какой надо юзать для
>обеспечения кроссплатформенности :(

ps: маны в таком вопросе, как слендование стандарту, далеко не самый правильный источник информации.

// wbr

  Рекомендовать в FAQ | Cообщить модератору | Наверх

5. "Проверка на принадлежность адреса сети: как?"
Сообщение от borik_ints emailИскать по авторуВ закладки(ok) on 24-Сен-04, 12:23  (MSK)
>>Во первых: на разных платформах порядок байтов в struct in_addr разный, а
>>из манов я так и не вынес, какой надо юзать для
>>обеспечения кроссплатформенности :(
>
>ps: маны в таком вопросе, как слендование стандарту, далеко не самый правильный
>источник информации.
>
>// wbr

cut <man inet>
<...>
INTERNET ADDRESSES
     Values specified using the `.' notation take one of the following forms:
           a.b.c.d
           a.b.c
           a.b
           a
     When four parts are specified, each is interpreted as a byte of data and assigned, from left to right, to the four bytes of an Internet address. Note that when an Internet address is viewed as a 32-bit integer quantity on the VAX the bytes referred to above appear as ``d.c.b.a''.  That is, VAX bytes are ordered from right to left.
<...>

man`ам FreeBSD я все-таки доверяю. Да и где-то читал (чуть ли не в "Руководстве по технологиям объединенных сетей" КискоПресса), что это платформозависимый параметр.

Ладно, с этим разберусь, почитаю стандарты. Теперь все-таки вопрос с организацией маски. Как ПРОСТО создать 4-х байтную переменную, состоящую из yy количества единиц слева и остальными нулями справа?

  Рекомендовать в FAQ | Cообщить модератору | Наверх

6. "Проверка на принадлежность адреса сети: как?"
Сообщение от klalafuda emailИскать по авторуВ закладки on 24-Сен-04, 13:09  (MSK)
>cut <man inet>
><...>
>INTERNET ADDRESSES
>     Values specified using the `.' notation take
>one of the following forms:
>           a.b.c.d
>
>           a.b.c
>
>           a.b
>
>           a
>
>     When four parts are specified, each is
>interpreted as a byte of data and assigned, from left to
>right, to the four bytes of an Internet address. Note that
>when an Internet address is viewed as a 32-bit integer quantity
>on the VAX the bytes referred to above appear as ``d.c.b.a''.
> That is, VAX bytes are ordered from right to left.
>
><...>
>
>man`ам FreeBSD я все-таки доверяю.

а man для BSD и не противоречит сказанному :) сверху ничего не сказано о том, в каком тменно порядке передаются/возвращаются параметны в sockaddr_in.

> Да и где-то читал (чуть ли не
>в "Руководстве по технологиям объединенных сетей" КискоПресса), что это платформозависимый параметр.

с их точки зрения может быть и так, не читал. с точки зрения стандарта - нет. если бы это было так, написание платформонезависимых приложений с исользоиванием сокетов превратилось бы в форменный кошмар.

>Ладно, с этим разберусь, почитаю стандарты. Теперь все-таки вопрос с организацией маски.
>Как ПРОСТО создать 4-х байтную переменную, состоящую из yy количества единиц
>слева и остальными нулями справа?

термин "просто" более чем растяжимое понятне :) ну, например:

---cut---
#include <stdio.h>
#include <stdint.h>

uint32_t
get_mask(int nbits)
{
        uint32_t result = 0, mask = 0x80000000;

        while (nbits-- > 0) {
                result |= mask;
                mask >>= 1;
        }

        return result;
}

int
main()
{
        int nbits = 0;

        while (nbits <= 32) {
                printf("nbits %-2d mask %08Xh\n",
                        nbits, get_mask(nbits));
                nbits++;
        }

        return 0;
}
---cut---

ps: ессно что в рабочей версии это нужно еще несколько подправить. внести проверки на nbits и пр.

// wbr

  Рекомендовать в FAQ | Cообщить модератору | Наверх

7. "Проверка на принадлежность адреса сети: как?"
Сообщение от dimus Искать по авторуВ закладки(??) on 24-Сен-04, 14:01  (MSK)
Скоростной метод:
Тупо руками создаем 32 маски и заносим в массив под соответствующим индексом. Это даст очень высокую скорость. Вообще, по моему, если важна скорость, лучше всю функцию распознавания переписать на ассемблере. Этот язык идеально подходит для битовых операций.
  Рекомендовать в FAQ | Cообщить модератору | Наверх

9. "Проверка на принадлежность адреса сети: как?"
Сообщение от klalafuda emailИскать по авторуВ закладки on 24-Сен-04, 14:16  (MSK)
>Скоростной метод:
>Тупо руками создаем 32 маски и заносим в массив под соответствующим индексом.

как вариант. с учетом вполне конкретной постановки задачи, это вполне подойдет.

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

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

// wbr

  Рекомендовать в FAQ | Cообщить модератору | Наверх

8. "В догонку - вопрос по теме"
Сообщение от Maxim Kuznetsov emailИскать по авторуВ закладки on 24-Сен-04, 14:09  (MSK)
>>cut <man inet>
>><...>
>>INTERNET ADDRESSES
>>     Values specified using the `.' notation take
>>one of the following forms:
>>           a.b.c.d
>>
>>           a.b.c
>>
>>           a.b
>>
>>           a
>>
>>     When four parts are specified, each is
>>interpreted as a byte of data and assigned, from left to
>>right, to the four bytes of an Internet address. Note that
>>when an Internet address is viewed as a 32-bit integer quantity
>>on the VAX the bytes referred to above appear as ``d.c.b.a''.
>> That is, VAX bytes are ordered from right to left.
>>
>><...>
>>
>>man`ам FreeBSD я все-таки доверяю.
>
>а man для BSD и не противоречит сказанному :) сверху ничего не
>сказано о том, в каком тменно порядке передаются/возвращаются параметны в sockaddr_in.
>
>
>> Да и где-то читал (чуть ли не
>>в "Руководстве по технологиям объединенных сетей" КискоПресса), что это платформозависимый параметр.
>
>с их точки зрения может быть и так, не читал. с точки
>зрения стандарта - нет. если бы это было так, написание платформонезависимых
>приложений с исользоиванием сокетов превратилось бы в форменный кошмар.
>
>>Ладно, с этим разберусь, почитаю стандарты. Теперь все-таки вопрос с организацией маски.
>>Как ПРОСТО создать 4-х байтную переменную, состоящую из yy количества единиц
>>слева и остальными нулями справа?
>
>термин "просто" более чем растяжимое понятне :) ну, например:
>
>---cut---
>#include <stdio.h>
>#include <stdint.h>
>
>uint32_t
>get_mask(int nbits)
>{
>        uint32_t result = 0,
>mask = 0x80000000;
>
>        while (nbits-- > 0) {
>            
>    result |= mask;
>                mask >>= 1;
>        }
>
>        return result;
>}
>
>int
>main()
>{
>        int nbits = 0;
>
>
>        while (nbits <= 32)
>{
>            
>    printf("nbits %-2d mask %08Xh\n",
>            
>          
> nbits, get_mask(nbits));
>            
>    nbits++;
>        }
>
>        return 0;
>}
>---cut---
>
>ps: ессно что в рабочей версии это нужно еще несколько подправить. внести
>проверки на nbits и пр.
>
>// wbr
видимо решаем схожие задачи :-)
Есть таблица с префиксами сетей ~5000 записей,
включает сети, некоторые подсети и отдельные хосты,
как в ней сделать быстрый поиск подходяшей записи с максимальной длинной маски (определение минимальной подсети) ?
Пока-что сделал в лоб, простым просмотром всего, но сразу для двух адресов. Но ведь есть алгоритмы оптимальнее...
Поделитесь ссылкой, или хотя-бы намёком :)
  Рекомендовать в FAQ | Cообщить модератору | Наверх

10. "В догонку - вопрос по теме"
Сообщение от klalafuda emailИскать по авторуВ закладки on 24-Сен-04, 14:19  (MSK)
>Есть таблица с префиксами сетей ~5000 записей,
>включает сети, некоторые подсети и отдельные хосты,
>как в ней сделать быстрый поиск подходяшей записи с максимальной длинной маски
>(определение минимальной подсети) ?

ммм... не совсем понял, что же именно вы хотите сделать. опишите задачу несколько подробнее :) что на входе, что на выходе.

// wbr

  Рекомендовать в FAQ | Cообщить модератору | Наверх

13. "В догонку - вопрос по теме"
Сообщение от Maxim Kuznetsov emailИскать по авторуВ закладки on 24-Сен-04, 14:48  (MSK)
>>Есть таблица с префиксами сетей ~5000 записей,
>>включает сети, некоторые подсети и отдельные хосты,
>>как в ней сделать быстрый поиск подходяшей записи с максимальной длинной маски
>>(определение минимальной подсети) ?
>
>ммм... не совсем понял, что же именно вы хотите сделать. опишите задачу
>несколько подробнее :) что на входе, что на выходе.
>
>// wbr
в терминах C (упрощенно)-
/** тут хранится информация о сетях/подсетях/хостах **/
struct net_info {
  uint32 addr; // net oh host address
  uint32 mask; // net (bit) mask
  unsigned short mask_size; //
  /* other info`s */
  ...
}net_tab[NET_TAB_SIZE];
/** функция поиска */
int net_resolve(struct net_info *table,
  uint32 addr1,
  struct netinfo **info1,
  uint32 addr2,
  struct netinfo **info2);
Ищет в таблице сразу два адреса (они и приходят по парам)..
Учитывая, что кол-во записей может быть велико(от 5000), меня этот алг. не совсем устраивает.

Хочется алгоритм O(ln n) для поиска в этом(в net_tab).Причем находить надо минимальную подсеть, то если есть записи для 192.168.0.0/16 и 192.168.10.0/24 для 192.168.10.11 должен быть найден 192.168.10.0/24..
Допускаю что вместо массива надо использовать динамическую структуру (дерево множест?, что-то еще??)

Если использовать просто бинарный поиск в массиве, то находится первое подходящее(например сеть с меньшей маской) и чтобы затем найти то что надо,требуется некоторое шаманство,
что не совсем красиво и скорости не прибавляет

  Рекомендовать в FAQ | Cообщить модератору | Наверх

14. "В догонку - вопрос по теме"
Сообщение от klalafuda emailИскать по авторуВ закладки on 24-Сен-04, 15:03  (MSK)
>в терминах C (упрощенно)-
>/** тут хранится информация о сетях/подсетях/хостах **/
>struct net_info {
>  uint32 addr; // net oh host address
>  uint32 mask; // net (bit) mask
>  unsigned short mask_size; //
>  /* other info`s */
>  ...
>}net_tab[NET_TAB_SIZE];
>/** функция поиска */
>int net_resolve(struct net_info *table,
>  uint32 addr1,
>  struct netinfo **info1,
>  uint32 addr2,
>  struct netinfo **info2);

нет уж, пожалуйста, давайте ставить задачу в терминах русского языка :)

>Ищет в таблице сразу два адреса (они и приходят по парам)..

да хоть квадруплями. если я правильно понял проблему, это значения не имеет.

>Хочется алгоритм O(ln n) для поиска в этом(в net_tab).Причем находить надо минимальную
>подсеть, то если есть записи для 192.168.0.0/16 и 192.168.10.0/24 для 192.168.10.11
>должен быть найден 192.168.10.0/24..

термины:
минимальная подсеть - подсеть с минимальной длиной в битах.
максимальная подсеть - подсеть с максимальной длиной в битах.
откуда: a.b.c.0/24 > a.b.0.0/16

итого, на входе:
есть некоторое множество подсетей вида <адрес>/<длина>. множество допускает "перекрытие" элементов i.e. <a.b.0.0>/16 и <a.b.c.0>/24. дан входящий адрес.

требуется:
в множестве найти подсеть с максимальной длиной для заданного адреса.

я правильно понял?

// wbr

  Рекомендовать в FAQ | Cообщить модератору | Наверх

17. "В догонку - вопрос по теме"
Сообщение от Maxim Kuznetsov emailИскать по авторуВ закладки on 24-Сен-04, 15:08  (MSK)
>итого, на входе:
>есть некоторое множество подсетей вида <адрес>/<длина>. множество допускает "перекрытие" элементов i.e. <a.b.0.0>/16 и <a.b.c.0>/24. дан входящий адрес.
>
>требуется:
>в множестве найти подсеть с максимальной длиной для заданного адреса.
>
>я правильно понял?
>
>// wbr
да

  Рекомендовать в FAQ | Cообщить модератору | Наверх

24. "В догонку - вопрос по теме"
Сообщение от klalafuda emailИскать по авторуВ закладки on 24-Сен-04, 15:58  (MSK)
>>итого, на входе:
>>есть некоторое множество подсетей вида <адрес>/<длина>. множество допускает "перекрытие" элементов i.e. <a.b.0.0>/16 и <a.b.c.0>/24. дан входящий адрес.
>>
>>требуется:
>>в множестве найти подсеть с максимальной длиной для заданного адреса.
>>
>>я правильно понял?
>>
>>// wbr
>да

подумайте в сторону организации множества сетей в виде дерева по принципу "от худшего к лучшему".

пример:

множество вида:
1.1.[1-254].0 /24
1.1.0.0       /16
1.2.[1-254].0 /24
1.2.0.0       /16
1.3.0.0       /16

адрес 1.3.4.5

после сортировки массива по разрядности сети от большей к меньшей вы получите, что для поиска адреса вы пройдете весь массив. а если бы вы построили дерево вида:

1.1.0.0/16
  1.1.[1-254].0/24
1.2.0.0/16
  1.2.[1-254].0/24
1.3.0.0/16

то первые два узла, вместе с дочерними, очевидно, отпали бы сразу.

"сперва ищите худшее подходящее, в неподходящем не ищите лучшего, в подходящем ищите лучшее".

// wbr

  Рекомендовать в FAQ | Cообщить модератору | Наверх

11. "В догонку - вопрос по теме"
Сообщение от dimus Искать по авторуВ закладки(??) on 24-Сен-04, 14:24  (MSK)
Честно говоря, не совсем понятно, что вам нужно. Можно поконкретнее обрисовать задачу?
  Рекомендовать в FAQ | Cообщить модератору | Наверх

12. "В догонку - вопрос по теме"
Сообщение от borik_ints emailИскать по авторуВ закладки(ok) on 24-Сен-04, 14:42  (MSK)
>видимо решаем схожие задачи :-)
>Есть таблица с префиксами сетей ~5000 записей,
>включает сети, некоторые подсети и отдельные хосты,
>как в ней сделать быстрый поиск подходяшей записи с максимальной длинной маски
>(определение минимальной подсети) ?
>Пока-что сделал в лоб, простым просмотром всего, но сразу для двух адресов.
>Но ведь есть алгоритмы оптимальнее...
>Поделитесь ссылкой, или хотя-бы намёком :)

Попробую потелепатить: есть массив сетей, надо определить, к которой из них относится указанный хост, при чем надо выбрать запись с минимальной маской.

Если да, то простейший способ: сортируешь однократно этот массив по убыванию размера маски (/32 - верхние элементы, /0 - нижние) и потом линейным поиском по массиву до первого совпадения. Возможно, есть варианты улучшения данного способа

  Рекомендовать в FAQ | Cообщить модератору | Наверх

15. "В догонку - вопрос по теме"
Сообщение от Maxim Kuznetsov emailИскать по авторуВ закладки on 24-Сен-04, 15:04  (MSK)
Телепат !!
так оно и есть - так оно сейчас и сделанно,
с простейшим улучшением (ищется сразу два адреса, пока не будут найденны оба)
Собственно вопрос - возможно ли другое, более оптимальное по скорости решение ?


  Рекомендовать в FAQ | Cообщить модератору | Наверх

18. "В догонку - вопрос по теме"
Сообщение от borik_ints emailИскать по авторуВ закладки(ok) on 24-Сен-04, 15:11  (MSK)
>Телепат !!
>так оно и есть - так оно сейчас и сделанно,
>с простейшим улучшением (ищется сразу два адреса, пока не будут найденны оба)
>
>Собственно вопрос - возможно ли другое, более оптимальное по скорости решение ?
>
Можно делать еще следующее: одномерный массив разбивается на 2-мерный с переменной длиной строки. Номер строки - количество значимых бит в маске. Каждая строка сортируется (либо по возрастанию, либо по убыванию). После этого бинарным поиском ищем необходимый элемент сначала в 32-й строке, не нашли? тогда в 31-й... и т.д.
  Рекомендовать в FAQ | Cообщить модератору | Наверх

16. "В догонку - вопрос по теме"
Сообщение от dimus Искать по авторуВ закладки(??) on 24-Сен-04, 15:07  (MSK)
>Попробую потелепатить: есть массив сетей, надо определить, к которой из них относится
>указанный хост, при чем надо выбрать запись с минимальной маской.
>
>Если да, то простейший способ: сортируешь однократно этот массив по убыванию размера
>маски (/32 - верхние элементы, /0 - нижние) и потом линейным
>поиском по массиву до первого совпадения. Возможно, есть варианты улучшения данного
>способа
Еще бы. Если массив отсортирован, то искать надо не линейным, а двоичным поиском - man bsearch

  Рекомендовать в FAQ | Cообщить модератору | Наверх

19. "В догонку - вопрос по теме"
Сообщение от Maxim Kuznetsov emailИскать по авторуВ закладки on 24-Сен-04, 15:12  (MSK)
>Еще бы. Если массив отсортирован, то искать надо не линейным, а двоичным
>поиском - man bsearch
к сожалению bsearch не помогает в этой задаче - практически наверняка
на первой же итерации он найдет ´подходящую´ запись 0.0.0.0/0 описывающую вообще всё множество сетей - а дальше как ?


  Рекомендовать в FAQ | Cообщить модератору | Наверх

21. "И возвращаясь к моим баранам, то бишь принадлежность хоста с..."
Сообщение от borik_ints emailИскать по авторуВ закладки(ok) on 24-Сен-04, 15:23  (MSK)
А у Вас как определяется принадлежность хоста сети?
  Рекомендовать в FAQ | Cообщить модератору | Наверх

23. "И возвращаясь к моим баранам, то бишь принадлежность хоста с..."
Сообщение от klalafuda emailИскать по авторуВ закладки on 24-Сен-04, 15:44  (MSK)
>А у Вас как определяется принадлежность хоста сети?

может я конечно что-то не так понимаю, но а что, могут быть варианты?

ok = (host_addr & net_mask) == net_addr;

// wbr

  Рекомендовать в FAQ | Cообщить модератору | Наверх

25. "И возвращаясь к моим баранам, то бишь принадлежность хоста с..."
Сообщение от Maxim Kuznetsov emailИскать по авторуВ закладки on 24-Сен-04, 16:03  (MSK)
>А у Вас как определяется принадлежность хоста сети?
опуская проверки, только для ip4, просто булевая функция,
все адреса и маски в сетевом представлении :
struct net_info {
  uint32 addr;
  uint32 mask;
  ...
};
int net_contain_host(struct net_info *net,uint32 host) {
...
if ((host & net->mask) == net->addr)
    return 1;
return 0;
}

  Рекомендовать в FAQ | Cообщить модератору | Наверх

20. "В догонку - вопрос по теме"
Сообщение от borik_ints emailИскать по авторуВ закладки(ok) on 24-Сен-04, 15:14  (MSK)
>>Попробую потелепатить: есть массив сетей, надо определить, к которой из них относится
>>указанный хост, при чем надо выбрать запись с минимальной маской.
>>
>>Если да, то простейший способ: сортируешь однократно этот массив по убыванию размера
>>маски (/32 - верхние элементы, /0 - нижние) и потом линейным
>>поиском по массиву до первого совпадения. Возможно, есть варианты улучшения данного
>>способа
>Еще бы. Если массив отсортирован, то искать надо не линейным, а двоичным
>поиском - man bsearch

Не пойдет, ключи сортировки и поиска не совпадают

  Рекомендовать в FAQ | Cообщить модератору | Наверх

22. "В догонку - вопрос по теме"
Сообщение от dimus Искать по авторуВ закладки(??) on 24-Сен-04, 15:26  (MSK)
>>Еще бы. Если массив отсортирован, то искать надо не линейным, а двоичным
>>поиском - man bsearch
>
>Не пойдет, ключи сортировки и поиска не совпадают
Если плясать от хоста - то да. Однако если нам известен хост, то можно было бы воспользоваться "алгоритмом связанности", который идеально решает задачу на принадлежность одного элемента множеству других. Я сейчас не помню все детали реализации, но, в общем, там нет ничего сложного. Алгоритм описан в книге "Фундаментальные алгоритмы на С/С++", которую я всем рекомендую.

  Рекомендовать в FAQ | Cообщить модератору | Наверх

26. "В догонку - вопрос по теме"
Сообщение от ed Искать по авторуВ закладки(??) on 25-Сен-04, 17:14  (MSK)
>Поделитесь ссылкой, или хотя-бы намёком :)
http://www.cs.unc.edu/~geom/TEACH/COMP122/LEC/29.ppt

>Но ведь есть алгоритмы оптимальнее...
http://netlab.cs.tsinghua.edu.cn/~lzy/Lookup/99/IP-address lookup using LC-tries_IEEE Journal on Selected Areas in Communications.pdf

  Рекомендовать в FAQ | Cообщить модератору | Наверх

27. "Большое спасибо"
Сообщение от Maxim Kuznetsov Искать по авторуВ закладки on 26-Сен-04, 01:30  (MSK)
>>Поделитесь ссылкой, или хотя-бы намёком :)
>http://www.cs.unc.edu/~geom/TEACH/COMP122/LEC/29.ppt
>
>>Но ведь есть алгоритмы оптимальнее...
>http://netlab.cs.tsinghua.edu.cn/~lzy/Lookup/99/IP-address lookup using LC-tries_IEEE Journal on Selected Areas in Communications.pdf

Спасибо за ссылки, очень порадовали фотки
в стиле "их разыскивает милиция" во втором документе ;-)

LC-tries конечно хорошо, но для моих целей пойдет и чего попроще ;-)
В результате размышлений пришёл к выводу, что вполне пойдет простое
сбалансированное дерево ;-) Сортируется по номерам сетей, ищется последний подходящий вариант - и вуаля - нужная сеть по хосту найденна !

Еще раз спасибо, документы добавил в личную коллекцию...

  Рекомендовать в FAQ | Cообщить модератору | Наверх


Удалить

Индекс форумов | Темы | Пред. тема | След. тема
Пожалуйста, прежде чем написать сообщение, ознакомьтесь с данными рекомендациями.




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей 		Created 1996-2025 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру