Matches IP addresses against a set of CIDR specifications. More...
Public Member Functions | |
| __construct (array $cfg) | |
| __construct() instantiate the object from an array of CIDR specs | |
| match ($ip) | |
| Match an IP address against the set. | |
Private Member Functions | |
| addCidr ($cidr) | |
| Add a single CIDR spec to the internal matching trees. | |
Static Private Member Functions | |
| static | recCompress (&$node, $curBit, $maxCompStart) |
| Recursively compresses a tree. | |
| static | recOptimize (&$node) |
| Recursively merges adjacent nets into larger supernets. | |
Private Attributes | |
| array | $root4 = array( false, false ) |
| $root4: the root of the IPv4 matching tree * | |
| array | $root6 = array( false, false ) |
| $root6: the root of the IPv6 matching tree * | |
Detailed Description
Matches IP addresses against a set of CIDR specifications.
Usage: // At startup, calculate the optimized data structure for the set: $ipset = new IPSet( $wgSquidServersNoPurge ); // runtime check against cached set (returns bool): $allowme = $ipset->match( $ip );
In rough benchmarking, this takes about 80% more time than in_array() checks on a short (a couple hundred at most) array of addresses. It's fast either way at those levels, though, and IPSet would scale better than in_array if the array were much larger.
For mixed-family CIDR sets, however, this code gives well over 100x speedup vs iterating IP::isInRange() over an array of CIDR specs.
The basic implementation is two separate binary trees (IPv4 and IPv6) as nested php arrays with keys named 0 and 1. The values false and true are terminal match-fail and match-success, otherwise the value is a deeper node in the tree.
A simple depth-compression scheme is also implemented: whole-byte tree compression at whole-byte boundaries only, where no branching occurs during that whole byte of depth. A compressed node has keys 'comp' (the byte to compare) and 'next' (the next node to recurse into if 'comp' matched successfully).
For example, given these inputs: 25.0.0.0/9 25.192.0.0/10
The v4 tree would look like: root4 => array( 'comp' => 25, 'next' => array( 0 => true, 1 => array( 0 => false, 1 => true, ), ), );
(multi-byte compression nodes were attempted as well, but were a net loss in my test scenarios due to additional match complexity)
- Since:
- 1.24
Constructor & Destructor Documentation
| IPSet::__construct | ( | array $ | cfg | ) |
__construct() instantiate the object from an array of CIDR specs
- Parameters:
-
array $cfg array of IPv[46] CIDR specs as strings
Invalid input network/mask values in $cfg will result in issuing E_WARNING and/or E_USER_WARNING and the bad values being ignored.
Member Function Documentation
| IPSet::addCidr | ( | $ | cidr | ) | [private] |
| IPSet::match | ( | $ | ip | ) |
| static IPSet::recCompress | ( | &$ | node, |
| $ | curBit, | ||
| $ | maxCompStart | ||
| ) | [static, private] |
Recursively compresses a tree.
- Parameters:
-
array &$node Tree node to compress, by-reference integer $curBit current depth in the tree integer $maxCompStart maximum depth at which compression can start, family-specific
This is a very simplistic compression scheme: if we go through a whole byte of address starting at a byte boundary with no real branching other than immediate false-vs-(node|true), compress that subtree down to a single byte-matching node. The $maxCompStart check elides recursing the final 7 levels of depth (family-dependent)
| static IPSet::recOptimize | ( | &$ | node | ) | [static, private] |
Member Data Documentation
The documentation for this class was generated from the following file:
- includes/libs/IPSet.php
