--- /dev/null
+/*
+ * Copyright (c) 2018 AT&T Intellectual Property. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.protocol.bgp.mode.impl;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+import com.google.common.annotations.Beta;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSet.Builder;
+import java.lang.reflect.Array;
+import java.util.Arrays;
+import java.util.Comparator;
+import org.opendaylight.yangtools.concepts.Immutable;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * A map maintaining a set of values in an external array corresponding to a set of keys. This class is expected to be
+ * used as a template, i.e. users subclass it to a concrete map and use exclusively that class to access the
+ * functionality.
+ */
+@Beta
+public abstract class AbstractOffsetMap<K extends Immutable & Comparable<K>, T extends AbstractOffsetMap<K, T>> {
+ private static final Logger LOG = LoggerFactory.getLogger(AbstractOffsetMap.class);
+ private static final String INVALIDOFFSET = "Invalid offset %s for %s router IDs";
+
+ private final K[] keys;
+
+ protected AbstractOffsetMap(final K[] emptyKeys, final Comparator<K> comparator, final ImmutableSet<K> routerIds) {
+ final K[] array = routerIds.toArray(emptyKeys);
+ Arrays.sort(array, comparator);
+ this.keys = array;
+ }
+
+ public final K getKey(final int offset) {
+ return this.keys[offset];
+ }
+
+ public final int offsetOf(final K key) {
+ return Arrays.binarySearch(keys, key, comparator());
+ }
+
+ public final boolean isEmpty() {
+ return keys.length == 0;
+ }
+
+ public final int size() {
+ return keys.length;
+ }
+
+ public final T with(final K key) {
+ // TODO: we could make this faster if we had an array-backed Set and requiring
+ // the caller to give us the result of offsetOf() -- as that indicates
+ // where to insert the new routerId while maintaining the sorted nature
+ // of the array
+ final Builder<K> builder = ImmutableSet.builderWithExpectedSize(size() + 1);
+ builder.add(keys);
+ builder.add(key);
+ return instanceForKeys(builder.build());
+ }
+
+ public final T without(final K key) {
+ final ImmutableSet<K> set;
+ final int index = indexOf(key);
+ if (index < 0) {
+ LOG.trace("Router key {} not found", key);
+ set = ImmutableSet.of();
+ } else {
+ set = ImmutableSet.copyOf(removeValue(keys, index, emptyKeys()));
+ }
+ return instanceForKeys(set);
+ }
+
+ public final <C> C getValue(final C[] array, final int offset) {
+ checkAccessOffest(offset);
+ return array[offset];
+ }
+
+ public final <C> void setValue(final C[] array, final int offset, final C value) {
+ checkAccessOffest(offset);
+ array[offset] = value;
+ }
+
+ public final <C> C[] expand(final T oldOffsets, final C[] oldArray, final int offset) {
+ @SuppressWarnings("unchecked")
+ final C[] ret = (C[]) Array.newInstance(oldArray.getClass().getComponentType(), keys.length);
+
+ System.arraycopy(oldArray, 0, ret, 0, offset);
+ System.arraycopy(oldArray, offset, ret, offset + 1, oldOffsets.size() - offset);
+ return ret;
+ }
+
+ public final <C> C[] removeValue(final C[] oldArray, final int offset, final C[] emptyArray) {
+ checkNegativeOffset(offset);
+ final int length = oldArray.length;
+ checkArgument(offset < keys.length, INVALIDOFFSET, offset, length);
+
+ final int newLength = length - 1;
+ if (newLength == 0) {
+ checkArgument(emptyArray.length == 0);
+ return emptyArray;
+ }
+
+ @SuppressWarnings("unchecked")
+ final C[] ret = (C[]) Array.newInstance(oldArray.getClass().getComponentType(), newLength);
+ System.arraycopy(oldArray, 0, ret, 0, offset);
+ if (offset < newLength) {
+ System.arraycopy(oldArray, offset + 1, ret, offset, newLength - offset);
+ }
+
+ return ret;
+ }
+
+ protected abstract Comparator<K> comparator();
+
+ protected abstract K[] emptyKeys();
+
+ protected abstract T instanceForKeys(ImmutableSet<K> newKeys);
+
+ private int indexOf(final K key) {
+ for (int i = 0; i < keys.length; i++) {
+ if (key.equals(keys[i])) {
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ private void checkAccessOffest(final int offset) {
+ checkNegativeOffset(offset);
+ checkArgument(offset < keys.length, INVALIDOFFSET, offset, keys.length);
+ }
+
+ private static void checkNegativeOffset(final int offset) {
+ checkArgument(offset >= 0, "Invalid negative offset %s", offset);
+ }
+}
private static final Long[] EMPTY_PATHS_ID = new Long[0];
private static final Route[] EMPTY_VALUES = new Route[0];
- private OffsetMap offsets = OffsetMap.EMPTY;
+ private RouteKeyOffsets offsets = RouteKeyOffsets.EMPTY;
private R[] values = (R[]) EMPTY_VALUES;
private Long[] pathsId = EMPTY_PATHS_ID;
private List<AddPathBestPath> bestPath;
private boolean isNonAddPathBestPathNew;
private R createRoute(final RIBSupport<C, S, R, I> ribSup, final String routeKey, final AddPathBestPath path) {
- final OffsetMap map = this.offsets;
+ final RouteKeyOffsets map = this.offsets;
final R route = map.getValue(this.values, map.offsetOf(path.getRouteKey()));
return ribSup.createRoute(route, ribSup.createRouteListKey(pathIdObj(path.getPathIdLong()), routeKey),
path.getAttributes());
final RouteKey key = new RouteKey(routerId, remotePathId);
int offset = this.offsets.offsetOf(key);
if (offset < 0) {
- final OffsetMap newOffsets = this.offsets.with(key);
+ final RouteKeyOffsets newOffsets = this.offsets.with(key);
offset = newOffsets.offsetOf(key);
final R[] newRoute = newOffsets.expand(this.offsets, this.values, offset);
final Long[] newPathsId = newOffsets.expand(this.offsets, this.pathsId, offset);
+++ /dev/null
-/*
- * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
- *
- * This program and the accompanying materials are made available under the
- * terms of the Eclipse Public License v1.0 which accompanies this distribution,
- * and is available at http://www.eclipse.org/legal/epl-v10.html
- */
-package org.opendaylight.protocol.bgp.mode.impl.add;
-
-import static com.google.common.base.Preconditions.checkArgument;
-
-import com.google.common.cache.CacheBuilder;
-import com.google.common.cache.CacheLoader;
-import com.google.common.cache.LoadingCache;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.ImmutableSet.Builder;
-import java.lang.reflect.Array;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.Set;
-import javax.annotation.Nonnull;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-/**
- * A map of Router identifier to an offset. Used to maintain a simple
- * offset-based lookup across multiple RouteEntry objects,
- * which share either contributors or consumers.
- * We also provide utility reformat methods, which provide access to
- * array members and array management features.
- */
-final class OffsetMap {
- private static final Logger LOG = LoggerFactory.getLogger(OffsetMap.class);
- private static final String NEGATIVEOFFSET = "Invalid negative offset %s";
- private static final String INVALIDOFFSET = "Invalid offset %s for %s router IDs";
- private static final LoadingCache<Set<RouteKey>, OffsetMap> OFFSETMAPS = CacheBuilder.newBuilder().weakValues()
- .build(new CacheLoader<Set<RouteKey>, OffsetMap>() {
- @Override
- public OffsetMap load(@Nonnull final Set<RouteKey> key) {
- return new OffsetMap(key);
- }
- });
- private static final Comparator<RouteKey> COMPARATOR = RouteKey::compareTo;
- private static final RouteKey[] EMPTY_KEYS = new RouteKey[0];
- static final OffsetMap EMPTY = new OffsetMap(Collections.emptySet());
-
- private final RouteKey[] routeKeys;
-
- private OffsetMap(final Set<RouteKey> routerIds) {
- final RouteKey[] array = routerIds.toArray(EMPTY_KEYS);
- Arrays.sort(array, COMPARATOR);
- this.routeKeys = array;
- }
-
- int offsetOf(final RouteKey key) {
- return Arrays.binarySearch(this.routeKeys, key, COMPARATOR);
- }
-
- int size() {
- return this.routeKeys.length;
- }
-
- OffsetMap with(final RouteKey key) {
- // TODO: we could make this faster if we had an array-backed Set and requiring
- // the caller to give us the result of offsetOf() -- as that indicates
- // where to insert the new routerId while maintaining the sorted nature
- // of the array
- final Builder<RouteKey> builder = ImmutableSet.builder();
- builder.add(this.routeKeys);
- builder.add(key);
-
- return OFFSETMAPS.getUnchecked(builder.build());
- }
-
- OffsetMap without(final RouteKey key) {
- final Builder<RouteKey> builder = ImmutableSet.builder();
- final int index = indexOfRouterId(key);
- if (index < 0) {
- LOG.trace("Router key {} not found", key);
- } else {
- builder.add(removeValue(this.routeKeys, index, EMPTY_KEYS));
- }
- return OFFSETMAPS.getUnchecked(builder.build());
- }
-
- private int indexOfRouterId(final RouteKey key) {
- for (int i = 0; i < this.routeKeys.length; i++) {
- if (key.equals(this.routeKeys[i])) {
- return i;
- }
- }
- return -1;
- }
-
- RouteKey getKey(final int offset) {
- return routeKeys[offset];
- }
-
- <T> T getValue(final T[] array, final int offset) {
- checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
- checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, this.routeKeys.length);
- return array[offset];
- }
-
- <T> void setValue(final T[] array, final int offset, final T value) {
- checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
- checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, this.routeKeys.length);
- array[offset] = value;
- }
-
- <T> T[] expand(final OffsetMap oldOffsets, final T[] oldArray, final int offset) {
- @SuppressWarnings("unchecked")
- final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), this.routeKeys.length);
- final int oldSize = oldOffsets.routeKeys.length;
-
- System.arraycopy(oldArray, 0, ret, 0, offset);
- System.arraycopy(oldArray, offset, ret, offset + 1, oldSize - offset);
-
- return ret;
- }
-
- <T> T[] removeValue(final T[] oldArray, final int offset, final T[] emptyArray) {
- final int length = oldArray.length;
- checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
- checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, length);
-
- final int newLength = length - 1;
- if (newLength == 0) {
- checkArgument(emptyArray.length == 0);
- return emptyArray;
- }
-
- final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), newLength);
- System.arraycopy(oldArray, 0, ret, 0, offset);
- if (offset < newLength) {
- System.arraycopy(oldArray, offset + 1, ret, offset, newLength - offset);
- }
-
- return ret;
- }
-
- boolean isEmpty() {
- return this.size() == 0;
- }
-}
\ No newline at end of file
--- /dev/null
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.protocol.bgp.mode.impl.add;
+
+import com.google.common.cache.CacheBuilder;
+import com.google.common.cache.CacheLoader;
+import com.google.common.cache.LoadingCache;
+import com.google.common.collect.ImmutableSet;
+import java.util.Comparator;
+import org.opendaylight.protocol.bgp.mode.impl.AbstractOffsetMap;
+
+/**
+ * A map of {@link RouteKey} to an offset.
+ *
+ * @see AbstractOffsetMap
+ */
+final class RouteKeyOffsets extends AbstractOffsetMap<RouteKey, RouteKeyOffsets> {
+ private static final LoadingCache<ImmutableSet<RouteKey>, RouteKeyOffsets> OFFSETMAPS = CacheBuilder.newBuilder()
+ .weakValues().build(new CacheLoader<ImmutableSet<RouteKey>, RouteKeyOffsets>() {
+ @Override
+ public RouteKeyOffsets load(final ImmutableSet<RouteKey> key) {
+ return new RouteKeyOffsets(key);
+ }
+ });
+ private static final Comparator<RouteKey> COMPARATOR = RouteKey::compareTo;
+ private static final RouteKey[] EMPTY_KEYS = new RouteKey[0];
+
+ static final RouteKeyOffsets EMPTY = new RouteKeyOffsets(ImmutableSet.of());
+
+ private RouteKeyOffsets(final ImmutableSet<RouteKey> routeKeys) {
+ super(EMPTY_KEYS, COMPARATOR, routeKeys);
+ }
+
+ @Override
+ protected Comparator<RouteKey> comparator() {
+ return COMPARATOR;
+ }
+
+ @Override
+ protected RouteKey[] emptyKeys() {
+ return EMPTY_KEYS;
+ }
+
+ @Override
+ protected RouteKeyOffsets instanceForKeys(final ImmutableSet<RouteKey> newKeys) {
+ return OFFSETMAPS.getUnchecked(newKeys);
+ }
+}
\ No newline at end of file
private static final Logger LOG = LoggerFactory.getLogger(BaseRouteEntry.class);
private static final Route[] EMPTY_VALUES = new Route[0];
- private OffsetMap offsets = OffsetMap.EMPTY;
+ private RouterIdOffsets offsets = RouterIdOffsets.EMPTY;
private R[] values = (R[]) EMPTY_VALUES;
private BaseBestPath bestPath;
private BaseBestPath removedBestPath;
// Select the best route.
for (int i = 0; i < this.offsets.size(); ++i) {
- final RouterId routerId = this.offsets.getRouterKey(i);
+ final RouterId routerId = this.offsets.getKey(i);
final Attributes attributes = this.offsets.getValue(this.values, i).getAttributes();
LOG.trace("Processing router id {} attributes {}", routerId, attributes);
selector.processPath(routerId, attributes);
public int addRoute(final RouterId routerId, final Long remotePathId, final R route) {
int offset = this.offsets.offsetOf(routerId);
if (offset < 0) {
- final OffsetMap newOffsets = this.offsets.with(routerId);
+ final RouterIdOffsets newOffsets = this.offsets.with(routerId);
offset = newOffsets.offsetOf(routerId);
this.values = newOffsets.expand(this.offsets, this.values, offset);
+++ /dev/null
-/*
- * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
- *
- * This program and the accompanying materials are made available under the
- * terms of the Eclipse Public License v1.0 which accompanies this distribution,
- * and is available at http://www.eclipse.org/legal/epl-v10.html
- */
-package org.opendaylight.protocol.bgp.mode.impl.base;
-
-import com.google.common.base.Preconditions;
-import com.google.common.cache.CacheBuilder;
-import com.google.common.cache.CacheLoader;
-import com.google.common.cache.LoadingCache;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.ImmutableSet.Builder;
-import java.lang.reflect.Array;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.Set;
-import javax.annotation.Nonnull;
-import org.opendaylight.protocol.bgp.rib.spi.RouterId;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-/**
- * A map of Router identifier to an offset. Used to maintain a simple
- * offset-based lookup across multiple RouteEntry objects,
- * which share either contributors or consumers.
- * We also provide utility reformat methods, which provide access to
- * array members and array management features.
- */
-final class OffsetMap {
- private static final Logger LOG = LoggerFactory.getLogger(OffsetMap.class);
- private static final String NEGATIVEOFFSET = "Invalid negative offset %s";
- private static final String INVALIDOFFSET = "Invalid offset %s for %s router IDs";
- private static final LoadingCache<Set<RouterId>, OffsetMap> OFFSETMAPS = CacheBuilder.newBuilder()
- .weakValues().build(new CacheLoader<Set<RouterId>, OffsetMap>() {
- @Override
- public OffsetMap load(@Nonnull final Set<RouterId> key) {
- return new OffsetMap(key);
- }
- });
- private static final Comparator<RouterId> COMPARATOR = RouterId::compareTo;
- private static final RouterId[] EMPTY_KEYS = new RouterId[0];
- static final OffsetMap EMPTY = new OffsetMap(Collections.emptySet());
-
- private final RouterId[] routerKeys;
-
- private OffsetMap(final Set<RouterId> routerIds) {
- final RouterId[] array = routerIds.toArray(EMPTY_KEYS);
- Arrays.sort(array, COMPARATOR);
- this.routerKeys = array;
- }
-
- RouterId getRouterKey(final int offset) {
- Preconditions.checkArgument(offset >= 0);
- return this.routerKeys[offset];
- }
-
- public int offsetOf(final RouterId key) {
- return Arrays.binarySearch(this.routerKeys, key, COMPARATOR);
- }
-
- public int size() {
- return this.routerKeys.length;
- }
-
- public OffsetMap with(final RouterId key) {
- // TODO: we could make this faster if we had an array-backed Set and requiring
- // the caller to give us the result of offsetOf() -- as that indicates
- // where to insert the new routerId while maintaining the sorted nature
- // of the array
- final Builder<RouterId> builder = ImmutableSet.builder();
- builder.add(this.routerKeys);
- builder.add(key);
-
- return OFFSETMAPS.getUnchecked(builder.build());
- }
-
- public OffsetMap without(final RouterId key) {
- final Builder<RouterId> builder = ImmutableSet.builder();
- final int index = indexOfRouterId(key);
- if (index < 0) {
- LOG.trace("Router key {} not found", key);
- } else {
- builder.add(removeValue(this.routerKeys, index, EMPTY_KEYS));
- }
- return OFFSETMAPS.getUnchecked(builder.build());
- }
-
- private int indexOfRouterId(final RouterId key) {
- for (int i = 0; i < this.routerKeys.length; i++) {
- if (key.equals(this.routerKeys[i])) {
- return i;
- }
- }
- return -1;
- }
-
- public <T> T getValue(final T[] array, final int offset) {
- Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
- Preconditions.checkArgument(offset < this.routerKeys.length, INVALIDOFFSET, offset, this.routerKeys.length);
- return array[offset];
- }
-
- public <T> void setValue(final T[] array, final int offset, final T value) {
- Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
- Preconditions.checkArgument(offset < this.routerKeys.length, INVALIDOFFSET, offset, this.routerKeys.length);
- array[offset] = value;
- }
-
- <T> T[] expand(final OffsetMap oldOffsets, final T[] oldArray, final int offset) {
- @SuppressWarnings("unchecked")
- final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), this.routerKeys.length);
- final int oldSize = oldOffsets.routerKeys.length;
-
- System.arraycopy(oldArray, 0, ret, 0, offset);
- System.arraycopy(oldArray, offset, ret, offset + 1, oldSize - offset);
-
- return ret;
- }
-
- public <T> T[] removeValue(final T[] oldArray, final int offset, final T[] emptyArray) {
- final int length = oldArray.length;
- Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
- Preconditions.checkArgument(offset < this.routerKeys.length, INVALIDOFFSET, offset, length);
-
- final int newLength = length - 1;
- if (newLength == 0) {
- Preconditions.checkArgument(emptyArray.length == 0);
- return emptyArray;
- }
-
- final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), newLength);
- System.arraycopy(oldArray, 0, ret, 0, offset);
- if (offset < newLength) {
- System.arraycopy(oldArray, offset + 1, ret, offset, newLength - offset);
- }
-
- return ret;
- }
-
- boolean isEmpty() {
- return this.size() == 0;
- }
-}
\ No newline at end of file
--- /dev/null
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.protocol.bgp.mode.impl.base;
+
+import com.google.common.cache.CacheBuilder;
+import com.google.common.cache.CacheLoader;
+import com.google.common.cache.LoadingCache;
+import com.google.common.collect.ImmutableSet;
+import java.util.Comparator;
+import org.opendaylight.protocol.bgp.mode.impl.AbstractOffsetMap;
+import org.opendaylight.protocol.bgp.rib.spi.RouterId;
+
+/**
+ * A map of {@link RouterId} to an offset.
+ *
+ * @see AbstractOffsetMap
+ */
+final class RouterIdOffsets extends AbstractOffsetMap<RouterId, RouterIdOffsets> {
+ private static final LoadingCache<ImmutableSet<RouterId>, RouterIdOffsets> OFFSETMAPS = CacheBuilder.newBuilder()
+ .weakValues().build(new CacheLoader<ImmutableSet<RouterId>, RouterIdOffsets>() {
+ @Override
+ public RouterIdOffsets load(final ImmutableSet<RouterId> key) {
+ return new RouterIdOffsets(key);
+ }
+ });
+ private static final Comparator<RouterId> COMPARATOR = RouterId::compareTo;
+ private static final RouterId[] EMPTY_KEYS = new RouterId[0];
+
+ static final RouterIdOffsets EMPTY = new RouterIdOffsets(ImmutableSet.of());
+
+ RouterIdOffsets(final ImmutableSet<RouterId> routerIds) {
+ super(EMPTY_KEYS, COMPARATOR, routerIds);
+ }
+
+ @Override
+ protected Comparator<RouterId> comparator() {
+ return COMPARATOR;
+ }
+
+ @Override
+ protected RouterId[] emptyKeys() {
+ return EMPTY_KEYS;
+ }
+
+ @Override
+ protected RouterIdOffsets instanceForKeys(final ImmutableSet<RouterId> newKeys) {
+ return OFFSETMAPS.getUnchecked(newKeys);
+ }
+}
Code Review / bgpcep.git / commitdiff