1 files changed, 149 insertions, 0 deletions
diff --git a/platform/util/src/com/intellij/util/io/CachingEnumerator.java b/platform/util/src/com/intellij/util/io/CachingEnumerator.java
new file mode 100644
index 000000000000..94ce68c981ca
--- /dev/null
+++ b/platform/util/src/com/intellij/util/io/CachingEnumerator.java
@@ -0,0 +1,149 @@
+/*
+ * 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.util.io;
+
+import com.intellij.util.containers.SLRUMap;
+import jsr166e.extra.SequenceLock;
+import org.jetbrains.annotations.Nullable;
+
+import java.io.IOException;
+import java.util.concurrent.locks.Lock;
+
+/**
+ * @author peter
+ */
+public class CachingEnumerator<Data> implements DataEnumerator<Data> {
+  private static final int STRIPE_POWER = 4;
+  private static final int STRIPE_COUNT = 1 << STRIPE_POWER;
+  private static final int STRIPE_MASK = STRIPE_COUNT - 1;
+  @SuppressWarnings("unchecked") private final SLRUMap<Integer, Integer>[] myHashcodeToIdCache = new SLRUMap[STRIPE_COUNT];
+  @SuppressWarnings("unchecked") private final SLRUMap<Integer, Data>[] myIdToStringCache = new SLRUMap[STRIPE_COUNT];
+  private final Lock[] myStripeLocks = new Lock[STRIPE_COUNT];
+  private final DataEnumerator<Data> myBase;
+  private final KeyDescriptor<Data> myDataDescriptor;
+
+  public CachingEnumerator(DataEnumerator<Data> base, KeyDescriptor<Data> dataDescriptor) {
+    myBase = base;
+    myDataDescriptor = dataDescriptor;
+    int protectedSize = 8192;
+    int probationalSize = 8192;
+
+    for(int i = 0; i < STRIPE_COUNT; ++i) {
+      myHashcodeToIdCache[i] = new SLRUMap<Integer, Integer>(protectedSize / STRIPE_COUNT, probationalSize / STRIPE_COUNT);
+      myIdToStringCache[i] = new SLRUMap<Integer, Data>(protectedSize / STRIPE_COUNT, probationalSize / STRIPE_COUNT);
+      myStripeLocks[i] = new SequenceLock();
+    }
+
+  }
+
+  public int enumerate(@Nullable Data value) throws IOException {
+    int valueHashCode =-1;
+    int stripe = -1;
+
+    if (myHashcodeToIdCache != null && value != null) {
+      valueHashCode = myDataDescriptor.getHashCode(value);
+      stripe = Math.abs(valueHashCode) & STRIPE_MASK;
+
+      Integer cachedId;
+
+      myStripeLocks[stripe].lock();
+      try {
+        cachedId = myHashcodeToIdCache[stripe].get(valueHashCode);
+      }
+      finally {
+        myStripeLocks[stripe].unlock();
+      }
+
+      if (cachedId != null) {
+        int stripe2 = idStripe(cachedId.intValue());
+        myStripeLocks[stripe2].lock();
+        try {
+          Data s = myIdToStringCache[stripe2].get(cachedId);
+          if (s != null && myDataDescriptor.isEqual(value, s)) return cachedId.intValue();
+        }
+        finally {
+          myStripeLocks[stripe2].unlock();
+        }
+      }
+    }
+
+    int enumerate = myBase.enumerate(value);
+
+    if (stripe != -1) {
+      Integer enumeratedInteger;
+
+      myStripeLocks[stripe].lock();
+      try {
+        enumeratedInteger = enumerate;
+        myHashcodeToIdCache[stripe].put(valueHashCode, enumeratedInteger);
+      } finally {
+        myStripeLocks[stripe].unlock();
+      }
+
+      int stripe2 = idStripe(enumerate);
+      myStripeLocks[stripe2].lock();
+      try {
+        myIdToStringCache[stripe2].put(enumeratedInteger, value);
+      } finally {
+        myStripeLocks[stripe2].unlock();
+      }
+    }
+
+    return enumerate;
+  }
+
+  private static int idStripe(int h) {
+    h ^= (h >>> 20) ^ (h >>> 12);
+    return Math.abs(h ^ (h >>> 7) ^ (h >>> 4)) & STRIPE_MASK;
+  }
+
+  @Nullable
+  public Data valueOf(int idx) throws IOException {
+    int stripe = -1;
+    if (myIdToStringCache != null) {
+      stripe = idStripe(idx);
+      myStripeLocks[stripe].lock();
+      try {
+        Data s = myIdToStringCache[stripe].get(idx);
+        if (s != null) return s;
+      }
+      finally {
+        myStripeLocks[stripe].unlock();
+      }
+    }
+    Data s = myBase.valueOf(idx);
+
+    if (stripe != -1 && s != null) {
+      myStripeLocks[stripe].lock();
+      try {
+        myIdToStringCache[stripe].put(idx, s);
+      }
+      finally {
+        myStripeLocks[stripe].unlock();
+      }
+    }
+    return s;
+  }
+
+  public void close() throws IOException {
+    for(int i = 0; i < myIdToStringCache.length; ++i) {
+      myStripeLocks[i].lock();
+      myIdToStringCache[i].clear();
+      myHashcodeToIdCache[i].clear();
+      myStripeLocks[i].unlock();
+    }
+  }
+}