< prev index next >

src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/objects/LinkedMap.java

Print this page




  45  * list nodes as values.</p>
  46  *
  47  * @see <a href="http://www.ecma-international.org/ecma-262/6.0/#sec-map.prototype.foreach">Map.prototype.forEach</a>
  48  * @see <a href="http://www.ecma-international.org/ecma-262/6.0/#sec-set.prototype.foreach">Set.prototype.forEach</a>
  49  */
  50 public class LinkedMap {
  51 
  52     // We use a plain hash map as our hash storage.
  53     private final Map<Object, Node> data = new HashMap<>();
  54 
  55     // The head and tail of our doubly-linked list. We use the same node to represent both the head and the
  56     // tail of the list, so the list is circular. This node is never unlinked and thus always remain alive.
  57     private final Node head = new Node();
  58 
  59     /**
  60      * A node of a linked list that is used as value in our map. The linked list uses insertion order
  61      * and allows fast iteration over its element even while the map is modified.
  62      */
  63     static class Node {
  64         private final Object key;
  65         private final Object value;
  66 
  67         private volatile boolean alive = true;
  68         private volatile Node prev;
  69         private volatile Node next;
  70 
  71         /**
  72          * Constructor for the list head. This creates an empty circular list.
  73          */
  74         private Node() {
  75             this(null, null);
  76             this.next = this;
  77             this.prev = this;
  78         }
  79 
  80         /**
  81          * Constructor for value nodes.
  82          *
  83          * @param key the key
  84          * @param value the value
  85          */
  86         private Node(final Object key, final Object value) {
  87             this.key = key;
  88             this.value = value;
  89         }
  90 
  91         /**
  92          * Get the node's key.
  93          * @return the hash key
  94          */
  95         public Object getKey() {
  96             return key;
  97         }
  98 
  99         /**
 100          * Get the node's value.
 101          * @return the value
 102          */
 103         public Object getValue() {
 104             return value;
 105         }








 106     }
 107 
 108     /**
 109      * An iterator over the elements in the map.
 110      */
 111     class LinkedMapIterator {
 112 
 113         private Node cursor;
 114 
 115         private LinkedMapIterator() {
 116             this.cursor = head;
 117         }
 118 
 119         /**
 120          * Get the next node in this iteration. Changes in the underlying map are reflected in the iteration
 121          * as required by the ES6 specification. Note that this method could return a deleted node if deletion
 122          * occurred concurrently on another thread.
 123          *
 124          * @return the next node
 125          */


 133                     cursor = cursor.prev;
 134                 }
 135 
 136                 cursor = cursor.next;
 137 
 138                 if (cursor == head) {
 139                     cursor = null; // We've come full circle to the end
 140                 }
 141             }
 142 
 143             return cursor;
 144         }
 145     }
 146 
 147     /**
 148      * Add a key-value pair to the map.
 149      * @param key the key
 150      * @param value the value
 151      */
 152     public void set(final Object key, final Object value) {
 153         final Node newNode = new Node(key, value);
 154         final Node oldNode = data.put(key, newNode);
 155         if (oldNode != null) {
 156             unlink(oldNode);



 157         }
 158         link(newNode);
 159     }
 160 
 161     /**
 162      * Get the value associated with {@code key}.
 163      * @param key the key
 164      * @return the associated value, or {@code null} if {@code key} is not contained in the map
 165      */
 166     public Object get(final Object key) {
 167         final Node node = data.get(key);
 168         return node == null ? Undefined.getUndefined() : node.getValue();
 169     }
 170 
 171     /**
 172      * Returns {@code true} if {@code key} is contained in the map.
 173      * @param key the key
 174      * @return {@code true} if {@code key} is contained
 175      */
 176     public boolean has(final Object key) {
 177         return data.containsKey(key);
 178     }




  45  * list nodes as values.</p>
  46  *
  47  * @see <a href="http://www.ecma-international.org/ecma-262/6.0/#sec-map.prototype.foreach">Map.prototype.forEach</a>
  48  * @see <a href="http://www.ecma-international.org/ecma-262/6.0/#sec-set.prototype.foreach">Set.prototype.forEach</a>
  49  */
  50 public class LinkedMap {
  51 
  52     // We use a plain hash map as our hash storage.
  53     private final Map<Object, Node> data = new HashMap<>();
  54 
  55     // The head and tail of our doubly-linked list. We use the same node to represent both the head and the
  56     // tail of the list, so the list is circular. This node is never unlinked and thus always remain alive.
  57     private final Node head = new Node();
  58 
  59     /**
  60      * A node of a linked list that is used as value in our map. The linked list uses insertion order
  61      * and allows fast iteration over its element even while the map is modified.
  62      */
  63     static class Node {
  64         private final Object key;
  65         private volatile Object value;
  66 
  67         private volatile boolean alive = true;
  68         private volatile Node prev;
  69         private volatile Node next;
  70 
  71         /**
  72          * Constructor for the list head. This creates an empty circular list.
  73          */
  74         private Node() {
  75             this(null, null);
  76             this.next = this;
  77             this.prev = this;
  78         }
  79 
  80         /**
  81          * Constructor for value nodes.
  82          *
  83          * @param key the key
  84          * @param value the value
  85          */
  86         private Node(final Object key, final Object value) {
  87             this.key = key;
  88             this.value = value;
  89         }
  90 
  91         /**
  92          * Get the node's key.
  93          * @return the hash key
  94          */
  95         public Object getKey() {
  96             return key;
  97         }
  98 
  99         /**
 100          * Get the node's value.
 101          * @return the value
 102          */
 103         public Object getValue() {
 104             return value;
 105         }
 106 
 107         /**
 108          * Set the node's value
 109          * @param value the new value
 110          */
 111         void setValue(final Object value) {
 112             this.value = value;
 113         }
 114     }
 115 
 116     /**
 117      * An iterator over the elements in the map.
 118      */
 119     class LinkedMapIterator {
 120 
 121         private Node cursor;
 122 
 123         private LinkedMapIterator() {
 124             this.cursor = head;
 125         }
 126 
 127         /**
 128          * Get the next node in this iteration. Changes in the underlying map are reflected in the iteration
 129          * as required by the ES6 specification. Note that this method could return a deleted node if deletion
 130          * occurred concurrently on another thread.
 131          *
 132          * @return the next node
 133          */


 141                     cursor = cursor.prev;
 142                 }
 143 
 144                 cursor = cursor.next;
 145 
 146                 if (cursor == head) {
 147                     cursor = null; // We've come full circle to the end
 148                 }
 149             }
 150 
 151             return cursor;
 152         }
 153     }
 154 
 155     /**
 156      * Add a key-value pair to the map.
 157      * @param key the key
 158      * @param value the value
 159      */
 160     public void set(final Object key, final Object value) {
 161         Node node = data.get(key);
 162         if (node != null) {
 163             node.setValue(value);
 164         } else {
 165             node = new Node(key, value);
 166             data.put(key, node);
 167             link(node);
 168         }

 169     }
 170 
 171     /**
 172      * Get the value associated with {@code key}.
 173      * @param key the key
 174      * @return the associated value, or {@code null} if {@code key} is not contained in the map
 175      */
 176     public Object get(final Object key) {
 177         final Node node = data.get(key);
 178         return node == null ? Undefined.getUndefined() : node.getValue();
 179     }
 180 
 181     /**
 182      * Returns {@code true} if {@code key} is contained in the map.
 183      * @param key the key
 184      * @return {@code true} if {@code key} is contained
 185      */
 186     public boolean has(final Object key) {
 187         return data.containsKey(key);
 188     }


< prev index next >