Move Index and IndexStore implementations into Engine.

pkg/analysis_server/lib/src/index/page_node_manager.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.page_node_manager;
-
-import 'dart:collection';
-import 'dart:typed_data';
-
-import 'package:analysis_server/src/index/b_plus_tree.dart';
-import 'package:analysis_server/src/index/lru_cache.dart';
-
-
-/**
- * A [NodeManager] that caches a specified number of index and leaf nodes.
- */
-class CachingNodeManager<K, V, N> implements NodeManager<K, V, N> {
-  final NodeManager<K, V, N> _delegate;
-  LRUCache<N, IndexNodeData<K, N>> _indexCache;
-  LRUCache<N, LeafNodeData<K, V>> _leafCache;
-
-  CachingNodeManager(this._delegate, int indexNodeCacheSize,
-      int leafNodeCacheSize) {
-    _indexCache = new LRUCache<N, IndexNodeData<K, N>>(indexNodeCacheSize,
-        _delegate.writeIndex);
-    _leafCache = new LRUCache<N, LeafNodeData<K, V>>(leafNodeCacheSize,
-        _delegate.writeLeaf);
-  }
-
-  @override
-  int get maxIndexKeys => _delegate.maxIndexKeys;
-
-  @override
-  int get maxLeafKeys => _delegate.maxLeafKeys;
-
-  @override
-  N createIndex() {
-    return _delegate.createIndex();
-  }
-
-  @override
-  N createLeaf() {
-    return _delegate.createLeaf();
-  }
-
-  @override
-  void delete(N id) {
-    _indexCache.remove(id);
-    _leafCache.remove(id);
-    _delegate.delete(id);
-  }
-
-  @override
-  bool isIndex(N id) {
-    return _delegate.isIndex(id);
-  }
-
-  @override
-  IndexNodeData<K, N> readIndex(N id) {
-    IndexNodeData<K, N> data = _indexCache.get(id);
-    if (data == null) {
-      data = _delegate.readIndex(id);
-      _indexCache.put(id, data);
-    }
-    return data;
-  }
-
-  @override
-  LeafNodeData<K, V> readLeaf(N id) {
-    LeafNodeData<K, V> data = _leafCache.get(id);
-    if (data == null) {
-      data = _delegate.readLeaf(id);
-      _leafCache.put(id, data);
-    }
-    return data;
-  }
-
-  @override
-  void writeIndex(N id, IndexNodeData<K, N> data) {
-    _indexCache.put(id, data);
-  }
-
-  @override
-  void writeLeaf(N id, LeafNodeData<K, V> data) {
-    _leafCache.put(id, data);
-  }
-}
-
-
-/**
- * A [Codec] encodes and decodes data.
- */
-abstract class Codec<E> {
-  /**
-   * The size of the value in bytes.
-   */
-  int get sizeInBytes;
-
-  /**
-   * Returns the value decoded from [buffer].
-   *
-   * The given [buffer] has exactly [sizeInBytes] bytes length.
-   */
-  E decode(ByteData buffer);
-
-  /**
-   * Encodes [value] into [buffer].
-   *
-   * The given [buffer] has exactly [sizeInBytes] bytes length.
-   */
-  void encode(ByteData buffer, E value);
-}
-
-
-/**
- * A [Codec] for strings with a predefined maximum length.
- */
-class FixedStringCodec implements Codec<String> {
-  final int maxLength;
-  final int sizeInBytes;
-
-  const FixedStringCodec(int maxLength)
-      : maxLength = maxLength,
-        sizeInBytes = 2 + 2 * maxLength;
-
-  @override
-  String decode(ByteData buffer) {
-    int length = buffer.getUint16(0);
-    int offset = 2;
-    List<int> codeUnits = new List<int>(length);
-    for (int i = 0; i < length; i++) {
-      codeUnits[i] = buffer.getUint16(offset);
-      offset += 2;
-    }
-    return new String.fromCharCodes(codeUnits);
-  }
-
-  @override
-  void encode(ByteData buffer, String value) {
-    int length = value.length;
-    if (length > maxLength) {
-      throw new ArgumentError(
-          'String $value length=$length is greater than allowed $maxLength');
-    }
-    buffer.setUint16(0, length);
-    int offset = 2;
-    List<int> codeUnits = value.codeUnits;
-    for (int i = 0; i < length; i++) {
-      buffer.setUint16(offset, codeUnits[i]);
-      offset += 2;
-    }
-  }
-}
-
-
-/**
- * A [PageManager] that keeps all [Uint8List] pages in memory.
- */
-class MemoryPageManager implements PageManager {
-  final int pageSizeInBytes;
-  int _nextPage = 0;
-  final Map<int, Uint8List> _pages = new HashMap<int, Uint8List>();
-
-  MemoryPageManager(this.pageSizeInBytes);
-
-  @override
-  int alloc() {
-    int id = _nextPage++;
-    Uint8List page = new Uint8List(pageSizeInBytes);
-    _pages[id] = page;
-    return id;
-  }
-
-  @override
-  void free(int id) {
-    Uint8List page = _pages.remove(id);
-    if (page == null) {
-      throw new StateError('Page $id has been already freed.');
-    }
-  }
-
-  @override
-  Uint8List read(int id) {
-    Uint8List page = _pages[id];
-    if (page == null) {
-      throw new StateError('Page $id does not exist.');
-    }
-    return page;
-  }
-
-  @override
-  void write(int id, Uint8List page) {
-    if (!_pages.containsKey(id)) {
-      throw new StateError('Page $id does not exist.');
-    }
-    if (page.length != pageSizeInBytes) {
-      throw new ArgumentError('Page $id has length ${page.length}, '
-          'but $pageSizeInBytes is expected.');
-    }
-    _pages[id] = page;
-  }
-}
-
-
-/**
- * [PageManager] allows to allocate, read, write and free [Uint8List] pages.
- */
-abstract class PageManager {
-  /**
-   * The size of pages provided by this [PageManager].
-   */
-  int get pageSizeInBytes;
-
-  /**
-   * Allocates a new page and returns its identifier.
-   */
-  int alloc();
-
-  /**
-   * Frees the page with the given identifier.
-   */
-  void free(int id);
-
-  /**
-   * Reads the page with the given identifier and returns its content.
-   *
-   * An internal representation of the page is returned, any changes made to it
-   * may be accessible to other clients reading the same page.
-   */
-  Uint8List read(int id);
-
-  /**
-   * Writes the given page.
-   */
-  void write(int id, Uint8List page);
-}
-
-
-/**
- * A [NodeManager] that keeps nodes in [PageManager].
- */
-class PageNodeManager<K, V> implements NodeManager<K, V, int> {
-  static const int _INDEX_OFFSET_DATA = 4;
-  static const int _INDEX_OFFSET_KEY_COUNT = 0;
-  static const int _LEAF_OFFSET_DATA = 4;
-  static const int _LEAF_OFFSET_KEY_COUNT = 0;
-
-  final Set<int> _indexPages = new HashSet<int>();
-  Codec<K> _keyCodec;
-  final Set<int> _leafPages = new HashSet<int>();
-  PageManager _pageManager;
-  Codec<V> _valueCodec;
-
-  PageNodeManager(this._pageManager, this._keyCodec, this._valueCodec);
-
-  @override
-  int get maxIndexKeys {
-    int keySize = _keyCodec.sizeInBytes;
-    int childSize = 4;
-    int dataSize = _pageManager.pageSizeInBytes - _INDEX_OFFSET_DATA;
-    return (dataSize - childSize) ~/ (keySize + childSize);
-  }
-
-  @override
-  int get maxLeafKeys {
-    int keySize = _keyCodec.sizeInBytes;
-    int valueSize = _valueCodec.sizeInBytes;
-    int dataSize = _pageManager.pageSizeInBytes - _INDEX_OFFSET_DATA;
-    return dataSize ~/ (keySize + valueSize);
-  }
-
-  @override
-  int createIndex() {
-    int id = _pageManager.alloc();
-    _indexPages.add(id);
-    return id;
-  }
-
-  @override
-  int createLeaf() {
-    int id = _pageManager.alloc();
-    _leafPages.add(id);
-    return id;
-  }
-
-  @override
-  void delete(int id) {
-    _pageManager.free(id);
-    _indexPages.remove(id);
-    _leafPages.remove(id);
-  }
-
-  @override
-  bool isIndex(int id) {
-    return _indexPages.contains(id);
-  }
-
-  @override
-  IndexNodeData<K, int> readIndex(int id) {
-    Uint8List page = _pageManager.read(id);
-    // read header
-    int keyCount;
-    {
-      ByteData data = new ByteData.view(page.buffer);
-      keyCount = data.getInt32(_INDEX_OFFSET_KEY_COUNT);
-    }
-    // read keys/children
-    List<K> keys = new List<K>();
-    List<int> children = new List<int>();
-    int keySize = _keyCodec.sizeInBytes;
-    int offset = _INDEX_OFFSET_DATA;
-    for (int i = 0; i < keyCount; i++) {
-      // read child
-      {
-        ByteData byteData = new ByteData.view(page.buffer, offset);
-        int childPage = byteData.getUint32(0);
-        children.add(childPage);
-        offset += 4;
-      }
-      // read key
-      {
-        ByteData byteData = new ByteData.view(page.buffer, offset, keySize);
-        K key = _keyCodec.decode(byteData);
-        keys.add(key);
-        offset += keySize;
-      }
-    }
-    // read last child
-    {
-      ByteData byteData = new ByteData.view(page.buffer, offset);
-      int childPage = byteData.getUint32(0);
-      children.add(childPage);
-    }
-    // done
-    return new IndexNodeData<K, int>(keys, children);
-  }
-
-  @override
-  LeafNodeData<K, V> readLeaf(int id) {
-    Uint8List page = _pageManager.read(id);
-    // read header
-    int keyCount;
-    {
-      ByteData data = new ByteData.view(page.buffer);
-      keyCount = data.getInt32(_LEAF_OFFSET_KEY_COUNT);
-    }
-    // read keys/children
-    List<K> keys = new List<K>();
-    List<V> values = new List<V>();
-    int keySize = _keyCodec.sizeInBytes;
-    int valueSize = _valueCodec.sizeInBytes;
-    int offset = _LEAF_OFFSET_DATA;
-    for (int i = 0; i < keyCount; i++) {
-      // read key
-      {
-        ByteData byteData = new ByteData.view(page.buffer, offset, keySize);
-        K key = _keyCodec.decode(byteData);
-        keys.add(key);
-        offset += keySize;
-      }
-      // read value
-      {
-        ByteData byteData = new ByteData.view(page.buffer, offset);
-        V value = _valueCodec.decode(byteData);
-        values.add(value);
-        offset += valueSize;
-      }
-    }
-    // done
-    return new LeafNodeData<K, V>(keys, values);
-  }
-
-  @override
-  void writeIndex(int id, IndexNodeData<K, int> data) {
-    Uint8List page = new Uint8List(_pageManager.pageSizeInBytes);
-    // write header
-    int keyCount = data.keys.length;
-    {
-      ByteData byteData = new ByteData.view(page.buffer);
-      byteData.setUint32(PageNodeManager._INDEX_OFFSET_KEY_COUNT, keyCount);
-    }
-    // write keys/children
-    int keySize = _keyCodec.sizeInBytes;
-    int offset = PageNodeManager._INDEX_OFFSET_DATA;
-    for (int i = 0; i < keyCount; i++) {
-      // write child
-      {
-        ByteData byteData = new ByteData.view(page.buffer, offset);
-        byteData.setUint32(0, data.children[i]);
-        offset += 4;
-      }
-      // write key
-      {
-        ByteData byteData = new ByteData.view(page.buffer, offset, keySize);
-        _keyCodec.encode(byteData, data.keys[i]);
-        offset += keySize;
-      }
-    }
-    // write last child
-    {
-      ByteData byteData = new ByteData.view(page.buffer, offset);
-      byteData.setUint32(0, data.children.last);
-    }
-    // write page
-    _pageManager.write(id, page);
-  }
-
-  @override
-  void writeLeaf(int id, LeafNodeData<K, V> data) {
-    Uint8List page = new Uint8List(_pageManager.pageSizeInBytes);
-    // write header
-    int keyCount = data.keys.length;
-    {
-      ByteData byteData = new ByteData.view(page.buffer);
-      byteData.setUint32(PageNodeManager._LEAF_OFFSET_KEY_COUNT, keyCount);
-    }
-    // write keys/values
-    int keySize = _keyCodec.sizeInBytes;
-    int valueSize = _valueCodec.sizeInBytes;
-    int offset = PageNodeManager._LEAF_OFFSET_DATA;
-    for (int i = 0; i < keyCount; i++) {
-      // write key
-      {
-        ByteData byteData = new ByteData.view(page.buffer, offset, keySize);
-        _keyCodec.encode(byteData, data.keys[i]);
-        offset += keySize;
-      }
-      // write value
-      {
-        ByteData byteData = new ByteData.view(page.buffer, offset);
-        _valueCodec.encode(byteData, data.values[i]);
-        offset += valueSize;
-      }
-    }
-    // write page
-    _pageManager.write(id, page);
-  }
-}
-
-
-/**
- * A [Codec] for unsigned 32-bit integers.
- */
-class Uint32Codec implements Codec<int> {
-  static const Uint32Codec INSTANCE = const Uint32Codec._();
-
-  const Uint32Codec._();
-
-  @override
-  int get sizeInBytes => 4;
-
-  @override
-  int decode(ByteData buffer) {
-    return buffer.getUint32(0);
-  }
-
-  @override
-  void encode(ByteData buffer, int element) {
-    buffer.setUint32(0, element);
-  }
-}