bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/OffsetMap.java

   1 /*
   2  * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   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
   7  */
   8 package org.opendaylight.protocol.bgp.mode.impl.add;
   9
  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;
  21 import java.util.Set;
  22 import java.util.stream.Collectors;
  23 import javax.annotation.Nonnull;
  24 import org.slf4j.Logger;
  25 import org.slf4j.LoggerFactory;
  26
  27 /**
  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.
  33  */
  34 public final class OffsetMap {
  35     private static final Logger LOG = LoggerFactory.getLogger(OffsetMap.class);
  36     private static final String NEGATIVEOFFSET = "Invalid negative offset %s";
  37     private static final String INVALIDOFFSET = "Invalid offset %s for %s router IDs";
  38     private static final LoadingCache<Set<RouteKey>, OffsetMap> OFFSETMAPS = CacheBuilder.newBuilder().weakValues()
  39         .build(new CacheLoader<Set<RouteKey>, OffsetMap>() {
  40                 @Override
  41                 public OffsetMap load(@Nonnull final Set<RouteKey> key) {
  42                     return new OffsetMap(key);
  43                 }
  44             });
  45     private static final Comparator<RouteKey> COMPARATOR = RouteKey::compareTo;
  46     private static final RouteKey[] EMPTY_KEYS = new RouteKey[0];
  47     static final OffsetMap EMPTY = new OffsetMap(Collections.emptySet());
  48
  49     private final RouteKey[] routeKeys;
  50
  51     private OffsetMap(final Set<RouteKey> routerIds) {
  52         final RouteKey[] array = routerIds.toArray(EMPTY_KEYS);
  53         Arrays.sort(array, COMPARATOR);
  54         this.routeKeys = array;
  55     }
  56
  57     public int offsetOf(final RouteKey key) {
  58         return Arrays.binarySearch(this.routeKeys, key, COMPARATOR);
  59     }
  60
  61     public int size() {
  62         return this.routeKeys.length;
  63     }
  64
  65     public OffsetMap with(final RouteKey key) {
  66         // TODO: we could make this faster if we had an array-backed Set and requiring
  67         //       the caller to give us the result of offsetOf() -- as that indicates
  68         //       where to insert the new routerId while maintaining the sorted nature
  69         //       of the array
  70         final Builder<RouteKey> builder = ImmutableSet.builder();
  71         builder.add(this.routeKeys);
  72         builder.add(key);
  73
  74         return OFFSETMAPS.getUnchecked(builder.build());
  75     }
  76
  77     public OffsetMap without(final RouteKey key) {
  78         final Builder<RouteKey> builder = ImmutableSet.builder();
  79         final int index = indexOfRouterId(key);
  80         if (index < 0) {
  81             LOG.trace("Router key not found", key);
  82         } else {
  83             builder.add(removeValue(this.routeKeys, index, EMPTY_KEYS));
  84         }
  85         return OFFSETMAPS.getUnchecked(builder.build());
  86     }
  87
  88     private int indexOfRouterId(final RouteKey key) {
  89         for (int i = 0; i < this.routeKeys.length; i++) {
  90             if (key.equals(this.routeKeys[i])) {
  91                 return i;
  92             }
  93         }
  94         return -1;
  95     }
  96
  97     public <T> T getValue(final T[] array, final int offset) {
  98         Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
  99         Preconditions.checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, this.routeKeys.length);
 100         return array[offset];
 101     }
 102
 103     public <T> void setValue(final T[] array, final int offset, final T value) {
 104         Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
 105         Preconditions.checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, this.routeKeys.length);
 106         array[offset] = value;
 107     }
 108
 109     public <T> T[] expand(final OffsetMap oldOffsets, final T[] oldArray, final int offset) {
 110         @SuppressWarnings("unchecked")
 111         final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), this.routeKeys.length);
 112         final int oldSize = oldOffsets.routeKeys.length;
 113
 114         System.arraycopy(oldArray, 0, ret, 0, offset);
 115         System.arraycopy(oldArray, offset, ret, offset + 1, oldSize - offset);
 116
 117         return ret;
 118     }
 119
 120     public <T> T[] removeValue(final T[] oldArray, final int offset, final T[] emptyArray) {
 121         final int length = oldArray.length;
 122         Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
 123         Preconditions.checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, length);
 124
 125         final int newLength = length - 1;
 126         if (newLength == 0) {
 127             Preconditions.checkArgument(emptyArray.length == 0);
 128             return emptyArray;
 129         }
 130
 131         final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), newLength);
 132         System.arraycopy(oldArray, 0, ret, 0, offset);
 133         if (offset < newLength) {
 134             System.arraycopy(oldArray, offset + 1, ret, offset, newLength - offset);
 135         }
 136
 137         return ret;
 138     }
 139
 140     boolean isEmpty() {
 141         return this.size() == 0;
 142     }
 143
 144     public List<RouteKey> getRouteKeysList() {
 145         return Arrays.stream(this.routeKeys).collect(Collectors.toList());
 146     }
 147 }