platform/util/src/com/intellij/util/io/PersistentEnumerator.java

/*
 * Copyright 2000-2013 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 org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.io.File;
import java.io.IOException;

/**
 * @author max
 * @author jeka
 */
public class PersistentEnumerator<Data> extends PersistentEnumeratorBase<Data> {
  private static final int DIRTY_MAGIC = 0xbabe0589;
  private static final int VERSION = 6;
  private static final int CORRECTLY_CLOSED_MAGIC = 0xebabafac + VERSION;

  private static final int FIRST_VECTOR_OFFSET = DATA_START;

  private static final int BITS_PER_LEVEL = 4;
  private static final int SLOTS_PER_VECTOR = 1 << BITS_PER_LEVEL;
  private static final int LEVEL_MASK = SLOTS_PER_VECTOR - 1;
  private static final byte[] EMPTY_VECTOR = new byte[SLOTS_PER_VECTOR * 4];

  private static final int BITS_PER_FIRST_LEVEL = 12;
  private static final int SLOTS_PER_FIRST_VECTOR = 1 << BITS_PER_FIRST_LEVEL;
  private static final int FIRST_LEVEL_MASK = SLOTS_PER_FIRST_VECTOR - 1;
  private static final byte[] FIRST_VECTOR = new byte[SLOTS_PER_FIRST_VECTOR * 4];

  private static final int COLLISION_OFFSET = 0;
  private static final int KEY_HASHCODE_OFFSET = COLLISION_OFFSET + 4;
  private static final int KEY_REF_OFFSET = KEY_HASHCODE_OFFSET + 4;
  private static final int RECORD_SIZE = KEY_REF_OFFSET + 4;
  private int valuesCount; // TODO: valuesCount should be persistent
  private static final Version ourVersion = new Version(CORRECTLY_CLOSED_MAGIC, DIRTY_MAGIC);

  public PersistentEnumerator(@NotNull File file, @NotNull KeyDescriptor<Data> dataDescriptor, int initialSize) throws IOException {
    this(file, dataDescriptor, initialSize, null);
  }

  public PersistentEnumerator(@NotNull File file,
                              @NotNull KeyDescriptor<Data> dataDescriptor,
                              int initialSize,
                              @Nullable PagedFileStorage.StorageLockContext storageLockContext) throws IOException {
    super(file, new ResizeableMappedFile(file, initialSize, storageLockContext, -1, false), dataDescriptor, initialSize, ourVersion,
          new RecordBufferHandler(), true);
  }

  @Override
  protected  void setupEmptyFile() throws IOException {
    allocVector(FIRST_VECTOR);
  }

  @Override
  public synchronized boolean traverseAllRecords(@NotNull RecordsProcessor p) throws IOException {
    return traverseRecords(FIRST_VECTOR_OFFSET, SLOTS_PER_FIRST_VECTOR, p);
  }

  private boolean traverseRecords(int vectorStart, int slotsCount, @NotNull RecordsProcessor p) throws IOException {
    lockStorage();
    try {
      for (int slotIdx = 0; slotIdx < slotsCount; slotIdx++) {
        final int vector = myStorage.getInt(vectorStart + slotIdx * 4);
        if (vector < 0) {
          for (int record = -vector; record != 0; record = nextCanditate(record)) {
            if (!p.process(record)) return false;
          }
        }
        else if (vector > 0) {
          if (!traverseRecords(vector, SLOTS_PER_VECTOR, p)) return false;
        }
      }
      return true;
    }
    finally {
      unlockStorage();
    }
  }

  @Override
  protected synchronized int enumerateImpl(final Data value, final boolean onlyCheckForExisting, boolean saveNewValue) throws IOException {
    lockStorage();
    try {
      int depth = 0;
      final int valueHC = myDataDescriptor.getHashCode(value);
      int hc = valueHC;
      int vector = FIRST_VECTOR_OFFSET;
      int pos;
      int lastVector;

      int levelMask = FIRST_LEVEL_MASK;
      int bitsPerLevel = BITS_PER_FIRST_LEVEL;
      do {
        lastVector = vector;
        pos = vector + (hc & levelMask) * 4;
        hc >>>= bitsPerLevel;
        vector = myStorage.getInt(pos);
        depth++;

        levelMask = LEVEL_MASK;
        bitsPerLevel = BITS_PER_LEVEL;
      }
      while (vector > 0);

      if (vector == 0) {
        // Empty slot
        if (onlyCheckForExisting) {
          return NULL_ID;
        }
        final int newId = writeData(value, valueHC);
        myStorage.putInt(pos, -newId);
        return newId;
      }
      else {
        int collision = -vector;
        boolean splitVector = false;
        int candidateHC;
        do {
          candidateHC = hashCodeOf(collision);
          if (candidateHC != valueHC) {
            splitVector = true;
            break;
          }

          Data candidate = valueOf(collision);
          if (myDataDescriptor.isEqual(value, candidate)) {
            return collision;
          }

          collision = nextCanditate(collision);
        }
        while (collision != 0);

        if (onlyCheckForExisting) {
          return NULL_ID;
        }

        final int newId = writeData(value, valueHC);

        if (splitVector) {
          depth--;
          do {
            final int valueHCByte = hcByte(valueHC, depth);
            final int oldHCByte = hcByte(candidateHC, depth);
            if (valueHCByte == oldHCByte) {
              int newVector = allocVector(EMPTY_VECTOR);
              myStorage.putInt(lastVector + oldHCByte * 4, newVector);
              lastVector = newVector;
            }
            else {
              myStorage.putInt(lastVector + valueHCByte * 4, -newId);
              myStorage.putInt(lastVector + oldHCByte * 4, vector);
              break;
            }
            depth++;
          }
          while (true);
        }
        else {
          // Hashcode collision detected. Insert new string into the list of colliding.
          myStorage.putInt(newId, vector);
          myStorage.putInt(pos, -newId);
        }
        return newId;
      }
    }
    finally {
      unlockStorage();
    }
  }

  @Override
  protected int writeData(final Data value, int hashCode) {
    int id = super.writeData(value, hashCode);
    ++valuesCount;

    if (IOStatistics.DEBUG && (valuesCount & IOStatistics.KEYS_FACTOR_MASK) == 0) {
      IOStatistics.dump("Index " + myFile + ", values " + valuesCount + ", storage size:" + myStorage.length());
    }
    return id;
  }

  private static int hcByte(int hashcode, int byteN) {
    if (byteN == 0) {
      return hashcode & FIRST_LEVEL_MASK;
    }

    hashcode >>>= BITS_PER_FIRST_LEVEL;
    byteN--;

    return (hashcode >>> (byteN * BITS_PER_LEVEL)) & LEVEL_MASK;
  }

  private int allocVector(@NotNull final byte[] empty) throws IOException {
    final int pos = (int)myStorage.length();
    myStorage.put(pos, empty, 0, empty.length);
    return pos;
  }

  private int nextCanditate(final int idx) throws IOException {
    return -myStorage.getInt(idx);
  }

  private int hashCodeOf(int idx) throws IOException {
    return myStorage.getInt(idx + KEY_HASHCODE_OFFSET);
  }

  @Override
  protected int indexToAddr(int idx) {
    return myStorage.getInt(idx + KEY_REF_OFFSET);
  }

  private static class RecordBufferHandler extends PersistentEnumeratorBase.RecordBufferHandler<PersistentEnumerator> {
    private final byte[] myBuffer = new byte[RECORD_SIZE];

    @Override
    protected int recordWriteOffset(@NotNull PersistentEnumerator enumerator, byte[] buf) {
      return (int)enumerator.myStorage.length();
    }

    @NotNull
    @Override
    byte[] getRecordBuffer(PersistentEnumerator t) {
      return myBuffer;
    }

    @Override
    void setupRecord(PersistentEnumerator enumerator, int hashCode, int dataOffset, byte[] buf) {
      Bits.putInt(buf, COLLISION_OFFSET, 0);
      Bits.putInt(buf, KEY_HASHCODE_OFFSET, hashCode);
      Bits.putInt(buf, KEY_REF_OFFSET, dataOffset);
    }
  }
}