| 1 | /******************************************************************************* |
| 2 | * Copyright (c) 2013, 2014 Ericsson |
| 3 | * |
| 4 | * All rights reserved. This program and the accompanying materials are |
| 5 | * made available under the terms of the Eclipse Public License v1.0 which |
| 6 | * accompanies this distribution, and is available at |
| 7 | * http://www.eclipse.org/legal/epl-v10.html |
| 8 | * |
| 9 | * Contributors: |
| 10 | * Marc-Andre Laperle - Initial API and implementation |
| 11 | *******************************************************************************/ |
| 12 | |
| 13 | package org.eclipse.tracecompass.internal.tmf.core.trace.indexer; |
| 14 | |
| 15 | import java.io.File; |
| 16 | import java.io.IOException; |
| 17 | import java.nio.ByteBuffer; |
| 18 | import java.text.MessageFormat; |
| 19 | |
| 20 | import org.eclipse.tracecompass.internal.tmf.core.Activator; |
| 21 | import org.eclipse.tracecompass.tmf.core.timestamp.ITmfTimestamp; |
| 22 | import org.eclipse.tracecompass.tmf.core.timestamp.TmfTimestamp; |
| 23 | import org.eclipse.tracecompass.tmf.core.trace.indexer.ITmfPersistentlyIndexable; |
| 24 | import org.eclipse.tracecompass.tmf.core.trace.indexer.checkpoint.ITmfCheckpoint; |
| 25 | import org.eclipse.tracecompass.tmf.core.trace.indexer.checkpoint.TmfCheckpoint; |
| 26 | import org.eclipse.tracecompass.tmf.core.trace.location.ITmfLocation; |
| 27 | |
| 28 | /** |
| 29 | * An array of checkpoints stored on disk. It is very efficient for searching |
| 30 | * checkpoints by rank (O(1)) |
| 31 | * |
| 32 | * @author Marc-Andre Laperle |
| 33 | */ |
| 34 | public class FlatArray extends AbstractFileCheckpointCollection { |
| 35 | /** |
| 36 | * Typical FlatArray file name |
| 37 | */ |
| 38 | public static final String INDEX_FILE_NAME = "checkpoint_flatarray.idx"; //$NON-NLS-1$ |
| 39 | |
| 40 | // Cached values |
| 41 | private int fCheckpointSize = 0; |
| 42 | private ByteBuffer fByteBuffer; |
| 43 | |
| 44 | /** |
| 45 | * Constructs a FlatArray for a given trace from scratch or from an existing |
| 46 | * file. When the FlatArray is created from scratch, it is populated by |
| 47 | * subsequent calls to {@link #insert}. |
| 48 | * |
| 49 | * @param file |
| 50 | * the file to use as the persistent storage |
| 51 | * @param trace |
| 52 | * the trace |
| 53 | */ |
| 54 | public FlatArray(File file, ITmfPersistentlyIndexable trace) { |
| 55 | super(file, trace); |
| 56 | |
| 57 | fCheckpointSize = getTrace().getCheckpointSize(); |
| 58 | fByteBuffer = ByteBuffer.allocate(fCheckpointSize); |
| 59 | fByteBuffer.clear(); |
| 60 | } |
| 61 | |
| 62 | /** |
| 63 | * Insert a checkpoint into the file-backed array |
| 64 | * |
| 65 | * @param checkpoint |
| 66 | * the checkpoint to insert |
| 67 | */ |
| 68 | @Override |
| 69 | public void insert(ITmfCheckpoint checkpoint) { |
| 70 | try { |
| 71 | CheckpointCollectionFileHeader header = getHeader(); |
| 72 | ++header.fSize; |
| 73 | getRandomAccessFile().seek(getRandomAccessFile().length()); |
| 74 | fByteBuffer.clear(); |
| 75 | checkpoint.serialize(fByteBuffer); |
| 76 | getRandomAccessFile().write(fByteBuffer.array()); |
| 77 | } catch (IOException e) { |
| 78 | Activator.logError(MessageFormat.format(Messages.FlatArray_IOErrorWriting, getFile()), e); |
| 79 | } |
| 80 | } |
| 81 | |
| 82 | /** |
| 83 | * Get a checkpoint from a rank |
| 84 | * |
| 85 | * @param rank |
| 86 | * the rank to search |
| 87 | * @return the checkpoint that has been found or null if not found |
| 88 | */ |
| 89 | public ITmfCheckpoint get(long rank) { |
| 90 | ITmfCheckpoint checkpoint = null; |
| 91 | try { |
| 92 | long pos = getHeader().getSize() + fCheckpointSize * rank; |
| 93 | getRandomAccessFile().seek(pos); |
| 94 | fByteBuffer.clear(); |
| 95 | getRandomAccessFile().read(fByteBuffer.array()); |
| 96 | ITmfLocation location = getTrace().restoreLocation(fByteBuffer); |
| 97 | ITmfTimestamp timeStamp = TmfTimestamp.create(fByteBuffer); |
| 98 | checkpoint = new TmfCheckpoint(timeStamp, location, fByteBuffer); |
| 99 | } catch (IOException e) { |
| 100 | Activator.logError(MessageFormat.format(Messages.FlatArray_IOErrorReading, getFile()), e); |
| 101 | } |
| 102 | return checkpoint; |
| 103 | } |
| 104 | |
| 105 | /** |
| 106 | * Search for a checkpoint and return the rank. |
| 107 | * |
| 108 | * @param checkpoint |
| 109 | * the checkpoint to search |
| 110 | * @return the checkpoint rank of the searched checkpoint, if it is |
| 111 | * contained in the index; otherwise, (-(insertion point) - 1). |
| 112 | */ |
| 113 | @Override |
| 114 | public long binarySearch(ITmfCheckpoint checkpoint) { |
| 115 | if (getHeader().fSize == 1) { |
| 116 | return 0; |
| 117 | } |
| 118 | |
| 119 | long lower = 0; |
| 120 | long upper = getHeader().fSize - 1; |
| 121 | long lastMiddle = -1; |
| 122 | long middle = 0; |
| 123 | while (lower <= upper && lastMiddle != middle) { |
| 124 | lastMiddle = middle; |
| 125 | middle = (lower + upper) / 2; |
| 126 | ITmfCheckpoint found = get(middle); |
| 127 | incCacheMisses(); |
| 128 | int compare = checkpoint.compareTo(found); |
| 129 | if (compare == 0) { |
| 130 | return middle; |
| 131 | } |
| 132 | |
| 133 | if (compare < 0) { |
| 134 | upper = middle; |
| 135 | } else { |
| 136 | lower = middle + 1; |
| 137 | } |
| 138 | } |
| 139 | long insertionPoint = lower; |
| 140 | return -(insertionPoint) - 1; |
| 141 | } |
| 142 | } |