2 * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v1.0 which accompanies this distribution,
6 * and is available at http://www.eclipse.org/legal/epl-v10.html
8 package org.opendaylight.protocol.bgp.mode.impl.add;
10 import com.google.common.base.Preconditions;
11 import com.google.common.cache.CacheBuilder;
12 import com.google.common.cache.CacheLoader;
13 import com.google.common.cache.LoadingCache;
14 import com.google.common.collect.ImmutableSet;
15 import com.google.common.collect.ImmutableSet.Builder;
16 import java.lang.reflect.Array;
17 import java.util.Arrays;
18 import java.util.Collections;
19 import java.util.Comparator;
20 import java.util.List;
22 import java.util.stream.Collectors;
23 import javax.annotation.Nonnull;
24 import org.slf4j.Logger;
25 import org.slf4j.LoggerFactory;
28 * A map of Router identifier to an offset. Used to maintain a simple
29 * offset-based lookup across multiple RouteEntry objects,
30 * which share either contributors or consumers.
31 * We also provide utility reformat methods, which provide access to
32 * array members and array management features.
34 public final class OffsetMap {
35 static final OffsetMap EMPTY = new OffsetMap(Collections.emptySet());
36 private static final Logger LOG = LoggerFactory.getLogger(OffsetMap.class);
37 private static final String NEGATIVEOFFSET = "Invalid negative offset %s";
38 private static final String INVALIDOFFSET = "Invalid offset %s for %s router IDs";
39 private static final LoadingCache<Set<RouteKey>, OffsetMap> OFFSETMAPS = CacheBuilder.newBuilder().weakValues().build(
40 new CacheLoader<Set<RouteKey>, OffsetMap>() {
42 public OffsetMap load(@Nonnull final Set<RouteKey> key) throws Exception {
43 return new OffsetMap(key);
46 private static final Comparator<RouteKey> COMPARATOR = RouteKey::compareTo;
47 private final RouteKey[] routeKeys;
49 private OffsetMap(final Set<RouteKey> routerIds) {
50 final RouteKey[] array = routerIds.toArray(new RouteKey[0]);
51 Arrays.sort(array, COMPARATOR);
52 this.routeKeys = array;
55 public int offsetOf(final RouteKey key) {
56 return Arrays.binarySearch(this.routeKeys, key, COMPARATOR);
60 return this.routeKeys.length;
63 public OffsetMap with(final RouteKey key) {
64 // TODO: we could make this faster if we had an array-backed Set and requiring
65 // the caller to give us the result of offsetOf() -- as that indicates
66 // where to insert the new routerId while maintaining the sorted nature
68 final Builder<RouteKey> builder = ImmutableSet.builder();
69 builder.add(this.routeKeys);
72 return OFFSETMAPS.getUnchecked(builder.build());
75 public OffsetMap without(final RouteKey key) {
76 final Builder<RouteKey> builder = ImmutableSet.builder();
77 final int index = indexOfRouterId(key);
79 LOG.trace("Router key not found", key);
81 builder.add(removeValue(this.routeKeys, index));
83 return OFFSETMAPS.getUnchecked(builder.build());
86 private int indexOfRouterId(final RouteKey key) {
87 for (int i = 0; i < this.routeKeys.length; i++) {
88 if (key.equals(this.routeKeys[i])) {
95 public <T> T getValue(final T[] array, final int offset) {
96 Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
97 Preconditions.checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, this.routeKeys.length);
101 public <T> void setValue(final T[] array, final int offset, final T value) {
102 Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
103 Preconditions.checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, this.routeKeys.length);
104 array[offset] = value;
107 public <T> T[] expand(final OffsetMap oldOffsets, final T[] oldArray, final int offset) {
108 @SuppressWarnings("unchecked")
109 final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), this.routeKeys.length);
110 final int oldSize = oldOffsets.routeKeys.length;
112 System.arraycopy(oldArray, 0, ret, 0, offset);
113 System.arraycopy(oldArray, offset, ret, offset + 1, oldSize - offset);
118 public <T> T[] removeValue(final T[] oldArray, final int offset) {
119 final int length = oldArray.length;
120 Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
121 Preconditions.checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, length);
123 final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), length - 1);
124 System.arraycopy(oldArray, 0, ret, 0, offset);
125 if (offset < length - 1) {
126 System.arraycopy(oldArray, offset + 1, ret, offset, length - offset - 1);
133 return this.size() == 0;
136 public List<RouteKey> getRouteKeysList() {
137 return Arrays.stream(this.routeKeys).collect(Collectors.toList());