Reapply "Implement an LRU cache in dart:_internal and use it for the getter/setter caches in the VM…

sdk/lib/internal/lru.dart

Index: sdk/lib/internal/lru.dart
diff --git a/sdk/lib/internal/lru.dart b/sdk/lib/internal/lru.dart
new file mode 100644
index 0000000000000000000000000000000000000000..8f8a64a5fe6b7473707271041da221e87e101851
--- /dev/null
+++ b/sdk/lib/internal/lru.dart
@@ -0,0 +1,125 @@
+// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+part of dart._internal;
+
+class LRUAssociation<K,V> {
+  K key;
+  V value;
+  LRUAssociation previous;
+  LRUAssociation next;
+
+  void insertBetween(before, after) {
+    after.previous = this;
+    before.next = this;
+    this.next = after;
+    this.previous = before;
+  }
+
+  void remove() {
+    var after = next;
+    var before = previous;
+    after.previous = before;
+    before.next = after;
+  }
+}
+
+/**
+ * A map with a fixed capacity that evicts associations when capacity is reached
+ * on a least-recently-used basis. Implemented as an open addressing hash table
+ * with doubly-linked entries forming the LRU queue.
+ */
+class LRUMap<K,V> {
+  final LRUAssociation<K,V> _head;
+  final List _table;
+  final int _mask;
+  final int _capacity;  // Max number of associations before we start evicting.
+  int _size = 0;  // Current number of associations.
+
+  /**
+   * Create an LRUMap whose capacity is 75% of 2^shift.
+   */
+  LRUMap.withShift(int shift)
+      : this._mask = (1 << shift) - 1
+      , this._capacity = (1 << shift) * 3 ~/ 4
+      , this._table = new List(1 << shift)
+      , this._head = new LRUAssociation() {
+    // The scheme used here for handling collisions relies on there always
+    // being at least one empty slot.
+    if (shift < 1) throw new Exception("LRUMap requires a shift >= 1");
+    assert(_table.length > _capacity);
+    _head.insertBetween(_head, _head);
+  }
+
+  int _scanFor(K key) {
+    var start = key.hashCode & _mask;
+    var index = start;
+    do {
+      var assoc = _table[index];
+      if (null == assoc || assoc.key == key) {
+        return index;
+      }
+      index = (index + 1) & _mask;
+    } while (index != start);
+    // Should never happen because we start evicting associations before the
+    // table is full.
+    throw new Exception("Internal error: LRUMap table full");
+  }
+
+  void _fixCollisionsAfter(start) {
+    var assoc;
+    var index = (start + 1) & _mask;
+    while (null != (assoc = _table[index])) {
+      var newIndex = _scanFor(assoc.key);
+      if (newIndex != index) {
+        assert(_table[newIndex] == null);
+        _table[newIndex] = assoc;
+        _table[index] = null;
+      }
+      index = (index + 1) & _mask;
+    }
+  }
+
+  operator []=(K key, V value) {
+    int index = _scanFor(key);
+    var assoc = _table[index];
+    if (null != assoc) {
+      // Existing key, replace value.
+      assert(assoc.key == key);
+      assoc.value = value;
+      assoc.remove();
+      assoc.insertBetween(_head, _head.next);
+    } else {
+      // New key.
+      var newAssoc;
+      if (_size == _capacity) {
+        // Knock out the oldest association.
+        var lru = _head.previous;
+        lru.remove();
+        index = _scanFor(lru.key);
+        _table[index] = null;
+        _fixCollisionsAfter(index);
+        index = _scanFor(key);
+        newAssoc = lru;  // Recycle the association.
+      } else {
+        newAssoc = new LRUAssociation();
+        _size++;
+      }
+      newAssoc.key = key;
+      newAssoc.value = value;
+      newAssoc.insertBetween(_head, _head.next);
+      _table[index] = newAssoc;
+    }
+  }
+
+  V operator [](K key) {
+    var index = _scanFor(key);
+    var assoc = _table[index];
+    if (null == assoc) return null;
+    // Move to front of LRU queue.
+    assoc.remove();
+    assoc.insertBetween(_head, _head.next);
+    return assoc.value;
+  }
+}