OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. |
| 4 |
| 5 part of dart._internal; |
| 6 |
| 7 class LRUAssociation<K,V> { |
| 8 K key; |
| 9 V value; |
| 10 LRUAssociation previous; |
| 11 LRUAssociation next; |
| 12 |
| 13 void insertBetween(before, after) { |
| 14 after.previous = this; |
| 15 before.next = this; |
| 16 this.next = after; |
| 17 this.previous = before; |
| 18 } |
| 19 |
| 20 void remove() { |
| 21 var after = next; |
| 22 var before = previous; |
| 23 after.previous = before; |
| 24 before.next = after; |
| 25 } |
| 26 } |
| 27 |
| 28 /** |
| 29 * A map with a fixed capacity that evicts associations when capacity is reached |
| 30 * on a least-recently-used basis. Implemented as an open addressing hash table |
| 31 * with doubly-linked entries forming the LRU queue. |
| 32 */ |
| 33 class LRUMap<K,V> { |
| 34 final LRUAssociation<K,V> _head; |
| 35 final List _table; |
| 36 final int _mask; |
| 37 final int _capacity; // Max number of associations before we start evicting. |
| 38 int _size = 0; // Current number of associations. |
| 39 |
| 40 /** |
| 41 * Create an LRUMap whose capacity is 75% of 2^shift. |
| 42 */ |
| 43 LRUMap.withShift(int shift) |
| 44 : this._mask = (1 << shift) - 1 |
| 45 , this._capacity = (1 << shift) * 3 ~/ 4 |
| 46 , this._table = new List(1 << shift) |
| 47 , this._head = new LRUAssociation() { |
| 48 // The scheme used here for handling collisions relies on there always |
| 49 // being at least one empty slot. |
| 50 if (shift < 1) throw new Exception("LRUMap requires a shift >= 1"); |
| 51 assert(_table.length > _capacity); |
| 52 _head.insertBetween(_head, _head); |
| 53 } |
| 54 |
| 55 int _scanFor(K key) { |
| 56 var start = key.hashCode & _mask; |
| 57 var index = start; |
| 58 do { |
| 59 var assoc = _table[index]; |
| 60 if (null == assoc || assoc.key == key) { |
| 61 return index; |
| 62 } |
| 63 index = (index + 1) & _mask; |
| 64 } while (index != start); |
| 65 // Should never happen because we start evicting associations before the |
| 66 // table is full. |
| 67 throw new Exception("Internal error: LRUMap table full"); |
| 68 } |
| 69 |
| 70 void _fixCollisionsAfter(start) { |
| 71 var assoc; |
| 72 var index = (start + 1) & _mask; |
| 73 while (null != (assoc = _table[index])) { |
| 74 var newIndex = _scanFor(assoc.key); |
| 75 if (newIndex != index) { |
| 76 assert(_table[newIndex] == null); |
| 77 _table[newIndex] = assoc; |
| 78 _table[index] = null; |
| 79 } |
| 80 index = (index + 1) & _mask; |
| 81 } |
| 82 } |
| 83 |
| 84 operator []=(K key, V value) { |
| 85 int index = _scanFor(key); |
| 86 var assoc = _table[index]; |
| 87 if (null != assoc) { |
| 88 // Existing key, replace value. |
| 89 assert(assoc.key == key); |
| 90 assoc.value = value; |
| 91 assoc.remove(); |
| 92 assoc.insertBetween(_head, _head.next); |
| 93 } else { |
| 94 // New key. |
| 95 var newAssoc; |
| 96 if (_size == _capacity) { |
| 97 // Knock out the oldest association. |
| 98 var lru = _head.previous; |
| 99 lru.remove(); |
| 100 index = _scanFor(lru.key); |
| 101 _table[index] = null; |
| 102 _fixCollisionsAfter(index); |
| 103 index = _scanFor(key); |
| 104 newAssoc = lru; // Recycle the association. |
| 105 } else { |
| 106 newAssoc = new LRUAssociation(); |
| 107 _size++; |
| 108 } |
| 109 newAssoc.key = key; |
| 110 newAssoc.value = value; |
| 111 newAssoc.insertBetween(_head, _head.next); |
| 112 _table[index] = newAssoc; |
| 113 } |
| 114 } |
| 115 |
| 116 V operator [](K key) { |
| 117 var index = _scanFor(key); |
| 118 var assoc = _table[index]; |
| 119 if (null == assoc) return null; |
| 120 // Move to front of LRU queue. |
| 121 assoc.remove(); |
| 122 assoc.insertBetween(_head, _head.next); |
| 123 return assoc.value; |
| 124 } |
| 125 } |
OLD | NEW |