You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by ap...@apache.org on 2010/01/09 22:10:05 UTC
svn commit: r897547 [4/10] - in
/hadoop/hbase/branches/0.20_on_hadoop-0.18.3: ./ bin/ conf/ lib/
src/contrib/ src/contrib/ec2/ src/contrib/ec2/bin/
src/contrib/ec2/bin/image/ src/contrib/indexed/ src/contrib/indexed/lib/
src/contrib/indexed/lib/fmpp-0....
Added: hadoop/hbase/branches/0.20_on_hadoop-0.18.3/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_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Bits.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Bits.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Bits.java Sat Jan 9 21:09:59 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_on_hadoop-0.18.3/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_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Callback.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Callback.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/Callback.java Sat Jan 9 21:09:59 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_on_hadoop-0.18.3/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_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/IdxClassSize.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/IdxClassSize.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/IdxClassSize.java Sat Jan 9 21:09:59 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_on_hadoop-0.18.3/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_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BigDecimalArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BigDecimalArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BigDecimalArrayList.java Sat Jan 9 21:09:59 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_on_hadoop-0.18.3/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_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BinarySearch.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BinarySearch.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/BinarySearch.java Sat Jan 9 21:09:59 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_on_hadoop-0.18.3/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_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayArrayList.java Sat Jan 9 21:09:59 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;
+ }
+}
Added: hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayList.java Sat Jan 9 21:09:59 2010
@@ -0,0 +1,372 @@
+/**
+ * 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;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class ByteArrayList 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;
+
+
+ /**
+ * Constructor that initialises with the default size.
+ */
+ public ByteArrayList() {
+ this(DEFAULT_SIZE);
+ }
+
+ /**
+ * Constructor which initialises with the specified initial capacity.
+ *
+ * @param initialCapacity the initial capacity of the backing array
+ */
+ public ByteArrayList(int initialCapacity) {
+ values = new byte[initialCapacity];
+ }
+
+ /**
+ * Constructor which initialises the content from the supplied array list.
+ *
+ * @param initial the initial contents
+ */
+ public ByteArrayList(ByteArrayList 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++;
+ }
+
+ @Override
+ public void add(byte[] bytes) {
+ add(fromBytes(bytes));
+ }
+
+ @Override
+ public int compare(Byte needle, int compareToIndex) {
+ byte compareTo = values[compareToIndex];
+ if (needle > compareTo) {
+ return 1;
+ } else if (needle < compareTo) {
+ return -1;
+ } else {
+ return 0;
+ }
+ }
+
+ /**
+ * 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
+ 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 (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");
+ }
+
+ 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 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--;
+ 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++;
+ }
+
+ @Override
+ public void insert(int index, byte[] newValue) {
+ insert(index, fromBytes(newValue));
+ }
+
+ /**
+ * 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--;
+
+
+ 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) {
+ assert bytes.length == 1;
+ return bytes[0];
+ }
+
+
+ @Override
+ public long heapSize() {
+ return FIXED_OVERHEAD + Bytes.SIZEOF_BYTE * 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 ByteArrayList)) {
+ return false;
+ }
+
+ ByteArrayList that = (ByteArrayList) 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_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayArrayList.java Sat Jan 9 21:09:59 2010
@@ -0,0 +1,394 @@
+/**
+ * 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 CharArrayArrayList implements List<char[]> {
+
+
+ //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 char[][] 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 CharArrayArrayList() {
+ this(DEFAULT_SIZE);
+ }
+
+ /**
+ * Constructor which initialises with the specified initial capacity.
+ *
+ * @param initialCapacity the initial capacity of the backing array
+ */
+ public CharArrayArrayList(int initialCapacity) {
+ values = new char[initialCapacity][];
+ }
+
+ /**
+ * Constructor which initialises the content from the supplied array list.
+ *
+ * @param initial the initial contents
+ */
+ public CharArrayArrayList(CharArrayArrayList 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(char[] element) {
+ ensureCapacity(size + 1);
+ values[size] = element;
+ size++;
+ totalElementsHeapSize += ClassSize.ARRAY +
+ (element != null ? element.length * Bytes.SIZEOF_CHAR: 0);
+ }
+
+ @Override
+ public void add(byte[] bytes) {
+ add(fromBytes(bytes));
+ }
+
+ @Override
+ public int compare(char[] needle, int compareToIndex) {
+ char[] 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));
+
+ char[][] newValues = new char[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 char[] 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(char[] 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<char[]> {
+
+ private char[][] values;
+ private int size;
+ private int current = 0;
+
+ private InternalIterator(char[][] values, int size) {
+ this.values = values;
+ this.size = size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean hasNext() {
+ return current < size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public char[] 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<char[]> 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, char[] 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_CHAR: 0);
+
+ values[index] = newValue;
+
+ totalElementsHeapSize += ClassSize.ARRAY +
+ (newValue != null ? newValue.length * Bytes.SIZEOF_CHAR: 0);
+ }
+
+ @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 char[] remove(int index) {
+ if (index >= size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+
+ char[] original = values[index];
+ System.arraycopy(values, index + 1, values, index, size - index - 1);
+ size--;
+ totalElementsHeapSize -= ClassSize.ARRAY +
+ (original != null ? original.length * Bytes.SIZEOF_CHAR: 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, char[] 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_CHAR: 0);
+ }
+
+ @Override
+ public void insert(int index, byte[] newValue) {
+ insert(index, fromBytes(newValue));
+ }
+
+ /**
+ * Removes the last item in the list.
+ *
+ * @return the original value
+ */
+ public char[] removeLast() {
+ if (size < 1) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+ }
+
+ char[] result = values[size - 1];
+ size--;
+ values[size] = null;
+ totalElementsHeapSize -= ClassSize.ARRAY +
+ (result != null ? result.length * Bytes.SIZEOF_CHAR: 0);
+
+
+ return result;
+ }
+
+ /**
+ * Returns the current number of elements in this list.
+ *
+ * @return the number of elements.
+ */
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public char[] fromBytes(byte[] bytes) {
+ return Bytes.toChars(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 CharArrayArrayList)) {
+ return false;
+ }
+
+ CharArrayArrayList that = (CharArrayArrayList) 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_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayList.java Sat Jan 9 21:09:59 2010
@@ -0,0 +1,371 @@
+/**
+ * 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;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class CharArrayList implements List<Character> {
+
+
+ //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 char[] values;
+
+ /**
+ * The number of values present in the list.
+ */
+ private int size;
+
+
+ /**
+ * Constructor that initialises with the default size.
+ */
+ public CharArrayList() {
+ this(DEFAULT_SIZE);
+ }
+
+ /**
+ * Constructor which initialises with the specified initial capacity.
+ *
+ * @param initialCapacity the initial capacity of the backing array
+ */
+ public CharArrayList(int initialCapacity) {
+ values = new char[initialCapacity];
+ }
+
+ /**
+ * Constructor which initialises the content from the supplied array list.
+ *
+ * @param initial the initial contents
+ */
+ public CharArrayList(CharArrayList 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(char element) {
+ ensureCapacity(size + 1);
+ values[size] = element;
+ size++;
+ }
+
+ @Override
+ public void add(byte[] bytes) {
+ add(fromBytes(bytes));
+ }
+
+ @Override
+ public int compare(Character needle, int compareToIndex) {
+ char compareTo = values[compareToIndex];
+ if (needle > compareTo) {
+ return 1;
+ } else if (needle < compareTo) {
+ return -1;
+ } else {
+ return 0;
+ }
+ }
+
+ /**
+ * 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
+ char[] newValues = new char[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 char 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(char 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] == 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<Character> {
+
+ private char[] values;
+ private int size;
+ private int current = 0;
+
+ private InternalIterator(char[] values, int size) {
+ this.values = values;
+ this.size = size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean hasNext() {
+ return current < size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public Character 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<Character> 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, char 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 char remove(int index) {
+ if (index >= size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+
+ char 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, char 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 char removeLast() {
+ if (size < 1) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+ }
+
+ char 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 Character fromBytes(byte[] bytes) {
+ return Bytes.toChar(bytes);
+ }
+
+
+ @Override
+ public long heapSize() {
+ return FIXED_OVERHEAD + Bytes.SIZEOF_CHAR * 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 CharArrayList)) {
+ return false;
+ }
+
+ CharArrayList that = (CharArrayList) 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_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/DoubleArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/DoubleArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/DoubleArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/DoubleArrayList.java Sat Jan 9 21:09:59 2010
@@ -0,0 +1,365 @@
+/**
+ * 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;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class DoubleArrayList implements List<Double> {
+
+
+ //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 double[] values;
+
+ /**
+ * The number of values present in the list.
+ */
+ private int size;
+
+
+ /**
+ * Constructor that initialises with the default size.
+ */
+ public DoubleArrayList() {
+ this(DEFAULT_SIZE);
+ }
+
+ /**
+ * Constructor which initialises with the specified initial capacity.
+ *
+ * @param initialCapacity the initial capacity of the backing array
+ */
+ public DoubleArrayList(int initialCapacity) {
+ values = new double[initialCapacity];
+ }
+
+ /**
+ * Constructor which initialises the content from the supplied array list.
+ *
+ * @param initial the initial contents
+ */
+ public DoubleArrayList(DoubleArrayList 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(double element) {
+ ensureCapacity(size + 1);
+ values[size] = element;
+ size++;
+ }
+
+ @Override
+ public void add(byte[] bytes) {
+ add(fromBytes(bytes));
+ }
+
+ @Override
+ public int compare(Double needle, int compareToIndex) {
+ double compareTo = values[compareToIndex];
+ return Double.compare(needle, 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
+ double[] newValues = new double[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 double 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(double 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] == 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<Double> {
+
+ private double[] values;
+ private int size;
+ private int current = 0;
+
+ private InternalIterator(double[] values, int size) {
+ this.values = values;
+ this.size = size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean hasNext() {
+ return current < size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public Double 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<Double> 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, double 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 double remove(int index) {
+ if (index >= size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+
+ double 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, double 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 double removeLast() {
+ if (size < 1) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+ }
+
+ double 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 Double fromBytes(byte[] bytes) {
+ return Bytes.toDouble(bytes);
+ }
+
+
+ @Override
+ public long heapSize() {
+ return FIXED_OVERHEAD + Bytes.SIZEOF_DOUBLE * 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 DoubleArrayList)) {
+ return false;
+ }
+
+ DoubleArrayList that = (DoubleArrayList) 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_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/FloatArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/FloatArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/FloatArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/FloatArrayList.java Sat Jan 9 21:09:59 2010
@@ -0,0 +1,365 @@
+/**
+ * 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;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class FloatArrayList implements List<Float> {
+
+
+ //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 float[] values;
+
+ /**
+ * The number of values present in the list.
+ */
+ private int size;
+
+
+ /**
+ * Constructor that initialises with the default size.
+ */
+ public FloatArrayList() {
+ this(DEFAULT_SIZE);
+ }
+
+ /**
+ * Constructor which initialises with the specified initial capacity.
+ *
+ * @param initialCapacity the initial capacity of the backing array
+ */
+ public FloatArrayList(int initialCapacity) {
+ values = new float[initialCapacity];
+ }
+
+ /**
+ * Constructor which initialises the content from the supplied array list.
+ *
+ * @param initial the initial contents
+ */
+ public FloatArrayList(FloatArrayList 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(float element) {
+ ensureCapacity(size + 1);
+ values[size] = element;
+ size++;
+ }
+
+ @Override
+ public void add(byte[] bytes) {
+ add(fromBytes(bytes));
+ }
+
+ @Override
+ public int compare(Float needle, int compareToIndex) {
+ float compareTo = values[compareToIndex];
+ return Float.compare(needle, 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
+ float[] newValues = new float[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 float 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(float 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] == 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<Float> {
+
+ private float[] values;
+ private int size;
+ private int current = 0;
+
+ private InternalIterator(float[] values, int size) {
+ this.values = values;
+ this.size = size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean hasNext() {
+ return current < size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public Float 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<Float> 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, float 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 float remove(int index) {
+ if (index >= size) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+ }
+
+ float 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, float 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 float removeLast() {
+ if (size < 1) {
+ throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+ }
+
+ float 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 Float fromBytes(byte[] bytes) {
+ return Bytes.toFloat(bytes);
+ }
+
+
+ @Override
+ public long heapSize() {
+ return FIXED_OVERHEAD + Bytes.SIZEOF_FLOAT * 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 FloatArrayList)) {
+ return false;
+ }
+
+ FloatArrayList that = (FloatArrayList) compareTo;
+
+ return this.size == that.size &&
+ ArrayUtils.isEquals(this.values, that.values);
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public int hashCode() {
+ return 31 * Arrays.hashCode(values) + size;
+ }
+}