You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by st...@apache.org on 2010/01/05 18:26:53 UTC
svn commit: r896138 [3/9] - in /hadoop/hbase/branches/0.20: ./ src/contrib/
src/contrib/indexed/ src/contrib/indexed/lib/
src/contrib/indexed/lib/fmpp-0.19.14/ src/contrib/indexed/src/
src/contrib/indexed/src/fmpp/ src/contrib/indexed/src/fmpp/src/ src...
Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegion.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegion.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegion.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegion.java Tue Jan 5 17:26:49 2010
@@ -0,0 +1,482 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.hadoop.hbase.regionserver;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.hbase.HBaseConfiguration;
+import org.apache.hadoop.hbase.HRegionInfo;
+import org.apache.hadoop.hbase.JmxHelper;
+import org.apache.hadoop.hbase.KeyValue;
+import org.apache.hadoop.hbase.client.Scan;
+import org.apache.hadoop.hbase.client.idx.IdxScan;
+import org.apache.hadoop.hbase.client.idx.exp.Expression;
+import org.apache.hadoop.hbase.regionserver.idx.support.sets.IntSet;
+import org.apache.hadoop.hbase.util.Bytes;
+import org.apache.hadoop.hbase.util.ClassSize;
+import org.apache.hadoop.metrics.util.MBeanUtil;
+import org.apache.hadoop.util.Progressable;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicLong;
+
+/**
+ * An indexed region - has the capability to index a subset of the columns and speedup scans which specify a
+ * filter expression.
+ */
+public class IdxRegion extends HRegion {
+ static final Log LOG = LogFactory.getLog(IdxRegion.class);
+
+ private static final int INDEX_BUILD_TIME_HISTORY_SIZE = 10;
+
+ private static final long FIXED_OVERHEAD = ClassSize.REFERENCE * 2 +
+ 2 * (ClassSize.REFERENCE + ClassSize.ATOMIC_INTEGER) +
+ ClassSize.REFERENCE + ClassSize.ATOMIC_LONG +
+ ClassSize.REFERENCE + ClassSize.ARRAY +
+ INDEX_BUILD_TIME_HISTORY_SIZE * Bytes.SIZEOF_LONG +
+ Bytes.SIZEOF_INT;
+
+ private IdxRegionIndexManager indexManager;
+ private IdxExpressionEvaluator expressionEvaluator;
+
+ // todo add a total number of ongoing scans to the HRegion
+ private AtomicInteger numberOfOngoingIndexedScans;
+ // todo add a a resetable total scan count when HRegion has jmx support
+ private AtomicLong totalIndexedScans;
+ private AtomicLong totalNonIndexedScans;
+ // the index build time history
+ private volatile long[] buildTimes;
+ private volatile int currentBuildTimesIndex;
+
+ /**
+ * A default constructor matching the default region constructor.
+ */
+ public IdxRegion() {
+ super();
+ }
+
+ /**
+ * See {@link HRegion#HRegion(org.apache.hadoop.fs.Path, HLog, org.apache.hadoop.fs.FileSystem, org.apache.hadoop.hbase.HBaseConfiguration, org.apache.hadoop.hbase.HRegionInfo, FlushRequester)}.
+ * <p/>
+ * Initializes the index manager and the expression evaluator.
+ */
+ public IdxRegion(Path basedir, HLog log, FileSystem fs, HBaseConfiguration
+ conf, HRegionInfo regionInfo, FlushRequester flushListener) {
+ super(basedir, log, fs, conf, regionInfo, flushListener);
+ indexManager = new IdxRegionIndexManager(this);
+ expressionEvaluator = new IdxExpressionEvaluator();
+ // monitoring parameters
+ numberOfOngoingIndexedScans = new AtomicInteger(0);
+ totalIndexedScans = new AtomicLong(0);
+ totalNonIndexedScans = new AtomicLong(0);
+ buildTimes = new long[INDEX_BUILD_TIME_HISTORY_SIZE];
+ resetIndexBuildTimes();
+ }
+
+ /**
+ * {@inheritDoc}
+ * <p/>
+ * calls super and then initialized the index manager.
+ */
+ @Override
+ public void initialize(Path initialFiles, Progressable reporter)
+ throws IOException {
+ super.initialize(initialFiles, reporter);
+ rebuildIndexes();
+ JmxHelper.registerMBean(
+ IdxRegionMBeanImpl.generateObjectName(getRegionInfo()),
+ IdxRegionMBeanImpl.newIdxRegionMBeanImpl(this));
+ }
+
+ /**
+ * {@inheritDoc}
+ * </p>
+ * Rebuilds the index.
+ */
+ @Override
+ protected void internalPreFlashcacheCommit() throws IOException {
+ rebuildIndexes();
+ super.internalPreFlashcacheCommit();
+ }
+
+ private void rebuildIndexes() throws IOException {
+ long time = indexManager.rebuildIndexes();
+ buildTimes[currentBuildTimesIndex] = time;
+ currentBuildTimesIndex = (currentBuildTimesIndex + 1) % buildTimes.length;
+ }
+
+
+ @Override
+ public List<StoreFile> close(boolean abort) throws IOException {
+ MBeanUtil.unregisterMBean(
+ IdxRegionMBeanImpl.generateObjectName(getRegionInfo()));
+ return super.close(abort);
+ }
+
+ /**
+ * {@inheritDoc}
+ * <p/>
+ * Constructs an internal scanner based on the scan expression. Reverts
+ * to default region scan in case an expression was not provided.
+ */
+ @Override
+ protected InternalScanner instantiateInternalScanner(Scan scan,
+ List<KeyValueScanner> additionalScanners) throws IOException {
+ Expression expression = IdxScan.getExpression(scan);
+ if (scan == null || expression == null) {
+ totalNonIndexedScans.incrementAndGet();
+ return super.instantiateInternalScanner(scan, additionalScanners);
+ } else {
+ totalIndexedScans.incrementAndGet();
+ // Grab a new search context
+ IdxSearchContext searchContext = indexManager.newSearchContext();
+ // use the expression evaluator to determine the final set of ints
+ IntSet matchedExpression = expressionEvaluator.evaluate(searchContext,
+ expression);
+ if (LOG.isDebugEnabled()) {
+ LOG.debug(String.format("%s rows matched the index expression",
+ matchedExpression.size()));
+ }
+ return new IdxRegionScanner(scan, searchContext, matchedExpression);
+ }
+ }
+
+ /**
+ * A monitoring operation which exposes the number of indexed keys.
+ *
+ * @return the number of indexed keys.
+ */
+ public int getNumberOfIndexedKeys() {
+ return indexManager.getNumberOfKeys();
+ }
+
+ /**
+ * The total heap size consumed by all indexes.
+ *
+ * @return the index heap size.
+ */
+ public long getIndexesTotalHeapSize() {
+ return indexManager.heapSize();
+ }
+
+ /**
+ * Gets the total number of indexed scan since the last reset.
+ *
+ * @return the total number of indexed scans.
+ */
+ public long getTotalIndexedScans() {
+ return totalIndexedScans.get();
+ }
+
+ /**
+ * Resets the total number of indexed scans.
+ *
+ * @return the number of indexed scans just before the reset
+ */
+ public long resetTotalIndexedScans() {
+ return totalIndexedScans.getAndSet(0);
+ }
+
+ /**
+ * Gets the total number of non indexed scan since the last reset.
+ *
+ * @return the total number of indexed scans.
+ */
+ public long getTotalNonIndexedScans() {
+ return totalNonIndexedScans.get();
+ }
+
+ /**
+ * Resets the total number of non indexed scans.
+ *
+ * @return the number of indexed scans just before the reset
+ */
+ public long resetTotalNonIndexedScans() {
+ return totalNonIndexedScans.getAndSet(0);
+ }
+
+ /**
+ * Exposes the number of indexed scans currently ongoing in the system.
+ *
+ * @return the number of ongoing indexed scans
+ */
+ public long getNumberOfOngoingIndexedScans() {
+ return numberOfOngoingIndexedScans.get();
+ }
+
+ /**
+ * Gets the index build times buffer.
+ *
+ * @return a rolling buffer of index build times
+ */
+ public long[] getIndexBuildTimes() {
+ return buildTimes;
+ }
+
+ /**
+ * Resets the index build times array.
+ *
+ * @return the previous build times array
+ */
+ public long[] resetIndexBuildTimes() {
+ // note: this may 'corrupt' the array if ran in parallel with a build time
+ // array modification and that's ok. we are not changing pointers so
+ // no catastrophy should happen - worse case the manager would reset again
+ long[] prevTimes = buildTimes.clone();
+ Arrays.fill(buildTimes, -1L);
+ currentBuildTimesIndex = 0;
+ return prevTimes;
+ }
+
+ /**
+ * The size of the index on the specified column in bytes.
+ *
+ * @param columnName the column to check.
+ * @return the size fo the requesed index
+ */
+ public long getIndexHeapSize(String columnName) {
+ return indexManager.getIndexHeapSize(columnName);
+ }
+
+ class IdxRegionScanner extends RegionScanner {
+ private final KeyProvider keyProvider;
+ private KeyValue lastKeyValue;
+
+ IdxRegionScanner(Scan scan, IdxSearchContext idxSearchContext,
+ IntSet matchedExpression) throws IOException {
+ super(scan);
+ numberOfOngoingIndexedScans.incrementAndGet();
+ keyProvider = new KeyProvider(idxSearchContext, matchedExpression, scan);
+ }
+
+ @Override
+ public boolean next(List<KeyValue> outResults) throws IOException {
+ // Seek to the next key value
+ seekNext();
+ boolean result = super.next(outResults);
+
+ // if there are results we need to key track of the key to ensure that the
+ // nextInternal method doesn't seek backwards on it's next invocation
+ if (!outResults.isEmpty()) {
+ lastKeyValue = outResults.get(0);
+ }
+
+ return result;
+ }
+
+ protected void seekNext() throws IOException {
+ KeyValue keyValue;
+ do {
+ keyValue = keyProvider.next();
+
+ if (keyValue == null) {
+ // out of results keys, nothing more to process
+ super.getStoreHeap().close();
+ return;
+ } else if (lastKeyValue == null) {
+ // first key returned from the key provider
+ break;
+ } else {
+ // it's possible that the super nextInternal method progressed past the
+ // ketProvider's next key. We need to keep calling next on the keyProvider
+ // until the key returned is after the last key returned from the
+ // next(List<KeyValue>) method.
+
+ // determine which of the two keys is less than the other
+ // when the keyValue is greater than the lastKeyValue then we're good
+ int comparisonResult = comparator.compareRows(keyValue, lastKeyValue);
+ if (comparisonResult > 0) {
+ break;
+ }
+ }
+ } while (true);
+
+ // seek the store heap to the next key
+ // (this is what makes the scanner faster)
+ getStoreHeap().seek(keyValue);
+ }
+
+ @Override
+ public void close() {
+ numberOfOngoingIndexedScans.decrementAndGet();
+ keyProvider.close();
+ super.close();
+ }
+ }
+
+ class KeyProvider {
+ private final KeyValueHeap memstoreHeap;
+ private final IdxSearchContext indexSearchContext;
+ private final IntSet.IntSetIterator matchedExpressionIterator;
+
+ private KeyValue currentMemstoreKey = null;
+ private KeyValue currentExpressionKey = null;
+ private boolean exhausted = false;
+ private byte[] startRow;
+ private boolean isStartRowSatisfied;
+
+ KeyProvider(IdxSearchContext idxSearchContext,
+ IntSet matchedExpression, Scan scan) {
+ this.indexSearchContext = idxSearchContext;
+ this.matchedExpressionIterator = matchedExpression.iterator();
+
+ memstoreHeap = initMemstoreHeap(scan);
+
+ startRow = scan.getStartRow();
+ isStartRowSatisfied = startRow == null;
+ }
+
+ private KeyValueHeap initMemstoreHeap(Scan scan) {
+ List<KeyValueScanner> scanners = new ArrayList<KeyValueScanner>();
+ // todo: can we reduce the cost of scanning the memory stores by
+ // only using one entry from the family map
+
+ for (byte[] family : regionInfo.getTableDesc().getFamiliesKeys()) {
+ Store store = stores.get(family);
+ scanners.addAll(getMemstoreScanners(store, scan.getStartRow()));
+ break; // we only need one
+ }
+ return new KeyValueHeap(scanners.toArray(new KeyValueScanner[scanners.size()]), comparator);
+ }
+
+ /*
+ * @return List of scanners ordered properly.
+ */
+ private List<KeyValueScanner> getMemstoreScanners(Store store, byte[] startRow) {
+ List<KeyValueScanner> scanners = new ArrayList<KeyValueScanner>();
+ // this seems a bit pointless because the memstore only ever returns an
+ // array with only one element, but just incase...
+ KeyValueScanner[] memstorescanners = store.memstore.getScanners();
+ // to make sure we don't provide rows that the scan is not interested in
+ // we seekTo the scan's startRow
+ KeyValue seekTo = KeyValue.createFirstOnRow(startRow);
+ for (int i = memstorescanners.length - 1; i >= 0; i--) {
+ memstorescanners[i].seek(seekTo);
+ scanners.add(memstorescanners[i]);
+ }
+
+ return scanners;
+ }
+
+ public KeyValue next() throws IOException {
+ if (exhausted) return null;
+
+ KeyValue currentKey;
+ /*
+ If either the current memstore or expression row is null get the next.
+ Note: the row will be nulled when it's consumed.
+ */
+ if (currentMemstoreKey == null)
+ currentMemstoreKey = nextMemstoreRow();
+ if (currentExpressionKey == null)
+ currentExpressionKey = nextExpressionRow();
+
+ if (currentMemstoreKey == null && currentExpressionKey == null) {
+ exhausted = true;
+ // if both rows are null then the scanner is done
+ return null;
+ } else if (currentMemstoreKey == null) {
+ currentKey = currentExpressionKey;
+ currentExpressionKey = null;
+ } else if (currentExpressionKey == null) {
+ currentKey = currentMemstoreKey;
+ currentMemstoreKey = null;
+ } else {
+ // determine which of the two keys is smaller (before the other) so that
+ // the scan is processed in-order
+ int comparisonResult = comparator.compareRows(currentMemstoreKey, currentExpressionKey);
+
+ if (comparisonResult == 0) {
+ // if the two rows are equal then we'll use the memstore and clear the
+ // current expression row so that the next invocation progresses...
+ currentExpressionKey = null;
+ currentKey = currentMemstoreKey;
+ } else if (comparisonResult < 0) {
+ currentKey = currentMemstoreKey;
+ currentMemstoreKey = null;
+ } else { // if (comparisonResult > 0)
+ currentKey = currentExpressionKey;
+ currentExpressionKey = null;
+ }
+ }
+
+ return currentKey;
+ }
+
+ private KeyValue nextExpressionRow() {
+ KeyValue nextExpressionKey = null;
+ while (matchedExpressionIterator.hasNext()) {
+ int index = matchedExpressionIterator.next();
+ nextExpressionKey = indexSearchContext.lookupRow(index);
+
+ // if the scan has specified a startRow we need to keep looping
+ // over the keys returned from the index until it's satisfied
+ if (!isStartRowSatisfied) {
+ if (comparator.compareRows(nextExpressionKey, startRow) >= 0) {
+ isStartRowSatisfied = true;
+ break;
+ }
+ } else {
+ break;
+ }
+ }
+
+ return nextExpressionKey;
+ }
+
+ private KeyValue nextMemstoreRow() {
+ /*
+ This may appear a little expensive but the initial version is not concerned
+ with the performance of the memstore.
+ */
+ final KeyValue firstOnNextRow = this.memstoreHeap.next();
+ KeyValue nextKeyValue = this.memstoreHeap.peek();
+ while (firstOnNextRow != null && nextKeyValue != null &&
+ comparator.compareRows(firstOnNextRow, nextKeyValue) == 0) {
+ // progress to the next row
+ // todo: is there a faster way of doing this?
+ this.memstoreHeap.next();
+ nextKeyValue = this.memstoreHeap.peek();
+ }
+
+ return firstOnNextRow;
+ }
+
+ /**
+ * Close this key provider - delegate close and free memory.
+ */
+ public void close() {
+ this.indexSearchContext.close();
+ this.memstoreHeap.close();
+ }
+ }
+
+ @Override
+ public long heapSize() {
+ return FIXED_OVERHEAD + super.heapSize() +
+ indexManager.heapSize() + expressionEvaluator.heapSize();
+ }
+}
Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionIndexManager.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionIndexManager.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionIndexManager.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionIndexManager.java Tue Jan 5 17:26:49 2010
@@ -0,0 +1,290 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.hadoop.hbase.regionserver;
+
+import org.apache.commons.lang.time.StopWatch;
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.hbase.HColumnDescriptor;
+import org.apache.hadoop.hbase.KeyValue;
+import org.apache.hadoop.hbase.NotServingRegionException;
+import org.apache.hadoop.hbase.client.Scan;
+import org.apache.hadoop.hbase.client.idx.IdxColumnDescriptor;
+import org.apache.hadoop.hbase.client.idx.IdxIndexDescriptor;
+import org.apache.hadoop.hbase.io.HeapSize;
+import org.apache.hadoop.hbase.regionserver.idx.support.IdxClassSize;
+import org.apache.hadoop.hbase.regionserver.idx.support.arrays.ObjectArrayList;
+import org.apache.hadoop.hbase.util.Bytes;
+import org.apache.hadoop.hbase.util.ClassSize;
+import org.apache.hadoop.hbase.util.Pair;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+
+/**
+ * Manages the indexes for a single region.
+ */
+public class IdxRegionIndexManager implements HeapSize {
+ private static final Log LOG = LogFactory.getLog(IdxRegionIndexManager.class);
+
+ static final long FIXED_SIZE =
+ ClassSize.align(ClassSize.OBJECT + 4 * ClassSize.REFERENCE +
+ IdxClassSize.HASHMAP + IdxClassSize.OBJECT_ARRAY_LIST +
+ Bytes.SIZEOF_LONG + ClassSize.REENTRANT_LOCK);
+
+
+ /**
+ * The wrapping region.
+ */
+ private IdxRegion region;
+ /**
+ * The index map. Each pair holds the column and qualifier.
+ */
+ private volatile Map<Pair<byte[], byte[]>, IdxIndex> indexMap;
+ /**
+ * The keys ordered by their id. The IntSet in the {@link IdxIndex} have
+ * members corresponding to the indices of this array.
+ */
+ private volatile ObjectArrayList<KeyValue> keys;
+ /**
+ * The heap size.
+ */
+ private long heapSize;
+
+ private ReadWriteLock indexSwitchLock;
+
+ /**
+ * Create and initialize a new index manager.
+ *
+ * @param region the region to connect to
+ */
+ public IdxRegionIndexManager(IdxRegion region) {
+ this.region = region;
+ indexSwitchLock = new ReentrantReadWriteLock();
+ heapSize = FIXED_SIZE;
+ }
+
+ /**
+ * Creates and populates all indexes. Bruteforce scan fetching everything
+ * into memory, creating indexes out of that.
+ *
+ * @return total time in millis to rebuild the indexes
+ * @throws IOException in case scan throws
+ */
+ public long rebuildIndexes() throws IOException {
+ long startMillis = System.currentTimeMillis();
+ if (LOG.isInfoEnabled()) {
+ LOG.info(String.format("Initializing index manager for region: %s",
+ region.toString()));
+ }
+ heapSize = FIXED_SIZE;
+ Map<Pair<byte[], byte[]>, CompleteIndexBuilder>
+ builderTable = initIndexTable();
+ // if the region is closing/closed then a fillIndex method will throw a
+ // NotServingRegion exection when an attempt to obtain a scanner is made
+ // NOTE: when the region is being created isClosing() returns true
+ if (!(region.isClosing() || region.isClosed()) && !builderTable.isEmpty()) {
+ try {
+ ObjectArrayList<KeyValue> newKeys = fillIndex(builderTable);
+ Map<Pair<byte[], byte[]>, IdxIndex> newIndexMap =
+ finalizeIndex(builderTable, newKeys);
+ switchIndex(newKeys, newIndexMap);
+ } catch (NotServingRegionException e) {
+ // the not serving exception may also be thrown during the scan if
+ // the region was closed during the scan
+ LOG.warn("Aborted index initialization", e);
+ }
+ } else {
+ switchIndex(new ObjectArrayList<KeyValue>(),
+ Collections.<Pair<byte[], byte[]>, IdxIndex>emptyMap());
+ }
+ return System.currentTimeMillis() - startMillis;
+ }
+
+ private void switchIndex(ObjectArrayList<KeyValue> newKeys,
+ Map<Pair<byte[], byte[]>, IdxIndex> newIndexMap) {
+ indexSwitchLock.writeLock().lock();
+ try {
+ this.keys = newKeys;
+ this.indexMap = newIndexMap;
+ } finally {
+ indexSwitchLock.writeLock().unlock();
+ }
+ }
+
+ /**
+ * Initiate the index table. Read the column desciprtors, extract the index
+ * descriptors from them and instantiate index builders for those columns.
+ *
+ * @return the initiated map of builders keyed by column:qualifer pair
+ * @throws IOException thrown by {@link IdxColumnDescriptor#getIndexDescriptors(org.apache.hadoop.hbase.HColumnDescriptor)}
+ */
+ private Map<Pair<byte[], byte[]>,
+ CompleteIndexBuilder> initIndexTable() throws IOException {
+ Map<Pair<byte[], byte[]>, CompleteIndexBuilder> indexBuilders =
+ new HashMap<Pair<byte[], byte[]>, CompleteIndexBuilder>();
+ for (HColumnDescriptor columnDescriptor :
+ region.getRegionInfo().getTableDesc().getColumnFamilies()) {
+ Collection<IdxIndexDescriptor> indexDescriptors =
+ IdxColumnDescriptor.getIndexDescriptors(columnDescriptor).values();
+ for (IdxIndexDescriptor indexDescriptor : indexDescriptors) {
+ LOG.info(String.format("Adding index for region: '%s' index: %s",
+ region.getRegionNameAsString(), indexDescriptor.toString()));
+ indexBuilders.put(Pair.of(columnDescriptor.getName(),
+ indexDescriptor.getQualifierName()),
+ new CompleteIndexBuilder(columnDescriptor, indexDescriptor));
+ }
+ }
+ return indexBuilders;
+ }
+
+ /**
+ * Fills the index. Scans the region for latest rows and sends key values
+ * to the matching index builder
+ *
+ * @param builders the map of builders keyed by column:qualifer pair
+ * @return the keyset (a fresh set)
+ * @throws IOException may be thrown by the scan
+ */
+ private ObjectArrayList<KeyValue> fillIndex(Map<Pair<byte[], byte[]>,
+ CompleteIndexBuilder> builders) throws IOException {
+ ObjectArrayList<KeyValue> newKeys = this.keys == null ?
+ new ObjectArrayList<KeyValue>() :
+ new ObjectArrayList<KeyValue>(this.keys.size());
+
+ StopWatch stopWatch = new StopWatch();
+ stopWatch.start();
+
+ InternalScanner scanner = region.getScanner(new Scan());
+ boolean moreRows;
+ int id = 0;
+ do {
+ List<KeyValue> nextRow = new ArrayList<KeyValue>();
+ moreRows = scanner.next(nextRow);
+ if (nextRow.size() > 0) {
+ KeyValue
+ firstOnRow = KeyValue.createFirstOnRow(nextRow.get(0).getRow());
+ newKeys.add(firstOnRow);
+ // add keyvalue to the heapsize
+ heapSize += firstOnRow.heapSize();
+ for (KeyValue keyValue : nextRow) {
+ CompleteIndexBuilder idx = builders.get(Pair.of(keyValue.getFamily(),
+ keyValue.getQualifier()));
+ if (idx != null) {
+ idx.addKeyValue(keyValue, id);
+ }
+ }
+ id++;
+ }
+ } while (moreRows);
+
+ stopWatch.stop();
+ LOG.info("Filled indices for region: '" + region.getRegionNameAsString()
+ + "' with " + id + " entries in " + stopWatch.toString());
+ return newKeys;
+ }
+
+ /**
+ * Converts the map of builders into complete indexes, calling
+ * {@link CompleteIndexBuilder#finalizeIndex(int)} on each builder.
+ *
+ * @param builders the map of builders
+ * @param newKeys the set of keys for the new index to be finalized
+ * @return the new index map
+ */
+ private Map<Pair<byte[], byte[]>, IdxIndex>
+ finalizeIndex(Map<Pair<byte[], byte[]>,
+ CompleteIndexBuilder> builders, ObjectArrayList<KeyValue> newKeys) {
+ Map<Pair<byte[], byte[]>, IdxIndex>
+ newIndexes = new HashMap<Pair<byte[], byte[]>, IdxIndex>();
+ for (Map.Entry<Pair<byte[], byte[]>, CompleteIndexBuilder> indexEntry :
+ builders.entrySet()) {
+ IdxIndex index = indexEntry.getValue().finalizeIndex(newKeys.size());
+ newIndexes.put(indexEntry.getKey(), index);
+ // adjust the heapsize
+ heapSize += ClassSize.align(ClassSize.MAP_ENTRY +
+ ClassSize.align(ClassSize.OBJECT + 2 * ClassSize.ARRAY +
+ indexEntry.getKey().getFirst().length +
+ indexEntry.getKey().getSecond().length) + index.heapSize()
+ );
+ }
+ return newIndexes;
+ }
+
+ public IdxSearchContext newSearchContext() {
+ indexSwitchLock.readLock().lock();
+ try {
+ return new IdxSearchContext(keys, indexMap);
+ } finally {
+ indexSwitchLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public long heapSize() {
+ return heapSize;
+ }
+
+ /**
+ * Exposes the number of keys in the index manager.
+ *
+ * @return the number of keys.
+ */
+ public int getNumberOfKeys() {
+ indexSwitchLock.readLock().lock();
+ try {
+ return keys.size();
+ } finally {
+ indexSwitchLock.readLock().unlock();
+ }
+ }
+
+ /**
+ * A monitoring operation which returns the byte size of a given index.
+ *
+ * @param columnName in [family]:[qualifier] format
+ * @return the byte size of the index
+ */
+ public long getIndexHeapSize(String columnName) {
+ String[] familyAndQualifier = columnName.split(":");
+ if (familyAndQualifier != null && familyAndQualifier.length == 2) {
+ Pair fqPair = Pair.of(Bytes.toBytes(familyAndQualifier[0]),
+ Bytes.toBytes(familyAndQualifier[1]));
+ indexSwitchLock.readLock().lock();
+ IdxIndex idx = null;
+ try {
+ idx = indexMap.get(fqPair);
+ } finally {
+ indexSwitchLock.readLock().unlock();
+ }
+ if (idx != null) {
+ return idx.heapSize();
+ }
+ }
+ throw new IllegalArgumentException("No index for " + columnName);
+ }
+}
Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionMBean.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionMBean.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionMBean.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionMBean.java Tue Jan 5 17:26:49 2010
@@ -0,0 +1,99 @@
+/*
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.hadoop.hbase.regionserver;
+
+/**
+ * An MBean exposing various region ops and info.
+ */
+public interface IdxRegionMBean {
+
+ /**
+ * Checks whether the region being exposed by this MBean is still alive.
+ *
+ * @return whether the region being exposed by this MBean is still alive.
+ */
+ boolean isValid();
+
+ /**
+ * The number of keys in the index which is equivalent to the number of top
+ * level rows in this region.
+ *
+ * @return the number of keys in the index.
+ */
+ int getNumberOfIndexedKeys();
+
+ /**
+ * The total heap size, in bytes, used by the indexes and their overhead.
+ *
+ * @return the total index heap size in bytes.
+ */
+ long getIndexesTotalHeapSize();
+
+ /**
+ * Gets the total number of indexed scan since the last reset.
+ *
+ * @return the total number of indexed scans.
+ */
+ public long getTotalIndexedScans();
+
+ /**
+ * Resets the total number of indexed scans.
+ *
+ * @return the number of indexed scans just before the reset
+ */
+ public long resetTotalIndexedScans();
+
+ /**
+ * Gets the total number of non indexed scan since the last reset.
+ *
+ * @return the total number of indexed scans.
+ */
+ public long getTotalNonIndexedScans();
+
+ /**
+ * Resets the total number of non indexed scans.
+ *
+ * @return the number of indexed scans just before the reset
+ */
+ public long resetTotalNonIndexedScans();
+
+ /**
+ * Exposes the number of indexed scans currently ongoing in the system.
+ *
+ * @return the number of ongoing indexed scans
+ */
+ public long getNumberOfOngoingIndexedScans();
+
+ /**
+ * Gets the index build times buffer as a comma delimited string
+ * where each item is the milliseconds required to rebuild the indexes.
+ *
+ * @return a rolling buffer of index build times
+ */
+ public String getIndexBuildTimes();
+
+ /**
+ * Resets the index build times buffer.
+ *
+ * @return the previous build times buffer
+ */
+ public String resetIndexBuildTimes();
+
+}
Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionMBeanImpl.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionMBeanImpl.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionMBeanImpl.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxRegionMBeanImpl.java Tue Jan 5 17:26:49 2010
@@ -0,0 +1,353 @@
+/*
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.hadoop.hbase.regionserver;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.hbase.HColumnDescriptor;
+import org.apache.hadoop.hbase.HRegionInfo;
+import org.apache.hadoop.hbase.client.idx.IdxColumnDescriptor;
+import org.apache.hadoop.hbase.client.idx.IdxIndexDescriptor;
+import org.apache.hadoop.hbase.util.Bytes;
+
+import javax.management.AttributeNotFoundException;
+import javax.management.MBeanAttributeInfo;
+import javax.management.MBeanException;
+import javax.management.MBeanInfo;
+import javax.management.MalformedObjectNameException;
+import javax.management.NotCompliantMBeanException;
+import javax.management.ObjectName;
+import javax.management.ReflectionException;
+import javax.management.StandardMBean;
+import java.io.IOException;
+import java.lang.ref.WeakReference;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+
+/**
+ * A delegate MBean to get stats / poke an idx region.
+ */
+public class IdxRegionMBeanImpl extends StandardMBean
+ implements IdxRegionMBean {
+ static final Log LOG = LogFactory.getLog(IdxRegionMBeanImpl.class);
+
+ private static final HashMap<String, String> ATTRIBUTE_DESCRIPTIONS =
+ new HashMap<String, String>() {{
+ put("Valid", "Indicates whether the region being exposed by " +
+ "this MBean is still alive");
+ put("NumberOfIndexedKeys", "The number of keys in the index " +
+ "which is equivalent to the number of top-level rows in this region");
+ put("IndexesTotalHeapSize", "The total heap size, in bytes, used by " +
+ "the indexes and their overhead");
+ }};
+
+
+ /**
+ * Instantiate an new IdxRegion MBean. this is a convenience method which
+ * allows the caller to avoid catching the
+ * {@link javax.management.NotCompliantMBeanException}.
+ *
+ * @param idxRegion the region to wrap
+ * @return a new instance of IdxRegionMBeanImpl
+ */
+ static IdxRegionMBeanImpl newIdxRegionMBeanImpl(IdxRegion idxRegion) {
+ try {
+ return new IdxRegionMBeanImpl(idxRegion);
+ } catch (NotCompliantMBeanException e) {
+ throw new IllegalStateException("Could not instantiate mbean", e);
+ }
+ }
+
+ /**
+ * Generate object name from the hregion info.
+ *
+ * @param regionInfo the region info to create the object name from.
+ * @return an valid object name.
+ */
+ static ObjectName generateObjectName(HRegionInfo regionInfo) {
+ StringBuilder builder =
+ new StringBuilder(IdxRegionMBeanImpl.class.getPackage().getName());
+ builder.append(':');
+ builder.append("table=");
+ builder.append(regionInfo.getTableDesc().getNameAsString());
+ builder.append(',');
+
+ builder.append("id=");
+ builder.append(regionInfo.getRegionId());
+ builder.append(',');
+
+ if (regionInfo.getStartKey() != null &&
+ regionInfo.getStartKey().length > 0) {
+ builder.append("startKey=");
+ builder.append(Bytes.toString(regionInfo.getStartKey()));
+ builder.append(',');
+ }
+
+ if (regionInfo.getEndKey() != null &&
+ regionInfo.getEndKey().length > 0) {
+ builder.append("endKey=");
+ builder.append(Bytes.toString(regionInfo.getEndKey()));
+ builder.append(',');
+ }
+
+ builder.append("type=IdxRegion");
+ try {
+ return ObjectName.getInstance(builder.toString());
+ } catch (MalformedObjectNameException e) {
+ throw new IllegalStateException("Failed to create a legal object name",
+ e);
+ }
+ }
+
+ /**
+ * Using a weak reference to the idx region.
+ * This way a failure to clear this MBean from the mbean server won't prevent
+ * the idx region to be garbage collected.
+ */
+ private WeakReference<IdxRegion> idxRegionRef;
+
+ private IdxRegionMBeanImpl(IdxRegion idxRegion)
+ throws NotCompliantMBeanException {
+ super(IdxRegionMBean.class);
+ idxRegionRef = new WeakReference<IdxRegion>(idxRegion);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public int getNumberOfIndexedKeys() {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ return region.getNumberOfIndexedKeys();
+ } else {
+ return -1;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public long getIndexesTotalHeapSize() {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ return region.getIndexesTotalHeapSize();
+ } else {
+ return -1;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean isValid() {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ return !(region.isClosed() || region.isClosing());
+ } else {
+ return false;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public long getTotalIndexedScans() {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ return region.getTotalIndexedScans();
+ } else {
+ return -1L;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public long resetTotalIndexedScans() {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ return region.resetTotalIndexedScans();
+ } else {
+ return -1L;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public long getTotalNonIndexedScans() {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ return region.getTotalNonIndexedScans();
+ } else {
+ return -1L;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public long resetTotalNonIndexedScans() {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ return region.resetTotalNonIndexedScans();
+ } else {
+ return -1L;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public long getNumberOfOngoingIndexedScans() {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ return region.getNumberOfOngoingIndexedScans();
+ } else {
+ return -1L;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public String getIndexBuildTimes() {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ return toIndexBuildTimesString(region.getIndexBuildTimes());
+ } else {
+ return "";
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public String resetIndexBuildTimes() {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ return toIndexBuildTimesString(region.resetIndexBuildTimes());
+ } else {
+ return "";
+ }
+ }
+
+ private String toIndexBuildTimesString(long[] buildTimes) {
+ StringBuilder builder = new StringBuilder();
+ for (long indexBuildTime : buildTimes) {
+ if (indexBuildTime >= 0) {
+ builder.append(indexBuildTime);
+ builder.append(", ");
+ }
+ }
+ return builder.length() > 2 ? builder.substring(0, builder.length() - 2) :
+ "";
+ }
+
+/* StandardMBean hooks and overrides */
+
+ @Override
+ protected String getDescription(MBeanAttributeInfo info) {
+ String description = ATTRIBUTE_DESCRIPTIONS.get(info.getName());
+ return description == null ? super.getDescription(info) : description;
+ }
+
+ @Override
+ public Object getAttribute(String attribute)
+ throws AttributeNotFoundException, MBeanException, ReflectionException {
+ if (attribute.endsWith(".heapSize")) {
+ String columnName = attribute.substring(0, attribute.indexOf('.'));
+ return getIndexHeapSize(columnName);
+ }
+ return super.getAttribute(attribute);
+ }
+
+ @Override
+ protected void cacheMBeanInfo(MBeanInfo info) {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ Set<String> columnNames;
+ try {
+ columnNames = extractIndexedColumnNames(region.getRegionInfo());
+ } catch (IOException e) {
+ throw new IllegalStateException("Invalid region info for " + region);
+ }
+ final MBeanAttributeInfo[] existingInfos = info.getAttributes();
+ for (MBeanAttributeInfo attributeInfo : existingInfos) {
+ String name = attributeInfo.getName();
+ if (name.indexOf('.') >= 0) {
+ columnNames.remove(name.substring(0, name.indexOf('.')));
+ }
+ }
+ MBeanAttributeInfo[] attributeInfos = new
+ MBeanAttributeInfo[columnNames.size() + existingInfos.length];
+ System.arraycopy(existingInfos, 0, attributeInfos, 0,
+ existingInfos.length);
+ Iterator<String> columnNameIterator = columnNames.iterator();
+ for (int i = existingInfos.length; i < attributeInfos.length; i++) {
+ String name = columnNameIterator.next() + ".heapSize";
+ attributeInfos[i] = new MBeanAttributeInfo(name,
+ "long", "The amount of heap space occupied by this index", true,
+ false, false);
+ }
+ info = new MBeanInfo(info.getClassName(), info.getDescription(),
+ attributeInfos, info.getConstructors(), info.getOperations(),
+ info.getNotifications(), info.getDescriptor());
+ }
+ super.cacheMBeanInfo(info);
+ }
+
+ private static Set<String> extractIndexedColumnNames(HRegionInfo regionInfo)
+ throws IOException {
+ Set<String> idxColumns = new HashSet<String>();
+ for (HColumnDescriptor columnDescriptor :
+ regionInfo.getTableDesc().getColumnFamilies()) {
+ Collection<IdxIndexDescriptor> indexDescriptors =
+ IdxColumnDescriptor.getIndexDescriptors(columnDescriptor).values();
+ for (IdxIndexDescriptor indexDescriptor : indexDescriptors) {
+ idxColumns.add(columnDescriptor.getNameAsString() + ":" +
+ Bytes.toString(indexDescriptor.getQualifierName()));
+ }
+ }
+ return idxColumns;
+ }
+
+ private long getIndexHeapSize(String columnName) {
+ IdxRegion region = idxRegionRef.get();
+ if (region != null) {
+ return region.getIndexHeapSize(columnName);
+ } else {
+ return -1L;
+ }
+ }
+}
Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxSearchContext.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxSearchContext.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxSearchContext.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/IdxSearchContext.java Tue Jan 5 17:26:49 2010
@@ -0,0 +1,107 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.hadoop.hbase.regionserver;
+
+import org.apache.hadoop.hbase.KeyValue;
+import org.apache.hadoop.hbase.regionserver.idx.support.Callback;
+import org.apache.hadoop.hbase.regionserver.idx.support.arrays.ObjectArrayList;
+import org.apache.hadoop.hbase.regionserver.idx.support.sets.IntSet;
+import org.apache.hadoop.hbase.util.Pair;
+
+import java.util.Map;
+
+/**
+ * The search context holds the context for a specific search request.
+ * It takes a snapshot of the indexes at the time the search was requested.
+ * <p/>
+ * The search context is a transient object whose life spans only while the
+ * search (typically a region scan) is in progress.
+ */
+public class IdxSearchContext {
+
+ private ObjectArrayList<KeyValue> keys;
+ private Map<Pair<byte[], byte[]>, IdxIndex> indexMap;
+
+ /**
+ * Construct a new search context.
+ *
+ * @param keys the keys to use when searching.
+ * @param indexMap the matching index map
+ */
+ public IdxSearchContext(ObjectArrayList<KeyValue> keys,
+ Map<Pair<byte[], byte[]>, IdxIndex> indexMap) {
+ this.keys = keys;
+ this.indexMap = indexMap;
+ }
+
+ /**
+ * Looks up an index based on the column and the qualifier. May return null if
+ * no such index is found.
+ *
+ * @param column the column
+ * @param qualifier the column qualifier
+ * @return the index for the column/qualifer
+ */
+ public IdxIndex getIndex(byte[] column, byte[] qualifier) {
+ return indexMap.get(Pair.of(column, qualifier));
+ }
+
+ /**
+ * Process a set of rows, typically to convert a query to a scan. Rows are
+ * processed in sorted order.
+ *
+ * @param rowSet the row set to process
+ * @param callback the callback to use to process those rows
+ */
+ public void processRows(IntSet rowSet, Callback<KeyValue> callback) {
+ IntSet.IntSetIterator iterator = rowSet.iterator();
+ while (iterator.hasNext()) {
+ int i = iterator.next();
+ callback.call(keys.get(i));
+ }
+ }
+
+ /**
+ * Unmap a index key to a actual key.
+ *
+ * @param index the index offset
+ * @return the byte
+ */
+ public KeyValue lookupRow(int index) {
+ return keys.get(index);
+ }
+
+ /**
+ * The number of rows indexed in this search context.
+ *
+ * @return the number of indexed rows.
+ */
+ public int rowCount() {
+ return keys.size();
+ }
+
+ /**
+ * close this search context
+ */
+ public void close(){
+ keys = null;
+ indexMap = null;
+ }
+}
Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Bits.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Bits.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Bits.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Bits.java Tue Jan 5 17:26:49 2010
@@ -0,0 +1,79 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.hadoop.hbase.regionserver.idx.support;
+
+/**
+ * Bits utility class.
+ * TODO consider delete this class since the Java SE implemetations are as good.
+ */
+public final class Bits {
+
+ /**
+ * De bruijn 64 number to implement set bit index extraction.
+ */
+ private static final long DEBRUIJN64 = 0x022fdd63cc95386dl;
+
+ private static final int[] DEBRUIJN64_TABLE = new int[]{
+ 0, 1, 2, 53, 3, 7, 54, 27,
+ 4, 38, 41, 8, 34, 55, 48, 28,
+ 62, 5, 39, 46, 44, 42, 22, 9,
+ 24, 35, 59, 56, 49, 18, 29, 11,
+ 63, 52, 6, 26, 37, 40, 33, 47,
+ 61, 45, 43, 21, 23, 58, 17, 10,
+ 51, 25, 36, 32, 60, 20, 57, 16,
+ 50, 31, 19, 15, 30, 14, 13, 12,
+ };
+
+ private static final int DEBRUIJN64_SHIFT = 58;
+
+ private Bits() {
+ //utility class private constructor
+ }
+
+
+ /**
+ * Finds the index of the lowest set bit.
+ *
+ * @param word the word to check. Should not be zero.
+ * @return the index of the lowest set bit.
+ */
+ public static int lowestSetBitIndex(long word) {
+ assert word != 0;
+ word &= -word;
+ return DEBRUIJN64_TABLE[(int) ((word * DEBRUIJN64) >>> DEBRUIJN64_SHIFT)];
+ }
+
+ /**
+ * Finds the index of the highest set bit.
+ *
+ * @param word the word to check. Should not be zero.
+ * @return the index of the highest set bit.
+ */
+ public static int highestSetBitIndex(long word) {
+ word |= word >> 1;
+ word |= word >> 2;
+ word |= word >> 4;
+ word |= word >> 8;
+ word |= word >> 16;
+ word |= word >> 32;
+ word = word + 1 >>> 1;
+ return DEBRUIJN64_TABLE[(int) ((word * DEBRUIJN64) >>> DEBRUIJN64_SHIFT)];
+ }
+}
Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Callback.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Callback.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Callback.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Callback.java Tue Jan 5 17:26:49 2010
@@ -0,0 +1,35 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.hadoop.hbase.regionserver.idx.support;
+
+/**
+ * An interface for callback with a given argument type.
+ *
+ * @param <T> the argument type
+ */
+public interface Callback<T> {
+
+ /**
+ * Call this callback with the given argument
+ *
+ * @param arg the argument to use
+ */
+ void call(T arg);
+}
Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/IdxClassSize.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/IdxClassSize.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/IdxClassSize.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/IdxClassSize.java Tue Jan 5 17:26:49 2010
@@ -0,0 +1,44 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.hadoop.hbase.regionserver.idx.support;
+
+import org.apache.hadoop.hbase.util.Bytes;
+import org.apache.hadoop.hbase.util.ClassSize;
+
+/**
+ * Holds class sizes used by Idx heap size calcs.
+ * TODO merge with ClassSize.
+ */
+public class IdxClassSize extends ClassSize {
+
+ /**
+ * Hash map fixed overhead.
+ */
+ public static final long HASHMAP = align(OBJECT + 3 * Bytes.SIZEOF_INT +
+ Bytes.SIZEOF_FLOAT + ARRAY + 4 * REFERENCE);
+
+ /**
+ * Object array list fixed overhead.
+ */
+ public static final long OBJECT_ARRAY_LIST = align(OBJECT + Bytes.SIZEOF_INT +
+ ARRAY + REFERENCE);
+
+
+}
Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BigDecimalArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BigDecimalArrayList.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BigDecimalArrayList.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BigDecimalArrayList.java Tue Jan 5 17:26:49 2010
@@ -0,0 +1,370 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.hadoop.hbase.regionserver.idx.support.arrays;
+
+
+import org.apache.hadoop.hbase.util.Bytes;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import org.apache.commons.lang.ArrayUtils;
+import java.math.BigDecimal;
+import org.apache.hadoop.hbase.util.ClassSize;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class BigDecimalArrayList implements List<BigDecimal> {
+
+
+ //DO NOT EDIT THIS FILE, EDIT THE FMPP TEMPLATE INSTEAD.
+ //To generate source execute
+ // **/src/contib/indexed# ant -f build-fmpp.xml -lib lib/fmpp-0.19.14
+
+ /**
+ * Default initial size of the array backing this list.
+ */
+ private static final int DEFAULT_SIZE = 1;
+
+ /**
+ * The scaling factor we use to resize the backing buffer when the list needs to grow.
+ */
+ private static final float SCALE_FACTOR = 1.5f;
+
+ /**
+ * The array backing this list.
+ */
+ private BigDecimal[] values;
+
+ /**
+ * The number of values present in the list.
+ */
+ private int size;
+
+
+ /**
+ * Constructor that initialises with the default size.
+ */
+ public BigDecimalArrayList() {
+ this(DEFAULT_SIZE);
+ }
+
+ /**
+ * Constructor which initialises with the specified initial capacity.
+ *
+ * @param initialCapacity the initial capacity of the backing array
+ */
+ public BigDecimalArrayList(int initialCapacity) {
+ values = new BigDecimal[initialCapacity];
+ }
+
+ /**
+ * Constructor which initialises the content from the supplied array list.
+ *
+ * @param initial the initial contents
+ */
+ public BigDecimalArrayList(BigDecimalArrayList initial) {
+ // Initialise the internal storage to the appropriate size
+ this(initial.size);
+
+ // Copy over the references/values
+ System.arraycopy(initial.values, 0, this.values, 0, initial.size);
+ this.size = initial.size;
+ }
+
+ /**
+ * Adds the element to the end of the list.
+ *
+ * @param element the new element
+ */
+ public void add(BigDecimal element) {
+ ensureCapacity(size + 1);
+ values[size] = element;
+ size++;
+ }
+
+ @Override
+ public void add(byte[] bytes) {
+ add(fromBytes(bytes));
+ }
+
+ @Override
+ public int compare(BigDecimal needle, int compareToIndex) {
+ BigDecimal compareTo = values[compareToIndex];
+ return needle.compareTo(compareTo);
+ }
+
+ /**
+ * Grows the backing array to the requested size.
+ *
+ * @param requested the new capacity.
+ */
+ private void ensureCapacity(int requested) {
+ // If we need to resize
+ if (requested > values.length) {
+ // Calculate the new size, growing slowly at the start to avoid overallocation too early.
+ int newSize = Math.max(requested, (int) (values.length * SCALE_FACTOR + 1));
+
+ // Create the new array
+ BigDecimal[] newValues = new BigDecimal[newSize];
+
+ // Populate the new backing array
+ System.arraycopy(values, 0, newValues, 0, size);
+ values = newValues;
+ }
+ }
+
+ /**
+ * Retrieves the element at the requested index.
+ *
+ * @param index the element index you wish to retrieve
+ * @return the value at that index
+ */
+ public BigDecimal get(int index) {
+ if (index >= size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+
+ return values[index];
+ }
+
+ /**
+ * Searches the list for the nominated value.
+ *
+ * @param searchFor the value you are looking for
+ * @return the first index the value was found at or -1 if not found
+ */
+ public int indexOf(BigDecimal searchFor) {
+ // Check each of the values. Don't bother with get() since we don't need its protection.
+ for (int i = 0; i < size; i++) {
+ if (values[i].equals(searchFor)) {
+ return i;
+ }
+ }
+
+ // Didn't find it.
+ return -1;
+ }
+
+ /**
+ * Simple iterator that runs over the values in the list.
+ */
+ private static final class InternalIterator
+ implements Iterator<BigDecimal> {
+
+ private BigDecimal[] values;
+ private int size;
+ private int current = 0;
+
+ private InternalIterator(BigDecimal[] values, int size) {
+ this.values = values;
+ this.size = size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean hasNext() {
+ return current < size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public BigDecimal next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ return values[current++];
+ }
+
+ /**
+ * Not supported.
+ */
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException("remove() is not supported");
+ }
+ }
+
+ /**
+ * Returns an iterator over the underlying content. Note that this is completely unsynchronised and the contents can change under you.
+ */
+ @Override
+ public Iterator<BigDecimal> iterator() {
+ return new InternalIterator(values, size);
+ }
+
+ /**
+ * Checks if the list is empty.
+ *
+ * @return true if the list is empty
+ */
+ @Override
+ public boolean isEmpty() {
+ return size == 0;
+ }
+
+ /**
+ * Sets the specified index to the nominated value.
+ *
+ * @param index the list index
+ * @param newValue the value
+ */
+ public void set(int index, BigDecimal newValue) {
+ if (index >= size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+
+ values[index] = newValue;
+
+ }
+
+ @Override
+ public void set(int index, byte[] newValue) {
+ set(index, fromBytes(newValue));
+ }
+
+ /**
+ * Removes the specified index from the list.
+ *
+ * @param index the index to remove
+ * @return the original value
+ */
+ public BigDecimal remove(int index) {
+ if (index >= size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+
+ BigDecimal original = values[index];
+ System.arraycopy(values, index + 1, values, index, size - index - 1);
+ size--;
+ return original;
+ }
+
+
+ /**
+ * Inserts at the specified index to the list.
+ *
+ * @param index the index to insert
+ * @param newValue the value to insert
+ */
+ public void insert(int index, BigDecimal newValue) {
+ if (index > size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+
+ ensureCapacity(size + 1);
+ if (index != size) {
+ System.arraycopy(values, index, values, index + 1, size - index);
+ }
+ values[index] = newValue;
+ size++;
+ }
+
+ @Override
+ public void insert(int index, byte[] newValue) {
+ insert(index, fromBytes(newValue));
+ }
+
+ /**
+ * Removes the last item in the list.
+ *
+ * @return the original value
+ */
+ public BigDecimal removeLast() {
+ if (size < 1) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+ }
+
+ BigDecimal result = values[size - 1];
+ size--;
+
+
+ return result;
+ }
+
+ /**
+ * Returns the current number of elements in this list.
+ *
+ * @return the number of elements.
+ */
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public BigDecimal fromBytes(byte[] bytes) {
+ return Bytes.toBigDecimal(bytes);
+ }
+
+
+ @Override
+ public long heapSize() {
+ // take a rough estimate that a big decimal's overhead is 50 bytes.
+ // TODO fix
+ return FIXED_OVERHEAD + Bytes.SIZEOF_LONG +
+ (ClassSize.REFERENCE + 50) * values.length;
+ }
+
+
+ /**
+ * Return a nice view of the list.
+ * {@inheritDoc}
+ */
+ @Override
+ public String toString() {
+ return Arrays.toString(Arrays.copyOf(values, size));
+ }
+
+ /**
+ * Checks the contents of the collection for equality.
+ * <p/>
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean equals(Object compareTo) {
+ if (this == compareTo) {
+ return true;
+ }
+ if (!(compareTo instanceof BigDecimalArrayList)) {
+ return false;
+ }
+
+ BigDecimalArrayList that = (BigDecimalArrayList) compareTo;
+
+ return this.size == that.size &&
+ ArrayUtils.isEquals(this.values, that.values);
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public int hashCode() {
+ return 31 * Arrays.hashCode(values) + size;
+ }
+}
Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BinarySearch.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BinarySearch.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BinarySearch.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BinarySearch.java Tue Jan 5 17:26:49 2010
@@ -0,0 +1,133 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.hadoop.hbase.regionserver.idx.support.arrays;
+
+/**
+ * A generic implementation of the binary search algorithm that can run on
+ * any type of object that conforms to the {@link Searchable} or any of the
+ * directly supported primitive types or buffers.
+ */
+public final class BinarySearch {
+
+ /**
+ * Suppress construction for utility classes.
+ */
+ private BinarySearch() {
+ }
+
+
+ /**
+ * Conducts a binary search for the requested value in the supplied target
+ * object.
+ * <p/>
+ * If not found, returns -(insertionPoint + 1)
+ * This is always a negative number. To convert this negative number into
+ * the real the insertion point, call convertToInsertionIndex(int)
+ *
+ * @param haystack the object you wish to search
+ * @param haystackLength the number of objects in the haystack
+ * @param needle the value you are looking for
+ * @param <H> the class that we are searching
+ * @param <N> the class of needle we are looking for
+ * @return the position the key was found in
+ */
+ public static <H extends Searchable<N>, N> int search(H haystack,
+ int haystackLength, N needle) {
+ // Check argument validity
+ if (haystack == null) {
+ throw new IllegalArgumentException("Argument 'Check' cannot be null");
+ }
+ if (needle == null) {
+ throw new IllegalArgumentException("Argument 'needle' cannot be null");
+ }
+
+ // Initialise boundaries
+ int high = haystackLength;
+ int low = -1;
+
+ // Search until the high and low markers are next to each other
+ while (high - low > 1) {
+ // Calculate the mid-point to check
+ int probe = (low + high) >>> 1;
+
+ // Move the markers. Note that the comparison returns < 0 if the needle is
+ // less than the comparison index so this test is opposite to the standard
+ int comparison = haystack.compare(needle, probe);
+ if (comparison > 0) {
+ low = probe;
+ } else {
+ high = probe;
+ }
+ }
+
+ // If the high marker hasn't moved (still off the end of the target), or
+ // the value we landed on isnt what we were looking for, we didn't find it
+ if (high == haystackLength || haystack.compare(needle, high) != 0) {
+ // Return the encoded insertion position.
+ return -(high + 1);
+ } else {
+ // Return the match position
+ return high;
+ }
+ }
+
+ /**
+ * Conducts a binary search for the requested value in the supplied target
+ * object.
+ * <p/>
+ * If not found, returns -(insertionPoint + 1)
+ * This is always a negative number. To convert this negative number into the
+ * real the insertion point, call convertToInsertionIndex(int)
+ *
+ * @param haystack the object you wish to search
+ * @param haystackLength the number of objects in the haystack
+ * @param needle the value you are looking for
+ * @param <H> the class that we are searching
+ * @param <N> the class of needle we are looking for
+ * @return the position the key was found in
+ */
+ public static <H extends Searchable<N>, N> int search(H haystack,
+ int haystackLength, byte[] needle) {
+ return search(haystack, haystackLength, haystack.fromBytes(needle));
+ }
+
+ /**
+ * This interface enforces the required methods to search an arbitrary
+ * object with a binary search algorithm.
+ */
+ public interface Searchable<N> {
+ /**
+ * Create the needle for a byte array.
+ *
+ * @param bytes the byte array to use
+ * @return the needle instance
+ */
+ N fromBytes(byte[] bytes);
+
+ /**
+ * Compares the two requested elements.
+ *
+ * @param needle the value we are looking for
+ * @param compareToIndex the index of the element to compare the needle to
+ * @return -ve, 0, +ve if the needle is <, = or > than the element to check
+ */
+ int compare(N needle, int compareToIndex);
+ }
+}
Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayArrayList.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayArrayList.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayArrayList.java Tue Jan 5 17:26:49 2010
@@ -0,0 +1,382 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.hadoop.hbase.regionserver.idx.support.arrays;
+
+
+import org.apache.hadoop.hbase.util.Bytes;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import org.apache.commons.lang.ArrayUtils;
+import org.apache.hadoop.hbase.util.ClassSize;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class ByteArrayArrayList implements List<byte[]> {
+
+
+ //DO NOT EDIT THIS FILE, EDIT THE FMPP TEMPLATE INSTEAD.
+ //To generate source execute
+ // **/src/contib/indexed# ant -f build-fmpp.xml -lib lib/fmpp-0.19.14
+
+ /**
+ * Default initial size of the array backing this list.
+ */
+ private static final int DEFAULT_SIZE = 1;
+
+ /**
+ * The scaling factor we use to resize the backing buffer when the list needs to grow.
+ */
+ private static final float SCALE_FACTOR = 1.5f;
+
+ /**
+ * The array backing this list.
+ */
+ private byte[][] values;
+
+ /**
+ * The number of values present in the list.
+ */
+ private int size;
+
+ /**
+ * The accumulated heap size of elements stored in this list.
+ */
+ private long totalElementsHeapSize;
+
+ /**
+ * Constructor that initialises with the default size.
+ */
+ public ByteArrayArrayList() {
+ this(DEFAULT_SIZE);
+ }
+
+ /**
+ * Constructor which initialises with the specified initial capacity.
+ *
+ * @param initialCapacity the initial capacity of the backing array
+ */
+ public ByteArrayArrayList(int initialCapacity) {
+ values = new byte[initialCapacity][];
+ }
+
+ /**
+ * Constructor which initialises the content from the supplied array list.
+ *
+ * @param initial the initial contents
+ */
+ public ByteArrayArrayList(ByteArrayArrayList initial) {
+ // Initialise the internal storage to the appropriate size
+ this(initial.size);
+
+ // Copy over the references/values
+ System.arraycopy(initial.values, 0, this.values, 0, initial.size);
+ this.size = initial.size;
+ }
+
+ /**
+ * Adds the element to the end of the list.
+ *
+ * @param element the new element
+ */
+ public void add(byte[] element) {
+ ensureCapacity(size + 1);
+ values[size] = element;
+ size++;
+ totalElementsHeapSize += ClassSize.ARRAY +
+ (element != null ? element.length * Bytes.SIZEOF_BYTE: 0);
+ }
+
+
+ @Override
+ public int compare(byte[] needle, int compareToIndex) {
+ byte[] compareTo = values[compareToIndex];
+ int length = Math.min(needle.length, compareTo.length);
+ for (int i = 0; i < length; i++) {
+ if (needle[i] != compareTo[i]) {
+ if (needle[i] > compareTo[i]) {
+ return 1;
+ } else if (needle[i] < compareTo[i]) {
+ return -1;
+ }
+ }
+ }
+
+ return needle.length - compareTo.length;
+ }
+
+ /**
+ * Grows the backing array to the requested size.
+ *
+ * @param requested the new capacity.
+ */
+ private void ensureCapacity(int requested) {
+ // If we need to resize
+ if (requested > values.length) {
+ // Calculate the new size, growing slowly at the start to avoid overallocation too early.
+ int newSize = Math.max(requested, (int) (values.length * SCALE_FACTOR + 1));
+
+ byte[][] newValues = new byte[newSize][];
+
+ // Populate the new backing array
+ System.arraycopy(values, 0, newValues, 0, size);
+ values = newValues;
+ }
+ }
+
+ /**
+ * Retrieves the element at the requested index.
+ *
+ * @param index the element index you wish to retrieve
+ * @return the value at that index
+ */
+ public byte[] get(int index) {
+ if (index >= size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+
+ return values[index];
+ }
+
+ /**
+ * Searches the list for the nominated value.
+ *
+ * @param searchFor the value you are looking for
+ * @return the first index the value was found at or -1 if not found
+ */
+ public int indexOf(byte[] searchFor) {
+ // Check each of the values. Don't bother with get() since we don't need its protection.
+ for (int i = 0; i < size; i++) {
+ if (Arrays.equals(values[i], searchFor)) {
+ return i;
+ }
+ }
+
+ // Didn't find it.
+ return -1;
+ }
+
+ /**
+ * Simple iterator that runs over the values in the list.
+ */
+ private static final class InternalIterator
+ implements Iterator<byte[]> {
+
+ private byte[][] values;
+ private int size;
+ private int current = 0;
+
+ private InternalIterator(byte[][] values, int size) {
+ this.values = values;
+ this.size = size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean hasNext() {
+ return current < size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public byte[] next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ return values[current++];
+ }
+
+ /**
+ * Not supported.
+ */
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException("remove() is not supported");
+ }
+ }
+
+ /**
+ * Returns an iterator over the underlying content. Note that this is completely unsynchronised and the contents can change under you.
+ */
+ @Override
+ public Iterator<byte[]> iterator() {
+ return new InternalIterator(values, size);
+ }
+
+ /**
+ * Checks if the list is empty.
+ *
+ * @return true if the list is empty
+ */
+ @Override
+ public boolean isEmpty() {
+ return size == 0;
+ }
+
+ /**
+ * Sets the specified index to the nominated value.
+ *
+ * @param index the list index
+ * @param newValue the value
+ */
+ public void set(int index, byte[] newValue) {
+ if (index >= size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+ totalElementsHeapSize -= ClassSize.ARRAY +
+ (values[index] != null ? values[index].length * Bytes.SIZEOF_BYTE: 0);
+
+ values[index] = newValue;
+
+ totalElementsHeapSize += ClassSize.ARRAY +
+ (newValue != null ? newValue.length * Bytes.SIZEOF_BYTE: 0);
+ }
+
+
+ /**
+ * Removes the specified index from the list.
+ *
+ * @param index the index to remove
+ * @return the original value
+ */
+ public byte[] remove(int index) {
+ if (index >= size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+
+ byte[] original = values[index];
+ System.arraycopy(values, index + 1, values, index, size - index - 1);
+ size--;
+ totalElementsHeapSize -= ClassSize.ARRAY +
+ (original != null ? original.length * Bytes.SIZEOF_BYTE: 0);
+ return original;
+ }
+
+
+ /**
+ * Inserts at the specified index to the list.
+ *
+ * @param index the index to insert
+ * @param newValue the value to insert
+ */
+ public void insert(int index, byte[] newValue) {
+ if (index > size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+
+ ensureCapacity(size + 1);
+ if (index != size) {
+ System.arraycopy(values, index, values, index + 1, size - index);
+ }
+ values[index] = newValue;
+ size++;
+ totalElementsHeapSize += ClassSize.ARRAY +
+ (newValue != null ? newValue.length * Bytes.SIZEOF_BYTE: 0);
+ }
+
+
+ /**
+ * Removes the last item in the list.
+ *
+ * @return the original value
+ */
+ public byte[] removeLast() {
+ if (size < 1) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+ }
+
+ byte[] result = values[size - 1];
+ size--;
+ values[size] = null;
+ totalElementsHeapSize -= ClassSize.ARRAY +
+ (result != null ? result.length * Bytes.SIZEOF_BYTE: 0);
+
+
+ return result;
+ }
+
+ /**
+ * Returns the current number of elements in this list.
+ *
+ * @return the number of elements.
+ */
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public byte[] fromBytes(byte[] bytes) {
+ return bytes;
+ }
+
+
+ @Override
+ public long heapSize() {
+ return FIXED_OVERHEAD + Bytes.SIZEOF_LONG +
+ ClassSize.REFERENCE * values.length + totalElementsHeapSize;
+ }
+
+
+ /**
+ * Return a nice view of the list.
+ * {@inheritDoc}
+ */
+ @Override
+ public String toString() {
+ return Arrays.toString(Arrays.copyOf(values, size));
+ }
+
+ /**
+ * Checks the contents of the collection for equality.
+ * <p/>
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean equals(Object compareTo) {
+ if (this == compareTo) {
+ return true;
+ }
+ if (!(compareTo instanceof ByteArrayArrayList)) {
+ return false;
+ }
+
+ ByteArrayArrayList that = (ByteArrayArrayList) compareTo;
+
+ return this.size == that.size &&
+ ArrayUtils.isEquals(this.values, that.values);
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public int hashCode() {
+ return 31 * Arrays.hashCode(values) + size;
+ }
+}