You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by al...@apache.org on 2009/03/02 07:11:21 UTC
svn commit: r749204 [1/2] -
/incubator/cassandra/src/org/apache/cassandra/utils/
Author: alakshman
Date: Mon Mar 2 06:11:20 2009
New Revision: 749204
URL: http://svn.apache.org/viewvc?rev=749204&view=rev
Log:
Adding Cassandra sources
Added:
incubator/cassandra/src/org/apache/cassandra/utils/
incubator/cassandra/src/org/apache/cassandra/utils/BasicUtilities.java
incubator/cassandra/src/org/apache/cassandra/utils/BitSet.java
incubator/cassandra/src/org/apache/cassandra/utils/BloomCalculations.java
incubator/cassandra/src/org/apache/cassandra/utils/BloomFilter.java
incubator/cassandra/src/org/apache/cassandra/utils/Cachetable.java
incubator/cassandra/src/org/apache/cassandra/utils/FBUtilities.java
incubator/cassandra/src/org/apache/cassandra/utils/FastHash.java
incubator/cassandra/src/org/apache/cassandra/utils/FastHashMap.java
incubator/cassandra/src/org/apache/cassandra/utils/FastLinkedHashMap.java
incubator/cassandra/src/org/apache/cassandra/utils/FastObjectHash.java
incubator/cassandra/src/org/apache/cassandra/utils/FileUtils.java
incubator/cassandra/src/org/apache/cassandra/utils/GuidGenerator.java
incubator/cassandra/src/org/apache/cassandra/utils/HashingSchemes.java
incubator/cassandra/src/org/apache/cassandra/utils/ICacheExpungeHook.java
incubator/cassandra/src/org/apache/cassandra/utils/ICachetable.java
incubator/cassandra/src/org/apache/cassandra/utils/JenkinsHash.java
incubator/cassandra/src/org/apache/cassandra/utils/Log4jLogger.java
incubator/cassandra/src/org/apache/cassandra/utils/LogUtil.java
incubator/cassandra/src/org/apache/cassandra/utils/PrimeFinder.java
incubator/cassandra/src/org/apache/cassandra/utils/SafeMessageDigest.java
incubator/cassandra/src/org/apache/cassandra/utils/XMLUtils.java
Added: incubator/cassandra/src/org/apache/cassandra/utils/BasicUtilities.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/src/org/apache/cassandra/utils/BasicUtilities.java?rev=749204&view=auto
==============================================================================
--- incubator/cassandra/src/org/apache/cassandra/utils/BasicUtilities.java (added)
+++ incubator/cassandra/src/org/apache/cassandra/utils/BasicUtilities.java Mon Mar 2 06:11:20 2009
@@ -0,0 +1,75 @@
+/**
+ * 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.cassandra.utils;
+
+import java.util.*;
+import java.util.concurrent.BlockingQueue;
+import java.util.concurrent.ThreadPoolExecutor;
+import java.math.BigInteger;
+import java.nio.ByteBuffer;
+
+/**
+ * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
+ */
+
+
+public class BasicUtilities
+{
+ public static byte[] longToByteArray(long arg)
+ {
+ byte[] retVal = new byte[8];
+ ByteBuffer bb= ByteBuffer.wrap(retVal);
+ bb.putLong(arg);
+ return retVal;
+ }
+
+ public static long byteArrayToLong(byte[] arg)
+ {
+ ByteBuffer bb= ByteBuffer.wrap(arg);
+ return bb.getLong();
+ }
+
+ public static byte[] intToByteArray(int arg)
+ {
+ byte[] retVal = new byte[4];
+ ByteBuffer bb= ByteBuffer.wrap(retVal);
+ bb.putInt(arg);
+ return retVal;
+ }
+
+ public static int byteArrayToInt(byte[] arg)
+ {
+ ByteBuffer bb= ByteBuffer.wrap(arg);
+ return bb.getInt();
+ }
+
+ public static byte[] shortToByteArray(short arg)
+ {
+ byte[] retVal = new byte[2];
+ ByteBuffer bb= ByteBuffer.wrap(retVal);
+ bb.putShort(arg);
+ return retVal;
+ }
+
+ public static short byteArrayToShort(byte[] arg)
+ {
+ ByteBuffer bb= ByteBuffer.wrap(arg);
+ return bb.getShort();
+ }
+}
Added: incubator/cassandra/src/org/apache/cassandra/utils/BitSet.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/src/org/apache/cassandra/utils/BitSet.java?rev=749204&view=auto
==============================================================================
--- incubator/cassandra/src/org/apache/cassandra/utils/BitSet.java (added)
+++ incubator/cassandra/src/org/apache/cassandra/utils/BitSet.java Mon Mar 2 06:11:20 2009
@@ -0,0 +1,1142 @@
+/**
+ * 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.cassandra.utils;
+
+import java.io.*;
+import java.util.*;
+
+import org.apache.cassandra.io.ICompactSerializer;
+
+
+/**
+ * This class implements a vector of bits that grows as needed. Each component
+ * of the bit set has a <code>boolean</code> value. The bits of a
+ * <code>BitSet</code> are indexed by nonnegative integers. Individual indexed
+ * bits can be examined, set, or cleared. One <code>BitSet</code> may be used
+ * to modify the contents of another <code>BitSet</code> through logical AND,
+ * logical inclusive OR, and logical exclusive OR operations.
+ * <p>
+ * By default, all bits in the set initially have the value <code>false</code>.
+ * <p>
+ * Every bit set has a current size, which is the number of bits of space
+ * currently in use by the bit set. Note that the size is related to the
+ * implementation of a bit set, so it may change with implementation. The length
+ * of a bit set relates to logical length of a bit set and is defined
+ * independently of implementation.
+ * <p>
+ * Unless otherwise noted, passing a null parameter to any of the methods in a
+ * <code>BitSet</code> will result in a <code>NullPointerException</code>.
+ *
+ * <p>
+ * A <code>BitSet</code> is not safe for multithreaded use without external
+ * synchronization.
+ *
+ * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
+ */
+public class BitSet implements Cloneable, java.io.Serializable
+{
+ /*
+ * BitSets are packed into arrays of "words." Currently a word is a long,
+ * which consists of 64 bits, requiring 6 address bits. The choice of word
+ * size is determined purely by performance concerns.
+ */
+ private final static int ADDRESS_BITS_PER_WORD = 6;
+ private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
+ private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
+
+ /* Used to shift left or right for a partial word mask */
+ private static final long WORD_MASK = 0xffffffffffffffffL;
+
+ /**
+ * @serialField bits long[]
+ *
+ * The bits in this BitSet. The ith bit is stored in bits[i/64] at bit
+ * position i % 64 (where bit position 0 refers to the least significant bit
+ * and 63 refers to the most significant bit).
+ */
+ private static final ObjectStreamField[] serialPersistentFields = { new ObjectStreamField(
+ "bits", long[].class), };
+ private static ICompactSerializer<BitSet> serializer_ = new BitSetSerializer();
+
+ static ICompactSerializer<BitSet> serializer()
+ {
+ return serializer_;
+ }
+
+ /**
+ * The internal field corresponding to the serialField "bits".
+ */
+ private long[] words;
+
+ /**
+ * The number of words in the logical size of this BitSet.
+ */
+ private int wordsInUse = 0;
+
+ /**
+ * Whether the size of "words" is user-specified. If so, we assume the user
+ * knows what he's doing and try harder to preserve it.
+ */
+ private transient boolean sizeIsSticky = false;
+
+ /* use serialVersionUID from JDK 1.0.2 for interoperability */
+ private static final long serialVersionUID = 7997698588986878753L;
+
+ /**
+ * Given a bit index, return word index containing it.
+ */
+ private static int wordIndex(int bitIndex)
+ {
+ return bitIndex >> ADDRESS_BITS_PER_WORD;
+ }
+
+ /**
+ * Every public method must preserve these invariants.
+ */
+ private void checkInvariants()
+ {
+ assert (wordsInUse == 0 || words[wordsInUse - 1] != 0);
+ assert (wordsInUse >= 0 && wordsInUse <= words.length);
+ assert (wordsInUse == words.length || words[wordsInUse] == 0);
+ }
+
+ /**
+ * Set the field wordsInUse with the logical size in words of the bit set.
+ * WARNING:This method assumes that the number of words actually in use is
+ * less than or equal to the current value of wordsInUse!
+ */
+ private void recalculateWordsInUse()
+ {
+ // Traverse the bitset until a used word is found
+ int i;
+ for (i = wordsInUse - 1; i >= 0; i--)
+ if (words[i] != 0)
+ break;
+
+ wordsInUse = i + 1; // The new logical size
+ }
+
+ /**
+ * Creates a new bit set. All bits are initially <code>false</code>.
+ */
+ public BitSet()
+ {
+ initWords(BITS_PER_WORD);
+ sizeIsSticky = false;
+ }
+
+ /**
+ * Creates a bit set whose initial size is large enough to explicitly
+ * represent bits with indices in the range <code>0</code> through
+ * <code>nbits-1</code>. All bits are initially <code>false</code>.
+ *
+ * @param nbits
+ * the initial size of the bit set.
+ * @exception NegativeArraySizeException
+ * if the specified initial size is negative.
+ */
+ public BitSet(int nbits)
+ {
+ // nbits can't be negative; size 0 is OK
+ if (nbits < 0)
+ throw new NegativeArraySizeException("nbits < 0: " + nbits);
+
+ initWords(nbits);
+ sizeIsSticky = true;
+ }
+
+ /**
+ * This version is used only during deserialization.
+ *
+ * @param words the array which we use to defreeze
+ * the BitSet.
+ */
+ BitSet(int wordsInUse, long[] words)
+ {
+ this.wordsInUse = wordsInUse;
+ this.words = words;
+ this.sizeIsSticky = true;
+ }
+
+ int wordsInUse()
+ {
+ return this.wordsInUse;
+ }
+
+ long[] words()
+ {
+ return this.words;
+ }
+
+ private void initWords(int nbits)
+ {
+ words = new long[wordIndex(nbits - 1) + 1];
+ }
+
+ /**
+ * Ensures that the BitSet can hold enough words.
+ *
+ * @param wordsRequired
+ * the minimum acceptable number of words.
+ */
+ private void ensureCapacity(int wordsRequired)
+ {
+ if (words.length < wordsRequired)
+ {
+ // Allocate larger of doubled size or required size
+ int request = Math.max(2 * words.length, wordsRequired);
+ words = Arrays.copyOf(words, request);
+ sizeIsSticky = false;
+ }
+ }
+
+ /**
+ * Ensures that the BitSet can accommodate a given wordIndex, temporarily
+ * violating the invariants. The caller must restore the invariants before
+ * returning to the user, possibly using recalculateWordsInUse().
+ *
+ * @param wordIndex
+ * the index to be accommodated.
+ */
+ private void expandTo(int wordIndex)
+ {
+ int wordsRequired = wordIndex + 1;
+ if (wordsInUse < wordsRequired)
+ {
+ ensureCapacity(wordsRequired);
+ wordsInUse = wordsRequired;
+ }
+ }
+
+ /**
+ * Checks that fromIndex ... toIndex is a valid range of bit indices.
+ */
+ private static void checkRange(int fromIndex, int toIndex)
+ {
+ if (fromIndex < 0)
+ throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
+ if (toIndex < 0)
+ throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
+ if (fromIndex > toIndex)
+ throw new IndexOutOfBoundsException("fromIndex: " + fromIndex
+ + " > toIndex: " + toIndex);
+ }
+
+ /**
+ * Sets the bit at the specified index to the complement of its current
+ * value.
+ *
+ * @param bitIndex
+ * the index of the bit to flip.
+ * @exception IndexOutOfBoundsException
+ * if the specified index is negative.
+ * @since 1.4
+ */
+ public void flip(int bitIndex)
+ {
+ if (bitIndex < 0)
+ throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
+
+ int wordIndex = wordIndex(bitIndex);
+ expandTo(wordIndex);
+
+ words[wordIndex] ^= (1L << bitIndex);
+
+ recalculateWordsInUse();
+ checkInvariants();
+ }
+
+ /**
+ * Sets each bit from the specified <tt>fromIndex</tt> (inclusive) to the
+ * specified <tt>toIndex</tt> (exclusive) to the complement of its current
+ * value.
+ *
+ * @param fromIndex
+ * index of the first bit to flip.
+ * @param toIndex
+ * index after the last bit to flip.
+ * @exception IndexOutOfBoundsException
+ * if <tt>fromIndex</tt> is negative, or <tt>toIndex</tt>
+ * is negative, or <tt>fromIndex</tt> is larger than
+ * <tt>toIndex</tt>.
+ * @since 1.4
+ */
+ public void flip(int fromIndex, int toIndex)
+ {
+ checkRange(fromIndex, toIndex);
+
+ if (fromIndex == toIndex)
+ return;
+
+ int startWordIndex = wordIndex(fromIndex);
+ int endWordIndex = wordIndex(toIndex - 1);
+ expandTo(endWordIndex);
+
+ long firstWordMask = WORD_MASK << fromIndex;
+ long lastWordMask = WORD_MASK >>> -toIndex;
+ if (startWordIndex == endWordIndex)
+ {
+ // Case 1: One word
+ words[startWordIndex] ^= (firstWordMask & lastWordMask);
+ }
+ else
+ {
+ // Case 2: Multiple words
+ // Handle first word
+ words[startWordIndex] ^= firstWordMask;
+
+ // Handle intermediate words, if any
+ for (int i = startWordIndex + 1; i < endWordIndex; i++)
+ words[i] ^= WORD_MASK;
+
+ // Handle last word
+ words[endWordIndex] ^= lastWordMask;
+ }
+
+ recalculateWordsInUse();
+ checkInvariants();
+ }
+
+ /**
+ * Sets the bit at the specified index to <code>true</code>.
+ *
+ * @param bitIndex
+ * a bit index.
+ * @exception IndexOutOfBoundsException
+ * if the specified index is negative.
+ * @since JDK1.0
+ */
+ public void set(int bitIndex)
+ {
+ if (bitIndex < 0)
+ throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
+
+ int wordIndex = wordIndex(bitIndex);
+ expandTo(wordIndex);
+
+ words[wordIndex] |= (1L << bitIndex); // Restores invariants
+
+ checkInvariants();
+ }
+
+ /**
+ * Sets the bit at the specified index to the specified value.
+ *
+ * @param bitIndex
+ * a bit index.
+ * @param value
+ * a boolean value to set.
+ * @exception IndexOutOfBoundsException
+ * if the specified index is negative.
+ * @since 1.4
+ */
+ public void set(int bitIndex, boolean value)
+ {
+ if (value)
+ set(bitIndex);
+ else
+ clear(bitIndex);
+ }
+
+ /**
+ * Sets the bits from the specified <tt>fromIndex</tt> (inclusive) to the
+ * specified <tt>toIndex</tt> (exclusive) to <code>true</code>.
+ *
+ * @param fromIndex
+ * index of the first bit to be set.
+ * @param toIndex
+ * index after the last bit to be set.
+ * @exception IndexOutOfBoundsException
+ * if <tt>fromIndex</tt> is negative, or <tt>toIndex</tt>
+ * is negative, or <tt>fromIndex</tt> is larger than
+ * <tt>toIndex</tt>.
+ * @since 1.4
+ */
+ public void set(int fromIndex, int toIndex)
+ {
+ checkRange(fromIndex, toIndex);
+
+ if (fromIndex == toIndex)
+ return;
+
+ // Increase capacity if necessary
+ int startWordIndex = wordIndex(fromIndex);
+ int endWordIndex = wordIndex(toIndex - 1);
+ expandTo(endWordIndex);
+
+ long firstWordMask = WORD_MASK << fromIndex;
+ long lastWordMask = WORD_MASK >>> -toIndex;
+ if (startWordIndex == endWordIndex)
+ {
+ // Case 1: One word
+ words[startWordIndex] |= (firstWordMask & lastWordMask);
+ }
+ else
+ {
+ // Case 2: Multiple words
+ // Handle first word
+ words[startWordIndex] |= firstWordMask;
+
+ // Handle intermediate words, if any
+ for (int i = startWordIndex + 1; i < endWordIndex; i++)
+ words[i] = WORD_MASK;
+
+ // Handle last word (restores invariants)
+ words[endWordIndex] |= lastWordMask;
+ }
+
+ checkInvariants();
+ }
+
+ /**
+ * Sets the bits from the specified <tt>fromIndex</tt> (inclusive) to the
+ * specified <tt>toIndex</tt> (exclusive) to the specified value.
+ *
+ * @param fromIndex
+ * index of the first bit to be set.
+ * @param toIndex
+ * index after the last bit to be set
+ * @param value
+ * value to set the selected bits to
+ * @exception IndexOutOfBoundsException
+ * if <tt>fromIndex</tt> is negative, or <tt>toIndex</tt>
+ * is negative, or <tt>fromIndex</tt> is larger than
+ * <tt>toIndex</tt>.
+ * @since 1.4
+ */
+ public void set(int fromIndex, int toIndex, boolean value)
+ {
+ if (value)
+ set(fromIndex, toIndex);
+ else
+ clear(fromIndex, toIndex);
+ }
+
+ /**
+ * Sets the bit specified by the index to <code>false</code>.
+ *
+ * @param bitIndex
+ * the index of the bit to be cleared.
+ * @exception IndexOutOfBoundsException
+ * if the specified index is negative.
+ * @since JDK1.0
+ */
+ public void clear(int bitIndex)
+ {
+ if (bitIndex < 0)
+ throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
+
+ int wordIndex = wordIndex(bitIndex);
+ if (wordIndex >= wordsInUse)
+ return;
+
+ words[wordIndex] &= ~(1L << bitIndex);
+
+ recalculateWordsInUse();
+ checkInvariants();
+ }
+
+ /**
+ * Sets the bits from the specified <tt>fromIndex</tt> (inclusive) to the
+ * specified <tt>toIndex</tt> (exclusive) to <code>false</code>.
+ *
+ * @param fromIndex
+ * index of the first bit to be cleared.
+ * @param toIndex
+ * index after the last bit to be cleared.
+ * @exception IndexOutOfBoundsException
+ * if <tt>fromIndex</tt> is negative, or <tt>toIndex</tt>
+ * is negative, or <tt>fromIndex</tt> is larger than
+ * <tt>toIndex</tt>.
+ * @since 1.4
+ */
+ public void clear(int fromIndex, int toIndex)
+ {
+ checkRange(fromIndex, toIndex);
+
+ if (fromIndex == toIndex)
+ return;
+
+ int startWordIndex = wordIndex(fromIndex);
+ if (startWordIndex >= wordsInUse)
+ return;
+
+ int endWordIndex = wordIndex(toIndex - 1);
+ if (endWordIndex >= wordsInUse)
+ {
+ toIndex = length();
+ endWordIndex = wordsInUse - 1;
+ }
+
+ long firstWordMask = WORD_MASK << fromIndex;
+ long lastWordMask = WORD_MASK >>> -toIndex;
+ if (startWordIndex == endWordIndex)
+ {
+ // Case 1: One word
+ words[startWordIndex] &= ~(firstWordMask & lastWordMask);
+ }
+ else
+ {
+ // Case 2: Multiple words
+ // Handle first word
+ words[startWordIndex] &= ~firstWordMask;
+
+ // Handle intermediate words, if any
+ for (int i = startWordIndex + 1; i < endWordIndex; i++)
+ words[i] = 0;
+
+ // Handle last word
+ words[endWordIndex] &= ~lastWordMask;
+ }
+
+ recalculateWordsInUse();
+ checkInvariants();
+ }
+
+ /**
+ * Sets all of the bits in this BitSet to <code>false</code>.
+ *
+ * @since 1.4
+ */
+ public void clear()
+ {
+ while (wordsInUse > 0)
+ words[--wordsInUse] = 0;
+ }
+
+ /**
+ * Returns the value of the bit with the specified index. The value is
+ * <code>true</code> if the bit with the index <code>bitIndex</code> is
+ * currently set in this <code>BitSet</code>; otherwise, the result is
+ * <code>false</code>.
+ *
+ * @param bitIndex
+ * the bit index.
+ * @return the value of the bit with the specified index.
+ * @exception IndexOutOfBoundsException
+ * if the specified index is negative.
+ */
+ public boolean get(int bitIndex)
+ {
+ if (bitIndex < 0)
+ throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
+
+ checkInvariants();
+
+ int wordIndex = wordIndex(bitIndex);
+ return (wordIndex < wordsInUse)
+ && ((words[wordIndex] & (1L << bitIndex)) != 0);
+ }
+
+ /**
+ * Returns a new <tt>BitSet</tt> composed of bits from this
+ * <tt>BitSet</tt> from <tt>fromIndex</tt> (inclusive) to
+ * <tt>toIndex</tt> (exclusive).
+ *
+ * @param fromIndex
+ * index of the first bit to include.
+ * @param toIndex
+ * index after the last bit to include.
+ * @return a new <tt>BitSet</tt> from a range of this <tt>BitSet</tt>.
+ * @exception IndexOutOfBoundsException
+ * if <tt>fromIndex</tt> is negative, or <tt>toIndex</tt>
+ * is negative, or <tt>fromIndex</tt> is larger than
+ * <tt>toIndex</tt>.
+ * @since 1.4
+ */
+ public BitSet get(int fromIndex, int toIndex)
+ {
+ checkRange(fromIndex, toIndex);
+
+ checkInvariants();
+
+ int len = length();
+
+ // If no set bits in range return empty bitset
+ if (len <= fromIndex || fromIndex == toIndex)
+ return new BitSet(0);
+
+ // An optimization
+ if (toIndex > len)
+ toIndex = len;
+
+ BitSet result = new BitSet(toIndex - fromIndex);
+ int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
+ int sourceIndex = wordIndex(fromIndex);
+ boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);
+
+ // Process all words but the last word
+ for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
+ result.words[i] = wordAligned ? words[sourceIndex]
+ : (words[sourceIndex] >>> fromIndex)
+ | (words[sourceIndex + 1] << -fromIndex);
+
+ // Process the last word
+ long lastWordMask = WORD_MASK >>> -toIndex;
+ result.words[targetWords - 1] = ((toIndex - 1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK) ? /*
+ * straddles
+ * source
+ * words
+ */
+ ((words[sourceIndex] >>> fromIndex) | (words[sourceIndex + 1] & lastWordMask) << -fromIndex)
+ : ((words[sourceIndex] & lastWordMask) >>> fromIndex);
+
+ // Set wordsInUse correctly
+ result.wordsInUse = targetWords;
+ result.recalculateWordsInUse();
+ result.checkInvariants();
+
+ return result;
+ }
+
+ /**
+ * Returns the index of the first bit that is set to <code>true</code>
+ * that occurs on or after the specified starting index. If no such bit
+ * exists then -1 is returned.
+ *
+ * To iterate over the <code>true</code> bits in a <code>BitSet</code>,
+ * use the following loop:
+ *
+ * <pre>
+ * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1))
+ * {
+ * // operate on index i here
+ * }
+ * </pre>
+ *
+ * @param fromIndex
+ * the index to start checking from (inclusive).
+ * @return the index of the next set bit.
+ * @throws IndexOutOfBoundsException
+ * if the specified index is negative.
+ * @since 1.4
+ */
+ public int nextSetBit(int fromIndex)
+ {
+ if (fromIndex < 0)
+ throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
+
+ checkInvariants();
+
+ int u = wordIndex(fromIndex);
+ if (u >= wordsInUse)
+ return -1;
+
+ long word = words[u] & (WORD_MASK << fromIndex);
+
+ while (true)
+ {
+ if (word != 0)
+ return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
+ if (++u == wordsInUse)
+ return -1;
+ word = words[u];
+ }
+ }
+
+ /**
+ * Returns the index of the first bit that is set to <code>false</code>
+ * that occurs on or after the specified starting index.
+ *
+ * @param fromIndex
+ * the index to start checking from (inclusive).
+ * @return the index of the next clear bit.
+ * @throws IndexOutOfBoundsException
+ * if the specified index is negative.
+ * @since 1.4
+ */
+ public int nextClearBit(int fromIndex)
+ {
+ // Neither spec nor implementation handle bitsets of maximal length.
+ // See 4816253.
+ if (fromIndex < 0)
+ throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
+
+ checkInvariants();
+
+ int u = wordIndex(fromIndex);
+ if (u >= wordsInUse)
+ return fromIndex;
+
+ long word = ~words[u] & (WORD_MASK << fromIndex);
+
+ while (true)
+ {
+ if (word != 0)
+ return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
+ if (++u == wordsInUse)
+ return wordsInUse * BITS_PER_WORD;
+ word = ~words[u];
+ }
+ }
+
+ /**
+ * Returns the "logical size" of this <code>BitSet</code>: the index of
+ * the highest set bit in the <code>BitSet</code> plus one. Returns zero
+ * if the <code>BitSet</code> contains no set bits.
+ *
+ * @return the logical size of this <code>BitSet</code>.
+ * @since 1.2
+ */
+ public int length()
+ {
+ if (wordsInUse == 0)
+ return 0;
+
+ return BITS_PER_WORD
+ * (wordsInUse - 1)
+ + (BITS_PER_WORD - Long
+ .numberOfLeadingZeros(words[wordsInUse - 1]));
+ }
+
+ /**
+ * Returns true if this <code>BitSet</code> contains no bits that are set
+ * to <code>true</code>.
+ *
+ * @return boolean indicating whether this <code>BitSet</code> is empty.
+ * @since 1.4
+ */
+ public boolean isEmpty()
+ {
+ return wordsInUse == 0;
+ }
+
+ /**
+ * Returns true if the specified <code>BitSet</code> has any bits set to
+ * <code>true</code> that are also set to <code>true</code> in this
+ * <code>BitSet</code>.
+ *
+ * @param set
+ * <code>BitSet</code> to intersect with
+ * @return boolean indicating whether this <code>BitSet</code> intersects
+ * the specified <code>BitSet</code>.
+ * @since 1.4
+ */
+ public boolean intersects(BitSet set)
+ {
+ for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
+ if ((words[i] & set.words[i]) != 0)
+ return true;
+ return false;
+ }
+
+ /**
+ * Returns the number of bits set to <tt>true</tt> in this
+ * <code>BitSet</code>.
+ *
+ * @return the number of bits set to <tt>true</tt> in this
+ * <code>BitSet</code>.
+ * @since 1.4
+ */
+ public int cardinality()
+ {
+ int sum = 0;
+ for (int i = 0; i < wordsInUse; i++)
+ sum += Long.bitCount(words[i]);
+ return sum;
+ }
+
+ /**
+ * Performs a logical <b>AND</b> of this target bit set with the argument
+ * bit set. This bit set is modified so that each bit in it has the value
+ * <code>true</code> if and only if it both initially had the value
+ * <code>true</code> and the corresponding bit in the bit set argument
+ * also had the value <code>true</code>.
+ *
+ * @param set
+ * a bit set.
+ */
+ public void and(BitSet set)
+ {
+ if (this == set)
+ return;
+
+ while (wordsInUse > set.wordsInUse)
+ words[--wordsInUse] = 0;
+
+ // Perform logical AND on words in common
+ for (int i = 0; i < wordsInUse; i++)
+ words[i] &= set.words[i];
+
+ recalculateWordsInUse();
+ checkInvariants();
+ }
+
+ /**
+ * Performs a logical <b>OR</b> of this bit set with the bit set argument.
+ * This bit set is modified so that a bit in it has the value
+ * <code>true</code> if and only if it either already had the value
+ * <code>true</code> or the corresponding bit in the bit set argument has
+ * the value <code>true</code>.
+ *
+ * @param set
+ * a bit set.
+ */
+ public void or(BitSet set)
+ {
+ if (this == set)
+ return;
+
+ int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
+
+ if (wordsInUse < set.wordsInUse)
+ {
+ ensureCapacity(set.wordsInUse);
+ wordsInUse = set.wordsInUse;
+ }
+
+ // Perform logical OR on words in common
+ for (int i = 0; i < wordsInCommon; i++)
+ words[i] |= set.words[i];
+
+ // Copy any remaining words
+ if (wordsInCommon < set.wordsInUse)
+ System.arraycopy(set.words, wordsInCommon, words, wordsInCommon,
+ wordsInUse - wordsInCommon);
+
+ // recalculateWordsInUse() is unnecessary
+ checkInvariants();
+ }
+
+ /**
+ * Performs a logical <b>XOR</b> of this bit set with the bit set argument.
+ * This bit set is modified so that a bit in it has the value
+ * <code>true</code> if and only if one of the following statements holds:
+ * <ul>
+ * <li>The bit initially has the value <code>true</code>, and the
+ * corresponding bit in the argument has the value <code>false</code>.
+ * <li>The bit initially has the value <code>false</code>, and the
+ * corresponding bit in the argument has the value <code>true</code>.
+ * </ul>
+ *
+ * @param set
+ * a bit set.
+ */
+ public void xor(BitSet set)
+ {
+ int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
+
+ if (wordsInUse < set.wordsInUse)
+ {
+ ensureCapacity(set.wordsInUse);
+ wordsInUse = set.wordsInUse;
+ }
+
+ // Perform logical XOR on words in common
+ for (int i = 0; i < wordsInCommon; i++)
+ words[i] ^= set.words[i];
+
+ // Copy any remaining words
+ if (wordsInCommon < set.wordsInUse)
+ System.arraycopy(set.words, wordsInCommon, words, wordsInCommon,
+ set.wordsInUse - wordsInCommon);
+
+ recalculateWordsInUse();
+ checkInvariants();
+ }
+
+ /**
+ * Clears all of the bits in this <code>BitSet</code> whose corresponding
+ * bit is set in the specified <code>BitSet</code>.
+ *
+ * @param set
+ * the <code>BitSet</code> with which to mask this
+ * <code>BitSet</code>.
+ * @since 1.2
+ */
+ public void andNot(BitSet set)
+ {
+ // Perform logical (a & !b) on words in common
+ for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
+ words[i] &= ~set.words[i];
+
+ recalculateWordsInUse();
+ checkInvariants();
+ }
+
+ /**
+ * Returns a hash code value for this bit set. The hash code depends only on
+ * which bits have been set within this <code>BitSet</code>. The
+ * algorithm used to compute it may be described as follows.
+ * <p>
+ * Suppose the bits in the <code>BitSet</code> were to be stored in an
+ * array of <code>long</code> integers called, say, <code>words</code>,
+ * in such a manner that bit <code>k</code> is set in the
+ * <code>BitSet</code> (for nonnegative values of <code>k</code>) if
+ * and only if the expression
+ *
+ * <pre>
+ * ((k >> 6) < words.length) && ((words[k >> 6] & (1L << (bit & 0x3F))) != 0)
+ * </pre>
+ *
+ * is true. Then the following definition of the <code>hashCode</code>
+ * method would be a correct implementation of the actual algorithm:
+ *
+ * <pre>
+ * public int hashCode()
+ * {
+ * long h = 1234;
+ * for (int i = words.length; --i >= 0;)
+ * {
+ * h ˆ= words[i] * (i + 1);
+ * }
+ * return (int) ((h >> 32) ˆ h);
+ * }
+ * </pre>
+ *
+ * Note that the hash code values change if the set of bits is altered.
+ * <p>
+ * Overrides the <code>hashCode</code> method of <code>Object</code>.
+ *
+ * @return a hash code value for this bit set.
+ */
+ public int hashCode()
+ {
+ long h = 1234;
+ for (int i = wordsInUse; --i >= 0;)
+ h ^= words[i] * (i + 1);
+
+ return (int) ((h >> 32) ^ h);
+ }
+
+ /**
+ * Returns the number of bits of space actually in use by this
+ * <code>BitSet</code> to represent bit values. The maximum element in the
+ * set is the size - 1st element.
+ *
+ * @return the number of bits currently in this bit set.
+ */
+ public int size()
+ {
+ return words.length * BITS_PER_WORD;
+ }
+
+ /**
+ * Compares this object against the specified object. The result is
+ * <code>true</code> if and only if the argument is not <code>null</code>
+ * and is a <code>Bitset</code> object that has exactly the same set of
+ * bits set to <code>true</code> as this bit set. That is, for every
+ * nonnegative <code>int</code> index <code>k</code>,
+ *
+ * <pre>
+ * ((BitSet) obj).get(k) == this.get(k)
+ * </pre>
+ *
+ * must be true. The current sizes of the two bit sets are not compared.
+ * <p>
+ * Overrides the <code>equals</code> method of <code>Object</code>.
+ *
+ * @param obj
+ * the object to compare with.
+ * @return <code>true</code> if the objects are the same;
+ * <code>false</code> otherwise.
+ * @see java.util.BitSet#size()
+ */
+ public boolean equals(Object obj)
+ {
+ if (!(obj instanceof BitSet))
+ return false;
+ if (this == obj)
+ return true;
+
+ BitSet set = (BitSet) obj;
+
+ checkInvariants();
+ set.checkInvariants();
+
+ if (wordsInUse != set.wordsInUse)
+ return false;
+
+ // Check words in use by both BitSets
+ for (int i = 0; i < wordsInUse; i++)
+ if (words[i] != set.words[i])
+ return false;
+
+ return true;
+ }
+
+ /**
+ * Cloning this <code>BitSet</code> produces a new <code>BitSet</code>
+ * that is equal to it. The clone of the bit set is another bit set that has
+ * exactly the same bits set to <code>true</code> as this bit set.
+ *
+ * <p>
+ * Overrides the <code>clone</code> method of <code>Object</code>.
+ *
+ * @return a clone of this bit set.
+ * @see java.util.BitSet#size()
+ */
+ public Object clone()
+ {
+ if (!sizeIsSticky)
+ trimToSize();
+
+ try
+ {
+ BitSet result = (BitSet) super.clone();
+ result.words = words.clone();
+ result.checkInvariants();
+ return result;
+ }
+ catch (CloneNotSupportedException e)
+ {
+ throw new InternalError();
+ }
+ }
+
+ /**
+ * Attempts to reduce internal storage used for the bits in this bit set.
+ * Calling this method may, but is not required to, affect the value
+ * returned by a subsequent call to the {@link #size()} method.
+ */
+ private void trimToSize()
+ {
+ if (wordsInUse != words.length)
+ {
+ words = Arrays.copyOf(words, wordsInUse);
+ checkInvariants();
+ }
+ }
+
+ /**
+ * Save the state of the <tt>BitSet</tt> instance to a stream (i.e.,
+ * serialize it).
+ */
+ private void writeObject(ObjectOutputStream s) throws IOException
+ {
+
+ checkInvariants();
+
+ if (!sizeIsSticky)
+ trimToSize();
+
+ ObjectOutputStream.PutField fields = s.putFields();
+ fields.put("bits", words);
+ s.writeFields();
+ }
+
+ /**
+ * Reconstitute the <tt>BitSet</tt> instance from a stream (i.e.,
+ * deserialize it).
+ */
+ private void readObject(ObjectInputStream s) throws IOException,
+ ClassNotFoundException
+ {
+
+ ObjectInputStream.GetField fields = s.readFields();
+ words = (long[]) fields.get("bits", null);
+
+ // Assume maximum length then find real length
+ // because recalculateWordsInUse assumes maintenance
+ // or reduction in logical size
+ wordsInUse = words.length;
+ recalculateWordsInUse();
+ sizeIsSticky = (words.length > 0 && words[words.length - 1] == 0L); // heuristic
+ checkInvariants();
+ }
+
+ /**
+ * Returns a string representation of this bit set. For every index for
+ * which this <code>BitSet</code> contains a bit in the set state, the
+ * decimal representation of that index is included in the result. Such
+ * indices are listed in order from lowest to highest, separated by
+ * ", " (a comma and a space) and surrounded by braces, resulting in
+ * the usual mathematical notation for a set of integers.
+ * <p>
+ * Overrides the <code>toString</code> method of <code>Object</code>.
+ * <p>
+ * Example:
+ *
+ * <pre>
+ * BitSet drPepper = new BitSet();
+ * </pre>
+ *
+ * Now <code>drPepper.toString()</code> returns "<code>{}</code>".
+ * <p>
+ *
+ * <pre>
+ * drPepper.set(2);
+ * </pre>
+ *
+ * Now <code>drPepper.toString()</code> returns "<code>{2}</code>".
+ * <p>
+ *
+ * <pre>
+ * drPepper.set(4);
+ * drPepper.set(10);
+ * </pre>
+ *
+ * Now <code>drPepper.toString()</code> returns "<code>{2, 4, 10}</code>".
+ *
+ * @return a string representation of this bit set.
+ */
+ public String toString()
+ {
+ checkInvariants();
+
+ int numBits = (wordsInUse > 128) ? cardinality() : wordsInUse
+ * BITS_PER_WORD;
+ StringBuilder b = new StringBuilder(6 * numBits + 2);
+ b.append('{');
+
+ int i = nextSetBit(0);
+ if (i != -1)
+ {
+ b.append(i);
+ for (i = nextSetBit(i + 1); i >= 0; i = nextSetBit(i + 1))
+ {
+ int endOfRun = nextClearBit(i);
+ do
+ {
+ b.append(", ").append(i);
+ }
+ while (++i < endOfRun);
+ }
+ }
+
+ b.append('}');
+ return b.toString();
+ }
+}
+
+class BitSetSerializer implements ICompactSerializer<BitSet>
+{
+ public void serialize(BitSet bs, DataOutputStream dos) throws IOException
+ {
+ dos.writeInt(bs.wordsInUse());
+ long[] words = bs.words();
+ dos.writeInt(words.length);
+ for ( int i = 0; i < words.length; ++i )
+ {
+ dos.writeLong(words[i]);
+ }
+ }
+
+ public BitSet deserialize(DataInputStream dis) throws IOException
+ {
+ int wordsInUse = dis.readInt();
+ int size = dis.readInt();
+ long[] words = new long[size];
+ for ( int i = 0; i < size; ++i )
+ {
+ words[i] = dis.readLong();
+ }
+ return new BitSet(wordsInUse, words);
+ }
+}
Added: incubator/cassandra/src/org/apache/cassandra/utils/BloomCalculations.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/src/org/apache/cassandra/utils/BloomCalculations.java?rev=749204&view=auto
==============================================================================
--- incubator/cassandra/src/org/apache/cassandra/utils/BloomCalculations.java (added)
+++ incubator/cassandra/src/org/apache/cassandra/utils/BloomCalculations.java Mon Mar 2 06:11:20 2009
@@ -0,0 +1,135 @@
+/**
+ * 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.cassandra.utils;
+
+/**
+ * The following calculations are taken from:
+ * http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html
+ * "Bloom Filters - the math"
+ *
+ * This class's static methods are meant to facilitate the use of the Bloom
+ * Filter class by helping to choose correct values of 'bits per element' and
+ * 'number of hash functions, k'.
+ * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
+ */
+public class BloomCalculations {
+
+ private static final int maxBits = 15;
+ private static final int minBits = 2;
+ private static final int minK = 1;
+ private static final int maxK = 8;
+ private static final int[] optKPerBits =
+ new int[]{1, // dummy K for 0 bits per element
+ 1, // dummy K for 1 bits per element
+ 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 8, 8};
+
+ /**
+ * In the following table, the row 'i' shows false positive rates if i bits
+ * per element are used. Column 'j' shows false positive rates if j hash
+ * functions are used. The first row is 'i=0', the first column is 'j=0'.
+ * Each cell (i,j) the false positive rate determined by using i bits per
+ * element and j hash functions.
+ */
+ private static final double[][] probs = new double[][]{
+ {1.0}, // dummy row representing 0 bits per element
+ {1.0, 1.0}, // dummy row representing 1 bits per element
+ {1.0, 0.393, 0.400},
+ {1.0, 0.283, 0.237, 0.253},
+ {1.0, 0.221, 0.155, 0.147, 0.160},
+ {1.0, 0.181, 0.109, 0.092, 0.092, 0.101},
+ {1.0, 0.154, 0.0804, 0.0609, 0.0561, 0.0578, 0.0638},
+ {1.0, 0.133, 0.0618, 0.0423, 0.0359, 0.0347, 0.0364},
+ {1.0, 0.118, 0.0489, 0.0306, 0.024, 0.0217, 0.0216, 0.0229},
+ {1.0, 0.105, 0.0397, 0.0228, 0.0166, 0.0141, 0.0133, 0.0135, 0.0145},
+ {1.0, 0.0952, 0.0329, 0.0174, 0.0118, 0.00943, 0.00844, 0.00819, 0.00846},
+ {1.0, 0.0869, 0.0276, 0.0136, 0.00864, 0.0065, 0.00552, 0.00513, 0.00509},
+ {1.0, 0.08, 0.0236, 0.0108, 0.00646, 0.00459, 0.00371, 0.00329, 0.00314},
+ {1.0, 0.074, 0.0203, 0.00875, 0.00492, 0.00332, 0.00255, 0.00217, 0.00199},
+ {1.0, 0.0689, 0.0177, 0.00718, 0.00381, 0.00244, 0.00179, 0.00146, 0.00129},
+ {1.0, 0.0645, 0.0156, 0.00596, 0.003, 0.00183, 0.00128, 0.001, 0.000852}
+ }; // the first column is a dummy column representing K=0.
+
+ public static double getFailureRate(int bitsPerElement){
+ int k = computeBestK(bitsPerElement);
+ if(bitsPerElement >= probs.length) bitsPerElement = probs.length-1;
+ return probs[bitsPerElement][k];
+ }
+
+ /**
+ * Given the number of bits that can be used per element, return the optimal
+ * number of hash functions in order to minimize the false positive rate.
+ *
+ * @param bitsPerElement
+ * @return The number of hash functions that minimize the false positive rate.
+ */
+ public static int computeBestK(int bitsPerElement){
+ if(bitsPerElement < 0)
+ return optKPerBits[0];
+ if(bitsPerElement >= optKPerBits.length)
+ return optKPerBits[optKPerBits.length-1];
+ return optKPerBits[bitsPerElement];
+ }
+
+ /**
+ * A wrapper class that holds two key parameters for a Bloom Filter: the
+ * number of hash functions used, and the number of bits per element used.
+ */
+ public static class BloomSpecification {
+ int K; // number of hash functions.
+ int bitsPerElement;
+ }
+
+ /**
+ * Given a maximum tolerable false positive probability, compute a Bloom
+ * specification which will give less than the specified false positive rate,
+ * but minimize the number of bits per element and the number of hash
+ * functions used. Because bandwidth (and therefore total bitvector size)
+ * is considered more expensive than computing power, preference is given
+ * to minimizing bits per element rather than number of hash funtions.
+ *
+ * @param maxFalsePosProb The maximum tolerable false positive rate.
+ * @return A Bloom Specification which would result in a false positive rate
+ * less than specified by the function call.
+ */
+ public static BloomSpecification computeBitsAndK(double maxFalsePosProb){
+ BloomSpecification spec = new BloomSpecification();
+ spec.bitsPerElement = 2;
+ spec.K = optKPerBits[spec.bitsPerElement];
+
+ // Handle the trivial cases:
+ if(maxFalsePosProb >= probs[minBits][minK]) return spec;
+ if(maxFalsePosProb < probs[maxBits][maxK]) {
+ spec.bitsPerElement = maxBits;
+ spec.K = maxK;
+ return spec;
+ }
+
+ // First find the minimal required number of bits:
+ while(probs[spec.bitsPerElement][spec.K] > maxFalsePosProb){
+ spec.bitsPerElement++;
+ spec.K = optKPerBits[spec.bitsPerElement];
+ }
+ // Now that the number of bits is sufficient, see if we can relax K
+ // without losing too much precision.
+ while(probs[spec.bitsPerElement][spec.K-1] <= maxFalsePosProb){
+ spec.K--;
+ }
+ return spec;
+ }
+}
Added: incubator/cassandra/src/org/apache/cassandra/utils/BloomFilter.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/src/org/apache/cassandra/utils/BloomFilter.java?rev=749204&view=auto
==============================================================================
--- incubator/cassandra/src/org/apache/cassandra/utils/BloomFilter.java (added)
+++ incubator/cassandra/src/org/apache/cassandra/utils/BloomFilter.java Mon Mar 2 06:11:20 2009
@@ -0,0 +1,633 @@
+/**
+ * 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.cassandra.utils;
+
+import java.math.*;
+import java.nio.ByteBuffer;
+import java.nio.LongBuffer;
+import java.io.*;
+import java.security.*;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+import java.util.zip.*;
+
+import javax.xml.bind.annotation.XmlElement;
+
+import org.apache.cassandra.io.DataInputBuffer;
+import org.apache.cassandra.io.DataOutputBuffer;
+import org.apache.cassandra.io.ICompactSerializer;
+import org.apache.cassandra.io.SSTable;
+
+
+/**
+ * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
+ */
+
+public class BloomFilter implements Serializable
+{
+ public static class CountingBloomFilter implements Serializable
+ {
+ private static ICompactSerializer<CountingBloomFilter> serializer_;
+ static
+ {
+ serializer_ = new CountingBloomFilterSerializer();
+ }
+
+ public static ICompactSerializer<CountingBloomFilter> serializer()
+ {
+ return serializer_;
+ }
+
+ @XmlElement(name="Filter")
+ private byte[] filter_ = new byte[0];
+
+ @XmlElement(name="Size")
+ private int size_;
+
+ @XmlElement(name="Hashes")
+ private int hashes_;
+
+ /* Keeps count of number of keys added to CBF */
+ private transient int count_ = 0;
+ private transient Random random_ = new Random(System.currentTimeMillis());
+
+ /*
+ * This is just for JAXB.
+ */
+ private CountingBloomFilter()
+ {
+ }
+
+ public CountingBloomFilter(int numElements, int bitsPerElement)
+ {
+ // TODO -- think about the trivial cases more.
+ // Note that it should indeed be possible to send a bloom filter that
+ // encodes the empty set.
+ if (numElements < 0 || bitsPerElement < 1)
+ throw new IllegalArgumentException("Number of elements and bits "
+ + "must be non-negative.");
+ // Adding a small random number of bits so that even if the set
+ // of elements hasn't changed, we'll get different false positives.
+ size_ = numElements * bitsPerElement + 20 + random_.nextInt(64);
+ filter_ = new byte[size_];
+ hashes_ = BloomCalculations.computeBestK(bitsPerElement);
+ }
+
+ CountingBloomFilter(int size, int hashes, byte[] filter)
+ {
+ size_ = size;
+ hashes_ = hashes;
+ filter_ = filter;
+ }
+
+ public CountingBloomFilter cloneMe()
+ {
+ byte[] filter = new byte[filter_.length];
+ System.arraycopy(filter_, 0, filter, 0, filter_.length);
+ return new BloomFilter.CountingBloomFilter(size_, hashes_, filter);
+ }
+
+ int size()
+ {
+ return size_;
+ }
+
+ int hashes()
+ {
+ return hashes_;
+ }
+
+ byte[] filter()
+ {
+ return filter_;
+ }
+
+ public BloomFilter.CountingBloomFilter merge(BloomFilter.CountingBloomFilter cbf)
+ {
+ if ( cbf == null )
+ return this;
+
+ if ( size_ >= cbf.size_ )
+ {
+ for ( int i = 0; i < cbf.filter_.length; ++i )
+ {
+ filter_[i] |= cbf.filter_[i];
+ }
+ return this;
+ }
+ else
+ {
+ for ( int i = 0; i < filter_.length; ++i )
+ {
+ cbf.filter_[i] |= filter_[i];
+ }
+ return cbf;
+ }
+ }
+
+ public boolean isPresent(String key)
+ {
+ boolean bVal = true;
+ for (int i = 0; i < hashes_; ++i)
+ {
+ ISimpleHash hash = hashLibrary_.get(i);
+ int hashValue = hash.hash(key);
+ int index = Math.abs(hashValue % size_);
+ if (filter_[index] == 0)
+ {
+ bVal = false;
+ break;
+ }
+ }
+ return bVal;
+ }
+
+ /*
+ param@ key -- value whose hash is used to fill
+ the filter_.
+ This is a general purpose API.
+ */
+ public void add(String key)
+ {
+ if ( !isPresent(key) )
+ ++count_;
+ for (int i = 0; i < hashes_; ++i)
+ {
+ ISimpleHash hash = hashLibrary_.get(i);
+ int hashValue = hash.hash(key);
+ int index = Math.abs(hashValue % size_);
+ byte value = (filter_[index] == 0xFF) ? filter_[index] : (byte)( (++filter_[index]) & 0xFF );
+ filter_[index] = value;
+ }
+ }
+
+ public boolean delete(String key)
+ {
+ boolean bVal = isPresent(key);
+ if ( !bVal )
+ {
+ --count_;
+ return bVal;
+ }
+
+ for (int i = 0; i < hashes_; ++i)
+ {
+ ISimpleHash hash = hashLibrary_.get(i);
+ int hashValue = hash.hash(key);
+ int index = Math.abs(hashValue % size_);
+ byte value = (filter_[index] == 0) ? filter_[index] : (byte)( (--filter_[index]) & 0xFF );
+ filter_[index] = value;
+ }
+
+ return bVal;
+ }
+
+ public int count()
+ {
+ return count_;
+ }
+ }
+
+ private static List<ISimpleHash> hashLibrary_ = new ArrayList<ISimpleHash>();
+ private static ICompactSerializer<BloomFilter> serializer_;
+
+ static
+ {
+ serializer_ = new BloomFilterSerializer();
+ hashLibrary_.add(new RSHash());
+ hashLibrary_.add(new JSHash());
+ hashLibrary_.add(new PJWHash());
+ hashLibrary_.add(new ELFHash());
+ hashLibrary_.add(new BKDRHash());
+ hashLibrary_.add(new SDBMHash());
+ hashLibrary_.add(new DJBHash());
+ hashLibrary_.add(new DEKHash());
+ hashLibrary_.add(new BPHash());
+ hashLibrary_.add(new FNVHash());
+ hashLibrary_.add(new APHash());
+ }
+
+ public static ICompactSerializer<BloomFilter> serializer()
+ {
+ return serializer_;
+ }
+
+ private BitSet filter_;
+ private int count_;
+ private int size_;
+ private int hashes_;
+ private Random random_ = new Random(System.currentTimeMillis());
+
+ public BloomFilter(int bitsPerElement)
+ {
+ if (bitsPerElement < 1)
+ throw new IllegalArgumentException("Number of bitsPerElement "
+ + "must be non-negative.");
+ // Adding a small random number of bits so that even if the set
+ // of elements hasn't changed, we'll get different false positives.
+ size_ = 20 + random_.nextInt(64);
+ filter_ = new BitSet(size_);
+ hashes_ = BloomCalculations.computeBestK(bitsPerElement);
+ }
+
+ public BloomFilter(int numElements, int bitsPerElement)
+ {
+ // TODO -- think about the trivial cases more.
+ // Note that it should indeed be possible to send a bloom filter that
+ // encodes the empty set.
+ if (numElements < 0 || bitsPerElement < 1)
+ throw new IllegalArgumentException("Number of elements and bits "
+ + "must be non-negative.");
+ // Adding a small random number of bits so that even if the set
+ // of elements hasn't changed, we'll get different false positives.
+ count_ = numElements;
+ size_ = numElements * bitsPerElement + 20 + random_.nextInt(64);
+ filter_ = new BitSet(size_);
+ //hashes_ = BloomCalculations.computeBestK(bitsPerElement);
+ hashes_ = 8;
+ }
+
+ public BloomFilter(int numElements, double maxFalsePosProbability)
+ {
+ if (numElements < 0)
+ throw new IllegalArgumentException("Number of elements must be "
+ + "non-negative.");
+ BloomCalculations.BloomSpecification spec = BloomCalculations
+ .computeBitsAndK(maxFalsePosProbability);
+ // Add a small random number of bits so that even if the set
+ // of elements hasn't changed, we'll get different false positives.
+ count_ = numElements;
+ size_ = numElements * spec.bitsPerElement + 20 + random_.nextInt(64);
+ filter_ = new BitSet(size_);
+ hashes_ = spec.K;
+ }
+
+ /*
+ * This version is only used by the deserializer.
+ */
+ BloomFilter(int count, int hashes, int size, BitSet filter)
+ {
+ count_ = count;
+ hashes_ = hashes;
+ size_ = size;
+ filter_ = filter;
+ }
+
+ int count()
+ {
+ return count_;
+ }
+
+ int size()
+ {
+ return size_;
+ }
+
+ int hashes()
+ {
+ return hashes_;
+ }
+
+ BitSet filter()
+ {
+ return filter_;
+ }
+
+ public BloomFilter merge(BloomFilter bf)
+ {
+ BloomFilter mergedBf = null;
+ if ( filter_.size() >= bf.filter_.size() )
+ {
+ filter_.or(bf.filter_);
+ mergedBf = this;
+ }
+ else
+ {
+ bf.filter_.or(filter_);
+ mergedBf = bf;
+ }
+ return mergedBf;
+ }
+
+ public boolean isPresent(String key)
+ {
+ boolean bVal = true;
+ for (int i = 0; i < hashes_; ++i)
+ {
+ ISimpleHash hash = hashLibrary_.get(i);
+ int hashValue = hash.hash(key);
+ int index = Math.abs(hashValue % size_);
+ if (!filter_.get(index))
+ {
+ bVal = false;
+ break;
+ }
+ }
+ return bVal;
+ }
+
+ /*
+ param@ key -- value whose hash is used to fill
+ the filter_.
+ This is a general purpose API.
+ */
+ public void fill(String key)
+ {
+ for (int i = 0; i < hashes_; ++i)
+ {
+ ISimpleHash hash = hashLibrary_.get(i);
+ int hashValue = hash.hash(key);
+ int index = Math.abs(hashValue % size_);
+ filter_.set(index);
+ }
+ }
+
+ public String toString()
+ {
+ return filter_.toString();
+ }
+
+ public static void main(String[] args) throws Throwable
+ {
+ BloomFilter bf = new BloomFilter(64*1024*1024, 15);
+ for ( int i = 0; i < 64*1024*1024; ++i )
+ {
+ bf.fill(Integer.toString(i));
+ }
+ System.out.println("Done filling ...");
+ for ( int i = 0; i < 64*1024*1024; ++i )
+ {
+ if ( !bf.isPresent(Integer.toString(i)) )
+ System.out.println("Oops");
+ }
+ }
+}
+
+class BloomFilterSerializer implements ICompactSerializer<BloomFilter>
+{
+ /*
+ * The following methods are used for compact representation
+ * of BloomFilter. This is essential, since we want to determine
+ * the size of the serialized Bloom Filter blob before it is
+ * populated armed with the knowledge of how many elements are
+ * going to reside in it.
+ */
+
+ public void serialize(BloomFilter bf, DataOutputStream dos) throws IOException
+ {
+ /* write out the count of the BloomFilter */
+ dos.writeInt(bf.count());
+ /* write the number of hash functions used */
+ dos.writeInt(bf.hashes());
+ /* write the size of the BloomFilter */
+ dos.writeInt(bf.size());
+ BitSet.serializer().serialize(bf.filter(), dos);
+ }
+
+ public BloomFilter deserialize(DataInputStream dis) throws IOException
+ {
+ /* read the count of the BloomFilter */
+ int count = dis.readInt();
+ /* read the number of hash functions */
+ int hashes = dis.readInt();
+ /* read the size of the bloom filter */
+ int size = dis.readInt();
+ BitSet bs = BitSet.serializer().deserialize(dis);
+ return new BloomFilter(count, hashes, size, bs);
+ }
+}
+
+class CountingBloomFilterSerializer implements ICompactSerializer<BloomFilter.CountingBloomFilter>
+{
+ /*
+ * The following methods are used for compact representation
+ * of BloomFilter. This is essential, since we want to determine
+ * the size of the serialized Bloom Filter blob before it is
+ * populated armed with the knowledge of how many elements are
+ * going to reside in it.
+ */
+
+ public void serialize(BloomFilter.CountingBloomFilter cbf, DataOutputStream dos)
+ throws IOException
+ {
+ /* write the size of the BloomFilter */
+ dos.writeInt(cbf.size());
+ /* write the number of hash functions used */
+ dos.writeInt(cbf.hashes());
+
+ byte[] filter = cbf.filter();
+ /* write length of the filter */
+ dos.writeInt(filter.length);
+ dos.write(filter);
+ }
+
+ public BloomFilter.CountingBloomFilter deserialize(DataInputStream dis) throws IOException
+ {
+ /* read the size of the bloom filter */
+ int size = dis.readInt();
+ /* read the number of hash functions */
+ int hashes = dis.readInt();
+ /* read the length of the filter */
+ int length = dis.readInt();
+ byte[] filter = new byte[length];
+ dis.readFully(filter);
+ return new BloomFilter.CountingBloomFilter(size, hashes, filter);
+ }
+}
+
+interface ISimpleHash
+{
+ public int hash(String str);
+}
+
+class RSHash implements ISimpleHash
+{
+ public int hash(String str)
+ {
+ int b = 378551;
+ int a = 63689;
+ int hash = 0;
+
+ for (int i = 0; i < str.length(); i++)
+ {
+ hash = hash * a + str.charAt(i);
+ a = a * b;
+ }
+ return hash;
+ }
+}
+
+class JSHash implements ISimpleHash
+{
+ public int hash(String str)
+ {
+ int hash = 1315423911;
+ for (int i = 0; i < str.length(); i++)
+ {
+ hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));
+ }
+ return hash;
+ }
+}
+
+class PJWHash implements ISimpleHash
+{
+ public int hash(String str)
+ {
+ int bitsInUnsignedInt = (4 * 8);
+ int threeQuarters = (bitsInUnsignedInt * 3) / 4;
+ int oneEighth = bitsInUnsignedInt / 8;
+ int highBits = (0xFFFFFFFF) << (bitsInUnsignedInt - oneEighth);
+ int hash = 0;
+ int test = 0;
+
+ for (int i = 0; i < str.length(); i++)
+ {
+ hash = (hash << oneEighth) + str.charAt(i);
+
+ if ((test = hash & highBits) != 0)
+ {
+ hash = ((hash ^ (test >> threeQuarters)) & (~highBits));
+ }
+ }
+ return hash;
+ }
+}
+
+class ELFHash implements ISimpleHash
+{
+ public int hash(String str)
+ {
+ int hash = 0;
+ int x = 0;
+ for (int i = 0; i < str.length(); i++)
+ {
+ hash = (hash << 4) + str.charAt(i);
+
+ if ((x = hash & 0xF0000000) != 0)
+ {
+ hash ^= (x >> 24);
+ }
+ hash &= ~x;
+ }
+ return hash;
+ }
+}
+
+class BKDRHash implements ISimpleHash
+{
+ public int hash(String str)
+ {
+ int seed = 131; // 31 131 1313 13131 131313 etc..
+ int hash = 0;
+ for (int i = 0; i < str.length(); i++)
+ {
+ hash = (hash * seed) + str.charAt(i);
+ }
+ return hash;
+ }
+}
+
+class SDBMHash implements ISimpleHash
+{
+ public int hash(String str)
+ {
+ int hash = 0;
+ for (int i = 0; i < str.length(); i++)
+ {
+ hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
+ }
+ return hash;
+ }
+}
+
+class DJBHash implements ISimpleHash
+{
+ public int hash(String str)
+ {
+ int hash = 5381;
+ for (int i = 0; i < str.length(); i++)
+ {
+ hash = ((hash << 5) + hash) + str.charAt(i);
+ }
+ return hash;
+ }
+}
+
+class DEKHash implements ISimpleHash
+{
+ public int hash(String str)
+ {
+ int hash = str.length();
+ for (int i = 0; i < str.length(); i++)
+ {
+ hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);
+ }
+ return hash;
+ }
+}
+
+class BPHash implements ISimpleHash
+{
+ public int hash(String str)
+ {
+ int hash = 0;
+ for (int i = 0; i < str.length(); i++)
+ {
+ hash = hash << 7 ^ str.charAt(i);
+ }
+ return hash;
+ }
+}
+
+class FNVHash implements ISimpleHash
+{
+ public int hash(String str)
+ {
+ int fnv_prime = 0x811C9DC5;
+ int hash = 0;
+ for (int i = 0; i < str.length(); i++)
+ {
+ hash *= fnv_prime;
+ hash ^= str.charAt(i);
+ }
+ return hash;
+ }
+}
+
+class APHash implements ISimpleHash
+{
+ public int hash(String str)
+ {
+ int hash = 0xAAAAAAAA;
+ for (int i = 0; i < str.length(); i++)
+ {
+ if ((i & 1) == 0)
+ {
+ hash ^= ((hash << 7) ^ str.charAt(i) ^ (hash >> 3));
+ }
+ else
+ {
+ hash ^= (~((hash << 11) ^ str.charAt(i) ^ (hash >> 5)));
+ }
+ }
+ return hash;
+ }
+}
Added: incubator/cassandra/src/org/apache/cassandra/utils/Cachetable.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/src/org/apache/cassandra/utils/Cachetable.java?rev=749204&view=auto
==============================================================================
--- incubator/cassandra/src/org/apache/cassandra/utils/Cachetable.java (added)
+++ incubator/cassandra/src/org/apache/cassandra/utils/Cachetable.java Mon Mar 2 06:11:20 2009
@@ -0,0 +1,219 @@
+/**
+ * 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.cassandra.utils;
+
+import java.util.*;
+import java.util.concurrent.ConcurrentHashMap;
+
+import org.apache.log4j.Logger;
+/**
+ * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
+ */
+
+public class Cachetable<K,V> implements ICachetable<K,V>
+{
+ private class CacheableObject<V>
+ {
+ private V value_;
+ private long age_;
+
+ CacheableObject(V o)
+ {
+ value_ = o;
+ age_ = System.currentTimeMillis();
+ }
+
+ public boolean equals(Object o)
+ {
+ return value_.equals(o);
+ }
+
+ public int hashCode()
+ {
+ return value_.hashCode();
+ }
+
+ V getValue()
+ {
+ return value_;
+ }
+
+ boolean isReadyToDie(long expiration)
+ {
+ return ( (System.currentTimeMillis() - age_) > expiration );
+ }
+ }
+
+ private class CacheMonitor extends TimerTask
+ {
+ private long expiration_;
+
+ CacheMonitor(long expiration)
+ {
+ expiration_ = expiration;
+ }
+
+ public void run()
+ {
+ Map<K,V> expungedValues = new HashMap<K,V>();
+ synchronized(cache_)
+ {
+ Enumeration<K> e = cache_.keys();
+ while( e.hasMoreElements() )
+ {
+ K key = e.nextElement();
+ CacheableObject<V> co = cache_.get(key);
+ if ( co != null && co.isReadyToDie(expiration_) )
+ {
+ V v = co.getValue();
+ if(null != v)
+ expungedValues.put(key, v);
+ cache_.remove(key);
+ }
+ }
+ }
+
+ /* Calling the hooks on the keys that have been expunged */
+ Set<K> keys = expungedValues.keySet();
+ for ( K key : keys )
+ {
+ V value = expungedValues.get(key);
+ ICacheExpungeHook<K,V> hook = hooks_.remove(key);
+ try
+ {
+ if ( hook != null )
+ {
+ hook.callMe(key, value);
+ }
+ else if ( globalHook_ != null )
+ {
+ globalHook_.callMe(key, value);
+ }
+ }
+ catch(Throwable e)
+ {
+ logger_.info(LogUtil.throwableToString(e));
+ }
+ }
+ expungedValues.clear();
+ }
+ }
+
+ private ICacheExpungeHook<K,V> globalHook_;
+ private Hashtable<K, CacheableObject<V>> cache_;
+ private Map<K, ICacheExpungeHook<K,V>> hooks_;
+ private Timer timer_;
+ private static int counter_ = 0;
+ private static Logger logger_ = Logger.getLogger(Cachetable.class);
+
+ private void init(long expiration)
+ {
+ if ( expiration <= 0 )
+ throw new IllegalArgumentException("Argument specified must be a positive number");
+
+ cache_ = new Hashtable<K, CacheableObject<V>>();
+ hooks_ = new Hashtable<K, ICacheExpungeHook<K,V>>();
+ timer_ = new Timer("CACHETABLE-TIMER-" + (++counter_), true);
+ timer_.schedule(new CacheMonitor(expiration), expiration, expiration);
+ }
+
+ /*
+ * Specify the TTL for objects in the cache
+ * in milliseconds.
+ */
+ public Cachetable(long expiration)
+ {
+ init(expiration);
+ }
+
+ /*
+ * Specify the TTL for objects in the cache
+ * in milliseconds and a global expunge hook. If
+ * a key has a key-specific hook installed invoke that
+ * instead.
+ */
+ public Cachetable(long expiration, ICacheExpungeHook<K,V> global)
+ {
+ init(expiration);
+ globalHook_ = global;
+ }
+
+ public void shutdown()
+ {
+ timer_.cancel();
+ }
+
+ public void put(K key, V value)
+ {
+ cache_.put(key, new CacheableObject<V>(value));
+ }
+
+ public void put(K key, V value, ICacheExpungeHook<K,V> hook)
+ {
+ put(key, value);
+ hooks_.put(key, hook);
+ }
+
+ public V get(K key)
+ {
+ V result = null;
+ CacheableObject<V> co = cache_.get(key);
+ if ( co != null )
+ {
+ result = co.getValue();
+ }
+ return result;
+ }
+
+ public V remove(K key)
+ {
+ CacheableObject<V> co = cache_.remove(key);
+ V result = null;
+ if ( co != null )
+ {
+ result = co.getValue();
+ }
+ return result;
+ }
+
+ public int size()
+ {
+ return cache_.size();
+ }
+
+ public boolean containsKey(K key)
+ {
+ return cache_.containsKey(key);
+ }
+
+ public boolean containsValue(V value)
+ {
+ return cache_.containsValue( new CacheableObject<V>(value) );
+ }
+
+ public boolean isEmpty()
+ {
+ return cache_.isEmpty();
+ }
+
+ public Set<K> keySet()
+ {
+ return cache_.keySet();
+ }
+}
Added: incubator/cassandra/src/org/apache/cassandra/utils/FBUtilities.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/src/org/apache/cassandra/utils/FBUtilities.java?rev=749204&view=auto
==============================================================================
--- incubator/cassandra/src/org/apache/cassandra/utils/FBUtilities.java (added)
+++ incubator/cassandra/src/org/apache/cassandra/utils/FBUtilities.java Mon Mar 2 06:11:20 2009
@@ -0,0 +1,370 @@
+/**
+ * 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.cassandra.utils;
+
+import java.util.*;
+import java.util.concurrent.ThreadPoolExecutor;
+import java.util.zip.Deflater;
+import java.util.zip.DataFormatException;
+import java.util.zip.Inflater;
+import java.security.MessageDigest;
+import java.text.DateFormat;
+import java.text.SimpleDateFormat;
+import java.io.*;
+import java.net.*;
+import java.nio.channels.SocketChannel;
+import java.nio.ByteBuffer;
+import java.math.BigInteger;
+/**
+ * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
+ */
+
+public class FBUtilities
+{
+
+ private static InetAddress localInetAddress_;
+ private static String host_;
+
+ public static String getTimestamp()
+ {
+ Date date = new Date();
+ DateFormat df = new SimpleDateFormat("MM/dd/yyyy HH:mm:ss");
+ return df.format(date);
+ }
+
+ public static String getTimestamp(long value)
+ {
+ Date date = new Date(value);
+ DateFormat df = new SimpleDateFormat("MM/dd/yyyy HH:mm:ss");
+ return df.format(date);
+ }
+
+ public static int getBits(int x, int p, int n)
+ {
+ return ( x >>> (p + 1 - n)) & ~(~0 << n);
+ }
+
+ public static String getCurrentThreadStackTrace()
+ {
+ Throwable throwable = new Throwable();
+ StackTraceElement[] ste = throwable.getStackTrace();
+ StringBuffer sbuf = new StringBuffer();
+
+ for ( int i = ste.length - 1; i > 0; --i )
+ {
+ sbuf.append(ste[i].getClassName() + "." + ste[i].getMethodName());
+ sbuf.append("/");
+ }
+ sbuf.deleteCharAt(sbuf.length() - 1);
+ return sbuf.toString();
+ }
+
+ public static String[] strip(String string, String token)
+ {
+ StringTokenizer st = new StringTokenizer(string, token);
+ List<String> result = new ArrayList<String>();
+ while ( st.hasMoreTokens() )
+ {
+ result.add( (String)st.nextElement() );
+ }
+ return result.toArray( new String[0] );
+ }
+
+ public static byte[] serializeToStream(Object o)
+ {
+ ByteArrayOutputStream bos = new ByteArrayOutputStream();
+ byte[] bytes = new byte[0];
+ try
+ {
+ ObjectOutputStream oos = new ObjectOutputStream(bos);
+ oos.writeObject(o);
+ oos.flush();
+ bytes = bos.toByteArray();
+ oos.close();
+ bos.close();
+ }
+ catch ( IOException e )
+ {
+ LogUtil.getLogger(FBUtilities.class.getName()).info( LogUtil.throwableToString(e) );
+ }
+ return bytes;
+ }
+
+ public static Object deserializeFromStream(byte[] bytes)
+ {
+ Object o = null;
+ ByteArrayInputStream bis = new ByteArrayInputStream(bytes);
+ try
+ {
+ ObjectInputStream ois = new ObjectInputStream(bis);
+ try
+ {
+ o = ois.readObject();
+ }
+ catch ( ClassNotFoundException e )
+ {
+ }
+ ois.close();
+ bis.close();
+ }
+ catch ( IOException e )
+ {
+ LogUtil.getLogger(FBUtilities.class.getName()).info( LogUtil.throwableToString(e) );
+ }
+ return o;
+ }
+
+ public static InetAddress getLocalAddress() throws UnknownHostException
+ {
+ if ( localInetAddress_ == null )
+ localInetAddress_ = InetAddress.getLocalHost();
+ return localInetAddress_;
+ }
+
+ public static String getLocalHostName() throws UnknownHostException
+ {
+ if ( host_ == null )
+ {
+ host_ = getLocalAddress().getHostName();
+ }
+ return host_;
+ }
+
+ public static String getHostName() throws UnknownHostException
+ {
+ return getLocalAddress().getCanonicalHostName();
+ }
+
+ public static boolean isHostLocalHost(InetAddress host)
+ {
+ try {
+ return getLocalAddress().equals(host);
+ }
+ catch ( UnknownHostException e )
+ {
+ return false;
+ }
+ }
+
+ public static byte[] toByteArray(int i)
+ {
+ byte[] bytes = new byte[4];
+ bytes[0] = (byte)( ( i >>> 24 ) & 0xFF);
+ bytes[1] = (byte)( ( i >>> 16 ) & 0xFF);
+ bytes[2] = (byte)( ( i >>> 8 ) & 0xFF);
+ bytes[3] = (byte)( i & 0xFF );
+ return bytes;
+ }
+
+ public static int byteArrayToInt(byte[] bytes)
+ {
+ return byteArrayToInt(bytes, 0);
+ }
+
+ public static int byteArrayToInt(byte[] bytes, int offset)
+ {
+ if ( bytes.length - offset < 4 )
+ {
+ throw new IllegalArgumentException("An integer must be 4 bytes in size.");
+ }
+ int n = 0;
+ for ( int i = 0; i < 4; ++i )
+ {
+ n <<= 8;
+ n |= bytes[offset + i] & 0xFF;
+ }
+ return n;
+ }
+
+ public static boolean isEqualBits(byte[] bytes1, byte[] bytes2)
+ {
+ return 0 == compareByteArrays(bytes1, bytes2);
+ }
+
+ public static int compareByteArrays(byte[] bytes1, byte[] bytes2){
+ if(null == bytes1){
+ if(null == bytes2) return 0;
+ else return -1;
+ }
+ if(null == bytes2) return 1;
+
+ for(int i = 0; i < bytes1.length && i < bytes2.length; i++){
+ int cmp = compareBytes(bytes1[i], bytes2[i]);
+ if(0 != cmp) return cmp;
+ }
+ if(bytes1.length == bytes2.length) return 0;
+ else return (bytes1.length < bytes2.length)? -1 : 1;
+ }
+
+ public static int compareBytes(byte b1, byte b2){
+ return compareBytes((int)b1, (int)b2);
+ }
+
+ public static int compareBytes(int b1, int b2){
+ int i1 = b1 & 0xFF;
+ int i2 = b2 & 0xFF;
+ if(i1 < i2) return -1;
+ else if(i1 == i2) return 0;
+ else return 1;
+ }
+
+ public static String stackTrace(Throwable e)
+ {
+ StringWriter sw = new StringWriter();
+ PrintWriter pw = new PrintWriter( sw );
+ e.printStackTrace(pw);
+ return sw.toString();
+ }
+
+ public static BigInteger hash(String data)
+ {
+ byte[] result = hash(HashingSchemes.MD5, data.getBytes());
+ BigInteger hash = new BigInteger(result);
+ return hash.abs();
+ }
+
+ public static byte[] hash(String type, byte[] data)
+ {
+ byte[] result = null;
+ try
+ {
+ MessageDigest messageDigest = MessageDigest.getInstance(type);
+ result = messageDigest.digest(data);
+ }
+ catch (Exception e)
+ {
+ LogUtil.getLogger(FBUtilities.class.getName()).debug(LogUtil.throwableToString(e));
+ }
+ return result;
+ }
+
+ public static boolean isEqual(byte[] digestA, byte[] digestB)
+ {
+ return MessageDigest.isEqual(digestA, digestB);
+ }
+
+ // The given bytearray is compressed onto the specifed stream.
+ // The method does not close the stream. The caller will have to do it.
+ public static void compressToStream(byte[] input, ByteArrayOutputStream bos) throws IOException
+ {
+ // Create the compressor with highest level of compression
+ Deflater compressor = new Deflater();
+ compressor.setLevel(Deflater.BEST_COMPRESSION);
+
+ // Give the compressor the data to compress
+ compressor.setInput(input);
+ compressor.finish();
+
+ // Write the compressed data to the stream
+ byte[] buf = new byte[1024];
+ while (!compressor.finished())
+ {
+ int count = compressor.deflate(buf);
+ bos.write(buf, 0, count);
+ }
+ }
+
+
+ public static byte[] compress(byte[] input) throws IOException
+ {
+ // Create an expandable byte array to hold the compressed data.
+ // You cannot use an array that's the same size as the orginal because
+ // there is no guarantee that the compressed data will be smaller than
+ // the uncompressed data.
+ ByteArrayOutputStream bos = new ByteArrayOutputStream(input.length);
+ compressToStream(input,bos);
+ bos.close();
+
+ // Get the compressed data
+ return bos.toByteArray();
+ }
+
+
+ public static byte[] decompress(byte[] compressedData, int off, int len) throws IOException, DataFormatException
+ {
+ // Create the decompressor and give it the data to compress
+ Inflater decompressor = new Inflater();
+ decompressor.setInput(compressedData, off, len);
+
+ // Create an expandable byte array to hold the decompressed data
+ ByteArrayOutputStream bos = new ByteArrayOutputStream(compressedData.length);
+
+ // Decompress the data
+ byte[] buf = new byte[1024];
+ while (!decompressor.finished())
+ {
+ int count = decompressor.inflate(buf);
+ bos.write(buf, 0, count);
+ }
+ bos.close();
+
+ // Get the decompressed data
+ return bos.toByteArray();
+ }
+
+ public static byte[] decompress(byte[] compressedData) throws IOException, DataFormatException
+ {
+ return decompress(compressedData, 0, compressedData.length);
+ }
+
+ public static byte[] xor(byte[] b1, byte[] b2)
+ {
+ byte[] bLess = null;
+ byte[] bMore = null;
+
+ if(b1.length > b2.length)
+ {
+ bLess = b2;
+ bMore = b1;
+ }
+ else
+ {
+ bLess = b1;
+ bMore = b2;
+ }
+
+ for(int i = 0 ; i< bLess.length; i++ )
+ {
+ bMore[i] = (byte)(bMore[i] ^ bLess[i]);
+ }
+
+ return bMore;
+ }
+
+ public static int getUTF8Length(String string)
+ {
+ /*
+ * We store the string as UTF-8 encoded, so when we calculate the length, it
+ * should be converted to UTF-8.
+ */
+ String utfName = string;
+ int length = utfName.length();
+ try
+ {
+ //utfName = new String(string.getBytes("UTF-8"));
+ length = string.getBytes("UTF-8").length;
+ }
+ catch (UnsupportedEncodingException e)
+ {
+ LogUtil.getLogger(FBUtilities.class.getName()).info(LogUtil.throwableToString(e));
+ }
+
+ return length;
+ }
+}