1 /*
   2  * Copyright (c) 2011, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 
  25 package org.graalvm.compiler.graph;
  26 
  27 import java.util.Arrays;
  28 import java.util.Iterator;
  29 import java.util.function.BiFunction;
  30 
  31 import jdk.internal.vm.compiler.collections.EconomicMap;
  32 import jdk.internal.vm.compiler.collections.MapCursor;
  33 
  34 public class NodeMap<T> extends NodeIdAccessor implements EconomicMap<Node, T> {
  35 
  36     private static final int MIN_REALLOC_SIZE = 16;
  37 
  38     protected Object[] values;
  39 
  40     public NodeMap(Graph graph) {
  41         super(graph);
  42         this.values = new Object[graph.nodeIdCount()];
  43     }
  44 
  45     public NodeMap(NodeMap<T> copyFrom) {
  46         super(copyFrom.graph);
  47         this.values = Arrays.copyOf(copyFrom.values, copyFrom.values.length);
  48     }
  49 
  50     @Override
  51     @SuppressWarnings("unchecked")
  52     public T get(Node node) {
  53         assert check(node);
  54         return (T) values[getNodeId(node)];
  55     }
  56 
  57     @SuppressWarnings("unchecked")
  58     public T getAndGrow(Node node) {
  59         checkAndGrow(node);
  60         return (T) values[getNodeId(node)];
  61     }
  62 
  63     private void checkAndGrow(Node node) {
  64         if (isNew(node)) {
  65             this.values = Arrays.copyOf(values, Math.max(MIN_REALLOC_SIZE, graph.nodeIdCount() * 3 / 2));
  66         }
  67         assert check(node);
  68     }
  69 
  70     @Override
  71     public boolean isEmpty() {
  72         throw new UnsupportedOperationException("isEmpty() is not supported for performance reasons");
  73     }
  74 
  75     @Override
  76     public boolean containsKey(Node node) {
  77         if (node.graph() == graph()) {
  78             return get(node) != null;
  79         }
  80         return false;
  81     }
  82 
  83     public boolean containsValue(Object value) {
  84         for (Object o : values) {
  85             if (o == value) {
  86                 return true;
  87             }
  88         }
  89         return false;
  90     }
  91 
  92     public Graph graph() {
  93         return graph;
  94     }
  95 
  96     public void set(Node node, T value) {
  97         assert check(node);
  98         values[getNodeId(node)] = value;
  99     }
 100 
 101     public void setAndGrow(Node node, T value) {
 102         checkAndGrow(node);
 103         set(node, value);
 104     }
 105 
 106     /**
 107      * @param i
 108      * @return Return the key for the entry at index {@code i}
 109      */
 110     protected Node getKey(int i) {
 111         return graph.getNode(i);
 112     }
 113 
 114     @Override
 115     public int size() {
 116         throw new UnsupportedOperationException("size() is not supported for performance reasons");
 117     }
 118 
 119     public int capacity() {
 120         return values.length;
 121     }
 122 
 123     public boolean isNew(Node node) {
 124         return getNodeId(node) >= capacity();
 125     }
 126 
 127     private boolean check(Node node) {
 128         assert node.graph() == graph : String.format("%s is not part of the graph", node);
 129         assert !isNew(node) : "this node was added to the graph after creating the node map : " + node;
 130         return true;
 131     }
 132 
 133     @Override
 134     public void clear() {
 135         Arrays.fill(values, null);
 136     }
 137 
 138     @Override
 139     public Iterable<Node> getKeys() {
 140         return new Iterable<Node>() {
 141 
 142             @Override
 143             public Iterator<Node> iterator() {
 144                 return new Iterator<Node>() {
 145 
 146                     int i = 0;
 147 
 148                     @Override
 149                     public boolean hasNext() {
 150                         forward();
 151                         return i < NodeMap.this.values.length;
 152                     }
 153 
 154                     @Override
 155                     public Node next() {
 156                         final int pos = i;
 157                         final Node key = NodeMap.this.getKey(pos);
 158                         i++;
 159                         forward();
 160                         return key;
 161                     }
 162 
 163                     @Override
 164                     public void remove() {
 165                         throw new UnsupportedOperationException();
 166                     }
 167 
 168                     private void forward() {
 169                         while (i < NodeMap.this.values.length && (NodeMap.this.getKey(i) == null || NodeMap.this.values[i] == null)) {
 170                             i++;
 171                         }
 172                     }
 173                 };
 174             }
 175         };
 176     }
 177 
 178     @Override
 179     public MapCursor<Node, T> getEntries() {
 180         return new MapCursor<Node, T>() {
 181 
 182             int current = -1;
 183 
 184             @Override
 185             public boolean advance() {
 186                 current++;
 187                 while (current < NodeMap.this.values.length && (NodeMap.this.values[current] == null || NodeMap.this.getKey(current) == null)) {
 188                     current++;
 189                 }
 190                 return current < NodeMap.this.values.length;
 191             }
 192 
 193             @Override
 194             public Node getKey() {
 195                 return NodeMap.this.getKey(current);
 196             }
 197 
 198             @SuppressWarnings("unchecked")
 199             @Override
 200             public T getValue() {
 201                 return (T) NodeMap.this.values[current];
 202             }
 203 
 204             @Override
 205             public void remove() {
 206                 assert NodeMap.this.values[current] != null;
 207                 NodeMap.this.values[current] = null;
 208             }
 209         };
 210     }
 211 
 212     @Override
 213     public Iterable<T> getValues() {
 214         return new Iterable<T>() {
 215 
 216             @Override
 217             public Iterator<T> iterator() {
 218                 return new Iterator<T>() {
 219 
 220                     int i = 0;
 221 
 222                     @Override
 223                     public boolean hasNext() {
 224                         forward();
 225                         return i < NodeMap.this.values.length;
 226                     }
 227 
 228                     @SuppressWarnings("unchecked")
 229                     @Override
 230                     public T next() {
 231                         final int pos = i;
 232                         final T value = (T) NodeMap.this.values[pos];
 233                         i++;
 234                         forward();
 235                         return value;
 236                     }
 237 
 238                     @Override
 239                     public void remove() {
 240                         throw new UnsupportedOperationException();
 241                     }
 242 
 243                     private void forward() {
 244                         while (i < NodeMap.this.values.length && (NodeMap.this.getKey(i) == null || NodeMap.this.values[i] == null)) {
 245                             i++;
 246                         }
 247                     }
 248                 };
 249             }
 250         };
 251     }
 252 
 253     @Override
 254     public String toString() {
 255         MapCursor<Node, T> i = getEntries();
 256         if (!i.advance()) {
 257             return "{}";
 258         }
 259 
 260         StringBuilder sb = new StringBuilder();
 261         sb.append('{');
 262         while (true) {
 263             Node key = i.getKey();
 264             T value = i.getValue();
 265             sb.append(key);
 266             sb.append('=');
 267             sb.append(value);
 268             if (!i.advance()) {
 269                 return sb.append('}').toString();
 270             }
 271             sb.append(',').append(' ');
 272         }
 273     }
 274 
 275     @Override
 276     public T put(Node key, T value) {
 277         T result = get(key);
 278         set(key, value);
 279         return result;
 280     }
 281 
 282     @Override
 283     public T removeKey(Node key) {
 284         return put(key, null);
 285     }
 286 
 287     @Override
 288     public void replaceAll(BiFunction<? super Node, ? super T, ? extends T> function) {
 289         for (Node n : getKeys()) {
 290             put(n, function.apply(n, get(n)));
 291         }
 292     }
 293 }