common/util/src/main/java/org/opendaylight/yangtools/util/OffsetMapCache.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.yangtools.util;
   9
  10 import com.google.common.annotations.VisibleForTesting;
  11 import com.google.common.base.Verify;
  12 import com.google.common.cache.Cache;
  13 import com.google.common.cache.CacheBuilder;
  14 import com.google.common.cache.CacheLoader;
  15 import com.google.common.cache.LoadingCache;
  16 import com.google.common.collect.ImmutableList;
  17 import com.google.common.collect.ImmutableMap;
  18 import com.google.common.collect.ImmutableMap.Builder;
  19 import com.google.common.collect.ImmutableSet;
  20 import java.lang.reflect.Array;
  21 import java.util.Collection;
  22 import java.util.Iterator;
  23 import java.util.List;
  24 import java.util.Map;
  25 import java.util.Set;
  26
  27 final class OffsetMapCache {
  28     /*
  29      * Cache for offsets where order matters. The key is a List, which defines the iteration order. Since we want
  30      * to retain this order, it is okay to use a simple LoadingCache.
  31      */
  32     private static final LoadingCache<List<?>, ImmutableMap<?, Integer>> ORDERED_CACHE =
  33             CacheBuilder.newBuilder().weakValues().build(new CacheLoader<List<?>, ImmutableMap<?, Integer>>() {
  34                 @Override
  35                 public ImmutableMap<?, Integer> load(final List<?> key) {
  36                     return createMap(key);
  37                 }
  38             });
  39     /*
  40      * Cache for offsets where order does not mapper. The key is a Set of elements. We use manual two-stage loading
  41      * because of the nature of the objects we store as values, which is ImmutableMaps. An ImmutableMap, when queried
  42      * for keys (as is done in ImmutableOffsetMap.keySet()), will instantiate an ImmutableSet to hold these keys. It
  43      * would be wasteful to use one Set for lookup only to have the map have an exact copy.
  44      *
  45      * We perform the first look up using a Set (which may come from the user, for example via
  46      * ImmutableOffsetMap.unorderedCopyOf()), hence potentially saving a copy operation. If we fail to find an entry,
  47      * we construct the map and put it conditionally with Map.keySet() as the key. This will detect concurrent loading
  48      * and also lead to the cache and the map sharing the same Set.
  49      */
  50     private static final Cache<Set<?>, ImmutableMap<?, Integer>> UNORDERED_CACHE =
  51             CacheBuilder.newBuilder().weakValues().build();
  52
  53     private OffsetMapCache() {
  54         throw new UnsupportedOperationException();
  55     }
  56
  57     @VisibleForTesting
  58     static void invalidateCache() {
  59         ORDERED_CACHE.invalidateAll();
  60         UNORDERED_CACHE.invalidateAll();
  61     }
  62
  63     @SuppressWarnings("unchecked")
  64     static <T> ImmutableMap<T, Integer> orderedOffsets(final Collection<T> args) {
  65         if (args.size() == 1) {
  66             return unorderedOffsets(args);
  67         }
  68
  69         return (ImmutableMap<T, Integer>) ORDERED_CACHE.getUnchecked(ImmutableList.copyOf(args));
  70     }
  71
  72     static <T> ImmutableMap<T, Integer> unorderedOffsets(final Collection<T> args) {
  73         return unorderedOffsets(args instanceof Set ? (Set<T>)args : ImmutableSet.copyOf(args));
  74     }
  75
  76     @SuppressWarnings("unchecked")
  77     private static <T> ImmutableMap<T, Integer> unorderedOffsets(final Set<T> args) {
  78         final ImmutableMap<T, Integer> existing = (ImmutableMap<T, Integer>) UNORDERED_CACHE.getIfPresent(args);
  79         if (existing != null) {
  80             return existing;
  81         }
  82
  83         final ImmutableMap<T, Integer> newMap = createMap(args);
  84         final ImmutableMap<?, Integer> raced = UNORDERED_CACHE.asMap().putIfAbsent(newMap.keySet(), newMap);
  85         return raced == null ? newMap : (ImmutableMap<T, Integer>)raced;
  86     }
  87
  88     static <K, V> V[] adjustedArray(final Map<K, Integer> offsets, final List<K> keys, final V[] array) {
  89         Verify.verify(offsets.size() == keys.size(), "Offsets %s do not match keys %s", offsets, keys);
  90
  91         // This relies on the fact that offsets has an ascending iterator
  92         final Iterator<K> oi = offsets.keySet().iterator();
  93         final Iterator<K> ki = keys.iterator();
  94
  95         while (oi.hasNext()) {
  96             final K o = oi.next();
  97             final K k = ki.next();
  98             if (!k.equals(o)) {
  99                 return adjustArray(offsets, keys, array);
 100             }
 101         }
 102
 103         return array;
 104     }
 105
 106     private static <T> ImmutableMap<T, Integer> createMap(final Collection<T> keys) {
 107         final Builder<T, Integer> b = ImmutableMap.builder();
 108         int counter = 0;
 109
 110         for (T arg : keys) {
 111             b.put(arg, counter++);
 112         }
 113
 114         return b.build();
 115     }
 116
 117     private static <K, V> V[] adjustArray(final Map<K, Integer> offsets, final List<K> keys, final V[] array) {
 118         @SuppressWarnings("unchecked")
 119         final V[] ret = (V[]) Array.newInstance(array.getClass().getComponentType(), array.length);
 120
 121         int offset = 0;
 122         for (final K k : keys) {
 123             final Integer o = Verify.verifyNotNull(offsets.get(k), "Key %s not present in offsets %s", k, offsets);
 124             ret[o] = array[offset++];
 125         }
 126
 127         return ret;
 128     }
 129 }