Mercurial > repos > rliterman > csp2

comparison CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/opt/bbmap-39.01-1/current/bloom/KCountArray7MTA.java @ 68:5028fdace37b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 16:23:26 -0400
parents
children
comparison
equal deleted inserted replaced
67:0e9998148a16 68:5028fdace37b
1 package bloom;
2
3 import java.lang.Thread.State;
4 import java.util.ArrayList;
5 import java.util.Arrays;
6 import java.util.Random;
7 import java.util.concurrent.atomic.AtomicIntegerArray;
8 import java.util.concurrent.locks.Lock;
9 import java.util.concurrent.locks.ReentrantLock;
10
11 import shared.KillSwitch;
12 import shared.Primes;
13 import shared.Shared;
14 import shared.Timer;
15 import shared.Tools;
16 import structures.ByteBuilder;
17
18
19 /**
20 *
21 * Uses prime numbers for array lengths.
22 * Uses atomic integers for concurrency control.
23 * Allows an optional prefilter.
24 *
25 * @author Brian Bushnell
26 * @date Aug 17, 2012
27 *
28 */
29 public final class KCountArray7MTA extends KCountArray {
30
31 /**
32 *
33 */
34 private static final long serialVersionUID = 568264681638739631L;
35
36 public static void main(String[] args){
37 long cells=Long.parseLong(args[0]);
38 int bits=Integer.parseInt(args[1]);
39 int hashes=Integer.parseInt(args[2]);
40
41 verbose=false;
42
43 KCountArray7MTA kca=new KCountArray7MTA(cells, bits, hashes, null, 0);
44
45 System.out.println(kca.read(0));
46 kca.increment(0);
47 System.out.println(kca.read(0));
48 kca.increment(0);
49 System.out.println(kca.read(0));
50 System.out.println();
51
52 System.out.println(kca.read(1));
53 kca.increment(1);
54 System.out.println(kca.read(1));
55 kca.increment(1);
56 System.out.println(kca.read(1));
57 System.out.println();
58
59 System.out.println(kca.read(100));
60 kca.increment(100);
61 System.out.println(kca.read(100));
62 kca.increment(100);
63 System.out.println(kca.read(100));
64 kca.increment(100);
65 System.out.println(kca.read(100));
66 System.out.println();
67
68
69 System.out.println(kca.read(150));
70 kca.increment(150);
71 System.out.println(kca.read(150));
72 System.out.println();
73
74 }
75
76 public KCountArray7MTA(long cells_, int bits_, int hashes_, KCountArray prefilter_, int prefilterLimit_){
77 super(getPrimeCells(cells_, bits_), bits_, getDesiredArrays(cells_, bits_));
78 // verbose=false;
79 // System.out.println(cells);
80 cellsPerArray=cells/numArrays;
81 wordsPerArray=(int)((cellsPerArray%cellsPerWord)==0 ? (cellsPerArray/cellsPerWord) : (cellsPerArray/cellsPerWord+1));
82 cellMod=cellsPerArray;
83 hashes=hashes_;
84 prefilter=prefilter_;
85 prefilterLimit=(prefilter==null ? 0 : Tools.min(prefilter.maxValue, prefilterLimit_));
86 // System.out.println("cells="+cells+", words="+words+", wordsPerArray="+wordsPerArray+", numArrays="+numArrays+", hashes="+hashes);
87
88 matrix=allocMatrix(numArrays, wordsPerArray);
89
90 useLocks=(cellBits>1 && hashes>1) && (LOCKED_INCREMENT || !SET_LOCKED_INCREMENT);
91 if(useLocks){
92 locks=new Lock[NUM_LOCKS];
93 for(int i=0; i<NUM_LOCKS; i++){locks[i]=new ReentrantLock();}
94 }else{locks=null;}
95
96 // matrix=new AtomicIntegerArray[numArrays];
97 // for(int i=0; i<matrix.length; i++){
98 // matrix[i]=new AtomicIntegerArray(wordsPerArray);
99 // }
100
101 assert(hashes>0 && hashes<=hashMasks.length);
102 }
103
104 private static int getDesiredArrays(long desiredCells, int bits){
105
106 long words=Tools.max((desiredCells*bits+31)/32, minArrays);
107 int arrays=minArrays;
108 while(words/arrays>=Integer.MAX_VALUE){
109 arrays*=2;
110 }
111 // assert(false) : arrays;
112 return arrays;
113 // return Tools.max(arrays, Data.LOGICAL_PROCESSORS*4);
114 }
115
116 private static long getPrimeCells(long desiredCells, int bits){
117
118 int arrays=getDesiredArrays(desiredCells, bits);
119
120 long x=(desiredCells+arrays-1)/arrays;
121 long x2=Primes.primeAtMost(x);
122 return x2*arrays;
123 }
124
125 @Override
126 public final int read(final long rawKey){
127 if(verbose){System.err.println("Reading raw key "+rawKey);}
128 if(prefilter!=null){
129 int pre=prefilter.read(rawKey);
130 if(pre<prefilterLimit){return pre;}
131 }
132 long key2=hash(rawKey, 0);
133 int min=readHashed(key2);
134 for(int i=1; i<hashes && min>0; i++){
135 if(verbose){System.err.println("Reading. i="+i+", key2="+key2);}
136 key2=Long.rotateRight(key2, hashBits);
137 key2=hash(key2, i);
138 if(verbose){System.err.println("Rot/hash. i="+i+", key2="+key2);}
139 min=min(min, readHashed(key2));
140 }
141 return min;
142 }
143
144 @Override
145 public final int read(final long[] rawKeys){
146 if(verbose){System.err.println("Reading raw key "+Arrays.toString(rawKeys));}
147 if(prefilter!=null){
148 int pre=prefilter.read(rawKeys);
149 if(pre<prefilterLimit){return pre;}
150 }
151 long key2=hash(rawKeys[0], (int)(1+(rawKeys[0])%5));
152 int min=maxValue;
153 for(int i=0; i<hashes; i++){
154 for(int keynum=0; keynum<rawKeys.length; keynum++){
155 if(verbose){System.err.println("Reading. i="+i+", key2="+key2);}
156 key2=hash(key2^rawKeys[keynum], i);
157 if(verbose){System.err.println("Rot/hash. i="+i+", key2="+key2);}
158 }
159 min=min(min, readHashed(key2));
160 key2=Long.rotateRight(key2, hashBits);
161 }
162 return min;
163 }
164
165 @Override
166 public final int readLeft(final long key, final int k, boolean makeCanonical){
167 assert(k<=32);
168 final long key2=key>>>2;
169 final int shift=2*(k-1);
170 final long akey=key2|(0L<<shift);
171 final long ckey=key2|(1L<<shift);
172 final long gkey=key2|(2L<<shift);
173 final long tkey=key2|(3L<<shift);
174 final int a=read(makeCanonical ? makeCanonical2(akey, k) : akey);
175 final int c=read(makeCanonical ? makeCanonical2(ckey, k) : ckey);
176 final int g=read(makeCanonical ? makeCanonical2(gkey, k) : gkey);
177 final int t=read(makeCanonical ? makeCanonical2(tkey, k) : tkey);
178 return a+c+g+t;
179 }
180
181 @Override
182 public final int readRight(final long key, final int k, boolean makeCanonical){
183 assert(k<=32);
184 final long mask=(k>=32 ? -1L : ~((-1L)<<(2*k)));
185 final long key2=(key<<2)&mask;
186 final long akey=key2|0L;
187 final long ckey=key2|1L;
188 final long gkey=key2|2L;
189 final long tkey=key2|3L;
190 final int a=read(makeCanonical ? makeCanonical2(akey, k) : akey);
191 final int c=read(makeCanonical ? makeCanonical2(ckey, k) : ckey);
192 final int g=read(makeCanonical ? makeCanonical2(gkey, k) : gkey);
193 final int t=read(makeCanonical ? makeCanonical2(tkey, k) : tkey);
194 return a+c+g+t;
195 }
196
197 @Override
198 public final int[] readAllLeft(final long key, final int k, boolean makeCanonical, int[] rvec){
199 assert(k<=32);
200 if(rvec==null){rvec=KillSwitch.allocInt1D(4);}
201 final long key2=key>>>2;
202 final int shift=2*(k-1);
203 final long akey=key2|(0L<<shift);
204 final long ckey=key2|(1L<<shift);
205 final long gkey=key2|(2L<<shift);
206 final long tkey=key2|(3L<<shift);
207 rvec[0]=read(makeCanonical ? makeCanonical2(akey, k) : akey);
208 rvec[1]=read(makeCanonical ? makeCanonical2(ckey, k) : ckey);
209 rvec[2]=read(makeCanonical ? makeCanonical2(gkey, k) : gkey);
210 rvec[3]=read(makeCanonical ? makeCanonical2(tkey, k) : tkey);
211 return rvec;
212 }
213
214 @Override
215 public final int[] readAllRight(final long key, final int k, boolean makeCanonical, int[] rvec){
216 assert(k<=32);
217 final long mask=(k>=32 ? -1L : ~((-1L)<<(2*k)));
218 final long key2=(key<<2)&mask;
219 final long akey=key2|0L;
220 final long ckey=key2|1L;
221 final long gkey=key2|2L;
222 final long tkey=key2|3L;
223 rvec[0]=read(makeCanonical ? makeCanonical2(akey, k) : akey);
224 rvec[1]=read(makeCanonical ? makeCanonical2(ckey, k) : ckey);
225 rvec[2]=read(makeCanonical ? makeCanonical2(gkey, k) : gkey);
226 rvec[3]=read(makeCanonical ? makeCanonical2(tkey, k) : tkey);
227 return rvec;
228 }
229
230 private final int readHashed(long key){
231 if(verbose){System.err.print("Reading hashed key "+key);}
232 // System.out.println("key="+key);
233 int arrayNum=(int)(key&arrayMask);
234 key=(key>>>arrayBits)%(cellMod);
235 // key=(key>>>(arrayBits+1))%(cellMod);
236 // System.out.println("array="+arrayNum);
237 // System.out.println("key2="+key);
238 AtomicIntegerArray array=matrix[arrayNum];
239 int index=(int)(key>>>indexShift);
240 // assert(false) : indexShift;
241 // System.out.println("index="+index);
242 int word=array.get(index);
243 // System.out.println("word="+Integer.toHexString(word));
244 assert(word>>>(cellBits*key) == word>>>(cellBits*(key&cellMask)));
245 // int cellShift=(int)(cellBits*(key&cellMask));
246 int cellShift=(int)(cellBits*key);
247 if(verbose){System.err.println(", array="+arrayNum+", index="+index+", cellShift="+(cellShift%32)+", value="+((int)((word>>>cellShift)&valueMask)));}
248 // System.out.println("cellShift="+cellShift);
249 return (int)((word>>>cellShift)&valueMask);
250 }
251
252 @Override
253 public final void write(final long key, int value){
254 throw new RuntimeException("Not allowed for this class.");
255 }
256
257 @Override
258 public final void increment(long[] keys){
259 // assert(false) : "This method is not really needed.";
260 for(int i=0; i<keys.length; i++){
261 increment(keys[i]);
262 // keys[i]=hash(keys[i], 0);
263 // incrementPartiallyHashed(hash(keys[i], 0));
264 }
265 }
266
267 @Override
268 public final void increment(final long rawKey, final int amt){
269 // if(verbose){System.err.println("\n*** Incrementing raw key "+rawKey+" ***");}
270 //
271 // if(prefilter!=null){
272 // int x=prefilter.read(rawKey);
273 // if(x<prefilterLimit){return;/* x;*/}
274 // }
275 //
276 // if(useLocks){incrementLocked(rawKey, amt);}
277 // else{incrementUnlocked(rawKey, amt);}
278 incrementAndReturnUnincremented(rawKey, amt);
279 }
280
281 /*
282 private void incrementUnlocked(long rawKey, int amt){
283 long key2=rawKey;
284 // int min=maxValue;
285 for(int i=0; i<hashes; i++){
286 key2=hash(key2, i);
287 if(verbose){System.err.println("key2="+key2+", value="+readHashed(key2));}
288 // min=min(min, incrementHashedLocal(key2, amt));
289 incrementHashedLocal(key2, amt);
290 key2=Long.rotateRight(key2, hashBits);
291 }
292 // return min;
293 }
294
295 private void incrementLocked(long rawKey, int amt){
296 assert(amt>0) : "Don't increment by zero, and negatives should use decrement amt="+amt;
297 final Lock lock=getLock(rawKey);
298 lock.lock();
299 final int min=read(rawKey);
300 final long newMinL=Tools.min(min+amt, maxValue);
301 final int newMin=(int)newMinL;
302 assert(newMin==newMinL && newMin>0) : newMin+", "+newMinL+", "+min+", "+amt;
303 if(newMin<=min){
304 assert(newMin==min) : min;
305 lock.unlock();
306 return;
307 }
308 long key2=rawKey;
309 for(int i=0; i<hashes; i++){
310 key2=hash(key2, i);
311 if(verbose){System.err.println("key2="+key2+", value="+readHashed(key2));}
312 //incrementHashedLocal_ifAtMost(key2, min);
313 incrementHashedLocal_toAtLeast(key2, newMin);
314 key2=Long.rotateRight(key2, hashBits);
315 }
316 lock.unlock();
317 // return max(min, newMin);
318 }
319 */
320
321 @Override
322 public final void decrement(final long rawKey, int amt){
323 if(verbose){System.err.println("\n*** Decrementing raw key "+rawKey+" ***");}
324
325 assert(prefilter!=null); //Why?
326
327 long key2=rawKey;
328 // int min=maxValue;
329 for(int i=0; i<hashes; i++){
330 key2=hash(key2, i);
331 if(verbose){System.err.println("key2="+key2+", value="+readHashed(key2));}
332
333 decrementHashedLocal(key2, amt);
334 // min=min(min, decrementHashedLocal(key2, amt));
335 key2=Long.rotateRight(key2, hashBits);
336 }
337 // return min;
338 }
339
340 @Override
341 public int incrementAndReturnUnincremented(final long rawKey, final int incr){
342
343 if(verbose){System.err.println("\n*** Incrementing raw key "+rawKey+" ***");}
344
345 if(prefilter!=null){
346 int x=prefilter.read(rawKey);
347 if(x<prefilterLimit){return x;}
348 }
349
350 if(useLocks){return incrementAndReturnUnincrementedLocked(rawKey, incr);}
351 else{return incrementAndReturnUnincrementedUnlocked(rawKey, incr);}
352 }
353
354 private int incrementAndReturnUnincrementedLocked(final long rawKey, final int incr){
355 assert(incr>0) : incr;
356 final Lock lock=getLock(rawKey);
357 lock.lock();
358 final int min=read(rawKey);
359 if(min>=maxValue){
360 lock.unlock();
361 return min;
362 }
363 final int newMin=(int)Tools.min(min+(long)incr, maxValue);
364 long key2=rawKey;
365 int value=maxValue;
366 for(int i=0; i<hashes; i++){
367 key2=hash(key2, i);
368 if(verbose){System.err.println("key2="+key2+", value="+readHashed(key2));}
369 int x=incrementHashedLocalAndReturnUnincremented_toAtLeast(key2, newMin);
370 value=min(value, x);
371 key2=Long.rotateRight(key2, hashBits);
372 }
373 lock.unlock();
374 return value;
375 }
376
377 private int incrementAndReturnUnincrementedUnlocked(final long rawKey, final int incr){
378 long key2=rawKey;
379 int value=maxValue;
380 for(int i=0; i<hashes; i++){
381 key2=hash(key2, i);
382 if(verbose){System.err.println("key2="+key2+", value="+readHashed(key2));}
383 int x=incrementHashedLocalAndReturnUnincremented(key2, incr);
384 value=min(value, x);
385 key2=Long.rotateRight(key2, hashBits);
386 }
387 return value;
388 }
389
390 @Override
391 public int incrementAndReturnUnincremented(final long[] rawKeys, final int incr){
392
393 if(verbose){System.err.println("\n*** Incrementing raw keys "+Arrays.toString(rawKeys)+" ***");}
394
395 if(prefilter!=null){
396 int x=prefilter.read(rawKeys);
397 if(x<prefilterLimit){return x;}
398 }
399
400 long key2=hash(rawKeys[0], (int)(1+(rawKeys[0])%5));
401 int value=maxValue;
402 for(int i=0; i<hashes; i++){
403 for(int keynum=0; keynum<rawKeys.length; keynum++){
404 key2=hash(key2^rawKeys[keynum], i);
405 if(verbose){System.err.println("key2="+key2+", value="+readHashed(key2));}
406 }
407 int x=incrementHashedLocalAndReturnUnincremented(key2, incr);
408 value=min(value, x);
409 key2=Long.rotateRight(key2, hashBits);
410 }
411 // assert(value+1==read(rawKeys) || value==maxValue) : value+", "+read(rawKeys);
412 return value;
413 }
414
415 @Override
416 public long[] transformToFrequency(){
417 return transformToFrequency(matrix);
418 }
419
420 @Override
421 public ByteBuilder toContentsString(){
422 ByteBuilder sb=new ByteBuilder();
423 sb.append('[');
424 String comma="";
425 for(AtomicIntegerArray array : matrix){
426 for(int i=0; i<array.length(); i++){
427 int word=array.get(i);
428 for(int j=0; j<cellsPerWord; j++){
429 int x=word&valueMask;
430 sb.append(comma);
431 sb.append(x);
432 word>>>=cellBits;
433 comma=", ";
434 }
435 }
436 }
437 sb.append(']');
438 return sb;
439 }
440
441 @Override
442 public double usedFraction(){return cellsUsed()/(double)cells;}
443
444 @Override
445 public double usedFraction(int mindepth){return cellsUsed(mindepth)/(double)cells;}
446
447 @Override
448 public long cellsUsed(int mindepth){
449 return cellsUsedMT(mindepth);
450 }
451
452 public long cellsUsedMT(int mindepth){
453 // assert(false) : matrix.length;
454 ArrayList<CountUsedThread> list=new ArrayList<CountUsedThread>(matrix.length);
455 for(AtomicIntegerArray aia : matrix){
456 CountUsedThread ctt=new CountUsedThread(aia, mindepth);
457 ctt.start();
458 list.add(ctt);
459 }
460 long x=0;
461 for(CountUsedThread ctt : list){
462 while(ctt.getState()!=State.TERMINATED){
463 try {
464 ctt.join();
465 } catch (InterruptedException e) {
466 // TODO Auto-generated catch block
467 e.printStackTrace();
468 }
469 }
470 x+=ctt.count;
471 }
472 return x;
473 }
474
475 private class CountUsedThread extends Thread{
476 public CountUsedThread(AtomicIntegerArray a_, int mindepth_){
477 array=a_;
478 mindepth=mindepth_;
479 }
480 @Override
481 public void run(){
482 long temp=0;
483 if(array!=null){
484 // System.out.println("C");
485 // assert(false) : Integer.toBinaryString(valueMask);
486 if(cellBits==32){
487 for(int i=0, max=array.length(); i<max; i++){
488 int word=array.get(i);
489 if(word!=0){
490 int x=word&valueMask;
491 if(x>=mindepth){temp++;}
492 }
493 }
494 }else{
495 for(int i=0, max=array.length(); i<max; i++){
496 // System.out.println("D: "+Integer.toHexString(word));
497 int word=array.get(i);
498 while(word!=0){
499 int x=word&valueMask;
500 // System.out.println("E: "+x+", "+mindepth);
501 if(x>=mindepth){temp++;}
502 word=word>>>cellBits;
503 }
504 }
505 }
506 }
507 count=temp;
508 }
509 private final AtomicIntegerArray array;
510 private final int mindepth;
511 public long count;
512 }
513
514
515 @Override
516 final long hash(long key, int row){
517 int cell=(int)((Long.MAX_VALUE&key)%(hashArrayLength-1));
518 // int cell=(int)(hashCellMask&(key));
519
520 if(row==0){//Doublehash only first time
521 key=key^hashMasks[(row+4)&7][cell];
522 // key=key^hashMasks[4][cell];
523 cell=(int)(hashCellMask&(key>>5));
524 // cell=(int)(hashCellMask&(key>>hashBits));
525 // cell=(int)((Long.MAX_VALUE&key)%(hashArrayLength-1));
526 }
527
528 assert(row>=0 && row<hashMasks.length) : row+", "+hashMasks.length;
529 assert(cell>=0 && cell<hashMasks[0].length) : cell+", "+hashMasks[0].length;
530 return key^hashMasks[row][cell];
531 }
532
533
534 // @Override
535 // final long hash(long key, int row){
536 // long code=key;
537 // for(int i=0; i<6; i++){
538 // int row2=((row+i)&7);
539 // int cell=(int)(key&hashCellMask);
540 // code^=hashMasks[row2][cell];
541 // key>>=6;
542 // }
543 // return code;
544 // }
545
546 /**
547 * @param i
548 * @param j
549 * @return
550 */
551 private static long[][] makeMasks(int rows, int cols) {
552
553 long seed;
554 synchronized(KCountArray7MTA.class){
555 seed=counter^SEEDMASK;
556 counter+=7;
557 }
558
559 Timer t=new Timer();
560 long[][] r=new long[rows][cols];
561 Random randy=Shared.threadLocalRandom(seed);
562 for(int i=0; i<r.length; i++){
563 fillMasks(r[i], randy);
564 }
565 t.stop();
566 if(t.elapsed>200000000L){System.out.println("Mask-creation time: "+t);}
567 return r;
568 }
569
570 private static void fillMasks(long[] r, Random randy) {
571 // for(int i=0; i<r.length; i++){
572 // long x=0;
573 // while(Long.bitCount(x&0xFFFFFFFF)!=16){
574 // x=randy.nextLong();
575 // }
576 // r[i]=(x&Long.MAX_VALUE);
577 // }
578
579 final int hlen=(1<<hashBits);
580 assert(r.length==hlen);
581 int[] count1=new int[hlen];
582 int[] count2=new int[hlen];
583 final long mask=hlen-1;
584
585 for(int i=0; i<r.length; i++){
586 long x=0;
587 int y=0;
588 int z=0;
589 while(Long.bitCount(x&0xFFFFFFFFL)!=16){
590 x=randy.nextLong();
591 while(Long.bitCount(x&0xFFFFFFFFL)<16){
592 x|=(1L<<randy.nextInt(32));
593 }
594 while(Long.bitCount(x&0xFFFFFFFFL)>16){
595 x&=(~(1L<<randy.nextInt(32)));
596 }
597 while(Long.bitCount(x&0xFFFFFFFF00000000L)<16){
598 x|=(1L<<(randy.nextInt(32)+32));
599 }
600 while(Long.bitCount(x&0xFFFFFFFF00000000L)>16){
601 x&=(~(1L<<(randy.nextInt(32)+32)));
602 }
603
604 // System.out.print(".");
605 // y=(((int)(x&mask))^i);
606 y=(((int)(x&mask)));
607 z=(int)((x>>hashBits)&mask);
608 if(count1[y]>0 || count2[z]>0){
609 x=0;
610 }
611 }
612 // System.out.println(Long.toBinaryString(x));
613 r[i]=(x&Long.MAX_VALUE);
614 count1[y]++;
615 count2[z]++;
616 }
617
618 }
619
620
621 @Override
622 public void initialize(){}
623
624 @Override
625 public void shutdown(){
626 if(finished){return;}
627 synchronized(this){
628 if(finished){return;}
629
630 cellsUsed=-1;
631 // for(int i=0; i<numArrays; i++){
632 // cellsUsed+=cellsUsedPersonal.get(i);
633 // }
634 cellsUsed();
635
636 assert(!finished);
637 finished=true;
638 }
639 }
640
641 private final Lock getLock(long rawKey){
642 final Lock lock=locks[(int)((rawKey&Long.MAX_VALUE)%(NUM_LOCKS))];
643 return lock;
644 }
645
646 private int incrementHashedLocal(long key, int amt){
647 final int num=(int)(key&arrayMask);
648 final AtomicIntegerArray array=matrix[num];
649 key=(key>>>arrayBits)%(cellMod);
650 // key=(key>>>(arrayBits+1))%(cellMod);
651 int index=(int)(key>>>indexShift);
652 int cellShift=(int)(cellBits*key);
653 int value, word, word2;
654 do{
655 assert(index>=0) : key+", "+cellMod+", "+cellBits+", "+valueMask+", "+arrayMask+", "+index+", "+num;
656 word=array.get(index);
657 value=((word>>>cellShift)&valueMask);
658 value=(int)min(value+(long)amt, maxValue);
659 word2=(value<<cellShift)|(word&~((valueMask)<<cellShift));
660 }while(word!=word2 && !array.compareAndSet(index, word, word2));
661 // if(value==1){cellsUsedPersonal.incrementAndGet(num);}
662 return value;
663 }
664
665 // private int incrementHashedLocal_ifAtMost(long key, final int thresh){
666 // final int num=(int)(key&arrayMask);
667 // final AtomicIntegerArray array=matrix[num];
668 // key=(key>>>arrayBits)%(cellMod);
669 //// key=(key>>>(arrayBits+1))%(cellMod);
670 // int index=(int)(key>>>indexShift);
671 // int cellShift=(int)(cellBits*key);
672 // int value, word, word2;
673 // do{
674 // assert(index>=0) : key+", "+cellMod+", "+cellBits+", "+valueMask+", "+arrayMask+", "+index+", "+num;
675 // word=array.get(index);
676 // value=((word>>>cellShift)&valueMask);
677 // if(value>thresh){return value;}//Too high; don't increment
678 // value=min(value+1, maxValue);
679 // word2=(value<<cellShift)|(word&~((valueMask)<<cellShift));
680 // }while(word!=word2 && !array.compareAndSet(index, word, word2));
681 // return value;
682 // }
683
684 private int incrementHashedLocal_toAtLeast(long key, final int newMin){
685 assert(newMin<=maxValue);
686 final int num=(int)(key&arrayMask);
687 final AtomicIntegerArray array=matrix[num];
688 key=(key>>>arrayBits)%(cellMod);
689 // key=(key>>>(arrayBits+1))%(cellMod);
690 int index=(int)(key>>>indexShift);
691 int cellShift=(int)(cellBits*key);
692 int value, word, word2;
693 do{
694 assert(index>=0) : key+", "+cellMod+", "+cellBits+", "+valueMask+", "+arrayMask+", "+index+", "+num;
695 word=array.get(index);
696 value=((word>>>cellShift)&valueMask);
697 if(value>=newMin){return value;}//Too high; don't increment
698 value=min(value+1, maxValue);
699 word2=(value<<cellShift)|(word&~((valueMask)<<cellShift));
700 }while(word!=word2 && !array.compareAndSet(index, word, word2));
701 return value;
702 }
703
704 private int incrementHashedLocalAndReturnUnincremented(long key, int incr){
705 assert(incr>=0);
706 final int num=(int)(key&arrayMask);
707 final AtomicIntegerArray array=matrix[num];
708 key=(key>>>arrayBits)%(cellMod);
709 // key=(key>>>(arrayBits+1))%(cellMod);
710 int index=(int)(key>>>indexShift);
711 int cellShift=(int)(cellBits*key);
712 int value, word, word2;
713 do{
714 word=array.get(index);
715 value=((word>>>cellShift)&valueMask);
716 int value2=min(value+incr, maxValue);
717 word2=(value2<<cellShift)|(word&~((valueMask)<<cellShift));
718 }while(word!=word2 && !array.compareAndSet(index, word, word2));
719 // if(value==1){cellsUsedPersonal.incrementAndGet(num);}
720 return value;
721 }
722
723 // private int incrementHashedLocalAndReturnUnincremented_ifAtMost(long key, int incr, final int thresh){
724 // assert(incr>=0);
725 // final int num=(int)(key&arrayMask);
726 // final AtomicIntegerArray array=matrix[num];
727 // key=(key>>>arrayBits)%(cellMod);
728 //// key=(key>>>(arrayBits+1))%(cellMod);
729 // int index=(int)(key>>>indexShift);
730 // int cellShift=(int)(cellBits*key);
731 // int value, word, word2;
732 // do{
733 // word=array.get(index);
734 // value=((word>>>cellShift)&valueMask);
735 // if(value>thresh){return value;}//Too high; don't increment
736 // int value2=min(value+incr, maxValue);
737 // word2=(value2<<cellShift)|(word&~((valueMask)<<cellShift));
738 // }while(word!=word2 && !array.compareAndSet(index, word, word2));
739 //// if(value==1){cellsUsedPersonal.incrementAndGet(num);}
740 // return value;
741 // }
742
743 private int incrementHashedLocalAndReturnUnincremented_toAtLeast(long key, int newMin){
744 assert(newMin>0 && newMin<=maxValue) : newMin;
745 final int num=(int)(key&arrayMask);
746 final AtomicIntegerArray array=matrix[num];
747 key=(key>>>arrayBits)%(cellMod);
748 // key=(key>>>(arrayBits+1))%(cellMod);
749 int index=(int)(key>>>indexShift);
750 int cellShift=(int)(cellBits*key);
751 int value, word, word2;
752 final int value2s=newMin<<cellShift;
753 do{
754 word=array.get(index);
755 value=((word>>>cellShift)&valueMask);
756 if(value>=newMin){return value;}//Too high; don't increment
757 word2=value2s|(word&~((valueMask)<<cellShift));
758 }while(word!=word2 && !array.compareAndSet(index, word, word2));
759 // if(value==1){cellsUsedPersonal.incrementAndGet(num);}
760 return value;
761 }
762
763 private int decrementHashedLocal(long key, int amt){
764 final int num=(int)(key&arrayMask);
765 final AtomicIntegerArray array=matrix[num];
766 key=(key>>>arrayBits)%(cellMod);
767 // key=(key>>>(arrayBits+1))%(cellMod);
768 int index=(int)(key>>>indexShift);
769 int cellShift=(int)(cellBits*key);
770 int value, word, word2;
771 do{
772 word=array.get(index);
773 value=((word>>>cellShift)&valueMask);
774 value=max(value-amt, 0);
775 word2=(value<<cellShift)|(word&~((valueMask)<<cellShift));
776 }while(word!=word2 && !array.compareAndSet(index, word, word2));
777 // if(value==1){cellsUsedPersonal.incrementAndGet(num);}
778 return value;
779 }
780
781 public long cellsUsed(){
782 if(cellsUsed<0){
783 synchronized(this){
784 if(cellsUsed<0){
785 cellsUsed=cellsUsed(1);
786 }
787 }
788 }
789 return cellsUsed;
790 }
791
792 @Override
793 public KCountArray prefilter(){
794 return prefilter;
795 }
796
797 @Override
798 public void purgeFilter(){
799 prefilter=null;
800 }
801
802 public static synchronized void setSeed(long seed){
803 if(seed>=0){SEEDMASK=seed;}
804 else{
805 Random randy=new Random();
806 SEEDMASK=randy.nextLong();
807 }
808 }
809
810 private boolean finished=false;
811
812 private long cellsUsed;
813 private final AtomicIntegerArray[] matrix;
814 private final int hashes;
815 private final int wordsPerArray;
816 private final long cellsPerArray;
817 private final long cellMod;
818 private final long[][] hashMasks=makeMasks(8, hashArrayLength);
819 private final int prefilterLimit;
820
821 private static final int hashBits=6;
822 private static final int hashArrayLength=1<<hashBits;
823 private static final int hashCellMask=hashArrayLength-1;
824
825 private KCountArray prefilter;
826
827 private final transient boolean useLocks;
828 private final transient Lock[] locks;
829 private static final transient int NUM_LOCKS=1999;
830
831 private static long counter=0;
832 private static long SEEDMASK=0;
833
834 }