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;
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.Comparator;
19 import java.util.List;
21 import java.util.stream.Collectors;
22 import javax.annotation.Nonnull;
23 import org.slf4j.Logger;
24 import org.slf4j.LoggerFactory;
27 * A map of Router identifier to an offset. Used to maintain a simple
28 * offset-based lookup across multiple RouteEntry objects,
29 * which share either contributors or consumers.
30 * We also provide utility reformat methods, which provide access to
31 * array members and array management features.
33 public final class OffsetMap<E extends Comparable<E>> {
34 private static final Logger LOG = LoggerFactory.getLogger(OffsetMap.class);
35 private static final String NEGATIVEOFFSET = "Invalid negative offset %s";
36 private static final String INVALIDOFFSET = "Invalid offset %s for %s router IDs";
37 private final Comparator<E> ipv4Comparator = E::compareTo;
38 private final E[] routeKeys;
39 private final Class<E> clazz;
40 private final LoadingCache<Set<E>, OffsetMap<E>> keyCache = CacheBuilder.newBuilder().weakValues().build(new CacheLoader<Set<E>, OffsetMap<E>>() {
42 public OffsetMap<E> load(@Nonnull final Set<E> key) throws Exception {
43 return new OffsetMap<>(key, clazz);
47 public OffsetMap(final Class<E> clazz) {
49 this.routeKeys = (E[]) Array.newInstance(clazz, 0);
52 private OffsetMap(final Set<E> keysSet, final Class<E> clazz) {
54 final E[] array = keysSet.toArray((E[]) Array.newInstance(this.clazz, keysSet.size()));
55 Arrays.sort(array, ipv4Comparator);
56 this.routeKeys = array;
59 public List<E> getRouteKeysList() {
60 return Arrays.stream(this.routeKeys).collect(Collectors.toList());
63 public E getRouterKey(final int offset) {
64 Preconditions.checkArgument(offset >= 0);
65 return this.routeKeys[offset];
68 public int offsetOf(final E key) {
69 return Arrays.binarySearch(this.routeKeys, key, ipv4Comparator);
73 return this.routeKeys.length;
76 public OffsetMap<E> with(final E key) {
77 // TODO: we could make this faster if we had an array-backed Set and requiring
78 // the caller to give us the result of offsetOf() -- as that indicates
79 // where to insert the new routerId while maintaining the sorted nature
81 final Builder<E> b = ImmutableSet.builder();
82 b.add(this.routeKeys);
85 return keyCache.getUnchecked(b.build());
88 public OffsetMap<E> without(final E key) {
89 final Builder<E> b = ImmutableSet.builder();
90 int index = indexOfRouterId(key);
92 LOG.trace("Router key not found", key);
94 b.add(removeValue(this.routeKeys, index));
96 return keyCache.getUnchecked(b.build());
99 private int indexOfRouterId(final E key) {
100 for (int i = 0; i < this.routeKeys.length; i++) {
101 if (key.equals(this.routeKeys[i])) {
108 public <T> T getValue(final T[] array, final int offset) {
109 Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
110 Preconditions.checkArgument(offset < routeKeys.length, INVALIDOFFSET, offset, routeKeys.length);
111 return array[offset];
114 public <T> void setValue(final T[] array, final int offset, final T value) {
115 Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
116 Preconditions.checkArgument(offset < routeKeys.length, INVALIDOFFSET, offset, routeKeys.length);
117 array[offset] = value;
120 public <T> T[] expand(final OffsetMap oldOffsets, final T[] oldArray, final int offset) {
121 @SuppressWarnings("unchecked")
122 final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), this.routeKeys.length);
123 final int oldSize = oldOffsets.routeKeys.length;
125 System.arraycopy(oldArray, 0, ret, 0, offset);
126 System.arraycopy(oldArray, offset, ret, offset + 1, oldSize - offset);
131 public <T> T[] removeValue(final T[] oldArray, final int offset) {
132 final int length = oldArray.length;
133 Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
134 Preconditions.checkArgument(offset < routeKeys.length, INVALIDOFFSET, offset, length);
136 final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), length - 1);
137 System.arraycopy(oldArray, 0, ret, 0, offset);
138 if (offset < length - 1) {
139 System.arraycopy(oldArray, offset + 1, ret, offset, length - offset - 1);
145 public boolean isEmty() {
146 return this.size() == 0;