Mercurial > repos > rliterman > csp2

comparison CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/opt/bbmap-39.01-1/current/kmer/HashArray2D.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 kmer;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5
6 import shared.KillSwitch;
7 import shared.Primes;
8 import shared.Shared;
9 import shared.Tools;
10
11 /**
12 * Stores kmers in a long[] and values in an int[][], with a victim cache.
13 * @author Brian Bushnell
14 * @date Nov 7, 2014
15 *
16 */
17 public final class HashArray2D extends HashArray {
18
19 /*--------------------------------------------------------------*/
20 /*---------------- Initialization ----------------*/
21 /*--------------------------------------------------------------*/
22
23 public HashArray2D(int[] schedule_, long coreMask_){
24 super(schedule_, coreMask_, true);
25 values=allocInt2D(prime+extra);
26 }
27
28 // public HashArray2D(int initialSize, int maxSize, long mask, boolean autoResize_){
29 // super(initialSize, maxSize, mask, autoResize_, true);
30 // values=allocInt2D(prime+extra);
31 // }
32
33 /*--------------------------------------------------------------*/
34 /*---------------- Public Methods ----------------*/
35 /*--------------------------------------------------------------*/
36
37 @Deprecated
38 @Override
39 public int increment(final long kmer, final int incr){
40 throw new RuntimeException("Unsupported.");
41 }
42
43 @Deprecated
44 @Override
45 public int incrementAndReturnNumCreated(final long kmer, final int incr){
46 throw new RuntimeException("Unsupported.");
47 }
48
49 /*--------------------------------------------------------------*/
50 /*---------------- Nonpublic Methods ----------------*/
51 /*--------------------------------------------------------------*/
52
53 @Override
54 protected final int readCellValue(int cell) {
55 int[] set=values[cell];
56 return set==null ? 0 : set[0];
57 }
58
59 @Override
60 protected final int[] readCellValues(int cell, int[] singleton) {
61 return values[cell];
62 }
63
64 /** Returns number of values added */
65 @Override
66 protected final void insertValue(final long kmer, final int v, final int cell){
67 assert(array[cell]==kmer);
68 if(values[cell]==null){
69 values[cell]=new int[] {v, NOT_PRESENT};
70 return;
71 }
72 int[] set=values[cell];
73 assert(set!=null);
74
75 for(int i=0; i<set.length; i++){
76 if(set[i]==v){return;}
77 else if(set[i]<0){set[i]=v;return;}
78 }
79 final int oldSize=set.length;
80 final int newSize=(int)Tools.min(Shared.MAX_ARRAY_LEN, oldSize*2L);
81 assert(newSize>set.length) : "Overflow.";
82 set=KillSwitch.copyOf(set, newSize);
83 set[oldSize]=v;
84 Arrays.fill(set, oldSize+1, newSize, NOT_PRESENT);
85 values[cell]=set;
86 }
87
88 /** Returns number of values added */
89 @Override
90 protected final void insertValue(final long kmer, final int[] vals, final int cell, final int vlen){
91 assert(array[cell]==kmer);
92 if(values[cell]==null){
93 values[cell]=vals;
94 }else{
95 for(int v : vals){
96 if(v<0){break;}
97 insertValue(kmer, v, cell);
98 }
99 }
100 }
101
102 /*--------------------------------------------------------------*/
103 /*---------------- Resizing and Rebalancing ----------------*/
104 /*--------------------------------------------------------------*/
105
106 @Override
107 public final boolean canRebalance() {return false;}
108
109 @Override
110 protected synchronized void resize(){
111 // assert(false);
112 // System.err.println("Resizing from "+prime+"; load="+(size*1f/prime));
113 if(prime>=maxPrime){
114 // sizeLimit=0xFFFFFFFFFFFFL;
115 // return;
116 KillSwitch.memKill(new OutOfMemoryError());
117 }
118
119 final long oldSize=size, oldVSize=victims.size;
120 if(schedule!=null){
121 final long oldPrime=prime;
122 prime=nextScheduleSize();
123 if(prime<=oldPrime){KillSwitch.memKill(new OutOfMemoryError());}
124 sizeLimit=(long)((atMaxSize() ? maxLoadFactorFinal : maxLoadFactor)*prime);
125 }else{//Old method
126 final long totalSize=oldSize+oldVSize;
127
128 final long maxAllowedByLoadFactor=(long)(totalSize*minLoadMult);
129 final long minAllowedByLoadFactor=(long)(totalSize*maxLoadMult);
130
131 // sizeLimit=Tools.min((long)(maxLoadFactor*prime), maxPrime);
132
133 assert(maxAllowedByLoadFactor>=minAllowedByLoadFactor);
134 if(maxAllowedByLoadFactor<prime){
135 sizeLimit=(long)(maxLoadFactor*prime);
136 return;
137 }
138
139 long x=10+(long)(prime*resizeMult);
140 x=Tools.max(x, minAllowedByLoadFactor);
141 x=Tools.min(x, maxAllowedByLoadFactor);
142
143 int prime2=(int)Tools.min(maxPrime, Primes.primeAtLeast(x));
144
145 if(prime2<=prime){
146 sizeLimit=(long)(maxLoadFactor*prime);
147 assert(prime2==prime) : "Resizing to smaller array? "+totalSize+", "+prime+", "+x;
148 return;
149 }
150 // System.err.println("Resizing from "+prime+" to "+prime2+"; size="+size);
151
152 prime=prime2;
153 sizeLimit=(long)(maxLoadFactor*prime);
154 }
155
156 // System.err.println("Resized to "+prime+"; load="+(size*1f/prime));
157 long[] oldk=array;
158 int[][] oldc=values;
159 KmerNode[] oldv=victims.array;
160 array=allocLong1D(prime+extra);
161 Arrays.fill(array, NOT_PRESENT);
162 values=allocInt2D(prime+extra);
163 ArrayList<KmerNode> list=new ArrayList<KmerNode>((int)(victims.size)); //Can fail if more than Integer.MAX_VALUE
164 for(int i=0; i<oldv.length; i++){
165 if(oldv[i]!=null){oldv[i].traverseInfix(list);}
166 }
167 Arrays.fill(oldv, null);
168 victims.size=0;
169 size=0;
170
171 final int[] singleton=new int[] {NOT_PRESENT};
172
173 for(int i=0; i<oldk.length; i++){
174 if(oldk[i]>NOT_PRESENT){
175 // assert(!contains(oldk[i]));
176 set(oldk[i], oldc[i], -1);
177 // assert(contains(oldk[i]));
178 // assert(Tools.equals(getValues(oldk[i], singleton), oldc[i]));
179 }
180 }
181
182 for(KmerNode n : list){
183 if(n.pivot>NOT_PRESENT){
184 // assert(!contains(n.pivot));
185 set(n.pivot, n.values(singleton), n.numValues());
186 // assert(contains(n.pivot));
187 // assert(Tools.equals(getValues(n.pivot, singleton), n.values(singleton)));
188 }
189 }
190
191 assert(oldSize+oldVSize==size+victims.size) : oldSize+", "+oldVSize+" -> "+size+", "+victims.size;
192 }
193
194 @Deprecated
195 @Override
196 public void rebalance(){
197 throw new RuntimeException("Unimplemented.");
198 }
199
200 @Deprecated
201 @Override
202 public long regenerate(final int limit){
203 assert(false) : "This is not tested or intended for use.";
204 long sum=0;
205 assert(owners==null) : "Clear ownership before regeneration.";
206 for(int pos=0; pos<values.length; pos++){
207 final long key=array[pos];
208 if(key>=0){
209 final int[] value=values[pos];
210 values[pos]=null;
211 array[pos]=NOT_PRESENT;
212 size--;
213 if(value!=null){
214 assert(value[0]>0);
215 set(key, value, -1);
216 }else{
217 sum++;
218 }
219 }
220 }
221
222 ArrayList<KmerNode> nodes=victims.toList();
223 victims.clear();
224 for(KmerNode node : nodes){
225 set(node.pivot, node.values(null), node.numValues());//TODO: Probably unsafe or unwise. Should test for singletons, etc.
226 }
227
228 return sum;
229 }
230
231 /*--------------------------------------------------------------*/
232 /*---------------- Fields ----------------*/
233 /*--------------------------------------------------------------*/
234
235 private int[][] values;
236
237
238
239 }