Finding Consecutive IP addresses in a LARGE array

[CarmenH]

I have a list of IP addresses in an very very very large array in random order.

 

I am trying to find a way to determine if there are at least 8 IP addresses that are consecutive. I was thinking some sort of for loop after a sort but that seems very time consuming and I'm sure PHP has a better way...

 

Some searching online revealed this: http://bytes.com/topic/php/answers/12143-flagging-consecutive-numbers-data-set  Is this the way to go?

 

Any tips?

 

Thanks!

Carmen

[schilly]

Sort the array.

 

Then loop through the array.

 

Check the previous one against the current one. If it's consecutive, increment a counter else reset it. If you hit 8 output/save the block.

 

It will be pretty slow if your data set is huge.

[PFMaBiSmAd]

If each set of 8 consecutive ip addresses you are trying to find start on a bit boundary such that you could mask off the lower three bits and if all the remaining bits are the same, they are in the same group of 8, you can do this by -

 

1) Either convert the IP address to integers or only operate on the last octet of the IP address.

2) Mask off the lower three bits using the & bitwise operator and the correct mask. You can form a mask by using  -1 ^ 8 (-1 xor . This will produce a mask of 1111 1111 1111 1111 1111 1111 1111 1000.

3) Use array_count_values() to combine and count the values.

4) Any results from array_count_values() equaling 8 would mean that all eight ip addresses in that group were present.

 

For example, if you had these values somewhere in your original data (order does not matter) -

 

192.168.1.232

192.168.1.233

192.168.1.234

192.168.1.235

192.168.1.236

192.168.1.237

192.168.1.238

192.168.1.239

 

After applying & with the mask you would have -

 

192.168.1.232

192.168.1.232

192.168.1.232

192.168.1.232

192.168.1.232

192.168.1.232

192.168.1.232

192.168.1.232

 

After array_count_values() you would have -

 

[192.168.1.232] => 8

 

The actual matching range would be from that IP address through and including that address + 7

[schilly]

After array_count_values() you would have -

 

[192.168.1.232] => 8

 

The actual matching range would be from that IP address through and including that address + 7

 

Nice!

[CarmenH]

I ended up using ip2long and sorting the array... and then using a counter.  I couldn't quite figure out the masking, although that idea sounds great!

 

Here's the code.

function DataSort ($ouid, $iplist)
{

foreach ($ouid as $value)
{
	$array1=$iplist[$value];
	sort($array1);
	$y=1;
		 /*print "Customer " .$value . " owns " . count($array1) ." ips </p>";
		echo "Consecutive IPs:</p>";*/
	for ($x = 0; $x < count($array1); $x++)
	{
		  $z= $x+1; 

				if ($z < count($array1))
				{
				$value1= $array1[$x];
				$value2 = $array1[$z];
				$consecnumb  = $value1 +1;
                            
						if($value2 == $consecnumb) //if the next value is consecutive
							{
								$y++; //add to the y counter
								$lastconsecip = ($value2);
								$lastip= long2ip($value2);
								$firstip= long2ip($value1);
								/*echo "$firstip , $lastip </p>";*/
							}




					else // if it is not consecutive
									{


						if	($y >= //but the counter is greater than or equal to 8
							{

							$r = $y-1;
							$firstlong = $lastconsecip - $r;
							$firstiprep = long2ip ($firstlong);
							$lastiprep = long2ip ($lastconsecip);

echo "<p><b>ALERT!</b>  There are $y consecutive IP 	
addresses owned by customer OUID: $value. </br> The first IP is $firstiprep and last IP in the consecutive list is $lastiprep</p>";


}//ifclose


	$y=1;
}//else close

}//ifclose




} // for close
} // foreach close

 

I had to butcher the formatting a bit but you get the idea