1 package ukmer; 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 HashArrayU2D extends HashArrayU { 18 19 /*--------------------------------------------------------------*/ 20 /*---------------- Initialization ----------------*/ 21 /*--------------------------------------------------------------*/ 22 HashArrayU2D(int[] schedule_, int k_, int kbig_)23 public HashArrayU2D(int[] schedule_, int k_, int kbig_){ 24 super(schedule_, k_, kbig_, true); 25 values=allocInt2D(prime+extra); 26 } 27 28 // public HashArrayU2D(int initialSize, int k_, int kbig_, boolean autoResize_){ 29 // super(initialSize, k_, kbig_, autoResize_, true); 30 // values=allocInt2D(prime+extra); 31 // } 32 33 /*--------------------------------------------------------------*/ 34 /*---------------- Public Methods ----------------*/ 35 /*--------------------------------------------------------------*/ 36 37 @Deprecated 38 @Override increment(final Kmer kmer)39 public int increment(final Kmer kmer){ 40 throw new RuntimeException("Unsupported."); 41 } 42 43 @Deprecated 44 @Override incrementAndReturnNumCreated(final Kmer kmer)45 public int incrementAndReturnNumCreated(final Kmer kmer){ 46 throw new RuntimeException("Unsupported."); 47 } 48 49 /*--------------------------------------------------------------*/ 50 /*---------------- Nonpublic Methods ----------------*/ 51 /*--------------------------------------------------------------*/ 52 53 @Override readCellValue(int cell)54 protected final int readCellValue(int cell) { 55 int[] set=values[cell]; 56 return set==null ? 0 : set[0]; 57 } 58 59 @Override readCellValues(int cell, int[] singleton)60 protected final int[] readCellValues(int cell, int[] singleton) { 61 return values[cell]; 62 } 63 64 /** Returns number of values added */ 65 @Override insertValue(final long[] kmer, final int v, final int cell)66 protected final void insertValue(final long[] kmer, final int v, final int cell){ 67 assert(matches(kmer, cell)); 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 insertValue(final long[] kmer, final int[] vals, final int cell)90 protected final void insertValue(final long[] kmer, final int[] vals, final int cell){ 91 assert(matches(kmer, cell)); 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 canRebalance()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 // } 117 // 118 // final long oldSize=size, oldVSize=victims.size; 119 // final long totalSize=oldSize+oldVSize; 120 // 121 // final long maxAllowedByLoadFactor=(long)(totalSize*minLoadMult); 122 // final long minAllowedByLoadFactor=(long)(totalSize*maxLoadMult); 123 // 124 //// sizeLimit=Tools.min((long)(maxLoadFactor*prime), maxPrime); 125 // 126 // assert(maxAllowedByLoadFactor>=minAllowedByLoadFactor); 127 // if(maxAllowedByLoadFactor<prime){ 128 // sizeLimit=(long)(maxLoadFactor*prime); 129 // return; 130 // } 131 // 132 // long x=10+(long)(prime*resizeMult); 133 // x=Tools.max(x, minAllowedByLoadFactor); 134 // x=Tools.min(x, maxAllowedByLoadFactor); 135 // 136 // int prime2=(int)Tools.min(maxPrime, Primes.primeAtLeast(x)); 137 // 138 // if(prime2<=prime){ 139 // sizeLimit=(long)(maxLoadFactor*prime); 140 // assert(prime2==prime) : "Resizing to smaller array? "+totalSize+", "+prime+", "+x; 141 // return; 142 // } 143 //// System.err.println("Resizing from "+prime+" to "+prime2+"; size="+size); 144 // 145 // prime=prime2; 146 //// System.err.println("Resized to "+prime+"; load="+(size*1f/prime)); 147 // long[][] oldk=arrays; 148 // int[][] oldc=values; 149 // arrays=allocLong2D(mult, prime2+extra); 150 // for(int i=0; i<mult; i++){ 151 // Arrays.fill(arrays[i], NOT_PRESENT); 152 // } 153 // values=allocInt2D(prime2+extra); 154 // ArrayList<KmerNodeU> list=victims.toList(); 155 // victims.clear(); 156 // size=0; 157 // sizeLimit=Long.MAX_VALUE; 158 // 159 // final int[] singleton=new int[] {NOT_PRESENT}; 160 // final Kmer kmer=new Kmer(kbig); 161 // { 162 // for(int i=0; i<oldk.length; i++){ 163 // if(oldk[0][i]>NOT_PRESENT){ 164 // set(fillKmer(i, kmer, oldk), oldc[i]); 165 // } 166 // } 167 // } 168 // 169 // for(KmerNodeU n : list){ 170 // if(n.pivot[0]>NOT_PRESENT){ 171 // kmer.setFrom(n.pivot()); 172 // set(kmer, n.values(singleton)); 173 // } 174 // else{assert(false);} 175 // } 176 // 177 // assert(oldSize+oldVSize==size+victims.size) : oldSize+", "+oldVSize+" -> "+size+", "+victims.size; 178 // 179 // sizeLimit=(long)(maxLoadFactor*prime); 180 // } 181 182 183 @Override resize()184 protected synchronized void resize(){ 185 if(verbose){System.err.println("Resizing from "+prime+"; load="+(size*1f/prime));} 186 if(prime>=maxPrime){ 187 // sizeLimit=0xFFFFFFFFFFFFL; 188 // return; 189 KillSwitch.memKill(new OutOfMemoryError()); 190 } 191 192 final int oldPrime=prime; 193 final long oldSize=size, oldVSize=victims.size; 194 final long totalSize=oldSize+oldVSize; 195 196 if(schedule!=null){ 197 prime=nextScheduleSize(); 198 if(prime<=oldPrime){KillSwitch.memKill(new OutOfMemoryError());} 199 sizeLimit=(long)((atMaxSize() ? maxLoadFactorFinal : maxLoadFactor)*prime); 200 }else{//Old method 201 final long maxAllowedByLoadFactor=(long)(totalSize*minLoadMult); 202 final long minAllowedByLoadFactor=(long)(totalSize*maxLoadMult); 203 204 // sizeLimit=Tools.min((long)(maxLoadFactor*prime), maxPrime); 205 206 assert(maxAllowedByLoadFactor>=minAllowedByLoadFactor); 207 if(maxAllowedByLoadFactor<prime){ 208 sizeLimit=(long)(maxLoadFactor*prime); 209 return; 210 } 211 212 long x=10+(long)(prime*resizeMult); 213 x=Tools.max(x, minAllowedByLoadFactor); 214 x=Tools.min(x, maxAllowedByLoadFactor); 215 216 int prime2=(int)Tools.min(maxPrime, Primes.primeAtLeast(x)); 217 218 if(prime2<=prime){ 219 sizeLimit=(long)(maxLoadFactor*prime); 220 assert(prime2==prime) : "Resizing to smaller array? "+totalSize+", "+prime+", "+x; 221 return; 222 } 223 224 prime=prime2; 225 sizeLimit=(long)(maxLoadFactor*prime); 226 } 227 228 // System.err.println("Resized to "+prime+"; load="+(size*1f/prime)); 229 long[][] oldk=arrays; 230 int[][] oldc=values; 231 arrays=allocLong2D(mult, prime+extra); 232 for(int i=0; i<mult; i++){ 233 Arrays.fill(arrays[i], NOT_PRESENT); 234 } 235 values=allocInt2D(prime+extra); 236 ArrayList<KmerNodeU> list=victims.toList(); 237 victims.clear(); 238 size=0; 239 240 final int[] singleton=new int[] {NOT_PRESENT}; 241 final Kmer kmer=new Kmer(kbig); 242 { 243 for(int i=0; i<oldk.length; i++){ 244 if(oldk[0][i]>NOT_PRESENT){ 245 set(fillKmer(i, kmer, oldk), oldc[i]); 246 } 247 } 248 } 249 250 for(KmerNodeU n : list){ 251 if(n.pivot[0]>NOT_PRESENT){ 252 kmer.setFrom(n.pivot()); 253 set(kmer, n.values(singleton)); 254 } 255 else{assert(false);} 256 } 257 258 assert(oldSize+oldVSize==size+victims.size) : oldSize+", "+oldVSize+" -> "+size+", "+victims.size; 259 } 260 261 @Deprecated 262 @Override rebalance()263 public void rebalance(){ 264 throw new RuntimeException("Unimplemented."); 265 } 266 267 @Deprecated 268 @Override regenerate(final int limit)269 public long regenerate(final int limit){ 270 assert(false) : "This is not tested or intended for use."; 271 long sum=0; 272 assert(owners==null) : "Clear ownership before regeneration."; 273 final Kmer kmer=new Kmer(kbig); 274 for(int pos=0; pos<values.length; pos++){ 275 Kmer key=fillKmer(pos, kmer); 276 if(key!=null){ 277 final int[] value=values[pos]; 278 values[pos]=null; 279 arrays[0][pos]=NOT_PRESENT; 280 size--; 281 if(value!=null){ 282 assert(value[0]>0); 283 set(key, value); 284 }else{ 285 sum++; 286 } 287 } 288 } 289 290 ArrayList<KmerNodeU> nodes=victims.toList(); 291 victims.clear(); 292 for(KmerNodeU node : nodes){ 293 int value=node.value(); 294 if(value<1){ 295 sum++; 296 }else{ 297 kmer.setFrom(node.pivot()); 298 set(kmer, node.values(null));//TODO: Probably unsafe or unwise. Should test for singletons, etc. 299 } 300 } 301 302 return sum; 303 } 304 305 /*--------------------------------------------------------------*/ 306 /*---------------- Fields ----------------*/ 307 /*--------------------------------------------------------------*/ 308 309 private int[][] values; 310 311 312 313 } 314