1 /*
   2  * Copyright (c) 2011, 2011, 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 package org.graalvm.compiler.graph;
  24 
  25 import java.util.AbstractMap.SimpleEntry;
  26 import java.util.Arrays;
  27 import java.util.Iterator;
  28 import java.util.Map.Entry;
  29 
  30 public class NodeMap<T> extends NodeIdAccessor {



  31 
  32     private static final int MIN_REALLOC_SIZE = 16;
  33 
  34     protected Object[] values;
  35 
  36     public NodeMap(Graph graph) {
  37         super(graph);
  38         this.values = new Object[graph.nodeIdCount()];
  39     }
  40 
  41     public NodeMap(NodeMap<T> copyFrom) {
  42         super(copyFrom.graph);
  43         this.values = Arrays.copyOf(copyFrom.values, copyFrom.values.length);
  44     }
  45 

  46     @SuppressWarnings("unchecked")
  47     public T get(Node node) {
  48         assert check(node);
  49         return (T) values[getNodeId(node)];
  50     }
  51 
  52     @SuppressWarnings("unchecked")
  53     public T getAndGrow(Node node) {
  54         checkAndGrow(node);
  55         return (T) values[getNodeId(node)];
  56     }
  57 
  58     private void checkAndGrow(Node node) {
  59         if (isNew(node)) {
  60             this.values = Arrays.copyOf(values, Math.max(MIN_REALLOC_SIZE, graph.nodeIdCount() * 3 / 2));
  61         }
  62         assert check(node);
  63     }
  64 

  65     public boolean isEmpty() {
  66         return !entries().iterator().hasNext();
  67     }
  68 
  69     public boolean containsKey(Object key) {
  70         if (key instanceof Node) {
  71             Node node = (Node) key;
  72             if (node.graph() == graph()) {
  73                 return get(node) != null;
  74             }
  75         }
  76         return false;
  77     }
  78 
  79     public boolean containsValue(Object value) {
  80         for (Object o : values) {
  81             if (o == value) {
  82                 return true;
  83             }
  84         }
  85         return false;
  86     }
  87 
  88     public Graph graph() {
  89         return graph;
  90     }
  91 
  92     public void set(Node node, T value) {
  93         assert check(node);
  94         values[getNodeId(node)] = value;
  95     }
  96 
  97     public void setAndGrow(Node node, T value) {
  98         checkAndGrow(node);
  99         values[getNodeId(node)] = value;
 100     }
 101 
 102     /**
 103      * @param i
 104      * @return Return the key for the entry at index {@code i}
 105      */
 106     protected Node getKey(int i) {
 107         return graph.getNode(i);
 108     }
 109 

 110     public int size() {




 111         return values.length;
 112     }
 113 
 114     public boolean isNew(Node node) {
 115         return getNodeId(node) >= size();
 116     }
 117 
 118     private boolean check(Node node) {
 119         assert node.graph() == graph : String.format("%s is not part of the graph", node);
 120         assert !isNew(node) : "this node was added to the graph after creating the node map : " + node;
 121         return true;
 122     }
 123 

 124     public void clear() {
 125         Arrays.fill(values, null);
 126     }
 127 
 128     public Iterable<Entry<Node, T>> entries() {
 129         return new Iterable<Entry<Node, T>>() {

 130 
 131             @Override
 132             public Iterator<Entry<Node, T>> iterator() {
 133                 return new Iterator<Entry<Node, T>>() {
 134 
 135                     int i = 0;
 136 
 137                     @Override
 138                     public boolean hasNext() {
 139                         forward();
 140                         return i < NodeMap.this.values.length;
 141                     }
 142 
 143                     @SuppressWarnings("unchecked")
 144                     @Override
 145                     public Entry<Node, T> next() {
 146                         final int pos = i;
 147                         Node key = NodeMap.this.getKey(pos);
 148                         T value = (T) NodeMap.this.values[pos];
 149                         i++;
 150                         forward();
 151                         return new SimpleEntry<Node, T>(key, value) {






 152 
 153                             private static final long serialVersionUID = 7813842391085737738L;








 154 
 155                             @Override
 156                             public T setValue(T v) {
 157                                 T oldv = super.setValue(v);
 158                                 NodeMap.this.values[pos] = v;
 159                                 return oldv;

























 160                             }
 161                         };
 162                     }
 163 
 164                     @Override


























 165                     public void remove() {
 166                         throw new UnsupportedOperationException();
 167                     }
 168 
 169                     private void forward() {
 170                         while (i < NodeMap.this.values.length && (NodeMap.this.getKey(i) == null || NodeMap.this.values[i] == null)) {
 171                             i++;
 172                         }
 173                     }
 174                 };
 175             }
 176         };
 177     }
 178 
 179     @Override
 180     public String toString() {
 181         Iterator<Entry<Node, T>> i = entries().iterator();
 182         if (!i.hasNext()) {
 183             return "{}";
 184         }
 185 
 186         StringBuilder sb = new StringBuilder();
 187         sb.append('{');
 188         while (true) {
 189             Entry<Node, T> e = i.next();
 190             Node key = e.getKey();
 191             T value = e.getValue();
 192             sb.append(key);
 193             sb.append('=');
 194             sb.append(value);
 195             if (!i.hasNext()) {
 196                 return sb.append('}').toString();
 197             }
 198             sb.append(',').append(' ');
 199         }
 200     }



















 201 }

   1 /*
   2  * Copyright (c) 2011, 2017, 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 package org.graalvm.compiler.graph;
  24 

  25 import java.util.Arrays;
  26 import java.util.Iterator;
  27 import java.util.function.BiFunction;
  28 
  29 import org.graalvm.util.EconomicMap;
  30 import org.graalvm.util.MapCursor;
  31 
  32 public class NodeMap<T> extends NodeIdAccessor implements EconomicMap<Node, T> {
  33 
  34     private static final int MIN_REALLOC_SIZE = 16;
  35 
  36     protected Object[] values;
  37 
  38     public NodeMap(Graph graph) {
  39         super(graph);
  40         this.values = new Object[graph.nodeIdCount()];
  41     }
  42 
  43     public NodeMap(NodeMap<T> copyFrom) {
  44         super(copyFrom.graph);
  45         this.values = Arrays.copyOf(copyFrom.values, copyFrom.values.length);
  46     }
  47 
  48     @Override
  49     @SuppressWarnings("unchecked")
  50     public T get(Node node) {
  51         assert check(node);
  52         return (T) values[getNodeId(node)];
  53     }
  54 
  55     @SuppressWarnings("unchecked")
  56     public T getAndGrow(Node node) {
  57         checkAndGrow(node);
  58         return (T) values[getNodeId(node)];
  59     }
  60 
  61     private void checkAndGrow(Node node) {
  62         if (isNew(node)) {
  63             this.values = Arrays.copyOf(values, Math.max(MIN_REALLOC_SIZE, graph.nodeIdCount() * 3 / 2));
  64         }
  65         assert check(node);
  66     }
  67 
  68     @Override
  69     public boolean isEmpty() {
  70         throw new UnsupportedOperationException("isEmpty() is not supported for performance reasons");
  71     }
  72 
  73     @Override
  74     public boolean containsKey(Node node) {

  75         if (node.graph() == graph()) {
  76             return get(node) != null;
  77         }

  78         return false;
  79     }
  80 
  81     public boolean containsValue(Object value) {
  82         for (Object o : values) {
  83             if (o == value) {
  84                 return true;
  85             }
  86         }
  87         return false;
  88     }
  89 
  90     public Graph graph() {
  91         return graph;
  92     }
  93 
  94     public void set(Node node, T value) {
  95         assert check(node);
  96         values[getNodeId(node)] = value;
  97     }
  98 
  99     public void setAndGrow(Node node, T value) {
 100         checkAndGrow(node);
 101         set(node, value);
 102     }
 103 
 104     /**
 105      * @param i
 106      * @return Return the key for the entry at index {@code i}
 107      */
 108     protected Node getKey(int i) {
 109         return graph.getNode(i);
 110     }
 111 
 112     @Override
 113     public int size() {
 114         throw new UnsupportedOperationException("size() is not supported for performance reasons");
 115     }
 116 
 117     public int capacity() {
 118         return values.length;
 119     }
 120 
 121     public boolean isNew(Node node) {
 122         return getNodeId(node) >= capacity();
 123     }
 124 
 125     private boolean check(Node node) {
 126         assert node.graph() == graph : String.format("%s is not part of the graph", node);
 127         assert !isNew(node) : "this node was added to the graph after creating the node map : " + node;
 128         return true;
 129     }
 130 
 131     @Override
 132     public void clear() {
 133         Arrays.fill(values, null);
 134     }
 135 
 136     @Override
 137     public Iterable<Node> getKeys() {
 138         return new Iterable<Node>() {
 139 
 140             @Override
 141             public Iterator<Node> iterator() {
 142                 return new Iterator<Node>() {
 143 
 144                     int i = 0;
 145 
 146                     @Override
 147                     public boolean hasNext() {
 148                         forward();
 149                         return i < NodeMap.this.values.length;
 150                     }
 151 

 152                     @Override
 153                     public Node next() {
 154                         final int pos = i;
 155                         final Node key = NodeMap.this.getKey(pos);

 156                         i++;
 157                         forward();
 158                         return key;
 159                     }
 160 
 161                     @Override
 162                     public void remove() {
 163                         throw new UnsupportedOperationException();
 164                     }
 165 
 166                     private void forward() {
 167                         while (i < NodeMap.this.values.length && (NodeMap.this.getKey(i) == null || NodeMap.this.values[i] == null)) {
 168                             i++;
 169                         }
 170                     }
 171                 };
 172             }
 173         };
 174     }
 175 
 176     @Override
 177     public MapCursor<Node, T> getEntries() {
 178         return new MapCursor<Node, T>() {
 179 
 180             int current = -1;
 181 
 182             @Override
 183             public boolean advance() {
 184                 current++;
 185                 while (current < NodeMap.this.values.length && (NodeMap.this.values[current] == null || NodeMap.this.getKey(current) == null)) {
 186                     current++;
 187                 }
 188                 return current < NodeMap.this.values.length;
 189             }
 190 
 191             @Override
 192             public Node getKey() {
 193                 return NodeMap.this.getKey(current);
 194             }
 195 
 196             @SuppressWarnings("unchecked")
 197             @Override
 198             public T getValue() {
 199                 return (T) NodeMap.this.values[current];
 200             }
 201 
 202             @Override
 203             public void remove() {
 204                 assert NodeMap.this.values[current] != null;
 205                 NodeMap.this.values[current] = null;
 206             }
 207         };
 208     }
 209 
 210     @Override
 211     public Iterable<T> getValues() {
 212         return new Iterable<T>() {
 213 
 214             @Override
 215             public Iterator<T> iterator() {
 216                 return new Iterator<T>() {
 217 
 218                     int i = 0;
 219 
 220                     @Override
 221                     public boolean hasNext() {
 222                         forward();
 223                         return i < NodeMap.this.values.length;
 224                     }
 225 
 226                     @SuppressWarnings("unchecked")
 227                     @Override
 228                     public T next() {
 229                         final int pos = i;
 230                         final T value = (T) NodeMap.this.values[pos];
 231                         i++;
 232                         forward();
 233                         return value;
 234                     }
 235 
 236                     @Override
 237                     public void remove() {
 238                         throw new UnsupportedOperationException();
 239                     }
 240 
 241                     private void forward() {
 242                         while (i < NodeMap.this.values.length && (NodeMap.this.getKey(i) == null || NodeMap.this.values[i] == null)) {
 243                             i++;
 244                         }
 245                     }
 246                 };
 247             }
 248         };
 249     }
 250 
 251     @Override
 252     public String toString() {
 253         MapCursor<Node, T> i = getEntries();
 254         if (!i.advance()) {
 255             return "{}";
 256         }
 257 
 258         StringBuilder sb = new StringBuilder();
 259         sb.append('{');
 260         while (true) {
 261             Node key = i.getKey();
 262             T value = i.getValue();

 263             sb.append(key);
 264             sb.append('=');
 265             sb.append(value);
 266             if (!i.advance()) {
 267                 return sb.append('}').toString();
 268             }
 269             sb.append(',').append(' ');
 270         }
 271     }
 272 
 273     @Override
 274     public T put(Node key, T value) {
 275         T result = get(key);
 276         set(key, value);
 277         return result;
 278     }
 279 
 280     @Override
 281     public T removeKey(Node key) {
 282         return put(key, null);
 283     }
 284 
 285     @Override
 286     public void replaceAll(BiFunction<? super Node, ? super T, ? extends T> function) {
 287         for (Node n : getKeys()) {
 288             put(n, function.apply(n, get(n)));
 289         }
 290     }
 291 }