import com.google.common.annotations.VisibleForTesting;

import com.google.common.base.MoreObjects;

import com.google.common.base.Objects;

import com.google.common.base.Preconditions;

import io.grpc.ConnectivityState;

import io.grpc.EquivalentAddressGroup;

import io.grpc.Internal;

import io.grpc.LoadBalancer;

import io.grpc.NameResolver;

import io.grpc.Status;

import java.util.ArrayList;

import java.util.Collection;

import java.util.HashSet;

import java.util.List;

import java.util.Map;

import java.util.Random;

import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;

import javax.annotation.Nonnull;

import java.util.concurrent.atomic.AtomicInteger;

/**

* A {@link LoadBalancer} that provides round-robin load-balancing over the {@link

* EquivalentAddressGroup}s from the {@link NameResolver}.

*/

@Internal

public class RoundRobinLoadBalancer extends MultiChildLoadBalancer {

private final Random random;

protected RoundRobinPicker currentPicker = new EmptyPicker(EMPTY_OK);

private final AtomicInteger sequence = new AtomicInteger(new Random().nextInt());

protected SubchannelPicker currentPicker = new EmptyPicker();

public RoundRobinLoadBalancer(Helper helper) {

super(helper);

this.random = new Random();

}

@Override

protected SubchannelPicker getSubchannelPicker(Map<Object, SubchannelPicker> childPickers) {

throw new UnsupportedOperationException(); // local updateOverallBalancingState doesn't use this

}

private static final Status EMPTY_OK = Status.OK.withDescription("no subchannels ready");

/**

* Updates picker with the list of active subchannels (state == READY).

*/

}

if (isConnecting) {

updateBalancingState(CONNECTING, new EmptyPicker(Status.OK));

updateBalancingState(CONNECTING, new EmptyPicker());

} else {

updateBalancingState(TRANSIENT_FAILURE, createReadyPicker(getChildLbStates()));

}

}

}

private void updateBalancingState(ConnectivityState state, RoundRobinPicker picker) {

if (state != currentConnectivityState || !picker.isEquivalentTo(currentPicker)) {

private void updateBalancingState(ConnectivityState state, SubchannelPicker picker) {

if (state != currentConnectivityState || !picker.equals(currentPicker)) {

getHelper().updateBalancingState(state, picker);

currentConnectivityState = state;

currentPicker = picker;

}

}

protected RoundRobinPicker createReadyPicker(Collection<ChildLbState> children) {

// initialize the Picker to a random start index to ensure that a high frequency of Picker

// churn does not skew subchannel selection.

int startIndex = random.nextInt(children.size());

protected SubchannelPicker createReadyPicker(Collection<ChildLbState> children) {

List<SubchannelPicker> pickerList = new ArrayList<>();

for (ChildLbState child : children) {

SubchannelPicker picker = child.getCurrentPicker();

pickerList.add(picker);

}

return new ReadyPicker(pickerList, startIndex);

}

public abstract static class RoundRobinPicker extends SubchannelPicker {

public abstract boolean isEquivalentTo(RoundRobinPicker picker);

return new ReadyPicker(pickerList, sequence);

}

@VisibleForTesting

static class ReadyPicker extends RoundRobinPicker {

private static final AtomicIntegerFieldUpdater<ReadyPicker> indexUpdater =

AtomicIntegerFieldUpdater.newUpdater(ReadyPicker.class, "index");

static class ReadyPicker extends SubchannelPicker {

private final List<SubchannelPicker> subchannelPickers; // non-empty

@SuppressWarnings("unused")

private volatile int index;

private final AtomicInteger index;

private final int hashCode;

public ReadyPicker(List<SubchannelPicker> list, int startIndex) {

public ReadyPicker(List<SubchannelPicker> list, AtomicInteger index) {

checkArgument(!list.isEmpty(), "empty list");

this.subchannelPickers = list;

this.index = startIndex - 1;

this.index = Preconditions.checkNotNull(index, "index");

// Every created picker is checked for equality in updateBalancingState() at least once.

// Pre-compute the hash so it can be checked cheaply. Using the hash in equals() makes it very

// fast except when the pickers are (very likely) equal.

//

// For equality we treat children as a set; use hash code as defined by Set

int sum = 0;

for (SubchannelPicker picker : subchannelPickers) {

sum += picker.hashCode();

}

this.hashCode = sum;

}

@Override

}

private int nextIndex() {

int size = subchannelPickers.size();

int i = indexUpdater.incrementAndGet(this);

if (i >= size) {

int oldi = i;

i %= size;

indexUpdater.compareAndSet(this, oldi, i);

}

return i;

int i = index.getAndIncrement() & Integer.MAX_VALUE;

return i % subchannelPickers.size();

}

@VisibleForTesting

}

@Override

public boolean isEquivalentTo(RoundRobinPicker picker) {

if (!(picker instanceof ReadyPicker)) {

public int hashCode() {

return hashCode;

}

@Override

public boolean equals(Object o) {

if (!(o instanceof ReadyPicker)) {

return false;

}

ReadyPicker other = (ReadyPicker) picker;

ReadyPicker other = (ReadyPicker) o;

if (other == this) {

return true;

}

// the lists cannot contain duplicate subchannels

return other == this

|| (subchannelPickers.size() == other.subchannelPickers.size() && new HashSet<>(

subchannelPickers).containsAll(other.subchannelPickers));

return hashCode == other.hashCode

&& index == other.index

&& subchannelPickers.size() == other.subchannelPickers.size()

&& new HashSet<>(subchannelPickers).containsAll(other.subchannelPickers);

}

}

@VisibleForTesting

static final class EmptyPicker extends RoundRobinPicker {

private final Status status;

EmptyPicker(@Nonnull Status status) {

this.status = Preconditions.checkNotNull(status, "status");

}

static final class EmptyPicker extends SubchannelPicker {

@Override

public PickResult pickSubchannel(PickSubchannelArgs args) {

return status.isOk() ? PickResult.withNoResult() : PickResult.withError(status);

return PickResult.withNoResult();

}

@Override

public boolean isEquivalentTo(RoundRobinPicker picker) {

return picker instanceof EmptyPicker && (Objects.equal(status, ((EmptyPicker) picker).status)

|| (status.isOk() && ((EmptyPicker) picker).status.isOk()));

public int hashCode() {

return getClass().hashCode();

}

@Override

public String toString() {

return MoreObjects.toStringHelper(EmptyPicker.class).add("status", status).toString();

}

}

/**

* A lighter weight Reference than AtomicReference.

*/

@VisibleForTesting

static final class Ref<T> {

T value;

Ref(T value) {

this.value = value;

public boolean equals(Object o) {

return o instanceof EmptyPicker;

}

}

}