Repository: incubator-geode Updated Branches: refs/heads/develop 92be457c6 -> e685fd85a
http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/e685fd85/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/IBuilder.java ---------------------------------------------------------------------- diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/IBuilder.java b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/IBuilder.java deleted file mode 100755 index e18be29..0000000 --- a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/IBuilder.java +++ /dev/null @@ -1,41 +0,0 @@ -/* - * 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 com.gemstone.gemfire.internal.redis.executor.hll; - -/* - * Copyright (C) 2011 Clearspring Technologies, Inc. - * - * Licensed 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. - */ - - -public interface IBuilder<T> { - - T build(); - - int sizeof(); -} http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/e685fd85/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/ICardinality.java ---------------------------------------------------------------------- diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/ICardinality.java b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/ICardinality.java deleted file mode 100755 index f89f91d..0000000 --- a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/ICardinality.java +++ /dev/null @@ -1,89 +0,0 @@ -/* - * 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 com.gemstone.gemfire.internal.redis.executor.hll; - -/* - * Copyright (C) 2011 Clearspring Technologies, Inc. - * - * Licensed 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. - */ - - -import java.io.IOException; - - -public interface ICardinality { - - /** - * @param o stream element - * @return false if the value returned by cardinality() is unaffected by the appearance of o in the stream. - */ - boolean offer(Object o); - - /** - * Offer the value as a hashed long value - * - * @param hashedLong - the hash of the item to offer to the estimator - * @return false if the value returned by cardinality() is unaffected by the appearance of hashedLong in the stream - */ - boolean offerHashed(long hashedLong); - - /** - * Offer the value as a hashed long value - * - * @param hashedInt - the hash of the item to offer to the estimator - * @return false if the value returned by cardinality() is unaffected by the appearance of hashedInt in the stream - */ - boolean offerHashed(int hashedInt); - - /** - * @return the number of unique elements in the stream or an estimate thereof - */ - long cardinality(); - - /** - * @return size in bytes needed for serialization - */ - int sizeof(); - - /** - * @return byte[] - * @throws IOException - */ - byte[] getBytes() throws IOException; - - /** - * Merges estimators to produce a new estimator for the combined streams - * of this estimator and those passed as arguments. - * <p/> - * Nor this estimator nor the one passed as parameters are modified. - * - * @param estimators Zero or more compatible estimators - * @throws CardinalityMergeException If at least one of the estimators is not compatible with this one - */ - ICardinality merge(ICardinality... estimators) throws CardinalityMergeException; -} http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/e685fd85/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/MurmurHash.java ---------------------------------------------------------------------- diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/MurmurHash.java b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/MurmurHash.java deleted file mode 100755 index 1c6b9d0..0000000 --- a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/MurmurHash.java +++ /dev/null @@ -1,234 +0,0 @@ -/* - * 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 com.gemstone.gemfire.internal.redis.executor.hll; - -/** - * 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. - */ - -/** - * This is a very fast, non-cryptographic hash suitable for general hash-based - * lookup. See http://murmurhash.googlepages.com/ for more details. - * <p/> - * <p> - * The C version of MurmurHash 2.0 found at that site was ported to Java by - * Andrzej Bialecki (ab at getopt org). - * </p> - */ -public class MurmurHash { - - public static int hash(Object o) { - if (o == null) { - return 0; - } - if (o instanceof Long) { - return hashLong((Long) o); - } - if (o instanceof Integer) { - return hashLong((Integer) o); - } - if (o instanceof Double) { - return hashLong(Double.doubleToRawLongBits((Double) o)); - } - if (o instanceof Float) { - return hashLong(Float.floatToRawIntBits((Float) o)); - } - if (o instanceof String) { - return hash(((String) o).getBytes()); - } - if (o instanceof byte[]) { - return hash((byte[]) o); - } - return hash(o.toString()); - } - - public static int hash(byte[] data) { - return hash(data, data.length, -1); - } - - public static int hash(byte[] data, int seed) { - return hash(data, data.length, seed); - } - - public static int hash(byte[] data, int length, int seed) { - int m = 0x5bd1e995; - int r = 24; - - int h = seed ^ length; - - int len_4 = length >> 2; - - for (int i = 0; i < len_4; i++) { - int i_4 = i << 2; - int k = data[i_4 + 3]; - k = k << 8; - k = k | (data[i_4 + 2] & 0xff); - k = k << 8; - k = k | (data[i_4 + 1] & 0xff); - k = k << 8; - k = k | (data[i_4 + 0] & 0xff); - k *= m; - k ^= k >>> r; - k *= m; - h *= m; - h ^= k; - } - - // avoid calculating modulo - int len_m = len_4 << 2; - int left = length - len_m; - - if (left != 0) { - if (left >= 3) { - h ^= (int) data[length - 3] << 16; - } - if (left >= 2) { - h ^= (int) data[length - 2] << 8; - } - if (left >= 1) { - h ^= (int) data[length - 1]; - } - - h *= m; - } - - h ^= h >>> 13; - h *= m; - h ^= h >>> 15; - - return h; - } - - public static int hashLong(long data) { - int m = 0x5bd1e995; - int r = 24; - - int h = 0; - - int k = (int) data * m; - k ^= k >>> r; - h ^= k * m; - - k = (int) (data >> 32) * m; - k ^= k >>> r; - h *= m; - h ^= k * m; - - h ^= h >>> 13; - h *= m; - h ^= h >>> 15; - - return h; - } - - public static long hash64(Object o) { - if (o == null) { - return 0l; - } else if (o instanceof String) { - final byte[] bytes = ((String) o).getBytes(); - return hash64(bytes, bytes.length); - } else if (o instanceof byte[]) { - final byte[] bytes = (byte[]) o; - return hash64(bytes, bytes.length); - } - return hash64(o.toString()); - } - - // 64 bit implementation copied from here: https://github.com/tnm/murmurhash-java - - /** - * Generates 64 bit hash from byte array with default seed value. - * - * @param data byte array to hash - * @param length length of the array to hash - * @return 64 bit hash of the given string - */ - public static long hash64(final byte[] data, int length) { - return hash64(data, length, 0xe17a1465); - } - - - /** - * Generates 64 bit hash from byte array of the given length and seed. - * - * @param data byte array to hash - * @param length length of the array to hash - * @param seed initial seed value - * @return 64 bit hash of the given array - */ - public static long hash64(final byte[] data, int length, int seed) { - final long m = 0xc6a4a7935bd1e995L; - final int r = 47; - - long h = (seed & 0xffffffffl) ^ (length * m); - - int length8 = length / 8; - - for (int i = 0; i < length8; i++) { - final int i8 = i * 8; - long k = ((long) data[i8 + 0] & 0xff) + (((long) data[i8 + 1] & 0xff) << 8) - + (((long) data[i8 + 2] & 0xff) << 16) + (((long) data[i8 + 3] & 0xff) << 24) - + (((long) data[i8 + 4] & 0xff) << 32) + (((long) data[i8 + 5] & 0xff) << 40) - + (((long) data[i8 + 6] & 0xff) << 48) + (((long) data[i8 + 7] & 0xff) << 56); - - k *= m; - k ^= k >>> r; - k *= m; - - h ^= k; - h *= m; - } - - switch (length % 8) { - case 7: - h ^= (long) (data[(length & ~7) + 6] & 0xff) << 48; - case 6: - h ^= (long) (data[(length & ~7) + 5] & 0xff) << 40; - case 5: - h ^= (long) (data[(length & ~7) + 4] & 0xff) << 32; - case 4: - h ^= (long) (data[(length & ~7) + 3] & 0xff) << 24; - case 3: - h ^= (long) (data[(length & ~7) + 2] & 0xff) << 16; - case 2: - h ^= (long) (data[(length & ~7) + 1] & 0xff) << 8; - case 1: - h ^= (long) (data[length & ~7] & 0xff); - h *= m; - } - ; - - h ^= h >>> r; - h *= m; - h ^= h >>> r; - - return h; - } -} http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/e685fd85/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFAddExecutor.java ---------------------------------------------------------------------- diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFAddExecutor.java b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFAddExecutor.java index 95af34a..150078a 100755 --- a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFAddExecutor.java +++ b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFAddExecutor.java @@ -19,6 +19,7 @@ package com.gemstone.gemfire.internal.redis.executor.hll; import java.util.List; import com.gemstone.gemfire.cache.Region; +import com.gemstone.gemfire.internal.hll.HyperLogLogPlus; import com.gemstone.gemfire.internal.redis.ByteArrayWrapper; import com.gemstone.gemfire.internal.redis.Command; import com.gemstone.gemfire.internal.redis.Coder; http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/e685fd85/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFCountExecutor.java ---------------------------------------------------------------------- diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFCountExecutor.java b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFCountExecutor.java index e081022..625a934 100755 --- a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFCountExecutor.java +++ b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFCountExecutor.java @@ -20,6 +20,8 @@ import java.util.ArrayList; import java.util.List; import com.gemstone.gemfire.cache.Region; +import com.gemstone.gemfire.internal.hll.CardinalityMergeException; +import com.gemstone.gemfire.internal.hll.HyperLogLogPlus; import com.gemstone.gemfire.internal.redis.ByteArrayWrapper; import com.gemstone.gemfire.internal.redis.Coder; import com.gemstone.gemfire.internal.redis.Command; http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/e685fd85/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFMergeExecutor.java ---------------------------------------------------------------------- diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFMergeExecutor.java b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFMergeExecutor.java index dd9afbc..f059cc2 100755 --- a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFMergeExecutor.java +++ b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/PFMergeExecutor.java @@ -20,6 +20,8 @@ import java.util.ArrayList; import java.util.List; import com.gemstone.gemfire.cache.Region; +import com.gemstone.gemfire.internal.hll.CardinalityMergeException; +import com.gemstone.gemfire.internal.hll.HyperLogLogPlus; import com.gemstone.gemfire.internal.redis.ByteArrayWrapper; import com.gemstone.gemfire.internal.redis.Coder; import com.gemstone.gemfire.internal.redis.Command; http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/e685fd85/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/RegisterSet.java ---------------------------------------------------------------------- diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/RegisterSet.java b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/RegisterSet.java deleted file mode 100755 index fcf3a38..0000000 --- a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/redis/executor/hll/RegisterSet.java +++ /dev/null @@ -1,126 +0,0 @@ -/* - * 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 com.gemstone.gemfire.internal.redis.executor.hll; - -/* - * Copyright (C) 2012 Clearspring Technologies, Inc. - * - * Licensed 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. - */ - -public class RegisterSet { - - public final static int LOG2_BITS_PER_WORD = 6; - public final static int REGISTER_SIZE = 5; - - public final int count; - public final int size; - - private final int[] M; - - public RegisterSet(int count) { - this(count, null); - } - - public RegisterSet(int count, int[] initialValues) { - this.count = count; - - if (initialValues == null) { - this.M = new int[getSizeForCount(count)]; - } else { - this.M = initialValues; - } - this.size = this.M.length; - } - - public static int getBits(int count) { - return count / LOG2_BITS_PER_WORD; - } - - public static int getSizeForCount(int count) { - int bits = getBits(count); - if (bits == 0) { - return 1; - } else if (bits % Integer.SIZE == 0) { - return bits; - } else { - return bits + 1; - } - } - - public void set(int position, int value) { - int bucketPos = position / LOG2_BITS_PER_WORD; - int shift = REGISTER_SIZE * (position - (bucketPos * LOG2_BITS_PER_WORD)); - this.M[bucketPos] = (this.M[bucketPos] & ~(0x1f << shift)) | (value << shift); - } - - public int get(int position) { - int bucketPos = position / LOG2_BITS_PER_WORD; - int shift = REGISTER_SIZE * (position - (bucketPos * LOG2_BITS_PER_WORD)); - return (this.M[bucketPos] & (0x1f << shift)) >>> shift; - } - - public boolean updateIfGreater(int position, int value) { - int bucket = position / LOG2_BITS_PER_WORD; - int shift = REGISTER_SIZE * (position - (bucket * LOG2_BITS_PER_WORD)); - int mask = 0x1f << shift; - - // Use long to avoid sign issues with the left-most shift - long curVal = this.M[bucket] & mask; - long newVal = value << shift; - if (curVal < newVal) { - this.M[bucket] = (int) ((this.M[bucket] & ~mask) | newVal); - return true; - } else { - return false; - } - } - - public void merge(RegisterSet that) { - for (int bucket = 0; bucket < M.length; bucket++) { - int word = 0; - for (int j = 0; j < LOG2_BITS_PER_WORD; j++) { - int mask = 0x1f << (REGISTER_SIZE * j); - - int thisVal = (this.M[bucket] & mask); - int thatVal = (that.M[bucket] & mask); - word |= (thisVal < thatVal) ? thatVal : thisVal; - } - this.M[bucket] = word; - } - } - - int[] readOnlyBits() { - return M; - } - - public int[] bits() { - int[] copy = new int[size]; - System.arraycopy(M, 0, copy, 0, M.length); - return copy; - } -} http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/e685fd85/gemfire-core/src/main/java/com/gemstone/gemfire/redis/GemFireRedisServer.java ---------------------------------------------------------------------- diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/redis/GemFireRedisServer.java b/gemfire-core/src/main/java/com/gemstone/gemfire/redis/GemFireRedisServer.java index e90b724..1f7e7a9 100644 --- a/gemfire-core/src/main/java/com/gemstone/gemfire/redis/GemFireRedisServer.java +++ b/gemfire-core/src/main/java/com/gemstone/gemfire/redis/GemFireRedisServer.java @@ -64,7 +64,7 @@ import com.gemstone.gemfire.internal.redis.Coder; import com.gemstone.gemfire.internal.redis.ExecutionHandlerContext; import com.gemstone.gemfire.internal.redis.RedisDataType; import com.gemstone.gemfire.internal.redis.RegionProvider; -import com.gemstone.gemfire.internal.redis.executor.hll.HyperLogLogPlus; +import com.gemstone.gemfire.internal.hll.HyperLogLogPlus; /** * The GemFireRedisServer is a server that understands the Redis protocol. As