common/util/src/main/java/org/opendaylight/yangtools/util/MapAdaptor.java

   1 /*
   2  * Copyright (c) 2014 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 static com.google.common.base.Preconditions.checkArgument;
  11
  12 import com.google.common.collect.ImmutableMap;
  13 import com.google.common.collect.Maps;
  14 import java.util.Collections;
  15 import java.util.HashMap;
  16 import java.util.Map;
  17 import java.util.Map.Entry;
  18 import org.opendaylight.yangtools.triemap.MutableTrieMap;
  19 import org.opendaylight.yangtools.triemap.TrieMap;
  20 import org.slf4j.Logger;
  21 import org.slf4j.LoggerFactory;
  22
  23 /**
  24  * A simple layer on top of maps, which performs snapshot mediation and optimization of
  25  * what the underlying implementation is.
  26  */
  27 public final class MapAdaptor {
  28     public static final int DEFAULT_COPY_MAX_ITEMS = 100;
  29     public static final String COPY_MAX_ITEMS_MAX_PROP = "org.opendaylight.yangtools.util.mapadaptor.maxcopy";
  30
  31     public static final int DEFAULT_PERSIST_MIN_ITEMS = 50;
  32     public static final String PERSIST_MIN_ITEMS_PROP = "org.opendaylight.yangtools.util.mapadaptor.minpersist";
  33
  34     private static final Logger LOG = LoggerFactory.getLogger(MapAdaptor.class);
  35     private static final MapAdaptor DEFAULT_INSTANCE;
  36
  37     private final boolean useSingleton;
  38     private final int persistMinItems;
  39     private final int copyMaxItems;
  40
  41     static {
  42         DEFAULT_INSTANCE = new MapAdaptor(true,
  43                 getProperty(COPY_MAX_ITEMS_MAX_PROP, DEFAULT_COPY_MAX_ITEMS),
  44                 getProperty(PERSIST_MIN_ITEMS_PROP, DEFAULT_PERSIST_MIN_ITEMS));
  45         LOG.debug("Configured HashMap/TrieMap cutoff at {}/{} entries",
  46                 DEFAULT_INSTANCE.persistMinItems, DEFAULT_INSTANCE.copyMaxItems);
  47     }
  48
  49     private static int getProperty(final String name, final int defaultValue) {
  50         final int val = Integer.getInteger(name, defaultValue).intValue();
  51         if (val > 0) {
  52             return val;
  53         }
  54
  55         LOG.warn("Ignoring illegal value of {}: has to be a positive number", name);
  56         return defaultValue;
  57     }
  58
  59     private MapAdaptor(final boolean useSingleton, final int copyMaxItems, final int persistMinItems) {
  60         this.useSingleton = useSingleton;
  61         this.copyMaxItems = copyMaxItems;
  62         this.persistMinItems = persistMinItems;
  63     }
  64
  65     /**
  66      * Return the default-configured instance.
  67      *
  68      * @return the singleton global instance
  69      */
  70     public static MapAdaptor getDefaultInstance() {
  71         return DEFAULT_INSTANCE;
  72     }
  73
  74     public static MapAdaptor getInstance(final boolean useSingleton, final int copyMaxItems,
  75             final int persistMinItems) {
  76         checkArgument(copyMaxItems >= 0, "copyMaxItems has to be a non-negative integer");
  77         checkArgument(persistMinItems >= 0, "persistMinItems has to be a positive integer");
  78         checkArgument(persistMinItems <= copyMaxItems, "persistMinItems must be less than or equal to copyMaxItems");
  79         return new MapAdaptor(useSingleton, copyMaxItems, persistMinItems);
  80     }
  81
  82     /**
  83      * Creates an initial snapshot. The backing map is selected according to the expected size.
  84      *
  85      * @param expectedSize Expected map size
  86      * @return An empty mutable map.
  87      */
  88     public <K, V> Map<K, V> initialSnapshot(final int expectedSize) {
  89         checkArgument(expectedSize >= 0);
  90         if (expectedSize > persistMinItems) {
  91             return new ReadWriteTrieMap<>();
  92         }
  93
  94         if (expectedSize < 2) {
  95             return new HashMap<>(1);
  96         }
  97         if (expectedSize == 2) {
  98             return new HashMap<>(2);
  99         }
 100         return Maps.newHashMapWithExpectedSize(expectedSize);
 101     }
 102
 103     /**
 104      * Input is treated is supposed to be left unmodified, result must be mutable.
 105      *
 106      * @param input input map
 107      * @return An isolated, read-write snapshot of input map
 108      * @throws NullPointerException if input is null
 109      */
 110     @SuppressWarnings("static-method")
 111     public <K, V> Map<K, V> takeSnapshot(final Map<K, V> input) {
 112         if (input instanceof ReadOnlyTrieMap) {
 113             return ((ReadOnlyTrieMap<K, V>)input).toReadWrite();
 114         }
 115
 116         LOG.trace("Converting input {} to a HashMap", input);
 117
 118         /*
 119          * The default HashMap copy constructor performs a bad thing for small maps, using the default capacity of 16
 120          * as the minimum sizing hint, which can lead to wasted memory. Since the HashMap grows in powers-of-two, we
 121          * only kick this in if we are storing 6 entries or less, as that results in 8-entry map -- the next power is
 122          * 16, which is the default.
 123          */
 124         final Map<K, V> ret;
 125         final int size = input.size();
 126         if (size <= 6) {
 127             final int target;
 128             switch (size) {
 129                 case 0:
 130                 case 1:
 131                     target = 1;
 132                     break;
 133                 case 2:
 134                     target = 2;
 135                     break;
 136                 case 3:
 137                     target = 4;
 138                     break;
 139                 default:
 140                     target = 8;
 141             }
 142
 143             ret = new HashMap<>(target);
 144             ret.putAll(input);
 145         } else if (input instanceof HashMap) {
 146             // HashMap supports cloning, but we want to make sure we trim it down if entries were removed, so we do
 147             // this only after having checked for small sizes.
 148             @SuppressWarnings("unchecked")
 149             final Map<K, V> tmp = (Map<K, V>) ((HashMap<K, V>) input).clone();
 150             ret = tmp;
 151         } else {
 152             ret = new HashMap<>(input);
 153         }
 154
 155         LOG.trace("Read-write HashMap is {}", ret);
 156         return ret;
 157     }
 158
 159     /**
 160      * Input will be thrown away, result will be retained for read-only access or
 161      * {@link #takeSnapshot(Map)} purposes.
 162      *
 163      * @param input non-optimized (read-write) map
 164      * @return optimized read-only map
 165      * @throws NullPointerException if input is null
 166      */
 167     public <K, V> Map<K, V> optimize(final Map<K, V> input) {
 168         if (input instanceof ReadOnlyTrieMap) {
 169             LOG.warn("Optimizing read-only map {}", input);
 170         }
 171
 172         final int size = input.size();
 173
 174         /*
 175          * No-brainer :)
 176          */
 177         if (size == 0) {
 178             LOG.trace("Reducing input {} to an empty map", input);
 179             return ImmutableMap.of();
 180         }
 181
 182         /*
 183          * We retain the persistent map as long as it holds at least
 184          * persistMinItems
 185          */
 186         if (input instanceof ReadWriteTrieMap && size >= persistMinItems) {
 187             return ((ReadWriteTrieMap<K, V>)input).toReadOnly();
 188         }
 189
 190         /*
 191          * If the user opted to use singleton maps, use them. Except for the case
 192          * when persistMinItems dictates we should not move off of the persistent
 193          * map.
 194          */
 195         if (useSingleton && size == 1) {
 196             final Entry<K, V> e = input.entrySet().iterator().next();
 197             final Map<K, V> ret = Collections.singletonMap(e.getKey(), e.getValue());
 198             LOG.trace("Reducing input {} to singleton map {}", input, ret);
 199             return ret;
 200         }
 201
 202         if (size <= copyMaxItems) {
 203             /*
 204              * Favor access speed: use a HashMap and copy it on modification.
 205              */
 206             if (input instanceof HashMap) {
 207                 return input;
 208             }
 209
 210             LOG.trace("Copying input {} to a HashMap ({} entries)", input, size);
 211             final Map<K, V> ret = new HashMap<>(input);
 212             LOG.trace("Read-only HashMap is {}", ret);
 213             return ret;
 214         }
 215
 216         /*
 217          * Favor isolation speed: use a TrieMap and perform snapshots
 218          *
 219          * This one is a bit tricky, as the TrieMap is concurrent and does not
 220          * keep an uptodate size. Updating it requires a full walk -- which is
 221          * O(N) and we want to avoid that. So we wrap it in an interceptor,
 222          * which will maintain the size for us.
 223          */
 224         LOG.trace("Copying input {} to a TrieMap ({} entries)", input, size);
 225         final MutableTrieMap<K, V> map = TrieMap.create();
 226         map.putAll(input);
 227         final Map<K, V> ret = new ReadOnlyTrieMap<>(map, size);
 228         LOG.trace("Read-only TrieMap is {}", ret);
 229         return ret;
 230     }
 231 }