From 5169ad7c66e7705fe7e8f7292b2664622c9a8117 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Fri, 7 Dec 2018 05:27:26 +0100 Subject: [PATCH] Remove duplicate OffsetMap code Having two copies of the same class is confusing and a problem with maintenance. Create an abstract base template to hold most of the code. Change-Id: I3078c2af94d440701d48e43da31c106fdbac78d2 Signed-off-by: Robert Varga --- .../bgp/mode/impl/AbstractOffsetMap.java | 142 +++++++++++++++++ .../impl/add/AddPathAbstractRouteEntry.java | 6 +- .../protocol/bgp/mode/impl/add/OffsetMap.java | 146 ----------------- .../bgp/mode/impl/add/RouteKeyOffsets.java | 53 +++++++ .../bgp/mode/impl/base/BaseRouteEntry.java | 6 +- .../bgp/mode/impl/base/OffsetMap.java | 147 ------------------ .../bgp/mode/impl/base/RouterIdOffsets.java | 54 +++++++ 7 files changed, 255 insertions(+), 299 deletions(-) create mode 100644 bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/AbstractOffsetMap.java delete mode 100644 bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/OffsetMap.java create mode 100644 bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/RouteKeyOffsets.java delete mode 100644 bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/OffsetMap.java create mode 100644 bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/RouterIdOffsets.java diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/AbstractOffsetMap.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/AbstractOffsetMap.java new file mode 100644 index 0000000000..11def110dd --- /dev/null +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/AbstractOffsetMap.java @@ -0,0 +1,142 @@ +/* + * 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, T extends AbstractOffsetMap> { + 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 comparator, final ImmutableSet 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 builder = ImmutableSet.builderWithExpectedSize(size() + 1); + builder.add(keys); + builder.add(key); + return instanceForKeys(builder.build()); + } + + public final T without(final K key) { + final ImmutableSet 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 getValue(final C[] array, final int offset) { + checkAccessOffest(offset); + return array[offset]; + } + + public final void setValue(final C[] array, final int offset, final C value) { + checkAccessOffest(offset); + array[offset] = value; + } + + public final 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[] 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 comparator(); + + protected abstract K[] emptyKeys(); + + protected abstract T instanceForKeys(ImmutableSet 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); + } +} diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java index 49e211149e..172dfd562f 100644 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java @@ -55,7 +55,7 @@ public abstract class AddPathAbstractRouteEntry bestPath; @@ -67,7 +67,7 @@ public abstract class AddPathAbstractRouteEntry 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()); @@ -78,7 +78,7 @@ public abstract class AddPathAbstractRouteEntry, OffsetMap> OFFSETMAPS = CacheBuilder.newBuilder().weakValues() - .build(new CacheLoader, OffsetMap>() { - @Override - public OffsetMap load(@Nonnull final Set key) { - return new OffsetMap(key); - } - }); - private static final Comparator 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 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 builder = ImmutableSet.builder(); - builder.add(this.routeKeys); - builder.add(key); - - return OFFSETMAPS.getUnchecked(builder.build()); - } - - OffsetMap without(final RouteKey key) { - final Builder 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 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]; - } - - 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[] 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[] 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 diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/RouteKeyOffsets.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/RouteKeyOffsets.java new file mode 100644 index 0000000000..b0cb226121 --- /dev/null +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/RouteKeyOffsets.java @@ -0,0 +1,53 @@ +/* + * 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 { + private static final LoadingCache, RouteKeyOffsets> OFFSETMAPS = CacheBuilder.newBuilder() + .weakValues().build(new CacheLoader, RouteKeyOffsets>() { + @Override + public RouteKeyOffsets load(final ImmutableSet key) { + return new RouteKeyOffsets(key); + } + }); + private static final Comparator COMPARATOR = RouteKey::compareTo; + private static final RouteKey[] EMPTY_KEYS = new RouteKey[0]; + + static final RouteKeyOffsets EMPTY = new RouteKeyOffsets(ImmutableSet.of()); + + private RouteKeyOffsets(final ImmutableSet routeKeys) { + super(EMPTY_KEYS, COMPARATOR, routeKeys); + } + + @Override + protected Comparator comparator() { + return COMPARATOR; + } + + @Override + protected RouteKey[] emptyKeys() { + return EMPTY_KEYS; + } + + @Override + protected RouteKeyOffsets instanceForKeys(final ImmutableSet newKeys) { + return OFFSETMAPS.getUnchecked(newKeys); + } +} \ No newline at end of file diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseRouteEntry.java index ea6574832e..701f4dc931 100644 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseRouteEntry.java +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseRouteEntry.java @@ -38,7 +38,7 @@ final class BaseRouteEntry, 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; @@ -69,7 +69,7 @@ final class BaseRouteEntry, // 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); @@ -92,7 +92,7 @@ final class BaseRouteEntry, 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); diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/OffsetMap.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/OffsetMap.java deleted file mode 100644 index 6c63e7556f..0000000000 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/OffsetMap.java +++ /dev/null @@ -1,147 +0,0 @@ -/* - * 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, OffsetMap> OFFSETMAPS = CacheBuilder.newBuilder() - .weakValues().build(new CacheLoader, OffsetMap>() { - @Override - public OffsetMap load(@Nonnull final Set key) { - return new OffsetMap(key); - } - }); - private static final Comparator 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 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 builder = ImmutableSet.builder(); - builder.add(this.routerKeys); - builder.add(key); - - return OFFSETMAPS.getUnchecked(builder.build()); - } - - public OffsetMap without(final RouterId key) { - final Builder 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 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 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[] 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[] 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 diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/RouterIdOffsets.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/RouterIdOffsets.java new file mode 100644 index 0000000000..07c710615e --- /dev/null +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/RouterIdOffsets.java @@ -0,0 +1,54 @@ +/* + * 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 { + private static final LoadingCache, RouterIdOffsets> OFFSETMAPS = CacheBuilder.newBuilder() + .weakValues().build(new CacheLoader, RouterIdOffsets>() { + @Override + public RouterIdOffsets load(final ImmutableSet key) { + return new RouterIdOffsets(key); + } + }); + private static final Comparator COMPARATOR = RouterId::compareTo; + private static final RouterId[] EMPTY_KEYS = new RouterId[0]; + + static final RouterIdOffsets EMPTY = new RouterIdOffsets(ImmutableSet.of()); + + RouterIdOffsets(final ImmutableSet routerIds) { + super(EMPTY_KEYS, COMPARATOR, routerIds); + } + + @Override + protected Comparator comparator() { + return COMPARATOR; + } + + @Override + protected RouterId[] emptyKeys() { + return EMPTY_KEYS; + } + + @Override + protected RouterIdOffsets instanceForKeys(final ImmutableSet newKeys) { + return OFFSETMAPS.getUnchecked(newKeys); + } +} -- 2.36.6