bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/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;
   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.Comparator;
  19 import java.util.List;
  20 import java.util.Set;
  21 import java.util.stream.Collectors;
  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 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>>() {
  41         @Override
  42         public OffsetMap<E> load(@Nonnull final Set<E> key) throws Exception {
  43             return new OffsetMap<>(key, clazz);
  44         }
  45     });
  46
  47     public OffsetMap(final Class<E> clazz) {
  48         this.clazz = clazz;
  49         this.routeKeys = (E[]) Array.newInstance(clazz, 0);
  50     }
  51
  52     private OffsetMap(final Set<E> keysSet, final Class<E> clazz) {
  53         this.clazz = clazz;
  54         final E[] array = keysSet.toArray((E[]) Array.newInstance(this.clazz, keysSet.size()));
  55         Arrays.sort(array, ipv4Comparator);
  56         this.routeKeys = array;
  57     }
  58
  59     public List<E> getRouteKeysList() {
  60         return Arrays.stream(this.routeKeys).collect(Collectors.toList());
  61     }
  62
  63     public E getRouterKey(final int offset) {
  64         Preconditions.checkArgument(offset >= 0);
  65         return this.routeKeys[offset];
  66     }
  67
  68     public int offsetOf(final E key) {
  69         return Arrays.binarySearch(this.routeKeys, key, ipv4Comparator);
  70     }
  71
  72     public int size() {
  73         return this.routeKeys.length;
  74     }
  75
  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
  80         //       of the array
  81         final Builder<E> b = ImmutableSet.builder();
  82         b.add(this.routeKeys);
  83         b.add(key);
  84
  85         return keyCache.getUnchecked(b.build());
  86     }
  87
  88     public OffsetMap<E> without(final E key) {
  89         final Builder<E> b = ImmutableSet.builder();
  90         int index = indexOfRouterId(key);
  91         if (index < 0) {
  92             LOG.trace("Router key not found", key);
  93         } else {
  94             b.add(removeValue(this.routeKeys, index));
  95         }
  96         return keyCache.getUnchecked(b.build());
  97     }
  98
  99     private int indexOfRouterId(final E key) {
 100         for (int i = 0; i < this.routeKeys.length; i++) {
 101             if (key.equals(this.routeKeys[i])) {
 102                 return i;
 103             }
 104         }
 105         return -1;
 106     }
 107
 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];
 112     }
 113
 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;
 118     }
 119
 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;
 124
 125         System.arraycopy(oldArray, 0, ret, 0, offset);
 126         System.arraycopy(oldArray, offset, ret, offset + 1, oldSize - offset);
 127
 128         return ret;
 129     }
 130
 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);
 135
 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);
 140         }
 141
 142         return ret;
 143     }
 144
 145     public boolean isEmty() {
 146         return this.size() == 0;
 147     }
 148 }