001/*
002 * Copyright (c) 2007-2016 Concurrent, 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  }