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 org.slf4j.Logger;
  18 import org.slf4j.LoggerFactory;
  19 import tech.pantheon.triemap.TrieMap;
  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);
  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         checkArgument(copyMaxItems >= 0, "copyMaxItems has to be a non-negative integer");
  75         checkArgument(persistMinItems >= 0, "persistMinItems has to be a positive integer");
  76         checkArgument(persistMinItems <= copyMaxItems, "persistMinItems must be less than or equal to copyMaxItems");
  77         return new MapAdaptor(useSingleton, copyMaxItems, persistMinItems);
  78     }
  79
  80     /**
  81      * Creates an initial snapshot. The backing map is selected according to the expected size.
  82      *
  83      * @param expectedSize Expected map size
  84      * @return An empty mutable map.
  85      */
  86     public <K, V> Map<K, V> initialSnapshot(final int expectedSize) {
  87         checkArgument(expectedSize >= 0);
  88         if (expectedSize > persistMinItems) {
  89             return new ReadWriteTrieMap<>();
  90         }
  91
  92         if (expectedSize < 2) {
  93             return new HashMap<>(1);
  94         }
  95         if (expectedSize == 2) {
  96             return new HashMap<>(2);
  97         }
  98         return Maps.newHashMapWithExpectedSize(expectedSize);
  99     }
 100
 101     /**
 102      * Input is treated is supposed to be left unmodified, result must be mutable.
 103      *
 104      * @param input input map
 105      * @return An isolated, read-write snapshot of input map
 106      * @throws NullPointerException if input is null
 107      */
 108     @SuppressWarnings("static-method")
 109     public <K, V> Map<K, V> takeSnapshot(final Map<K, V> input) {
 110         return input instanceof ReadOnlyTrieMap<K, V> rotm ? rotm.toReadWrite() : toReadWrite(input);
 111     }
 112
 113     private static <K, V> Map<K, V> toReadWrite(final Map<K, V> input) {
 114         LOG.trace("Converting input {} to a HashMap", input);
 115
 116         /*
 117          * The default HashMap copy constructor performs a bad thing for small maps, using the default capacity of 16
 118          * as the minimum sizing hint, which can lead to wasted memory. Since the HashMap grows in powers-of-two, we
 119          * only kick this in if we are storing 6 entries or less, as that results in 8-entry map -- the next power is
 120          * 16, which is the default.
 121          */
 122         final Map<K, V> ret;
 123         final int size = input.size();
 124         if (size <= 6) {
 125             final var target = switch (size) {
 126                 case 0, 1 -> 1;
 127                 case 2 -> 2;
 128                 case 3 -> 4;
 129                 default -> 8;
 130             };
 131             ret = new HashMap<>(target);
 132             ret.putAll(input);
 133         } else {
 134             ret = switch (input) {
 135                 case HashMap<K, V> hm -> {
 136                     // HashMap supports cloning, but we want to make sure we trim it down if entries were removed, so we
 137                     // do this only after having checked for small sizes.
 138                     @SuppressWarnings("unchecked")
 139                     final var tmp = (Map<K, V>) hm.clone();
 140                     yield tmp;
 141                 }
 142                 default -> new HashMap<>(input);
 143             };
 144         }
 145
 146         LOG.trace("Read-write HashMap is {}", ret);
 147         return ret;
 148     }
 149
 150     /**
 151      * Input will be thrown away, result will be retained for read-only access or {@link #takeSnapshot(Map)} purposes.
 152      *
 153      * @param input non-optimized (read-write) map
 154      * @return optimized read-only map
 155      * @throws NullPointerException if input is null
 156      */
 157     public <K, V> Map<K, V> optimize(final Map<K, V> input) {
 158         if (input instanceof ReadOnlyTrieMap) {
 159             LOG.warn("Optimizing read-only map {}", input);
 160         }
 161
 162         final int size = input.size();
 163
 164         /*
 165          * No-brainer :)
 166          */
 167         if (size == 0) {
 168             LOG.trace("Reducing input {} to an empty map", input);
 169             return ImmutableMap.of();
 170         }
 171
 172         /*
 173          * We retain the persistent map as long as it holds at least
 174          * persistMinItems
 175          */
 176         if (input instanceof ReadWriteTrieMap<K, V> rwtm && size >= persistMinItems) {
 177             return rwtm.toReadOnly();
 178         }
 179
 180         /*
 181          * If the user opted to use singleton maps, use them. Except for the case
 182          * when persistMinItems dictates we should not move off of the persistent
 183          * map.
 184          */
 185         if (useSingleton && size == 1) {
 186             final var e = input.entrySet().iterator().next();
 187             final var ret = Collections.singletonMap(e.getKey(), e.getValue());
 188             LOG.trace("Reducing input {} to singleton map {}", input, ret);
 189             return ret;
 190         }
 191
 192         if (size <= copyMaxItems) {
 193             /*
 194              * Favor access speed: use a HashMap and copy it on modification.
 195              */
 196             if (input instanceof HashMap) {
 197                 return input;
 198             }
 199
 200             LOG.trace("Copying input {} to a HashMap ({} entries)", input, size);
 201             final var ret = new HashMap<>(input);
 202             LOG.trace("Read-only HashMap is {}", ret);
 203             return ret;
 204         }
 205
 206         /*
 207          * Favor isolation speed: use a TrieMap and perform snapshots
 208          *
 209          * This one is a bit tricky, as the TrieMap is concurrent and does not
 210          * keep an uptodate size. Updating it requires a full walk -- which is
 211          * O(N) and we want to avoid that. So we wrap it in an interceptor,
 212          * which will maintain the size for us.
 213          */
 214         LOG.trace("Copying input {} to a TrieMap ({} entries)", input, size);
 215         final var map = TrieMap.<K, V>create();
 216         map.putAll(input);
 217         final var ret = new ReadOnlyTrieMap<>(map, size);
 218         LOG.trace("Read-only TrieMap is {}", ret);
 219         return ret;
 220     }
 221 }