Kea  2.1.7-git
isc::dhcp::IPRangePermutation Class Reference

Random IP address/prefix permutation based on Fisher-Yates shuffle. More...

#include <ip_range_permutation.h>

Public Member Functions

 IPRangePermutation (const AddressRange &range)
 Constructor for address ranges. More...
 
 IPRangePermutation (const PrefixRange &range)
 Constructor for prefix ranges. More...
 
bool exhausted () const
 Checks if the range has been exhausted. More...
 
asiolink::IOAddress next (bool &done)
 Returns next random address or prefix from the permutation. More...
 

Detailed Description

Random IP address/prefix permutation based on Fisher-Yates shuffle.

This class is used to shuffle IP addresses or delegated prefixes within the specified range. It is following the Fisher-Yates shuffle algorithm described in https://en.wikipedia.org/wiki/Fisher–Yates_shuffle.

The original algorithm is modified to keep the minimal information about the current state of the permutation and relies on the caller to collect and store the next available value. In other words, the generated and already returned random values are not stored by this class.

The class assumes that initially the IP addresses or delegated prefixes in the specified range are in increasing order. Suppose we're dealing with the following address range: 192.0.2.1-192.0.2.5. Therefore our addresses are initially ordered like this: a[0]=192.0.2.1, a[1]=192.0.2.2 ..., a[4]=192.0.2.5. The algorithm starts from the end of that range, i.e. i=4, so a[i]=192.0.2.5. A random value from the range of [0..i-1] is picked, i.e. a value from the range of [0..3]. Let's say it is 1. This value initially corresponds to the address a[1]=192.0.2.2. In the original algorithm the value of a[1] is swapped with a[4], yelding the following partial permutation: 192.0.2.1, 192.0.2.5, 192.0.2.3, 192.0.2.4, 192.0.2.2. In our case, we simply return the value of 192.0.2.2 to the caller and remember that a[1]=192.0.2.5. At this point we don't store the values of a[0], a[2] and a[3] because the corresponding IP addresses can be calculated from the range start and their index in the permutation. The value of a[1] must be stored because it has been swapped with a[4] and can't be calculated from the position index.

In the next step, the current index i (cursor value) is decreased by one. It now has the value of 3. Again, a random index is picked from the range of [0..3]. Note that it can be the same or different index than selected in the previous step. Let's assume it is 0. This corresponds to the address of 192.0.2.1. This address will be returned to the caller. The value of a[3]=192.0.2.4 is moved to a[0]. This yelds the following permutation: 192.0.2.4, 192.0.2.5, 192.0.2.3, 192.0.2.1, 192.0.2.2. However, we only remember a[0] and a[1]. The a[3] can be still computed from the range start and the position. The other two have been already returned to the caller so we forget them.

This algorithm guarantees that all IP addresses or delegated prefixes belonging to the given range are returned and no duplicates are returned. The addresses or delegated prefixes are returned in a random order.

Todo:
Methods of this class should be called in thread safe context. Otherwise they should be made thread safe.

Definition at line 66 of file ip_range_permutation.h.

Constructor & Destructor Documentation

◆ IPRangePermutation() [1/2]

isc::dhcp::IPRangePermutation::IPRangePermutation ( const AddressRange range)

Constructor for address ranges.

Parameters
rangeaddress range for which the permutation will be generated.

Definition at line 18 of file ip_range_permutation.cc.

◆ IPRangePermutation() [2/2]

isc::dhcp::IPRangePermutation::IPRangePermutation ( const PrefixRange range)

Constructor for prefix ranges.

Parameters
rangerange of delegated prefixes for which the permutation will be generated.

Definition at line 25 of file ip_range_permutation.cc.

Member Function Documentation

◆ exhausted()

bool isc::dhcp::IPRangePermutation::exhausted ( ) const
inline

Checks if the range has been exhausted.

Returns
false if the algorithm went over all addresses or prefixes in the range, true otherwise.

Definition at line 84 of file ip_range_permutation.h.

References next().

+ Here is the call graph for this function:

◆ next()

IOAddress isc::dhcp::IPRangePermutation::next ( bool &  done)

Returns next random address or prefix from the permutation.

This method returns all addresses or prefixes belonging to the specified range in random order. For the first number of calls equal to the size of the range it guarantees to return a non-zero IP address from that range without duplicates.

Parameters
[out]donethis parameter is set to true if no more addresses or prefixes can be returned for this permutation.
Returns
next available IP address or prefix. It returns IPv4 zero or IPv6 zero address after this method walked over all available IP addresses or prefixes in the range.

Definition at line 32 of file ip_range_permutation.cc.

References isc::asiolink::IOAddress::IPV4_ZERO_ADDRESS(), isc::asiolink::IOAddress::IPV6_ZERO_ADDRESS(), isc::asiolink::IOAddress::isV4(), and isc::asiolink::offsetAddress().

Referenced by exhausted().

+ Here is the call graph for this function:

The documentation for this class was generated from the following files: