Kea
1.9.9git

Random IP address/prefix permutation based on FisherYates 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...  
Random IP address/prefix permutation based on FisherYates shuffle.
This class is used to shuffle IP addresses or delegated prefixes within the specified range. It is following the FisherYates 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.1192.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..i1] 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.
Definition at line 66 of file ip_range_permutation.h.
isc::dhcp::IPRangePermutation::IPRangePermutation  (  const AddressRange &  range  ) 
Constructor for address ranges.
range  address range for which the permutation will be generated. 
Definition at line 18 of file ip_range_permutation.cc.
isc::dhcp::IPRangePermutation::IPRangePermutation  (  const PrefixRange &  range  ) 
Constructor for prefix ranges.
range  range of delegated prefixes for which the permutation will be generated. 
Definition at line 25 of file ip_range_permutation.cc.

inline 
Checks if the range has been exhausted.
Definition at line 84 of file ip_range_permutation.h.
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 nonzero IP address from that range without duplicates.
[out]  done  this parameter is set to true if no more addresses or prefixes can be returned for this permutation. 
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().