forum.opennet.ru - "Проверка на принадлежность адреса сети: как?" (27)

форумы

помощь

поиск

регистрация

майллист

ВХОД

слежка

"Проверка на принадлежность адреса сети: как?"

Форумы Программирование под UNIX (Public)
Вариант для распечатки		Архивированная нить - только для чтения! Пред. тема \| След. тема
Изначальное сообщение		[Проследить за развитием треда]

"Проверка на принадлежность адреса сети: как?"
Сообщение от borik_ints (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ообщить модератору \| Наверх

Оглавление

Проверка на принадлежность адреса сети: как?, dimus, 10:17 , 24-Сен-04, (1)
- Проверка на принадлежность адреса сети: как?, borik_ints, 11:39 , 24-Сен-04, (2)
  - Проверка на принадлежность адреса сети: как?, klalafuda, 11:55 , 24-Сен-04, (3)
  - Проверка на принадлежность адреса сети: как?, klalafuda, 11:58 , 24-Сен-04, (4)
    - Проверка на принадлежность адреса сети: как?, borik_ints, 12:23 , 24-Сен-04, (5)
      - Проверка на принадлежность адреса сети: как?, klalafuda, 13:09 , 24-Сен-04, (6)
        
        Проверка на принадлежность адреса сети: как?, dimus, 14:01 , 24-Сен-04, (7)
        
        Проверка на принадлежность адреса сети: как?, klalafuda, 14:16 , 24-Сен-04, (9)
        
        В догонку - вопрос по теме, Maxim Kuznetsov, 14:09 , 24-Сен-04, (8)
        
        В догонку - вопрос по теме, klalafuda, 14:19 , 24-Сен-04, (10)
        
        В догонку - вопрос по теме, Maxim Kuznetsov, 14:48 , 24-Сен-04, (13)
        
        В догонку - вопрос по теме, klalafuda, 15:03 , 24-Сен-04, (14)
        
        В догонку - вопрос по теме, Maxim Kuznetsov, 15:08 , 24-Сен-04, (17)
        
        В догонку - вопрос по теме, klalafuda, 15:58 , 24-Сен-04, (24)
        
        В догонку - вопрос по теме, dimus, 14:24 , 24-Сен-04, (11)
        В догонку - вопрос по теме, borik_ints, 14:42 , 24-Сен-04, (12)
        
        В догонку - вопрос по теме, Maxim Kuznetsov, 15:04 , 24-Сен-04, (15)
        
        В догонку - вопрос по теме, borik_ints, 15:11 , 24-Сен-04, (18)
        
        В догонку - вопрос по теме, dimus, 15:07 , 24-Сен-04, (16)
        
        В догонку - вопрос по теме, Maxim Kuznetsov, 15:12 , 24-Сен-04, (19)
        
        И возвращаясь к моим баранам, то бишь принадлежность хоста с..., borik_ints, 15:23 , 24-Сен-04, (21)
        
        И возвращаясь к моим баранам, то бишь принадлежность хоста с..., klalafuda, 15:44 , 24-Сен-04, (23)
        И возвращаясь к моим баранам, то бишь принадлежность хоста с..., Maxim Kuznetsov, 16:03 , 24-Сен-04, (25)
        
        В догонку - вопрос по теме, borik_ints, 15:14 , 24-Сен-04, (20)
        
        В догонку - вопрос по теме, dimus, 15:26 , 24-Сен-04, (22)
        
        В догонку - вопрос по теме, ed, 17:14 , 25-Сен-04, (26)
        
        Большое спасибо, Maxim Kuznetsov, 01:30 , 26-Сен-04, (27)

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

Сообщения по теме

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 (ok) on 24-Сен-04, 11:39  (MSK)

Как именно организуетс маска подсети, мне известно, но все равно спасибо за разъяснение :)
>Используя старый добрый оператор & можно быстро и эффективно решить проблему. Никаких
>циклов не надо.
Во первых: на разных платформах порядок байтов в struct in_addr разный, а из манов я так и не вынес, какой надо юзать для обеспечения кроссплатформенности :(
Во-вторых: мне надо каждый раз создавать накладываемую маску разной длинны, как ее создать? воспользоваться потом оператором & проблемы не составит...
то есть, мне нужно на 192.168.21.15 наложить маску /21, а на 197.185.16.11 - /24. При помощи чего мне эти маски создавать?
ЗЫ: циклы использовались для создания массива сетей, а не определения маски :)

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

3. "Проверка на принадлежность адреса сети: как?"

Сообщение от klalafuda 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 on 24-Сен-04, 11:58  (MSK)

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

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

5. "Проверка на принадлежность адреса сети: как?"

Сообщение от borik_ints (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 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 on 24-Сен-04, 14:16  (MSK)

>Скоростной метод:
>Тупо руками создаем 32 маски и заносим в массив под соответствующим индексом.
как вариант. с учетом вполне конкретной постановки задачи, это вполне подойдет.
>Это даст очень высокую скорость. Вообще, по моему, если важна скорость,
>лучше всю функцию распознавания переписать на ассемблере. Этот язык идеально подходит
>для битовых операций.
а вот этого делать видимо не стоит :) выигрыш по сравнению с таблицей такой подход даст нулевой, а вот геморою с сопровождением такого решения можно огрестить по полной программе, причем, на пустом месте.
// wbr

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

8. "В догонку - вопрос по теме"

Сообщение от Maxim Kuznetsov 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 on 24-Сен-04, 14:19  (MSK)

>Есть таблица с префиксами сетей ~5000 записей,
>включает сети, некоторые подсети и отдельные хосты,
>как в ней сделать быстрый поиск подходяшей записи с максимальной длинной маски
>(определение минимальной подсети) ?
ммм... не совсем понял, что же именно вы хотите сделать. опишите задачу несколько подробнее :) что на входе, что на выходе.
// wbr

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

13. "В догонку - вопрос по теме"

Сообщение от Maxim Kuznetsov 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 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 on 24-Сен-04, 15:08  (MSK)

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

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

24. "В догонку - вопрос по теме"

Сообщение от klalafuda 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 (ok) on 24-Сен-04, 14:42  (MSK)

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

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

15. "В догонку - вопрос по теме"

Сообщение от Maxim Kuznetsov on 24-Сен-04, 15:04  (MSK)

Телепат !!
так оно и есть - так оно сейчас и сделанно,
с простейшим улучшением (ищется сразу два адреса, пока не будут найденны оба)
Собственно вопрос - возможно ли другое, более оптимальное по скорости решение ?

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

18. "В догонку - вопрос по теме"

Сообщение от borik_ints (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 on 24-Сен-04, 15:12  (MSK)

>Еще бы. Если массив отсортирован, то искать надо не линейным, а двоичным
>поиском - man bsearch
к сожалению bsearch не помогает в этой задаче - практически наверняка
на первой же итерации он найдет ´подходящую´ запись 0.0.0.0/0 описывающую вообще всё множество сетей - а дальше как ?

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

21. "И возвращаясь к моим баранам, то бишь принадлежность хоста с..."

Сообщение от borik_ints (ok) on 24-Сен-04, 15:23  (MSK)

А у Вас как определяется принадлежность хоста сети?

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

23. "И возвращаясь к моим баранам, то бишь принадлежность хоста с..."

Сообщение от klalafuda on 24-Сен-04, 15:44  (MSK)

>А у Вас как определяется принадлежность хоста сети?
может я конечно что-то не так понимаю, но а что, могут быть варианты?
ok = (host_addr & net_mask) == net_addr;
// wbr

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

25. "И возвращаясь к моим баранам, то бишь принадлежность хоста с..."

Сообщение от Maxim Kuznetsov 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 (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ообщить модератору | Наверх

Удалить

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

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

Партнёры:

Хостинг:

Закладки на сайте
Проследить за страницей

Created 1996-2025 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру

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 (ok) on 24-Сен-04, 11:39 (MSK)
	Как именно организуетс маска подсети, мне известно, но все равно спасибо за разъяснение :) >Используя старый добрый оператор & можно быстро и эффективно решить проблему. Никаких >циклов не надо. Во первых: на разных платформах порядок байтов в struct in_addr разный, а из манов я так и не вынес, какой надо юзать для обеспечения кроссплатформенности :( Во-вторых: мне надо каждый раз создавать накладываемую маску разной длинны, как ее создать? воспользоваться потом оператором & проблемы не составит... то есть, мне нужно на 192.168.21.15 наложить маску /21, а на 197.185.16.11 - /24. При помощи чего мне эти маски создавать? ЗЫ: циклы использовались для создания массива сетей, а не определения маски :)
		Рекомендовать в FAQ \| Cообщить модератору \| Наверх


	3. "Проверка на принадлежность адреса сети: как?"
	Сообщение от klalafuda 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 on 24-Сен-04, 11:58 (MSK)
	>Во первых: на разных платформах порядок байтов в struct in_addr разный, а >из манов я так и не вынес, какой надо юзать для >обеспечения кроссплатформенности :( ps: маны в таком вопросе, как слендование стандарту, далеко не самый правильный источник информации. // wbr
		Рекомендовать в FAQ \| Cообщить модератору \| Наверх


	5. "Проверка на принадлежность адреса сети: как?"
	Сообщение от borik_ints (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 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 on 24-Сен-04, 14:16 (MSK)
	>Скоростной метод: >Тупо руками создаем 32 маски и заносим в массив под соответствующим индексом. как вариант. с учетом вполне конкретной постановки задачи, это вполне подойдет. >Это даст очень высокую скорость. Вообще, по моему, если важна скорость, >лучше всю функцию распознавания переписать на ассемблере. Этот язык идеально подходит >для битовых операций. а вот этого делать видимо не стоит :) выигрыш по сравнению с таблицей такой подход даст нулевой, а вот геморою с сопровождением такого решения можно огрестить по полной программе, причем, на пустом месте. // wbr
		Рекомендовать в FAQ \| Cообщить модератору \| Наверх


	8. "В догонку - вопрос по теме"
	Сообщение от Maxim Kuznetsov 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 on 24-Сен-04, 14:19 (MSK)
	>Есть таблица с префиксами сетей ~5000 записей, >включает сети, некоторые подсети и отдельные хосты, >как в ней сделать быстрый поиск подходяшей записи с максимальной длинной маски >(определение минимальной подсети) ? ммм... не совсем понял, что же именно вы хотите сделать. опишите задачу несколько подробнее :) что на входе, что на выходе. // wbr
		Рекомендовать в FAQ \| Cообщить модератору \| Наверх


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


	24. "В догонку - вопрос по теме"
	Сообщение от klalafuda 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 (ok) on 24-Сен-04, 14:42 (MSK)
	>видимо решаем схожие задачи :-) >Есть таблица с префиксами сетей ~5000 записей, >включает сети, некоторые подсети и отдельные хосты, >как в ней сделать быстрый поиск подходяшей записи с максимальной длинной маски >(определение минимальной подсети) ? >Пока-что сделал в лоб, простым просмотром всего, но сразу для двух адресов. >Но ведь есть алгоритмы оптимальнее... >Поделитесь ссылкой, или хотя-бы намёком :) Попробую потелепатить: есть массив сетей, надо определить, к которой из них относится указанный хост, при чем надо выбрать запись с минимальной маской. Если да, то простейший способ: сортируешь однократно этот массив по убыванию размера маски (/32 - верхние элементы, /0 - нижние) и потом линейным поиском по массиву до первого совпадения. Возможно, есть варианты улучшения данного способа
		Рекомендовать в FAQ \| Cообщить модератору \| Наверх


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


	18. "В догонку - вопрос по теме"
	Сообщение от borik_ints (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 on 24-Сен-04, 15:12 (MSK)
	>Еще бы. Если массив отсортирован, то искать надо не линейным, а двоичным >поиском - man bsearch к сожалению bsearch не помогает в этой задаче - практически наверняка на первой же итерации он найдет ´подходящую´ запись 0.0.0.0/0 описывающую вообще всё множество сетей - а дальше как ?
		Рекомендовать в FAQ \| Cообщить модератору \| Наверх


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


	23. "И возвращаясь к моим баранам, то бишь принадлежность хоста с..."
	Сообщение от klalafuda on 24-Сен-04, 15:44 (MSK)
	>А у Вас как определяется принадлежность хоста сети? может я конечно что-то не так понимаю, но а что, могут быть варианты? ok = (host_addr & net_mask) == net_addr; // wbr
		Рекомендовать в FAQ \| Cообщить модератору \| Наверх


	25. "И возвращаясь к моим баранам, то бишь принадлежность хоста с..."
	Сообщение от Maxim Kuznetsov 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 (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ообщить модератору \| Наверх