 |
Kea 2.7.6
|
|
Kea 2.7.6
|
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. | |
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.
Definition at line 67 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 85 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 non-zero 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 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:| 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.
1.12.0