001/* 002 * Copyright (c) 2007-2017 Xplenty, Inc. All Rights Reserved. 003 * 004 * Project and contact information: http://www.cascading.org/ 005 * 006 * This file is part of the Cascading project. 007 * 008 * Licensed under the Apache License, Version 2.0 (the "License"); 009 * you may not use this file except in compliance with the License. 010 * You may obtain a copy of the License at 011 * 012 * http://www.apache.org/licenses/LICENSE-2.0 013 * 014 * Unless required by applicable law or agreed to in writing, software 015 * distributed under the License is distributed on an "AS IS" BASIS, 016 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 017 * See the License for the specific language governing permissions and 018 * limitations under the License. 019 */ 020 021package cascading.util.cache; 022 023import java.util.AbstractCollection; 024import java.util.AbstractSet; 025import java.util.Collection; 026import java.util.Iterator; 027import java.util.Map; 028import java.util.NoSuchElementException; 029import java.util.Set; 030 031import org.slf4j.Logger; 032import org.slf4j.LoggerFactory; 033 034/** 035 * DirectMappedCache is an implementation of the {@link cascading.util.cache.CascadingCache} interface following the semantics of 036 * http://en.wikipedia.org/wiki/CPU_cache#Direct-mapped_cache. The Cache is backed by an array that stays constant in size. 037 * <p/> 038 * Unlike other implementation of a Map a hash collision will lead to the entry being overwritten. 039 * The {@link CacheEvictionCallback} is called with the entry that will be overwritten. 040 * <p/> 041 * Use this cache if the keys are arriving in a random if not uniformly distributed order in order to reduce the number 042 * of hash and equality comparisons. 043 * <p/> 044 * If duplicate keys are clustered near each other in the incoming tuple stream, consider the {@link cascading.util.cache.LRUHashMapCache} cache 045 * instead. 046 * <p/> 047 * DirectMappedCache does not permit <code>null</code> keys nor <code>null</code> values 048 * 049 * @see cascading.pipe.assembly.Unique 050 * @see cascading.pipe.assembly.AggregateBy 051 * @see DirectMappedCacheFactory 052 * @see LRUHashMapCacheFactory 053 * @see LRUHashMapCache 054 */ 055public final class DirectMappedCache<Key, Value> implements CascadingCache<Key, Value> 056 { 057 /** logger */ 058 private static final Logger LOG = LoggerFactory.getLogger( DirectMappedCache.class ); 059 060 /** size of the backing array. */ 061 private int capacity; 062 063 /** number of actual key in the map. */ 064 private int actualSize = 0; 065 066 /** array used for storing the entries */ 067 private Entry<Key, Value>[] elements; 068 069 private long collisions = 0; 070 071 private long putCalls = 0; 072 073 public boolean initialized = false; 074 075 /** callback that is called whenever an entry is overwritten or removed from the cache. */ 076 private CacheEvictionCallback evictionCallBack = CacheEvictionCallback.NULL; 077 078 @Override 079 public int size() 080 { 081 return actualSize; 082 } 083 084 @Override 085 public boolean isEmpty() 086 { 087 return actualSize < 1; 088 } 089 090 @Override 091 public boolean containsKey( Object key ) 092 { 093 if( key == null ) 094 throw new IllegalArgumentException( "null keys are not permitted" ); 095 096 return get( key ) != null; 097 } 098 099 @Override 100 public boolean containsValue( Object value ) 101 { 102 if( value == null ) 103 throw new IllegalArgumentException( "value cannot be null" ); 104 105 Iter<Entry<Key, Value>> iter = new Iter<Entry<Key, Value>>( elements ); 106 107 while( iter.hasNext() ) 108 { 109 Value current = iter.next().getValue(); 110 if( current.equals( value ) ) 111 return true; 112 } 113 114 return false; 115 } 116 117 @Override 118 public Value get( Object key ) 119 { 120 int index = index( key ); 121 Entry<Key, Value> existing = elements[ index ]; 122 123 if( existing == null || !key.equals( existing.getKey() ) ) 124 return null; 125 126 return existing.getValue(); 127 } 128 129 @Override 130 public Value put( Key key, Value value ) 131 { 132 if( key == null ) 133 throw new IllegalArgumentException( "key cannot be null" ); 134 135 if( value == null ) 136 throw new IllegalArgumentException( "value cannot be null" ); 137 138 putCalls++; 139 140 Value previous = null; 141 int index = index( key ); 142 Entry<Key, Value> existing = elements[ index ]; 143 144 if( existing != null ) 145 { 146 previous = existing.getValue(); 147 collisions++; 148 evictionCallBack.evict( existing ); 149 } 150 else 151 actualSize++; 152 153 elements[ index ] = new CacheEntry<Key, Value>( key, value ); 154 155 if( putCalls % getCapacity() == 0 ) 156 { 157 Runtime runtime = Runtime.getRuntime(); 158 long freeMem = runtime.freeMemory() / 1024 / 1024; 159 long maxMem = runtime.maxMemory() / 1024 / 1024; 160 long totalMem = runtime.totalMemory() / 1024 / 1024; 161 LOG.info( "mem on flush (mb), free: " + freeMem + ", total: " + totalMem + ", max: " + maxMem ); 162 LOG.info( "capacity={}, puts={}, collisions={}, fill factor={}%", getCapacity(), putCalls, collisions, 163 ( (double) getCapacity() / actualSize ) * 100 ); 164 float percent = (float) totalMem / (float) maxMem; 165 if( percent < 0.80F ) 166 LOG.info( "total mem is {}% of max mem, to better utilize unused memory consider increasing the cache size", (int) ( percent * 100.0F ) ); 167 } 168 169 return previous; 170 } 171 172 private int index( Object key ) 173 { 174 return Math.abs( key.hashCode() % capacity ); 175 } 176 177 @Override 178 public Value remove( Object key ) 179 { 180 if( key == null ) 181 throw new IllegalArgumentException( "key cannot be null" ); 182 183 int index = index( key ); 184 Entry<Key, Value> existing = elements[ index ]; 185 186 if( existing == null || !existing.getKey().equals( key ) ) 187 return null; 188 189 elements[ index ] = null; 190 actualSize--; 191 evictionCallBack.evict( existing ); 192 193 return existing.getValue(); 194 } 195 196 @Override 197 public void putAll( Map<? extends Key, ? extends Value> m ) 198 { 199 for( Entry<? extends Key, ? extends Value> entry : m.entrySet() ) 200 put( entry.getKey(), entry.getValue() ); 201 } 202 203 @Override 204 public void clear() 205 { 206 elements = new CacheEntry[ capacity ]; 207 actualSize = 0; 208 } 209 210 @Override 211 public Set<Key> keySet() 212 { 213 return new KeySetView<Key>( new SetView<Map.Entry<Key, ?>>( elements, actualSize ) ); 214 } 215 216 @Override 217 public Collection<Value> values() 218 { 219 return new ValueCollection( new SetView<Map.Entry<?, Value>>( elements, actualSize ) ); 220 } 221 222 @Override 223 public Set<Map.Entry<Key, Value>> entrySet() 224 { 225 return new SetView<Entry<Key, Value>>( elements, actualSize ); 226 } 227 228 @Override 229 public int getCapacity() 230 { 231 return capacity; 232 } 233 234 @Override 235 public void setCacheEvictionCallback( CacheEvictionCallback cacheEvictionCallback ) 236 { 237 if( initialized ) 238 throw new IllegalStateException( "cannot set callback after initialization" ); 239 240 this.evictionCallBack = cacheEvictionCallback; 241 } 242 243 @Override 244 public void setCapacity( int capacity ) 245 { 246 if( initialized ) 247 throw new IllegalArgumentException( "cannot set size after initialization" ); 248 249 this.capacity = capacity; 250 } 251 252 @Override 253 public void initialize() 254 { 255 if( capacity < 1 ) 256 throw new IllegalStateException( "capacity must be larger than 0" ); 257 258 if( evictionCallBack == null ) 259 throw new IllegalStateException( "evictionCallback cannot be null" ); 260 261 elements = new CacheEntry[ capacity ]; 262 initialized = true; 263 } 264 265 static class CacheEntry<Key, Value> implements Entry<Key, Value> 266 { 267 private final Key key; 268 private Value value; 269 270 CacheEntry( Key key, Value value ) 271 { 272 this.key = key; 273 this.value = value; 274 } 275 276 @Override 277 public Key getKey() 278 { 279 return key; 280 } 281 282 @Override 283 public Value getValue() 284 { 285 return value; 286 } 287 288 @Override 289 public Value setValue( Value value ) 290 { 291 Value oldValue = this.value; 292 this.value = value; 293 return oldValue; 294 } 295 296 @Override 297 public boolean equals( Object object ) 298 { 299 if( this == object ) 300 return true; 301 if( object == null || getClass() != object.getClass() ) 302 return false; 303 304 Entry that = (Entry) object; 305 306 if( key != null ? !key.equals( that.getKey() ) : that.getKey() != null ) 307 return false; 308 309 if( value != null ? !value.equals( that.getValue() ) : that.getValue() != null ) 310 return false; 311 312 return true; 313 } 314 315 @Override 316 public int hashCode() 317 { 318 int result = key != null ? key.hashCode() : 0; 319 result = 31 * result + ( value != null ? value.hashCode() : 0 ); 320 return result; 321 } 322 323 @Override 324 public String toString() 325 { 326 return "CacheEntry{" + 327 "key=" + key + 328 ", value=" + value + 329 '}'; 330 } 331 } 332 333 class SetView<T> extends AbstractSet<T> 334 { 335 private final T[] elements; 336 private final int size; 337 private final Iter<T> iter; 338 339 SetView( T[] elements, int size ) 340 { 341 this.elements = elements; 342 this.size = size; 343 this.iter = new Iter<T>( elements ); 344 } 345 346 @Override 347 public int size() 348 { 349 return size; 350 } 351 352 @Override 353 public Iterator<T> iterator() 354 { 355 return new Iter<T>( elements ); 356 } 357 358 @Override 359 public boolean containsAll( Collection<?> c ) 360 { 361 for( Object object : c ) 362 { 363 if( !contains( object ) ) 364 return false; 365 } 366 367 return true; 368 } 369 370 @Override 371 public boolean addAll( Collection<? extends T> c ) 372 { 373 throw new UnsupportedOperationException( "SetView is read only." ); 374 } 375 376 @Override 377 public boolean retainAll( Collection<?> c ) 378 { 379 throw new UnsupportedOperationException( "SetView is read only." ); 380 } 381 382 @Override 383 public boolean removeAll( Collection<?> c ) 384 { 385 throw new UnsupportedOperationException( "SetView is read only." ); 386 } 387 388 @Override 389 public void clear() 390 { 391 throw new UnsupportedOperationException( "SetView is read only." ); 392 } 393 } 394 395 static class Iter<T> implements Iterator<T> 396 { 397 private final T[] elements; 398 private T nextElement; 399 int currentIndex = -1; 400 401 public Iter( T[] elements ) 402 { 403 this.elements = elements; 404 this.nextElement = findNext(); 405 } 406 407 private T findNext() 408 { 409 while( currentIndex < elements.length - 1 ) 410 { 411 currentIndex++; 412 413 if( elements[ currentIndex ] != null ) 414 return elements[ currentIndex ]; 415 } 416 417 return null; 418 } 419 420 @Override 421 public boolean hasNext() 422 { 423 return nextElement != null; 424 } 425 426 @Override 427 public T next() 428 { 429 if( !hasNext() ) 430 throw new NoSuchElementException(); 431 432 T current = nextElement; 433 434 nextElement = findNext(); 435 436 return current; 437 } 438 439 @Override 440 public void remove() 441 { 442 throw new UnsupportedOperationException( "Not supported" ); 443 } 444 445 public void reset() 446 { 447 currentIndex = -1; 448 nextElement = findNext(); 449 } 450 } 451 452 static class KeySetView<Key> extends AbstractSet<Key> 453 { 454 private final Set<Map.Entry<Key, ?>> parent; 455 456 public KeySetView( Set<Map.Entry<Key, ?>> parent ) 457 { 458 this.parent = parent; 459 } 460 461 @Override 462 public Iterator<Key> iterator() 463 { 464 return new KeyIterator<Key>( parent.iterator() ); 465 } 466 467 @Override 468 public int size() 469 { 470 return parent.size(); 471 } 472 } 473 474 static class ValueCollection<Value> extends AbstractCollection<Value> 475 { 476 private Set<Entry<?, Value>> parent; 477 478 ValueCollection( Set<Entry<?, Value>> parent ) 479 { 480 this.parent = parent; 481 } 482 483 @Override 484 public Iterator<Value> iterator() 485 { 486 return new ValueIterator<Value>( parent.iterator() ); 487 } 488 489 @Override 490 public int size() 491 { 492 return parent.size(); 493 } 494 } 495 496 static class KeyIterator<Key> implements Iterator<Key> 497 { 498 private final Iterator<Map.Entry<Key, ?>> parent; 499 500 public KeyIterator( Iterator<Map.Entry<Key, ?>> parent ) 501 { 502 this.parent = parent; 503 } 504 505 @Override 506 public Key next() 507 { 508 return parent.next().getKey(); 509 } 510 511 @Override 512 public boolean hasNext() 513 { 514 return parent.hasNext(); 515 } 516 517 @Override 518 public void remove() 519 { 520 parent.remove(); 521 } 522 } 523 524 static class ValueIterator<Value> implements Iterator<Value> 525 { 526 private final Iterator<Map.Entry<?, Value>> parent; 527 528 public ValueIterator( Iterator<Map.Entry<?, Value>> parent ) 529 { 530 this.parent = parent; 531 } 532 533 @Override 534 public Value next() 535 { 536 return parent.next().getValue(); 537 } 538 539 @Override 540 public boolean hasNext() 541 { 542 return parent.hasNext(); 543 } 544 545 @Override 546 public void remove() 547 { 548 parent.remove(); 549 } 550 } 551 }