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