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