FilePageManager - disk based PageManager.

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 25 matching lines @@
   final int _maxLeafKeys;
 
   /**
    * The root node.
    */
   _Node<K, V, N> _root;
 
   /**
    * Creates a new [BPlusTree] instance.
    */
-  BPlusTree(this._maxIndexKeys, this._maxLeafKeys, this._comparator,
-      this._manager) {
+  BPlusTree(this._comparator, NodeManager<K, V, N> manager)
+      : _manager = manager,
+        _maxIndexKeys = manager.maxIndexKeys,
+        _maxLeafKeys = manager.maxLeafKeys {
     _root = _newLeafNode();
     _writeLeafNode(_root);
   }
 
   /**
    * Returns the value for [key] or `null` if [key] is not in the tree.
    */
   V find(K key) {
     return _root.find(key);
   }
@@ skipping 123 matching lines @@
   final List<K> keys;
   final List<V> values;
   LeafNodeData(this.keys, this.values);
 }
 
 
 /**
  * An implementation of [NodeManager] that keeps node information in memory.
  */
 class MemoryNodeManager<K, V> implements NodeManager<K, V, int> {
+  final int maxIndexKeys;
+  final int maxLeafKeys;
   Map<int, IndexNodeData> _indexDataMap = new HashMap<int, IndexNodeData>();
   Map<int, LeafNodeData> _leafDataMap = new HashMap<int, LeafNodeData>();
+
   int _nextPageIndexId = 0;
   int _nextPageLeafId = 1;
 
+  MemoryNodeManager(this.maxIndexKeys, this.maxLeafKeys);
+
   @override
   int createIndex() {
     int id = _nextPageIndexId;
     _nextPageIndexId += 2;
     return id;
   }
 
   @override
   int createLeaf() {
     int id = _nextPageLeafId;
@@ skipping 35 matching lines @@
     _leafDataMap[id] = data;
   }
 }
 
 
 /**
  * A manager that manages nodes.
  */
 abstract class NodeManager<K, V, N> {
   /**
+   * The maximum number of keys in an index node.
+   */
+  int get maxIndexKeys;
+
+  /**
+   * The maximum number of keys in a leaf node.
+   */
+  int get maxLeafKeys;
+
+  /**
    * Generates an identifier for a new index node.
    */
   N createIndex();
 
   /**
    * Generates an identifier for a new leaf node.
    */
   N createLeaf();
 
   /**
@@ skipping 301 matching lines @@
     // Perform balancing.
     if (keys.length < minKeys) {
       // Try left sibling.
       if (left is _LeafNode<K, V, N>) {
         // Try to redistribute.
         int leftLength = left.keys.length;
         if (leftLength > minKeys) {
           int halfExcess = (leftLength - minKeys + 1) ~/ 2;
           int newLeftLength = leftLength - halfExcess;
           keys.insertAll(0, left.keys.getRange(newLeftLength, leftLength));
-          values.insertAll(0, left.values.getRange(newLeftLength,
-              leftLength));
+          values.insertAll(0, left.values.getRange(newLeftLength, leftLength));
           left.keys.length = newLeftLength;
           left.values.length = newLeftLength;
           tree._writeLeafNode(this);
           tree._writeLeafNode(left);
           return new _Remove<K, V>.borrowLeft(value, keys.first);
         }
         // Do merge.
         left.keys.addAll(keys);
         left.values.addAll(values);
         tree._writeLeafNode(this);
@@ skipping 149 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);
 }