Kea 2.5.9
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.
 
 IPRangePermutation (const PrefixRange &range)
 Constructor for prefix ranges.
 
bool exhausted () const
 Checks if the range has been exhausted.
 
asiolink::IOAddress next (bool &done)
 Returns next random address or prefix from the permutation.
 
void reset ()
 Resets the permutation state.
 

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 67 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 85 of file ip_range_permutation.h.

◆ 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 34 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().

+ Here is the call graph for this function:

◆ reset()

void isc::dhcp::IPRangePermutation::reset ( )

Resets the permutation state.

It effectively causes the permutation to start over the process of serving addresses. Any previously returned addresses can be returned again after calling this function.

Definition at line 107 of file ip_range_permutation.cc.


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