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