Node cache, binary search.

pkg/analysis_server/lib/src/index/b_plus_tree.dart

 // 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.
 
 library index.b_plus_tree;
 
 import 'dart:collection';
 
 
 /**
@@ skipping 105 matching lines @@
     N id = _manager.createLeaf();
     return new _LeafNode<K, V, N>(this, id, _maxLeafKeys);
   }
 
   /**
    * Reads the [_IndexNode] with [id] from the manager.
    */
   _IndexNode<K, V, N> _readIndexNode(N id) {
     IndexNodeData<K, N> data = _manager.readIndex(id);
     _IndexNode<K, V, N> node = new _IndexNode<K, V, N>(this, id, _maxIndexKeys);
-    node.keys.addAll(data.keys);
-    node.children.addAll(data.children);
+    node.keys = data.keys;
+    node.children = data.children;
     return node;
   }
 
   /**
    * Reads the [_LeafNode] with [id] from the manager.
    */
   _LeafNode<K, V, N> _readLeafNode(N id) {
     _LeafNode<K, V, N> node = new _LeafNode<K, V, N>(this, id, _maxLeafKeys);
     LeafNodeData<K, V> data = _manager.readLeaf(id);
-    node.keys.addAll(data.keys);
-    node.values.addAll(data.values);
+    node.keys = data.keys;
+    node.values = data.values;
     return node;
   }
 
   /**
    * Reads the [_IndexNode] or [_LeafNode] with [id] from the manager.
    */
   _Node<K, V, N> _readNode(N id) {
     if (_manager.isIndex(id)) {
       return _readIndexNode(id);
     } else {
@@ skipping 154 matching lines @@
    * Writes information about the leaf node with the given identifier.
    */
   void writeLeaf(N id, LeafNodeData<K, V> data);
 }
 
 
 /**
  * An index node with keys and children references.
  */
 class _IndexNode<K, V, N> extends _Node<K, V, N> {
-  final List<N> children = new List<N>();
+  List<N> children = new List<N>();
   final int maxKeys;
   final int minKeys;
 
   _IndexNode(BPlusTree<K, V, N> tree, N id, int maxKeys)
       : super(tree, id),
         maxKeys = maxKeys,
         minKeys = maxKeys ~/ 2;
 
   @override
   V find(K key) {
@@ skipping 157 matching lines @@
     _Node<K, V, N> child = tree._readNode(children[keys.length]);
     child.writeOn(buffer, indent + '    ');
     buffer.write(indent);
     buffer.write('}\n');
   }
 
   /**
    * Returns the index of the child into which [key] should be inserted.
    */
   int _findChildIndex(K key) {
-    for (int i = 0; i < keys.length; i++) {
-      if (comparator(keys[i], key) > 0) {
-        return i;
+    int lo = 0;

[Brian Wilkerson, 2014/06/10 17:08:29]

Seems like a good candidate for a general utility method.

[scheglov, 2014/06/10 17:23:45]

Yes, in general, but they are not completely identical.

+    int hi = keys.length - 1;
+    while (lo <= hi) {
+      int mid = lo + (hi - lo) ~/ 2;
+      int compare = comparator(key, keys[mid]);
+      if (compare < 0) {
+        hi = mid - 1;
+      } else if (compare > 0) {
+        lo = mid + 1;
+      } else {
+        return mid + 1;
       }
     }
-    return keys.length;
+    return lo;
   }
 
   void _insertNotFull(K key, V value) {
     int index = _findChildIndex(key);
     _Node<K, V, N> child = tree._readNode(children[index]);
     _Split<K, N> result = child.insert(key, value);
     if (result != null) {
       keys.insert(index, result.key);
       children[index] = result.left;
       children.insert(index + 1, result.right);
       tree._writeIndexNode(this);
     }
   }
 }
 
 
 /**
  * A leaf node with keys and values.
  */
 class _LeafNode<K, V, N> extends _Node<K, V, N> {
   final int maxKeys;
   final int minKeys;
-  final List<V> values = new List<V>();
+  List<V> values = new List<V>();
 
   _LeafNode(BPlusTree<K, V, N> tree, N id, int maxKeys)
       : super(tree, id),
         maxKeys = maxKeys,
         minKeys = maxKeys ~/ 2;
 
   @override
   V find(K key) {
     int index = _findKeyIndex(key);
     if (index < 0) {
@@ skipping 108 matching lines @@
       buffer.write(': ');
       buffer.write(values[i]);
     }
     buffer.write('}\n');
   }
 
   /**
    * Returns the index where [key] should be inserted.
    */
   int _findKeyIndex(K key) {
-    for (int i = 0; i < keys.length; i++) {
-      if (comparator(keys[i], key) >= 0) {
-        return i;
+    int lo = 0;

[Brian Wilkerson, 2014/06/10 17:08:29]

Especially since it's already been duplicated. :-)

+    int hi = keys.length - 1;
+    while (lo <= hi) {
+      int mid = lo + (hi - lo) ~/ 2;
+      int compare = comparator(key, keys[mid]);
+      if (compare < 0) {
+        hi = mid - 1;
+      } else if (compare > 0) {
+        lo = mid + 1;
+      } else {
+        return mid;
       }
     }
-    return keys.length;
+    return lo;
   }
 
   void _insertNotFull(K key, V value, int index) {
     if (index < keys.length && keys[index] == key) {
       values[index] = value;
     } else {
       keys.insert(index, key);
       values.insert(index, value);
     }
     tree._writeLeafNode(this);
@@ skipping 11 matching lines @@
   final Comparator<K> comparator;
 
   /**
    * The identifier of this node.
    */
   final N id;
 
   /**
    *  The list of keys.
    */
-  final List<K> keys = new List<K>();
+  List<K> keys = new List<K>();
 
   /**
    * The [NodeManager] for this tree.
    */
   final NodeManager<K, V, N> manager;
 
   /**
    * The [BPlusTree] this node belongs to.
    */
   final BPlusTree<K, V, N> tree;
@@ skipping 53 matching lines @@
 
 /**
  * A container with information about split during insert.
  */
 class _Split<K, N> {
   final K key;
   final N left;
   final N right;
   _Split(this.key, this.left, this.right);
 }