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

   1 /*
   2  * Copyright 2000-2007 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.util.io;
  17
  18 import com.intellij.openapi.Forceable;
  19 import com.intellij.openapi.util.io.FileUtil;
  20 import com.intellij.util.CommonProcessors;
  21 import com.intellij.util.Processor;
  22 import com.intellij.util.containers.SLRUMap;
  23 import com.intellij.util.containers.ShareableKey;
  24 import org.jetbrains.annotations.Nullable;
  25
  26 import java.io.*;
  27 import java.util.ArrayList;
  28 import java.util.Collection;
  29 import java.util.List;
  30
  31 /**
  32  * @author max
  33  * @author jeka
  34  */
  35 public class PersistentEnumerator<Data> implements Forceable {
  36   protected static final int NULL_ID = 0;
  37   protected static final int DATA_OFFSET = 8;
  38   private static final int META_DATA_OFFSET = 4;
  39   private static final int FIRST_VECTOR_OFFSET = 8;
  40   private static final int DIRTY_MAGIC = 0xbabe0589;
  41   private static final int VERSION = 4;
  42   private static final int CORRECTLY_CLOSED_MAGIC = 0xebabafac + VERSION;
  43
  44   private static final int BITS_PER_LEVEL = 4;
  45   private static final int SLOTS_PER_VECTOR = 1 << BITS_PER_LEVEL;
  46   private static final int LEVEL_MASK = SLOTS_PER_VECTOR - 1;
  47   private static final byte[] EMPTY_VECTOR = new byte[SLOTS_PER_VECTOR * 4];
  48
  49   private static final int BITS_PER_FIRST_LEVEL = 12;
  50   private static final int SLOTS_PER_FIRST_VECTOR = 1 << BITS_PER_FIRST_LEVEL;
  51   private static final int FIRST_LEVEL_MASK = SLOTS_PER_FIRST_VECTOR - 1;
  52   private static final byte[] FIRST_VECTOR = new byte[SLOTS_PER_FIRST_VECTOR * 4];
  53
  54
  55   protected final ResizeableMappedFile myStorage;
  56
  57   private boolean myClosed = false;
  58   private boolean myDirty = false;
  59   private final KeyDescriptor<Data> myDataDescriptor;
  60   private final byte[] myBuffer = new byte[RECORD_SIZE];
  61
  62   private static final CacheKey ourFlyweight = new FlyweightKey();
  63
  64   private final File myFile;
  65   private static final int COLLISION_OFFSET = 0;
  66   private static final int KEY_HASHCODE_OFFSET = COLLISION_OFFSET + 4;
  67   private static final int KEY_REF_OFFSET = KEY_HASHCODE_OFFSET + 4;
  68   protected static final int RECORD_SIZE = KEY_REF_OFFSET + 4;
  69
  70   private final MyAppenderStream myKeyStream;
  71   private final MyDataIS myKeyReadStream;
  72   private final RandomAccessFile myKeyRaf;
  73   private boolean myCorrupted = false;
  74
  75   private static class MyAppenderStream extends DataOutputStream {
  76     public MyAppenderStream(final File out) throws FileNotFoundException {
  77       super(new BufferedOutputStream(new FileOutputStream(out, true)));
  78       written = (int) out.length();
  79     }
  80   }
  81
  82   private static class CacheKey implements ShareableKey {
  83     public PersistentEnumerator owner;
  84     public Object key;
  85
  86     private CacheKey(final Object key, final PersistentEnumerator owner) {
  87       this.key = key;
  88       this.owner = owner;
  89     }
  90
  91     public ShareableKey getStableCopy() {
  92       return this;
  93     }
  94
  95     public boolean equals(final Object o) {
  96       if (this == o) return true;
  97       if (!(o instanceof CacheKey)) return false;
  98
  99       final CacheKey cacheKey = (CacheKey)o;
 100
 101       if (!key.equals(cacheKey.key)) return false;
 102       if (!owner.equals(cacheKey.owner)) return false;
 103
 104       return true;
 105     }
 106
 107     public int hashCode() {
 108       return key.hashCode();
 109     }
 110   }
 111
 112   private static CacheKey sharedKey(Object key, PersistentEnumerator owner) {
 113     ourFlyweight.key = key;
 114     ourFlyweight.owner = owner;
 115     return ourFlyweight;
 116   }
 117
 118   private static final SLRUMap<Object, Integer> ourEnumerationCache = new SLRUMap<Object, Integer>(8192, 8192);
 119
 120   public static class CorruptedException extends IOException {
 121     @SuppressWarnings({"HardCodedStringLiteral"})
 122     public CorruptedException(File file) {
 123       super("PersistentStringEnumerator storage corrupted " + file.getPath());
 124     }
 125   }
 126
 127   public PersistentEnumerator(File file, KeyDescriptor<Data> dataDescriptor, int initialSize) throws IOException {
 128     myDataDescriptor = dataDescriptor;
 129     myFile = file;
 130     if (!file.exists()) {
 131       FileUtil.delete(keystreamFile());
 132       if (!FileUtil.createIfDoesntExist(file)) {
 133         throw new IOException("Cannot create empty file: " + file);
 134       }
 135     }
 136
 137     myStorage = new ResizeableMappedFile(myFile, initialSize);
 138     myKeyStream = new MyAppenderStream(keystreamFile());
 139
 140     if (myStorage.length() == 0) {
 141       markDirty(true);
 142       putMetaData(0);
 143       allocVector(FIRST_VECTOR);
 144     }
 145     else {
 146       int sign;
 147       try {
 148         sign = myStorage.getInt(0);
 149       }
 150       catch(Exception e) {
 151         sign = DIRTY_MAGIC;
 152       }
 153       if (sign != CORRECTLY_CLOSED_MAGIC) {
 154         myStorage.close();
 155         throw new CorruptedException(file);
 156       }
 157     }
 158
 159     myKeyRaf = new RandomAccessFile(keystreamFile(), "r");
 160     myKeyReadStream = new MyDataIS(myKeyRaf);
 161   }
 162
 163   protected synchronized int tryEnumerate(Data value) throws IOException {
 164     synchronized (ourEnumerationCache) {
 165       final Integer cachedId = ourEnumerationCache.get(sharedKey(value, this));
 166       if (cachedId != null) return cachedId.intValue();
 167     }
 168     final int id = enumerateImpl(value, false);
 169     if (id != NULL_ID) {
 170       synchronized (ourEnumerationCache) {
 171         ourEnumerationCache.put(new CacheKey(value, this), id);
 172       }
 173     }
 174     return id;
 175   }
 176
 177   public synchronized int enumerate(Data value) throws IOException {
 178     synchronized (ourEnumerationCache) {
 179       final Integer cachedId = ourEnumerationCache.get(sharedKey(value, this));
 180       if (cachedId != null) return cachedId.intValue();
 181     }
 182
 183     final int id = enumerateImpl(value, true);
 184     synchronized (ourEnumerationCache) {
 185       ourEnumerationCache.put(new CacheKey(value, this), id);
 186     }
 187
 188     return id;
 189   }
 190
 191   public interface DataFilter {
 192     boolean accept(int id);
 193   }
 194
 195   public synchronized void putMetaData(int data) throws IOException {
 196     myStorage.putInt(META_DATA_OFFSET, data);
 197   }
 198
 199   public synchronized int getMetaData() throws IOException {
 200     return myStorage.getInt(META_DATA_OFFSET);
 201   }
 202
 203   public boolean processAllDataObject(final Processor<Data> processor, @Nullable final DataFilter filter) throws IOException {
 204     return traverseAllRecords(new RecordsProcessor() {
 205       public boolean process(final int record) throws IOException {
 206         if (filter == null || filter.accept(record)) {
 207           return processor.process(valueOf(record));
 208         }
 209         return true;
 210       }
 211     });
 212
 213   }
 214
 215   public Collection<Data> getAllDataObjects(@Nullable final DataFilter filter) throws IOException {
 216     final List<Data> values = new ArrayList<Data>();
 217     processAllDataObject(new CommonProcessors.CollectProcessor<Data>(values), filter);
 218     return values;
 219   }
 220
 221   public interface RecordsProcessor {
 222     boolean process(int record) throws IOException;
 223   }
 224
 225   public synchronized boolean traverseAllRecords(RecordsProcessor p) throws IOException {
 226     return traverseRecords(FIRST_VECTOR_OFFSET, SLOTS_PER_FIRST_VECTOR, p);
 227   }
 228
 229   private boolean traverseRecords(int vectorStart, int slotsCount, RecordsProcessor p) throws IOException {
 230     for (int slotIdx = 0; slotIdx < slotsCount; slotIdx++) {
 231       final int vector = myStorage.getInt(vectorStart + slotIdx * 4);
 232       if (vector < 0) {
 233         for (int record = -vector; record != 0; record = nextCanditate(record)) {
 234           if (!p.process(record)) return false;
 235         }
 236       }
 237       else if (vector > 0) {
 238         if (!traverseRecords(vector, SLOTS_PER_VECTOR, p)) return false;
 239       }
 240     }
 241     return true;
 242   }
 243
 244   private int enumerateImpl(final Data value, final boolean saveNewValue) throws IOException {
 245     try {
 246       int depth = 0;
 247       final int valueHC = myDataDescriptor.getHashCode(value);
 248       int hc = valueHC;
 249       int vector = FIRST_VECTOR_OFFSET;
 250       int pos;
 251       int lastVector;
 252
 253       int levelMask = FIRST_LEVEL_MASK;
 254       int bitsPerLevel = BITS_PER_FIRST_LEVEL;
 255       do {
 256         lastVector = vector;
 257         pos = vector + (hc & levelMask) * 4;
 258         hc >>>= bitsPerLevel;
 259         vector = myStorage.getInt(pos);
 260         depth++;
 261
 262         levelMask = LEVEL_MASK;
 263         bitsPerLevel = BITS_PER_LEVEL;
 264       }
 265       while (vector > 0);
 266
 267       if (vector == 0) {
 268         // Empty slot
 269         if (!saveNewValue) {
 270           return NULL_ID;
 271         }
 272         final int newId = writeData(value, valueHC);
 273         myStorage.putInt(pos, -newId);
 274         return newId;
 275       }
 276       else {
 277         int collision = -vector;
 278         boolean splitVector = false;
 279         int candidateHC;
 280         do {
 281           candidateHC = hashCodeOf(collision);
 282           if (candidateHC != valueHC) {
 283             splitVector = true;
 284             break;
 285           }
 286
 287           Data candidate = valueOf(collision);
 288           if (myDataDescriptor.isEqual(value, candidate)) {
 289             return collision;
 290           }
 291
 292           collision = nextCanditate(collision);
 293         }
 294         while (collision != 0);
 295
 296         if (!saveNewValue) {
 297           return NULL_ID;
 298         }
 299
 300         final int newId = writeData(value, valueHC);
 301         if (splitVector) {
 302           depth--;
 303           do {
 304             final int valueHCByte = hcByte(valueHC, depth);
 305             final int oldHCByte = hcByte(candidateHC, depth);
 306             if (valueHCByte == oldHCByte) {
 307               int newVector = allocVector(EMPTY_VECTOR);
 308               myStorage.putInt(lastVector + oldHCByte * 4, newVector);
 309               lastVector = newVector;
 310             }
 311             else {
 312               myStorage.putInt(lastVector + valueHCByte * 4, -newId);
 313               myStorage.putInt(lastVector + oldHCByte * 4, vector);
 314               break;
 315             }
 316             depth++;
 317           }
 318           while (true);
 319         }
 320         else {
 321           // Hashcode collision detected. Insert new string into the list of colliding.
 322           myStorage.putInt(newId, vector);
 323           myStorage.putInt(pos, -newId);
 324         }
 325         return newId;
 326       }
 327     }
 328     catch (IOException io) {
 329       markCorrupted();
 330       throw io;
 331     }
 332     catch (Throwable e) {
 333       markCorrupted();
 334       throw new RuntimeException(e);
 335     }
 336   }
 337
 338   private static int hcByte(int hashcode, int byteN) {
 339     if (byteN == 0) {
 340       return hashcode & FIRST_LEVEL_MASK;
 341     }
 342
 343     hashcode >>>= BITS_PER_FIRST_LEVEL;
 344     byteN--;
 345
 346     return (hashcode >>> (byteN * BITS_PER_LEVEL)) & LEVEL_MASK;
 347   }
 348
 349   private int allocVector(final byte[] empty) throws IOException {
 350     final int pos = (int)myStorage.length();
 351     myStorage.put(pos, empty, 0, empty.length);
 352     return pos;
 353   }
 354
 355   private int nextCanditate(final int idx) throws IOException {
 356     return -myStorage.getInt(idx);
 357   }
 358
 359   private int writeData(final Data value, int hashCode) {
 360     try {
 361       markDirty(true);
 362
 363       byte[] buf = prepareEntryRecordBuf(hashCode, myKeyStream.size());
 364       myDataDescriptor.save(myKeyStream, value);
 365
 366       final ResizeableMappedFile storage = myStorage;
 367       final int pos = (int)storage.length();
 368       storage.put(pos, buf, 0, buf.length);
 369
 370       return pos;
 371     }
 372     catch (IOException e) {
 373       throw new RuntimeException(e);
 374     }
 375   }
 376
 377   private byte[] prepareEntryRecordBuf(int hashCode, int dataOffset) {
 378     final byte[] buf = getRecordBuffer();
 379     setupRecord(hashCode, dataOffset, buf);
 380     return buf;
 381   }
 382
 383   protected byte[] getRecordBuffer() {
 384     return myBuffer;
 385   }
 386
 387   protected void setupRecord(int hashCode, final int dataOffset, final byte[] buf) {
 388     Bits.putInt(buf, COLLISION_OFFSET, 0);
 389     Bits.putInt(buf, KEY_HASHCODE_OFFSET, hashCode);
 390     Bits.putInt(buf, KEY_REF_OFFSET, dataOffset);
 391   }
 392
 393   public boolean iterateData(final Processor<Data> processor) throws IOException {
 394     flushKeysStream();
 395
 396     DataInputStream keysStream = new DataInputStream(new BufferedInputStream(new FileInputStream(keystreamFile())));
 397     try {
 398       try {
 399         while (true) {
 400           Data key = myDataDescriptor.read(keysStream);
 401           if (!processor.process(key)) return false;
 402         }
 403       }
 404       catch (EOFException e) {
 405         // Done
 406       }
 407       return true;
 408     }
 409     finally {
 410       keysStream.close();
 411     }
 412   }
 413
 414   private File keystreamFile() {
 415     return new File(myFile.getPath() + ".keystream");
 416   }
 417
 418   private void flushKeysStream() {
 419     try {
 420       myKeyStream.flush();
 421     }
 422     catch (IOException e) {
 423       throw new RuntimeException(e);
 424     }
 425   }
 426
 427   private int hashCodeOf(int idx) throws IOException {
 428     return myStorage.getInt(idx + KEY_HASHCODE_OFFSET);
 429   }
 430
 431   public synchronized Data valueOf(int idx) throws IOException {
 432     try {
 433       myKeyStream.flush();
 434       final ResizeableMappedFile storage = myStorage;
 435       int addr = storage.getInt(idx + KEY_REF_OFFSET);
 436       myKeyReadStream.setup(addr, myKeyStream.size());
 437       return myDataDescriptor.read(myKeyReadStream);
 438     }
 439     catch (IOException io) {
 440       markCorrupted();
 441       throw io;
 442     }
 443     catch (Throwable e) {
 444       markCorrupted();
 445       throw new RuntimeException(e);
 446     }
 447   }
 448
 449   private static class MyDataIS extends DataInputStream {
 450     private MyDataIS(RandomAccessFile raf) {
 451       super(new MyBufferedIS(new RandomAccessFileInputStream(raf, 0, 0)));
 452     }
 453
 454     public void setup(long pos, long limit) {
 455       ((MyBufferedIS)in).setup(pos, limit);
 456     }
 457   }
 458
 459   private static class MyBufferedIS extends BufferedInputStream {
 460     public MyBufferedIS(final InputStream in) {
 461       super(in, 512);
 462     }
 463
 464     public void setup(long pos, long limit) {
 465       this.pos = 0;
 466       count = 0;
 467       ((RandomAccessFileInputStream)in).setup(pos, limit);
 468     }
 469   }
 470
 471   public synchronized void close() throws IOException {
 472     if (!myClosed) {
 473       myClosed = true;
 474       try {
 475         myKeyStream.close();
 476         myKeyReadStream.close();
 477         myKeyRaf.close();
 478         flush();
 479       }
 480       finally {
 481         myStorage.close();
 482       }
 483     }
 484   }
 485
 486   public synchronized boolean isClosed() {
 487     return myClosed;
 488   }
 489
 490   public synchronized boolean isDirty() {
 491     return myDirty;
 492   }
 493
 494   public synchronized void flush() throws IOException {
 495      if (myStorage.isDirty() || isDirty()) {
 496        markDirty(false);
 497        myStorage.force();
 498      }
 499    }
 500
 501   public synchronized void force() {
 502     try {
 503       flushKeysStream();
 504       flush();
 505     }
 506     catch (IOException e) {
 507       throw new RuntimeException(e);
 508     }
 509   }
 510
 511   private void markDirty(boolean dirty) throws IOException {
 512     if (myDirty) {
 513       if (!dirty) {
 514         markClean();
 515       }
 516     }
 517     else {
 518       if (dirty) {
 519         myStorage.putInt(0, DIRTY_MAGIC);
 520         myDirty = true;
 521       }
 522     }
 523   }
 524
 525   private void markCorrupted() {
 526     if (!myCorrupted) {
 527       myCorrupted = true;
 528       try {
 529         markDirty(true);
 530         force();
 531       }
 532       catch (IOException e) {
 533         // ignore...
 534       }
 535     }
 536   }
 537
 538   protected void markClean() throws IOException {
 539     if (!myCorrupted) {
 540       myStorage.putInt(0, CORRECTLY_CLOSED_MAGIC);
 541       myDirty = false;
 542     }
 543   }
 544
 545   private static class FlyweightKey extends CacheKey {
 546     public FlyweightKey() {
 547       super(null, null);
 548     }
 549
 550     public ShareableKey getStableCopy() {
 551       return new CacheKey(key, owner);
 552     }
 553   }
 554 }