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