You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by yo...@apache.org on 2015/05/17 18:09:42 UTC
svn commit: r1679877 - in /lucene/dev/branches/branch_5x: ./ solr/
solr/core/ solr/core/src/java/org/apache/solr/search/
solr/core/src/java/org/apache/solr/search/facet/
solr/core/src/test/org/apache/solr/search/facet/ solr/solrj/
solr/solrj/src/java/o...
Author: yonik
Date: Sun May 17 16:09:42 2015
New Revision: 1679877
URL: http://svn.apache.org/r1679877
Log:
SOLR-7553: hll function for hyperloglog
Added:
lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/HLLAgg.java
- copied unchanged from r1679876, lucene/dev/trunk/solr/core/src/java/org/apache/solr/search/facet/HLLAgg.java
lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/UniqueSlotAcc.java
- copied unchanged from r1679876, lucene/dev/trunk/solr/core/src/java/org/apache/solr/search/facet/UniqueSlotAcc.java
Modified:
lucene/dev/branches/branch_5x/ (props changed)
lucene/dev/branches/branch_5x/solr/ (props changed)
lucene/dev/branches/branch_5x/solr/CHANGES.txt (contents, props changed)
lucene/dev/branches/branch_5x/solr/core/ (props changed)
lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/ValueSourceParser.java
lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/SlotAcc.java
lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/UniqueAgg.java
lucene/dev/branches/branch_5x/solr/core/src/test/org/apache/solr/search/facet/TestJsonFacets.java
lucene/dev/branches/branch_5x/solr/solrj/ (props changed)
lucene/dev/branches/branch_5x/solr/solrj/src/java/org/apache/solr/common/util/Hash.java
Modified: lucene/dev/branches/branch_5x/solr/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/solr/CHANGES.txt?rev=1679877&r1=1679876&r2=1679877&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/solr/CHANGES.txt (original)
+++ lucene/dev/branches/branch_5x/solr/CHANGES.txt Sun May 17 16:09:42 2015
@@ -133,6 +133,12 @@ New Features
* SOLR-7377: Solr Streaming Expressions (Dennis Gove, Joel Bernstein, Steven Bower)
+* SOLR-7553: Facet Analytics Module: new "hll" function that uses HyperLogLog to calculate
+ distributed cardinality. The original "unique" function is still available.
+ Example: json.facet={ numProducts : "hll(product_id)" }
+ (yonik)
+
+
Bug Fixes
----------------------
Modified: lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/ValueSourceParser.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/ValueSourceParser.java?rev=1679877&r1=1679876&r2=1679877&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/ValueSourceParser.java (original)
+++ lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/ValueSourceParser.java Sun May 17 16:09:42 2015
@@ -43,6 +43,7 @@ import org.apache.solr.schema.*;
import org.apache.solr.search.facet.AggValueSource;
import org.apache.solr.search.facet.AvgAgg;
import org.apache.solr.search.facet.CountAgg;
+import org.apache.solr.search.facet.HLLAgg;
import org.apache.solr.search.facet.MaxAgg;
import org.apache.solr.search.facet.MinAgg;
import org.apache.solr.search.facet.PercentileAgg;
@@ -818,6 +819,13 @@ public abstract class ValueSourceParser
}
});
+ addParser("agg_hll", new ValueSourceParser() {
+ @Override
+ public ValueSource parse(FunctionQParser fp) throws SyntaxError {
+ return new HLLAgg(fp.parseArg());
+ }
+ });
+
addParser("agg_sum", new ValueSourceParser() {
@Override
public ValueSource parse(FunctionQParser fp) throws SyntaxError {
Modified: lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/SlotAcc.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/SlotAcc.java?rev=1679877&r1=1679876&r2=1679877&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/SlotAcc.java (original)
+++ lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/SlotAcc.java Sun May 17 16:09:42 2015
@@ -436,266 +436,4 @@ class SortSlotAcc extends SlotAcc {
// sort slot only works with direct-mapped accumulators
throw new UnsupportedOperationException();
}
-}
-
-
-abstract class UniqueSlotAcc extends SlotAcc {
- SchemaField field;
- FixedBitSet[] arr;
- int currentDocBase;
- int[] counts; // populated with the cardinality once
- int nTerms;
-
- public UniqueSlotAcc(FacetContext fcontext, String field, int numSlots) throws IOException {
- super(fcontext);
- arr = new FixedBitSet[numSlots];
- this.field = fcontext.searcher.getSchema().getField(field);
- }
-
- @Override
- public void reset() {
- counts = null;
- for (FixedBitSet bits : arr) {
- if (bits == null) continue;
- bits.clear(0, bits.length());
- }
- }
-
- @Override
- public void setNextReader(LeafReaderContext readerContext) throws IOException {
- currentDocBase = readerContext.docBase;
- }
-
- @Override
- public Object getValue(int slot) throws IOException {
- if (fcontext.isShard()) {
- return getShardValue(slot);
- }
- if (counts != null) { // will only be pre-populated if this was used for sorting.
- return counts[slot];
- }
-
- FixedBitSet bs = arr[slot];
- return bs==null ? 0 : bs.cardinality();
- }
-
- public Object getShardValue(int slot) throws IOException {
- FixedBitSet ords = arr[slot];
- int unique;
- if (counts != null) {
- unique = counts[slot];
- } else {
- unique = ords==null ? 0 : ords.cardinality();
- }
-
- SimpleOrderedMap map = new SimpleOrderedMap();
- map.add("unique", unique);
- map.add("nTerms", nTerms);
-
- int maxExplicit=100;
- // TODO: make configurable
- // TODO: share values across buckets
- if (unique > 0) {
-
- List lst = new ArrayList( Math.min(unique, maxExplicit) );
-
- long maxOrd = ords.length();
- if (ords != null && ords.length() > 0) {
- for (int ord=0; lst.size() < maxExplicit;) {
- ord = ords.nextSetBit(ord);
- if (ord == DocIdSetIterator.NO_MORE_DOCS) break;
- BytesRef val = lookupOrd(ord);
- Object o = field.getType().toObject(field, val);
- lst.add(o);
- if (++ord >= maxOrd) break;
- }
- }
-
- map.add("vals", lst);
- }
-
- return map;
- }
-
- protected abstract BytesRef lookupOrd(int ord) throws IOException;
-
- // we only calculate all the counts when sorting by count
- public void calcCounts() {
- counts = new int[arr.length];
- for (int i=0; i<arr.length; i++) {
- FixedBitSet bs = arr[i];
- counts[i] = bs == null ? 0 : bs.cardinality();
- }
- }
-
- @Override
- public int compare(int slotA, int slotB) {
- if (counts == null) { // TODO: a more efficient way to do this? prepareSort?
- calcCounts();
- }
- return counts[slotA] - counts[slotB];
- }
-
- @Override
- public void resize(Resizer resizer) {
- arr = resizer.resize(arr, null);
- }
-}
-
-
-class UniqueSinglevaluedSlotAcc extends UniqueSlotAcc {
- final SortedDocValues topLevel;
- final SortedDocValues[] subDvs;
- final MultiDocValues.OrdinalMap ordMap;
- LongValues toGlobal;
- SortedDocValues subDv;
-
- public UniqueSinglevaluedSlotAcc(FacetContext fcontext, String field, int numSlots) throws IOException {
- super(fcontext, field, numSlots);
- SolrIndexSearcher searcher = fcontext.qcontext.searcher();
- topLevel = FieldUtil.getSortedDocValues(fcontext.qcontext, searcher.getSchema().getField(field), null);
- nTerms = topLevel.getValueCount();
- if (topLevel instanceof MultiDocValues.MultiSortedDocValues) {
- ordMap = ((MultiDocValues.MultiSortedDocValues)topLevel).mapping;
- subDvs = ((MultiDocValues.MultiSortedDocValues)topLevel).values;
- } else {
- ordMap = null;
- subDvs = null;
- }
- }
-
- @Override
- protected BytesRef lookupOrd(int ord) {
- return topLevel.lookupOrd(ord);
- }
-
- @Override
- public void setNextReader(LeafReaderContext readerContext) throws IOException {
- super.setNextReader(readerContext);
- if (subDvs != null) {
- subDv = subDvs[readerContext.ord];
- toGlobal = ordMap.getGlobalOrds(readerContext.ord);
- } else {
- assert readerContext.ord==0 || topLevel.getValueCount() == 0;
- subDv = topLevel;
- }
- }
-
- @Override
- public void collect(int doc, int slotNum) {
- int segOrd = subDv.getOrd(doc);
- if (segOrd < 0) return; // -1 means missing
- int ord = toGlobal==null ? segOrd : (int)toGlobal.get(segOrd);
-
- FixedBitSet bits = arr[slotNum];
- if (bits == null) {
- bits = new FixedBitSet(nTerms);
- arr[slotNum] = bits;
- }
- bits.set(ord);
- }
-}
-
-
-class UniqueMultiDvSlotAcc extends UniqueSlotAcc {
- final SortedSetDocValues topLevel;
- final SortedSetDocValues[] subDvs;
- final MultiDocValues.OrdinalMap ordMap;
- LongValues toGlobal;
- SortedSetDocValues subDv;
-
- public UniqueMultiDvSlotAcc(FacetContext fcontext, String field, int numSlots) throws IOException {
- super(fcontext, field, numSlots);
- SolrIndexSearcher searcher = fcontext.qcontext.searcher();
- topLevel = FieldUtil.getSortedSetDocValues(fcontext.qcontext, searcher.getSchema().getField(field), null);
- nTerms = (int) topLevel.getValueCount();
- if (topLevel instanceof MultiDocValues.MultiSortedSetDocValues) {
- ordMap = ((MultiDocValues.MultiSortedSetDocValues) topLevel).mapping;
- subDvs = ((MultiDocValues.MultiSortedSetDocValues) topLevel).values;
- } else {
- ordMap = null;
- subDvs = null;
- }
- }
-
- @Override
- protected BytesRef lookupOrd(int ord) {
- return topLevel.lookupOrd(ord);
- }
-
- @Override
- public void setNextReader(LeafReaderContext readerContext) throws IOException {
- super.setNextReader(readerContext);
- if (subDvs != null) {
- subDv = subDvs[readerContext.ord];
- toGlobal = ordMap.getGlobalOrds(readerContext.ord);
- } else {
- assert readerContext.ord==0 || topLevel.getValueCount() == 0;
- subDv = topLevel;
- }
- }
-
- @Override
- public void collect(int doc, int slotNum) {
- subDv.setDocument(doc);
- int segOrd = (int) subDv.nextOrd();
- if (segOrd < 0) return;
-
- FixedBitSet bits = arr[slotNum];
- if (bits == null) {
- bits = new FixedBitSet(nTerms);
- arr[slotNum] = bits;
- }
-
- do {
- int ord = toGlobal == null ? segOrd : (int) toGlobal.get(segOrd);
- bits.set(ord);
- segOrd = (int) subDv.nextOrd();
- } while (segOrd >= 0);
- }
-}
-
-
-
-class UniqueMultivaluedSlotAcc extends UniqueSlotAcc implements UnInvertedField.Callback {
- private UnInvertedField uif;
- private UnInvertedField.DocToTerm docToTerm;
-
- public UniqueMultivaluedSlotAcc(FacetContext fcontext, String field, int numSlots) throws IOException {
- super(fcontext, field, numSlots);
- SolrIndexSearcher searcher = fcontext.qcontext.searcher();
- uif = UnInvertedField.getUnInvertedField(field, searcher);
- docToTerm = uif.new DocToTerm();
- fcontext.qcontext.addCloseHook(this); // TODO: find way to close accumulators instead of using close hook?
- nTerms = uif.numTerms();
- }
-
- @Override
- protected BytesRef lookupOrd(int ord) throws IOException {
- return docToTerm.lookupOrd(ord);
- }
-
- private FixedBitSet bits; // bits for the current slot, only set for the callback
- @Override
- public void call(int termNum) {
- bits.set(termNum);
- }
-
- @Override
- public void collect(int doc, int slotNum) throws IOException {
- bits = arr[slotNum];
- if (bits == null) {
- bits = new FixedBitSet(nTerms);
- arr[slotNum] = bits;
- }
- docToTerm.getTerms(doc + currentDocBase, this); // this will call back to our Callback.call(int termNum)
- }
-
- @Override
- public void close() throws IOException {
- if (docToTerm != null) {
- docToTerm.close();
- docToTerm = null;
- }
- }
}
\ No newline at end of file
Modified: lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/UniqueAgg.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/UniqueAgg.java?rev=1679877&r1=1679876&r2=1679877&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/UniqueAgg.java (original)
+++ lucene/dev/branches/branch_5x/solr/core/src/java/org/apache/solr/search/facet/UniqueAgg.java Sun May 17 16:09:42 2015
@@ -26,10 +26,7 @@ import java.util.Set;
import org.apache.lucene.index.DocValues;
import org.apache.lucene.index.LeafReaderContext;
import org.apache.lucene.index.NumericDocValues;
-import org.apache.lucene.search.DocIdSetIterator;
import org.apache.lucene.util.Bits;
-import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.FixedBitSet;
import org.apache.solr.common.util.SimpleOrderedMap;
import org.apache.solr.schema.SchemaField;
@@ -48,15 +45,15 @@ public class UniqueAgg extends StrAggVal
SchemaField sf = fcontext.qcontext.searcher().getSchema().getField(getArg());
if (sf.multiValued() || sf.getType().multiValuedFieldCache()) {
if (sf.hasDocValues()) {
- return new UniqueMultiDvSlotAcc(fcontext, getArg(), numSlots);
+ return new UniqueMultiDvSlotAcc(fcontext, getArg(), numSlots, null);
} else {
- return new UniqueMultivaluedSlotAcc(fcontext, getArg(), numSlots);
+ return new UniqueMultivaluedSlotAcc(fcontext, getArg(), numSlots, null);
}
} else {
if (sf.getType().getNumericType() != null) {
return new NumericAcc(fcontext, getArg(), numSlots);
} else {
- return new UniqueSinglevaluedSlotAcc(fcontext, getArg(), numSlots);
+ return new UniqueSinglevaluedSlotAcc(fcontext, getArg(), numSlots, null);
}
}
}
Modified: lucene/dev/branches/branch_5x/solr/core/src/test/org/apache/solr/search/facet/TestJsonFacets.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/solr/core/src/test/org/apache/solr/search/facet/TestJsonFacets.java?rev=1679877&r1=1679876&r2=1679877&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/solr/core/src/test/org/apache/solr/search/facet/TestJsonFacets.java (original)
+++ lucene/dev/branches/branch_5x/solr/core/src/test/org/apache/solr/search/facet/TestJsonFacets.java Sun May 17 16:09:42 2015
@@ -28,6 +28,7 @@ import java.util.Map;
import java.util.Random;
import com.tdunning.math.stats.AVLTreeDigest;
+import net.agkn.hll.HLL;
import org.apache.lucene.queryparser.flexible.standard.processors.NumericQueryNodeProcessor;
import org.apache.lucene.util.LuceneTestCase;
import org.apache.lucene.util.packed.GrowableWriter;
@@ -294,6 +295,14 @@ public class TestJsonFacets extends Solr
doStats(Client.localClient, params());
}
+ @Test
+ public void testDistrib() throws Exception {
+ initServers();
+ Client client = servers.getClient(random().nextInt());
+ client.queryDefaults().set( "shards", servers.getShards() );
+ doStats( client, params() );
+ }
+
public void doStats(Client client, ModifiableSolrParams p) throws Exception {
Map<String, List<String>> fieldLists = new HashMap<>();
@@ -373,8 +382,7 @@ public class TestJsonFacets extends Solr
client.commit();
-
- // straight query facets
+ // straight query facets
client.testJQ(params(p, "q", "*:*"
, "json.facet", "{catA:{query:{q:'${cat_s}:A'}}, catA2:{query:{query:'${cat_s}:A'}}, catA3:{query:'${cat_s}:A'} }"
)
@@ -460,12 +468,14 @@ public class TestJsonFacets extends Solr
, "json.facet", "{f1:{type:terms, field:'${cat_s}', sort:'x desc', facet:{x:'min(${num_d})'} }" +
" , f2:{type:terms, field:'${cat_s}', sort:'x desc', facet:{x:'max(${num_d})'} } " +
" , f3:{type:terms, field:'${cat_s}', sort:'x desc', facet:{x:'unique(${where_s})'} } " +
+ " , f4:{type:terms, field:'${cat_s}', sort:'x desc', facet:{x:'hll(${where_s})'} } " +
"}"
)
, "facets=={ 'count':6, " +
" f1:{ 'buckets':[{ val:'A', count:2, x:2.0 }, { val:'B', count:3, x:-9.0}]}" +
", f2:{ 'buckets':[{ val:'B', count:3, x:11.0 }, { val:'A', count:2, x:4.0 }]} " +
", f3:{ 'buckets':[{ val:'A', count:2, x:2 }, { val:'B', count:3, x:2 }]} " +
+ ", f4:{ 'buckets':[{ val:'A', count:2, x:2 }, { val:'B', count:3, x:2 }]} " +
"}"
);
@@ -722,18 +732,28 @@ public class TestJsonFacets extends Solr
// stats at top level
client.testJQ(params(p, "q", "*:*"
- , "json.facet", "{ sum1:'sum(${num_d})', sumsq1:'sumsq(${num_d})', avg1:'avg(${num_d})', min1:'min(${num_d})', max1:'max(${num_d})', numwhere:'unique(${where_s})', unique_num_i:'unique(${num_i})', unique_num_d:'unique(${num_d})', unique_date:'unique(${date})', med:'percentile(${num_d},50)', perc:'percentile(${num_d},0,50.0,100)' }"
+ , "json.facet", "{ sum1:'sum(${num_d})', sumsq1:'sumsq(${num_d})', avg1:'avg(${num_d})', min1:'min(${num_d})', max1:'max(${num_d})'" +
+ ", numwhere:'unique(${where_s})', unique_num_i:'unique(${num_i})', unique_num_d:'unique(${num_d})', unique_date:'unique(${date})'" +
+ ", where_hll:'hll(${where_s})', hll_num_i:'hll(${num_i})', hll_num_d:'hll(${num_d})', hll_date:'hll(${date})'" +
+ ", med:'percentile(${num_d},50)', perc:'percentile(${num_d},0,50.0,100)' }"
)
, "facets=={ 'count':6, " +
- "sum1:3.0, sumsq1:247.0, avg1:0.5, min1:-9.0, max1:11.0, numwhere:2, unique_num_i:4, unique_num_d:5, unique_date:5, med:2.0, perc:[-9.0,2.0,11.0] }"
+ "sum1:3.0, sumsq1:247.0, avg1:0.5, min1:-9.0, max1:11.0" +
+ ", numwhere:2, unique_num_i:4, unique_num_d:5, unique_date:5" +
+ ", where_hll:2, hll_num_i:4, hll_num_d:5, hll_date:5" +
+ ", med:2.0, perc:[-9.0,2.0,11.0] }"
);
// stats at top level, no matches
client.testJQ(params(p, "q", "id:DOESNOTEXIST"
- , "json.facet", "{ sum1:'sum(${num_d})', sumsq1:'sumsq(${num_d})', avg1:'avg(${num_d})', min1:'min(${num_d})', max1:'max(${num_d})', numwhere:'unique(${where_s})', unique_num_i:'unique(${num_i})', unique_num_d:'unique(${num_d})', unique_date:'unique(${date})', med:'percentile(${num_d},50)', perc:'percentile(${num_d},0,50.0,100)' }"
+ , "json.facet", "{ sum1:'sum(${num_d})', sumsq1:'sumsq(${num_d})', avg1:'avg(${num_d})', min1:'min(${num_d})', max1:'max(${num_d})'" +
+ ", numwhere:'unique(${where_s})', unique_num_i:'unique(${num_i})', unique_num_d:'unique(${num_d})', unique_date:'unique(${date})'" +
+ ", where_hll:'hll(${where_s})', hll_num_i:'hll(${num_i})', hll_num_d:'hll(${num_d})', hll_date:'hll(${date})'" +
+ ", med:'percentile(${num_d},50)', perc:'percentile(${num_d},0,50.0,100)' }"
)
, "facets=={count:0 " +
- "/* ,sum1:0.0, sumsq1:0.0, avg1:0.0, min1:'NaN', max1:'NaN', numwhere:0 */ }"
+ "/* ,sum1:0.0, sumsq1:0.0, avg1:0.0, min1:'NaN', max1:'NaN', numwhere:0 */" +
+ " }"
);
//
@@ -750,11 +770,19 @@ public class TestJsonFacets extends Solr
// test unique on multi-valued field
client.testJQ(params(p, "q", "*:*"
- , "json.facet", "{x:'unique(${multi_ss})', y:{query:{q:'id:2', facet:{x:'unique(${multi_ss})'} }} }"
+ , "json.facet", "{" +
+ "x:'unique(${multi_ss})'" +
+ ",y:{query:{q:'id:2', facet:{x:'unique(${multi_ss})'} }} " +
+ ",x2:'hll(${multi_ss})'" +
+ ",y2:{query:{q:'id:2', facet:{x:'hll(${multi_ss})'} }} " +
+
+ " }"
)
- , "facets=={ 'count':6, " +
- "x:2," +
- "y:{count:1, x:2}" + // single document should yield 2 unique values
+ , "facets=={count:6 " +
+ ",x:2" +
+ ",y:{count:1, x:2}" + // single document should yield 2 unique values
+ ",x2:2" +
+ ",y2:{count:1, x:2}" + // single document should yield 2 unique values
" }"
);
@@ -936,13 +964,7 @@ public class TestJsonFacets extends Solr
}
- @Test
- public void testDistrib() throws Exception {
- initServers();
- Client client = servers.getClient(random().nextInt());
- client.queryDefaults().set( "shards", servers.getShards() );
- doStats( client, params() );
- }
+
@Test
@@ -1002,6 +1024,17 @@ public class TestJsonFacets extends Solr
, "facets=={ 'count':" + ndocs + "," +
"'f1':{ 'buckets':[{ 'val':'0', 'count':" + ndocs + ", x:" + sz + " }]} } "
);
+
+ if (client.local()) {
+ // distrib estimation prob won't match
+ client.testJQ(params(p, "q", "*:*"
+ , "json.facet", "{f1:{type:terms, field:${cat_s}, limit:2, facet:{x:'hll($where_s)'} }}"
+ )
+ , "facets=={ 'count':" + ndocs + "," +
+ "'f1':{ 'buckets':[{ 'val':'0', 'count':" + ndocs + ", x:" + sz + " }]} } "
+ );
+ }
+
}
@@ -1086,4 +1119,12 @@ public class TestJsonFacets extends Solr
System.out.println(top.quantile(0.5));
System.out.println(top.quantile(0.9));
}
+
+ public void XtestHLL() {
+ HLLAgg.HLLFactory fac = new HLLAgg.HLLFactory();
+ HLL hll = fac.getHLL();
+ hll.addRaw(123456789);
+ hll.addRaw(987654321);
+ }
+
}
Modified: lucene/dev/branches/branch_5x/solr/solrj/src/java/org/apache/solr/common/util/Hash.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/solr/solrj/src/java/org/apache/solr/common/util/Hash.java?rev=1679877&r1=1679876&r2=1679877&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/solr/solrj/src/java/org/apache/solr/common/util/Hash.java (original)
+++ lucene/dev/branches/branch_5x/solr/solrj/src/java/org/apache/solr/common/util/Hash.java Sun May 17 16:09:42 2015
@@ -419,4 +419,102 @@ public class Hash {
}
+ /** 128 bits of state */
+ public static final class LongPair {
+ public long val1;
+ public long val2;
+ }
+
+ public static final int fmix32(int h) {
+ h ^= h >>> 16;
+ h *= 0x85ebca6b;
+ h ^= h >>> 13;
+ h *= 0xc2b2ae35;
+ h ^= h >>> 16;
+ return h;
+ }
+
+ public static final long fmix64(long k) {
+ k ^= k >>> 33;
+ k *= 0xff51afd7ed558ccdL;
+ k ^= k >>> 33;
+ k *= 0xc4ceb9fe1a85ec53L;
+ k ^= k >>> 33;
+ return k;
+ }
+
+ /** Gets a long from a byte buffer in little endian byte order. */
+ public static final long getLongLittleEndian(byte[] buf, int offset) {
+ return ((long)buf[offset+7] << 56) // no mask needed
+ | ((buf[offset+6] & 0xffL) << 48)
+ | ((buf[offset+5] & 0xffL) << 40)
+ | ((buf[offset+4] & 0xffL) << 32)
+ | ((buf[offset+3] & 0xffL) << 24)
+ | ((buf[offset+2] & 0xffL) << 16)
+ | ((buf[offset+1] & 0xffL) << 8)
+ | ((buf[offset ] & 0xffL)); // no shift needed
+ }
+
+
+ /** Returns the MurmurHash3_x64_128 hash, placing the result in "out". */
+ public static void murmurhash3_x64_128(byte[] key, int offset, int len, int seed, LongPair out) {
+ // The original algorithm does have a 32 bit unsigned seed.
+ // We have to mask to match the behavior of the unsigned types and prevent sign extension.
+ long h1 = seed & 0x00000000FFFFFFFFL;
+ long h2 = seed & 0x00000000FFFFFFFFL;
+
+ final long c1 = 0x87c37b91114253d5L;
+ final long c2 = 0x4cf5ad432745937fL;
+
+ int roundedEnd = offset + (len & 0xFFFFFFF0); // round down to 16 byte block
+ for (int i=offset; i<roundedEnd; i+=16) {
+ long k1 = getLongLittleEndian(key, i);
+ long k2 = getLongLittleEndian(key, i+8);
+ k1 *= c1; k1 = Long.rotateLeft(k1,31); k1 *= c2; h1 ^= k1;
+ h1 = Long.rotateLeft(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
+ k2 *= c2; k2 = Long.rotateLeft(k2,33); k2 *= c1; h2 ^= k2;
+ h2 = Long.rotateLeft(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
+ }
+
+ long k1 = 0;
+ long k2 = 0;
+
+ switch (len & 15) {
+ case 15: k2 = (key[roundedEnd+14] & 0xffL) << 48;
+ case 14: k2 |= (key[roundedEnd+13] & 0xffL) << 40;
+ case 13: k2 |= (key[roundedEnd+12] & 0xffL) << 32;
+ case 12: k2 |= (key[roundedEnd+11] & 0xffL) << 24;
+ case 11: k2 |= (key[roundedEnd+10] & 0xffL) << 16;
+ case 10: k2 |= (key[roundedEnd+ 9] & 0xffL) << 8;
+ case 9: k2 |= (key[roundedEnd+ 8] & 0xffL);
+ k2 *= c2; k2 = Long.rotateLeft(k2, 33); k2 *= c1; h2 ^= k2;
+ case 8: k1 = ((long)key[roundedEnd+7]) << 56;
+ case 7: k1 |= (key[roundedEnd+6] & 0xffL) << 48;
+ case 6: k1 |= (key[roundedEnd+5] & 0xffL) << 40;
+ case 5: k1 |= (key[roundedEnd+4] & 0xffL) << 32;
+ case 4: k1 |= (key[roundedEnd+3] & 0xffL) << 24;
+ case 3: k1 |= (key[roundedEnd+2] & 0xffL) << 16;
+ case 2: k1 |= (key[roundedEnd+1] & 0xffL) << 8;
+ case 1: k1 |= (key[roundedEnd ] & 0xffL);
+ k1 *= c1; k1 = Long.rotateLeft(k1,31); k1 *= c2; h1 ^= k1;
+ }
+
+ //----------
+ // finalization
+
+ h1 ^= len; h2 ^= len;
+
+ h1 += h2;
+ h2 += h1;
+
+ h1 = fmix64(h1);
+ h2 = fmix64(h2);
+
+ h1 += h2;
+ h2 += h1;
+
+ out.val1 = h1;
+ out.val2 = h2;
+ }
+
}