mirror of https://github.com/sipwise/kamailio.git
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
115 lines
4.0 KiB
115 lines
4.0 KiB
/* $Id$
|
|
*
|
|
* Copyright (C) 2008 iptelorg GmbH
|
|
*
|
|
* This file is part of ser, a free SIP server.
|
|
*
|
|
* ser is free software; you can redistribute it and/or modify
|
|
* it under the terms of the GNU General Public License as published by
|
|
* the Free Software Foundation; either version 2 of the License, or
|
|
* (at your option) any later version
|
|
*
|
|
* For a license to use the ser software under conditions
|
|
* other than those described here, or to purchase support for this
|
|
* software, please contact iptel.org by e-mail at the following addresses:
|
|
* info@iptel.org
|
|
*
|
|
* ser is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
* GNU General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU General Public License
|
|
* along with this program; if not, write to the Free Software
|
|
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
|
|
*
|
|
*/
|
|
|
|
#ifndef _IP_TREE_H_
|
|
#define _IP_TREE_H_ 1
|
|
|
|
#include <stdio.h>
|
|
#include "../../sr_module.h"
|
|
#include "../../dprint.h"
|
|
#include "../../ip_addr.h"
|
|
#include "../../error.h"
|
|
#include "../../mem/mem.h"
|
|
#include "../../trim.h"
|
|
#include "../../ut.h"
|
|
|
|
/*
|
|
Implements algorithm for testing if particular address is in a iP adrress set.
|
|
IP adresses may also describe a subnetwork, i.e. only prefix is valuable and trailing part
|
|
of address has no effect for decision. The algorithm is common, both IPv4 and IPv6
|
|
are supported.
|
|
|
|
Reduce(match)/decide(fork) algorithm is applied to minimize memory consumption and looping.
|
|
As many bits as possible are matched in leaf (longest prefix match) . If does not match "match_bit_num" then IP is not in set
|
|
otherwise next bit decides what is next leaf and matching goes on.
|
|
If there is not next leaf then algorithm is over (it's subnet address or special case
|
|
particular IP address, in this case address is matched completly).
|
|
|
|
Examples of ip tree {prefix_match_len, prefix_match, next}:
|
|
|
|
0.0.0.0/0, i.e. all addresses
|
|
{0, {}, {NULL, NULL}}
|
|
|
|
128.0.0.0/1
|
|
{1, {0x80}, {NULL, NULL}}
|
|
|
|
127.0.1.0/24
|
|
{24, {0x7F, 0x00, 0x01}, {NULL, NULL}}
|
|
|
|
127.0.1.0/24, 127.0.2.0/24
|
|
01111111.00000000.00000001.00000000 01111111.00000000.00000010.00000000
|
|
{22, {0x7F, 0x00, 0x00}, {
|
|
{1, {0x80}, {NULL, NULL}},
|
|
{1, {0x00}, {NULL, NULL}}
|
|
}
|
|
}
|
|
|
|
127.0.0.0/32, 127.0.0.1/32
|
|
{31, {0x7F, 0x00, 0x00, 0x00}, {NULL, NULL}}
|
|
|
|
192.168.5.64/26, 192.168.5.15/32, 10.0.0.0/8
|
|
11000000.10101000.00000101.01-000000 11000000.10101000.00000101.00001111 00001010-00000000.00000000.00000000
|
|
|
|
{0, {}, {
|
|
{7, {00010100}, {NULL, NULL}},
|
|
{24, {10000001,01010000,00001010}, {
|
|
{6, {00111100}, {NULL, NULL}},
|
|
{0, {}, {NULL, NULL}}
|
|
}}
|
|
}}
|
|
|
|
|
|
*/
|
|
|
|
struct ip_tree_leaf {
|
|
unsigned int prefix_match_len; /* next prefix_match_len must be equal to next bit in IP address being compared */
|
|
struct ip_tree_leaf *next[2]; /* tree goes on in leaf based on first bit following prefix_match, if next[0] && next[1] are null then IP matches - it's subnet address */
|
|
unsigned char prefix_match[0]; /* match_bits div 8 + 1, the same representation as ip address */
|
|
};
|
|
|
|
struct ip_tree_find {
|
|
struct ip_tree_leaf *leaf;
|
|
unsigned int leaf_prefix_match_len;
|
|
unsigned char *leaf_prefix_match;
|
|
unsigned char leaf_prefix_match_mask;
|
|
unsigned char *ip;
|
|
unsigned int ip_len;
|
|
unsigned char ip_mask;
|
|
};
|
|
|
|
#define IP_TREE_FIND_NOT_FOUND 0
|
|
#define IP_TREE_FIND_FOUND 1
|
|
#define IP_TREE_FIND_FOUND_UPPER_SET 2
|
|
|
|
extern void ip_tree_init(struct ip_tree_leaf **tree);
|
|
extern void ip_tree_destroy(struct ip_tree_leaf **tree, int leaves_only, int use_shm);
|
|
extern int ip_tree_find_ip(struct ip_tree_leaf *tree, unsigned char *ip, unsigned int ip_len, struct ip_tree_find *h);
|
|
extern int ip_tree_add_ip(struct ip_tree_leaf **tree, unsigned char *ip, unsigned int ip_len, int use_shm);
|
|
extern void ip_tree_print(FILE *stream, struct ip_tree_leaf *tree, unsigned int indent);
|
|
extern str ip_tree_mask_to_str(unsigned char *pm, unsigned int len);
|
|
#endif
|