hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From apurt...@apache.org
Subject 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....
Date Sat, 09 Jan 2010 21:10:05 GMT
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;
+  }
+}



Mime
View raw message