Class: IPSet  - X-Ref

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)