1 files changed, 386 insertions, 0 deletions
diff --git a/platform/indexing-impl/src/com/intellij/psi/impl/PersistentIntList.java b/platform/indexing-impl/src/com/intellij/psi/impl/PersistentIntList.java
new file mode 100644
index 000000000000..aa5998364db4
--- /dev/null
+++ b/platform/indexing-impl/src/com/intellij/psi/impl/PersistentIntList.java
@@ -0,0 +1,386 @@
+/*
+ * Copyright 2000-2014 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.intellij.psi.impl;
+
+import com.intellij.openapi.Disposable;
+import com.intellij.openapi.util.Ref;
+import com.intellij.openapi.util.io.FileUtil;
+import com.intellij.util.ArrayUtil;
+import com.intellij.util.io.Bits;
+import com.intellij.util.io.IntToIntBtree;
+import com.intellij.util.io.PagedFileStorage;
+import com.intellij.util.io.RandomAccessDataFile;
+import gnu.trove.TIntHashSet;
+import gnu.trove.TIntIntHashMap;
+import gnu.trove.TIntIntProcedure;
+import org.jetbrains.annotations.NotNull;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.Arrays;
+
+/**
+ * the (int -> int[]) map which is persisted to the specified file.
+ */
+public class PersistentIntList implements Disposable {
+  public static final int MAX_DATA_BYTES = 500000000;
+  public static final int MAX_LIST_LENGTH = 100000;
+  private final IntToIntBtree index;
+  private RandomAccessDataFile data;
+  public int gap; // bytes lost due to fragmentation
+  private final int dataStart; // offset of real data; the bytes before are reserved for 'index' meta information, see persistsVarsTo()
+
+  public PersistentIntList(@NotNull File indexFile, @NotNull File dataFile, boolean initial) throws IOException {
+    if (initial) {
+      FileUtil.writeToFile(dataFile, ArrayUtil.EMPTY_BYTE_ARRAY);
+    }
+    PagedFileStorage.StorageLockContext context = new PagedFileStorage.StorageLockContext(true);
+    context.lock();
+    try {
+      data = new RandomAccessDataFile(dataFile);
+      index = new IntToIntBtree(4096, indexFile, context, initial);
+      dataStart = persistsVarsTo(data, initial);
+    }
+    finally {
+      context.unlock();
+    }
+  }
+
+  private int persistsVarsTo(@NotNull final RandomAccessDataFile data, boolean toDisk) {
+    return index.persistVars(new IntToIntBtree.BtreeDataStorage() {
+      @Override
+      public int persistInt(int offset, int value, boolean toDisk) {
+        if (toDisk) {
+          data.putInt(offset, value);
+          return value;
+        }
+        else {
+          return data.getInt(offset);
+        }
+      }
+    }, toDisk);
+  }
+
+  @Override
+  public void dispose() {
+    index.withStorageLock(new Runnable() {
+      @Override
+      public void run() {
+        try {
+          persistsVarsTo(data, true);
+          index.doClose();
+        }
+        catch (IOException e) {
+          throw new RuntimeException(e);
+        }
+        data.dispose();
+      }
+    });
+  }
+
+  @NotNull
+  public int[] get(final int id) {
+    final Ref<int[]> res = new Ref<int[]>();
+
+    index.withStorageLock(new Runnable() {
+      @Override
+      public void run() {
+        final int[] ptrPtr = new int[1];
+        boolean exists = index.get(id, ptrPtr);
+        if (!exists) {
+          ptrPtr[0] = 0;
+        }
+        int pointer = ptrPtr[0];
+        if (pointer == 0) {
+          res.set(ArrayUtil.EMPTY_INT_ARRAY);
+        }
+        else {
+          assertPointer(pointer);
+          int listLength = data.getInt(pointer);
+          int capacity = data.getInt(pointer + 4);
+          assertListLength(listLength, capacity);
+          int[] result = new int[listLength];
+          byte[] bytes = new byte[listLength * 4];
+          data.get(pointer + 8, bytes, 0, bytes.length);
+          for (int i = 0; i < listLength; i++) {
+            result[i] = Bits.getInt(bytes, i*4);
+          }
+          res.set(result);
+        }
+      }
+    });
+    return res.get();
+  }
+
+  // return true if was added
+  public boolean add(final int id, final int value) {
+    assert value > 0;
+    assert id > 0;
+    final boolean[] added = new boolean[1];
+    index.withStorageLock(new Runnable() {
+      @Override
+      public void run() {
+        int[] ptrPtr = new int[1];
+        index.get(id, ptrPtr);
+        final int pointer = ptrPtr[0];
+        int[] stored;
+        int capacity;
+        final int listLength;
+        if (pointer == 0) {
+          stored = ArrayUtil.EMPTY_INT_ARRAY;
+          listLength = 0;
+          capacity = 2;
+        }
+        else {
+          assertPointer(pointer);
+          listLength = data.getInt(pointer);
+          capacity = data.getInt(pointer+4);
+          assertListLength(listLength,capacity);
+          stored = new int[listLength];
+          for (int i = 0; i < listLength; i++) {
+            int v = data.getInt(pointer + (i + 2) * 4);
+            stored[i] = v;
+            if (v == value) return;
+          }
+          // append
+          if (capacity > listLength /*|| data.length() == pointer + 4 + 4 + 4*capacity*/) {
+            data.putInt(pointer + (listLength + 2) * 4, value);
+            data.putInt(pointer, listLength + 1);
+            if (capacity <= listLength) {
+              data.putInt(pointer+4, capacity + 1);
+            }
+            added[0] = true;
+            return;
+          }
+          // reallocate
+          gap += 4 + 4 + 4 * capacity;
+        }
+
+        int storePointer = (int)data.length();
+        data.putInt(storePointer, stored.length + 1);
+        int newCapacity = capacity < 10 ? capacity * 2 : (int)(capacity * 1.5);
+        assert newCapacity > stored.length + 1;
+        data.putInt(storePointer+4, newCapacity);
+        for (int i = 0; i < stored.length; i++) {
+          int v = stored[i];
+          data.putInt(storePointer + (i+2)*4, v);
+        }
+        data.putInt(storePointer + (stored.length+2)*4, value);
+        for (int i = stored.length + 1; i < newCapacity; i++) {
+          data.putInt(storePointer + (i+2)*4, 0); // gap
+        }
+        index.put(id, storePointer);
+        if (storePointer > 10000000) {
+          int i = 0;
+        }
+        added[0] = true;
+      }
+    });
+
+    return added[0];
+  }
+
+  private static void assertListLength(int listLength, int capacity) {
+    assert 0 < listLength && listLength <= MAX_LIST_LENGTH : listLength;
+    assert 0 < capacity && capacity <= MAX_LIST_LENGTH : capacity;
+    assert capacity >= listLength : listLength + ", " + capacity;
+    assert capacity <= (listLength+1)*2 : listLength + ", " + capacity;
+  }
+
+  public void addAll(final int id, @NotNull final int[] values) {
+    assertListLength(values.length, values.length);
+    assert id > 0;
+    Arrays.sort(values);
+
+    index.withStorageLock(new Runnable() {
+      @Override
+      public void run() {
+        int[] ptrPtr = new int[1];
+        index.get(id, ptrPtr);
+        final int pointer = ptrPtr[0];
+        int capacity;
+        final int newListLength;
+        byte[] mergedBytes;
+
+        if (pointer == 0) {
+          mergedBytes = toBytes(values);
+          newListLength = values.length;
+          capacity = 0;
+        }
+        else {
+          int[] oldIds = get(id);
+          checkSorted(oldIds);
+
+          assertPointer(pointer);
+          int storedListLength = data.getInt(pointer);
+          capacity = data.getInt(pointer + 4);
+          assertListLength(storedListLength, capacity);
+          // try to merge inplace and if failed, reallocate at the end
+          byte[] storedBytes = new byte[storedListLength * 4];
+          data.get(pointer + 8, storedBytes, 0, storedListLength * 4);
+
+          mergedBytes = new byte[storedBytes.length + values.length * 4];
+          int outPtr = 0;
+          int i = 0;
+          int j = 0;
+          while (i < storedListLength || j < values.length) {
+            int stored = i < storedListLength ? Bits.getInt(storedBytes, i * 4) : Integer.MAX_VALUE;
+            int value = j < values.length ? values[j] : Integer.MAX_VALUE;
+            if (stored < value) {
+              Bits.putInt(mergedBytes, outPtr, stored);
+              outPtr += 4;
+              i++;
+            }
+            else if (stored > value) {
+              Bits.putInt(mergedBytes, outPtr, value);
+              outPtr += 4;
+              j++;
+            }
+            else {
+              Bits.putInt(mergedBytes, outPtr, value);
+              outPtr += 4;
+              j++;
+              i++;
+            }
+          }
+          int[] mergedInts = fromBytes(mergedBytes, outPtr);
+          checkSorted(mergedInts);
+
+          newListLength = outPtr / 4;
+          assertListLength(newListLength, newListLength);
+          if (newListLength <= capacity) {
+            storeArray(data, pointer, newListLength, capacity, mergedBytes);
+            return;
+          }
+          gap += capacity * 4 + 8;
+        }
+        // reallocate at the end
+
+        int storePointer = (int)data.length();
+        assertPointer(storePointer);
+        int oldCapacity = Math.max(capacity, newListLength);
+        int newCapacity = oldCapacity < 10 ? (oldCapacity + 1) * 2 : (int)(oldCapacity * 1.5);
+        assert newCapacity > newListLength + 1;
+        storeArray(data, storePointer, newListLength, newCapacity, mergedBytes);
+        index.put(id, storePointer);
+      }
+    });
+
+    int[] ids = get(id);
+    checkSorted(ids);
+    TIntHashSet set = new TIntHashSet(ids);
+    assert set.containsAll(values): "ids: "+Arrays.toString(ids)+";\n values:"+Arrays.toString(values);
+  }
+
+  private static void checkSorted(int[] oldIds) {
+    for (int i = 1; i < oldIds.length; i++) {
+      assert oldIds[i - 1] < oldIds[i] : oldIds[i-1] + ", " + oldIds[i];
+    }
+  }
+
+  private static byte[] toBytes(@NotNull int[] values) {
+    byte[] mergedBytes = new byte[4 * values.length];
+    for (int i = 0; i < values.length; i++) {
+      int value = values[i];
+      Bits.putInt(mergedBytes, i * 4, value);
+    }
+    return mergedBytes;
+  }
+
+  private static int[] fromBytes(@NotNull byte[] bytes, int length) {
+    assert length % 4 == 0;
+    int[] ints = new int[length/4];
+    for (int i = 0; i < length; i+=4) {
+      int value = Bits.getInt(bytes, i);
+      ints[i/4] = value;
+    }
+    return ints;
+  }
+
+  private static void storeArray(@NotNull RandomAccessDataFile data,
+                                 int storePointer,
+                                 int newListLength,
+                                 int newCapacity,
+                                 @NotNull byte[] mergedBytes) {
+    assertListLength(newListLength, newCapacity);
+    data.putInt(storePointer, newListLength);
+    data.putInt(storePointer + 4, newCapacity);
+    data.put(storePointer + 8, mergedBytes, 0, newListLength * 4);
+    byte[] fill = new byte[(newCapacity - newListLength) * 4];
+    Arrays.fill(fill, (byte)-1);
+    data.put(storePointer + 8 + newListLength * 4, fill, 0, fill.length);
+  }
+
+  private static void assertPointer(int pointer) {
+    assert 0 < pointer && pointer <= MAX_DATA_BYTES : pointer;
+  }
+
+  public void flush() {
+    index.withStorageLock(new Runnable() {
+      @Override
+      public void run() {
+        persistsVarsTo(data, true);
+        index.doFlush();
+        data.sync();
+        //data.force();
+      }
+    });
+  }
+
+  private void compactIfNecessary() {
+    if (gap < data.length() / 2) return;
+    index.withStorageLock(new Runnable() {
+      @Override
+      public void run() {
+        persistsVarsTo(data, true);
+        index.doFlush();
+        data.sync();
+
+        try {
+          final RandomAccessDataFile newData = new RandomAccessDataFile(new File(data.getFile().getParentFile(), "newData"));
+          persistsVarsTo(newData, true);
+          final TIntIntHashMap map = new TIntIntHashMap();
+          index.processMappings(new IntToIntBtree.KeyValueProcessor() {
+            @Override
+            public boolean process(int key, int value) throws IOException {
+              map.put(key, value);
+              return true;
+            }
+          });
+          map.forEachEntry(new TIntIntProcedure() {
+            @Override
+            public boolean execute(int key, int value) {
+              int[] ids = get(key);
+              int pointer = (int)newData.length();
+              byte[] bytes = toBytes(ids);
+              storeArray(newData, pointer, ids.length, (int)(ids.length * 1.3), bytes);
+              index.put(key, pointer);
+              return true;
+            }
+          });
+
+          data.dispose();
+          data = newData;
+          gap = 0;
+          flush();
+        }
+        catch (IOException e) {
+          throw new RuntimeException(e);
+        }
+      }
+    });
+  }
+}