Home | History | Annotate | Download | only in collect 
      1 /*
      2  * Copyright (C) 2007 The Guava Authors
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  * http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 package com.google.common.collect;
     18 
     19 import static com.google.common.base.Preconditions.checkNotNull;
     20 
     21 import com.google.common.annotations.GwtCompatible;
     22 import com.google.common.annotations.GwtIncompatible;
     23 import com.google.common.annotations.VisibleForTesting;
     24 
     25 import java.io.IOException;
     26 import java.io.ObjectOutputStream;
     27 import java.io.Serializable;
     28 import java.util.Collection;
     29 import java.util.Comparator;
     30 import java.util.Iterator;
     31 import java.util.List;
     32 import java.util.ListIterator;
     33 import java.util.Map;
     34 import java.util.RandomAccess;
     35 import java.util.Set;
     36 import java.util.SortedMap;
     37 import java.util.SortedSet;
     38 
     39 import javax.annotation.Nullable;
     40 
     41 /**
     42  * Synchronized collection views. The returned synchronized collection views are
     43  * serializable if the backing collection and the mutex are serializable.
     44  *
     45  * <p>If {@code null} is passed as the {@code mutex} parameter to any of this
     46  * class's top-level methods or inner class constructors, the created object
     47  * uses itself as the synchronization mutex.
     48  *
     49  * <p>This class should be used by other collection classes only.
     50  *
     51  * @author Mike Bostock
     52  * @author Jared Levy
     53  */
     54 @GwtCompatible(emulated = true)
     55 final class Synchronized {
     56   private Synchronized() {}
     57 
     58   static class SynchronizedObject implements Serializable {
     59     final Object delegate;
     60     final Object mutex;
     61 
     62     SynchronizedObject(Object delegate, @Nullable Object mutex) {
     63       this.delegate = checkNotNull(delegate);
     64       this.mutex = (mutex == null) ? this : mutex;
     65     }
     66 
     67     Object delegate() {
     68       return delegate;
     69     }
     70 
     71     // No equals and hashCode; see ForwardingObject for details.
     72 
     73     @Override public String toString() {
     74       synchronized (mutex) {
     75         return delegate.toString();
     76       }
     77     }
     78 
     79     // Serialization invokes writeObject only when it's private.
     80     // The SynchronizedObject subclasses don't need a writeObject method since
     81     // they don't contain any non-transient member variables, while the
     82     // following writeObject() handles the SynchronizedObject members.
     83 
     84     @GwtIncompatible("java.io.ObjectOutputStream")
     85     private void writeObject(ObjectOutputStream stream) throws IOException {
     86       synchronized (mutex) {
     87         stream.defaultWriteObject();
     88       }
     89     }
     90 
     91     @GwtIncompatible("not needed in emulated source")
     92     private static final long serialVersionUID = 0;
     93   }
     94 
     95   private static <E> Collection<E> collection(
     96       Collection<E> collection, @Nullable Object mutex) {
     97     return new SynchronizedCollection<E>(collection, mutex);
     98   }
     99 
    100   @VisibleForTesting static class SynchronizedCollection<E>
    101       extends SynchronizedObject implements Collection<E> {
    102     private SynchronizedCollection(
    103         Collection<E> delegate, @Nullable Object mutex) {
    104       super(delegate, mutex);
    105     }
    106 
    107     @SuppressWarnings("unchecked")
    108     @Override Collection<E> delegate() {
    109       return (Collection<E>) super.delegate();
    110     }
    111 
    112     @Override
    113     public boolean add(E e) {
    114       synchronized (mutex) {
    115         return delegate().add(e);
    116       }
    117     }
    118 
    119     @Override
    120     public boolean addAll(Collection<? extends E> c) {
    121       synchronized (mutex) {
    122         return delegate().addAll(c);
    123       }
    124     }
    125 
    126     @Override
    127     public void clear() {
    128       synchronized (mutex) {
    129         delegate().clear();
    130       }
    131     }
    132 
    133     @Override
    134     public boolean contains(Object o) {
    135       synchronized (mutex) {
    136         return delegate().contains(o);
    137       }
    138     }
    139 
    140     @Override
    141     public boolean containsAll(Collection<?> c) {
    142       synchronized (mutex) {
    143         return delegate().containsAll(c);
    144       }
    145     }
    146 
    147     @Override
    148     public boolean isEmpty() {
    149       synchronized (mutex) {
    150         return delegate().isEmpty();
    151       }
    152     }
    153 
    154     @Override
    155     public Iterator<E> iterator() {
    156       return delegate().iterator(); // manually synchronized
    157     }
    158 
    159     @Override
    160     public boolean remove(Object o) {
    161       synchronized (mutex) {
    162         return delegate().remove(o);
    163       }
    164     }
    165 
    166     @Override
    167     public boolean removeAll(Collection<?> c) {
    168       synchronized (mutex) {
    169         return delegate().removeAll(c);
    170       }
    171     }
    172 
    173     @Override
    174     public boolean retainAll(Collection<?> c) {
    175       synchronized (mutex) {
    176         return delegate().retainAll(c);
    177       }
    178     }
    179 
    180     @Override
    181     public int size() {
    182       synchronized (mutex) {
    183         return delegate().size();
    184       }
    185     }
    186 
    187     @Override
    188     public Object[] toArray() {
    189       synchronized (mutex) {
    190         return delegate().toArray();
    191       }
    192     }
    193 
    194     @Override
    195     public <T> T[] toArray(T[] a) {
    196       synchronized (mutex) {
    197         return delegate().toArray(a);
    198       }
    199     }
    200 
    201     private static final long serialVersionUID = 0;
    202   }
    203 
    204   @VisibleForTesting static <E> Set<E> set(Set<E> set, @Nullable Object mutex) {
    205     return new SynchronizedSet<E>(set, mutex);
    206   }
    207 
    208   static class SynchronizedSet<E>
    209       extends SynchronizedCollection<E> implements Set<E> {
    210 
    211     SynchronizedSet(Set<E> delegate, @Nullable Object mutex) {
    212       super(delegate, mutex);
    213     }
    214 
    215     @Override Set<E> delegate() {
    216       return (Set<E>) super.delegate();
    217     }
    218 
    219     @Override public boolean equals(Object o) {
    220       if (o == this) {
    221         return true;
    222       }
    223       synchronized (mutex) {
    224         return delegate().equals(o);
    225       }
    226     }
    227 
    228     @Override public int hashCode() {
    229       synchronized (mutex) {
    230         return delegate().hashCode();
    231       }
    232     }
    233 
    234     private static final long serialVersionUID = 0;
    235   }
    236 
    237   private static <E> SortedSet<E> sortedSet(
    238       SortedSet<E> set, @Nullable Object mutex) {
    239     return new SynchronizedSortedSet<E>(set, mutex);
    240   }
    241 
    242   static class SynchronizedSortedSet<E> extends SynchronizedSet<E>
    243       implements SortedSet<E> {
    244     SynchronizedSortedSet(SortedSet<E> delegate, @Nullable Object mutex) {
    245       super(delegate, mutex);
    246     }
    247 
    248     @Override SortedSet<E> delegate() {
    249       return (SortedSet<E>) super.delegate();
    250     }
    251 
    252     @Override
    253     public Comparator<? super E> comparator() {
    254       synchronized (mutex) {
    255         return delegate().comparator();
    256       }
    257     }
    258 
    259     @Override
    260     public SortedSet<E> subSet(E fromElement, E toElement) {
    261       synchronized (mutex) {
    262         return sortedSet(delegate().subSet(fromElement, toElement), mutex);
    263       }
    264     }
    265 
    266     @Override
    267     public SortedSet<E> headSet(E toElement) {
    268       synchronized (mutex) {
    269         return sortedSet(delegate().headSet(toElement), mutex);
    270       }
    271     }
    272 
    273     @Override
    274     public SortedSet<E> tailSet(E fromElement) {
    275       synchronized (mutex) {
    276         return sortedSet(delegate().tailSet(fromElement), mutex);
    277       }
    278     }
    279 
    280     @Override
    281     public E first() {
    282       synchronized (mutex) {
    283         return delegate().first();
    284       }
    285     }
    286 
    287     @Override
    288     public E last() {
    289       synchronized (mutex) {
    290         return delegate().last();
    291       }
    292     }
    293 
    294     private static final long serialVersionUID = 0;
    295   }
    296 
    297   private static <E> List<E> list(List<E> list, @Nullable Object mutex) {
    298     return (list instanceof RandomAccess)
    299         ? new SynchronizedRandomAccessList<E>(list, mutex)
    300         : new SynchronizedList<E>(list, mutex);
    301   }
    302 
    303   private static class SynchronizedList<E> extends SynchronizedCollection<E>
    304       implements List<E> {
    305     SynchronizedList(List<E> delegate, @Nullable Object mutex) {
    306       super(delegate, mutex);
    307     }
    308 
    309     @Override List<E> delegate() {
    310       return (List<E>) super.delegate();
    311     }
    312 
    313     @Override
    314     public void add(int index, E element) {
    315       synchronized (mutex) {
    316         delegate().add(index, element);
    317       }
    318     }
    319 
    320     @Override
    321     public boolean addAll(int index, Collection<? extends E> c) {
    322       synchronized (mutex) {
    323         return delegate().addAll(index, c);
    324       }
    325     }
    326 
    327     @Override
    328     public E get(int index) {
    329       synchronized (mutex) {
    330         return delegate().get(index);
    331       }
    332     }
    333 
    334     @Override
    335     public int indexOf(Object o) {
    336       synchronized (mutex) {
    337         return delegate().indexOf(o);
    338       }
    339     }
    340 
    341     @Override
    342     public int lastIndexOf(Object o) {
    343       synchronized (mutex) {
    344         return delegate().lastIndexOf(o);
    345       }
    346     }
    347 
    348     @Override
    349     public ListIterator<E> listIterator() {
    350       return delegate().listIterator(); // manually synchronized
    351     }
    352 
    353     @Override
    354     public ListIterator<E> listIterator(int index) {
    355       return delegate().listIterator(index); // manually synchronized
    356     }
    357 
    358     @Override
    359     public E remove(int index) {
    360       synchronized (mutex) {
    361         return delegate().remove(index);
    362       }
    363     }
    364 
    365     @Override
    366     public E set(int index, E element) {
    367       synchronized (mutex) {
    368         return delegate().set(index, element);
    369       }
    370     }
    371 
    372     @Override
    373     public List<E> subList(int fromIndex, int toIndex) {
    374       synchronized (mutex) {
    375         return list(delegate().subList(fromIndex, toIndex), mutex);
    376       }
    377     }
    378 
    379     @Override public boolean equals(Object o) {
    380       if (o == this) {
    381         return true;
    382       }
    383       synchronized (mutex) {
    384         return delegate().equals(o);
    385       }
    386     }
    387 
    388     @Override public int hashCode() {
    389       synchronized (mutex) {
    390         return delegate().hashCode();
    391       }
    392     }
    393 
    394     private static final long serialVersionUID = 0;
    395   }
    396 
    397   private static class SynchronizedRandomAccessList<E>
    398       extends SynchronizedList<E> implements RandomAccess {
    399     SynchronizedRandomAccessList(List<E> list, @Nullable Object mutex) {
    400       super(list, mutex);
    401     }
    402     private static final long serialVersionUID = 0;
    403   }
    404 
    405   static <E> Multiset<E> multiset(
    406       Multiset<E> multiset, @Nullable Object mutex) {
    407     if (multiset instanceof SynchronizedMultiset ||
    408         multiset instanceof ImmutableMultiset) {
    409       return multiset;
    410     }
    411     return new SynchronizedMultiset<E>(multiset, mutex);
    412   }
    413 
    414   private static class SynchronizedMultiset<E> extends SynchronizedCollection<E>
    415       implements Multiset<E> {
    416     transient Set<E> elementSet;
    417     transient Set<Entry<E>> entrySet;
    418 
    419     SynchronizedMultiset(Multiset<E> delegate, @Nullable Object mutex) {
    420       super(delegate, mutex);
    421     }
    422 
    423     @Override Multiset<E> delegate() {
    424       return (Multiset<E>) super.delegate();
    425     }
    426 
    427     @Override
    428     public int count(Object o) {
    429       synchronized (mutex) {
    430         return delegate().count(o);
    431       }
    432     }
    433 
    434     @Override
    435     public int add(E e, int n) {
    436       synchronized (mutex) {
    437         return delegate().add(e, n);
    438       }
    439     }
    440 
    441     @Override
    442     public int remove(Object o, int n) {
    443       synchronized (mutex) {
    444         return delegate().remove(o, n);
    445       }
    446     }
    447 
    448     @Override
    449     public int setCount(E element, int count) {
    450       synchronized (mutex) {
    451         return delegate().setCount(element, count);
    452       }
    453     }
    454 
    455     @Override
    456     public boolean setCount(E element, int oldCount, int newCount) {
    457       synchronized (mutex) {
    458         return delegate().setCount(element, oldCount, newCount);
    459       }
    460     }
    461 
    462     @Override
    463     public Set<E> elementSet() {
    464       synchronized (mutex) {
    465         if (elementSet == null) {
    466           elementSet = typePreservingSet(delegate().elementSet(), mutex);
    467         }
    468         return elementSet;
    469       }
    470     }
    471 
    472     @Override
    473     public Set<Entry<E>> entrySet() {
    474       synchronized (mutex) {
    475         if (entrySet == null) {
    476           entrySet = typePreservingSet(delegate().entrySet(), mutex);
    477         }
    478         return entrySet;
    479       }
    480     }
    481 
    482     @Override public boolean equals(Object o) {
    483       if (o == this) {
    484         return true;
    485       }
    486       synchronized (mutex) {
    487         return delegate().equals(o);
    488       }
    489     }
    490 
    491     @Override public int hashCode() {
    492       synchronized (mutex) {
    493         return delegate().hashCode();
    494       }
    495     }
    496 
    497     private static final long serialVersionUID = 0;
    498   }
    499 
    500   static <K, V> Multimap<K, V> multimap(
    501       Multimap<K, V> multimap, @Nullable Object mutex) {
    502     if (multimap instanceof SynchronizedMultimap ||
    503         multimap instanceof ImmutableMultimap) {
    504       return multimap;
    505     }
    506     return new SynchronizedMultimap<K, V>(multimap, mutex);
    507   }
    508 
    509   private static class SynchronizedMultimap<K, V> extends SynchronizedObject
    510       implements Multimap<K, V> {
    511     transient Set<K> keySet;
    512     transient Collection<V> valuesCollection;
    513     transient Collection<Map.Entry<K, V>> entries;
    514     transient Map<K, Collection<V>> asMap;
    515     transient Multiset<K> keys;
    516 
    517     @SuppressWarnings("unchecked")
    518     @Override Multimap<K, V> delegate() {
    519       return (Multimap<K, V>) super.delegate();
    520     }
    521 
    522     SynchronizedMultimap(Multimap<K, V> delegate, @Nullable Object mutex) {
    523       super(delegate, mutex);
    524     }
    525 
    526     @Override
    527     public int size() {
    528       synchronized (mutex) {
    529         return delegate().size();
    530       }
    531     }
    532 
    533     @Override
    534     public boolean isEmpty() {
    535       synchronized (mutex) {
    536         return delegate().isEmpty();
    537       }
    538     }
    539 
    540     @Override
    541     public boolean containsKey(Object key) {
    542       synchronized (mutex) {
    543         return delegate().containsKey(key);
    544       }
    545     }
    546 
    547     @Override
    548     public boolean containsValue(Object value) {
    549       synchronized (mutex) {
    550         return delegate().containsValue(value);
    551       }
    552     }
    553 
    554     @Override
    555     public boolean containsEntry(Object key, Object value) {
    556       synchronized (mutex) {
    557         return delegate().containsEntry(key, value);
    558       }
    559     }
    560 
    561     @Override
    562     public Collection<V> get(K key) {
    563       synchronized (mutex) {
    564         return typePreservingCollection(delegate().get(key), mutex);
    565       }
    566     }
    567 
    568     @Override
    569     public boolean put(K key, V value) {
    570       synchronized (mutex) {
    571         return delegate().put(key, value);
    572       }
    573     }
    574 
    575     @Override
    576     public boolean putAll(K key, Iterable<? extends V> values) {
    577       synchronized (mutex) {
    578         return delegate().putAll(key, values);
    579       }
    580     }
    581 
    582     @Override
    583     public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
    584       synchronized (mutex) {
    585         return delegate().putAll(multimap);
    586       }
    587     }
    588 
    589     @Override
    590     public Collection<V> replaceValues(K key, Iterable<? extends V> values) {
    591       synchronized (mutex) {
    592         return delegate().replaceValues(key, values); // copy not synchronized
    593       }
    594     }
    595 
    596     @Override
    597     public boolean remove(Object key, Object value) {
    598       synchronized (mutex) {
    599         return delegate().remove(key, value);
    600       }
    601     }
    602 
    603     @Override
    604     public Collection<V> removeAll(Object key) {
    605       synchronized (mutex) {
    606         return delegate().removeAll(key); // copy not synchronized
    607       }
    608     }
    609 
    610     @Override
    611     public void clear() {
    612       synchronized (mutex) {
    613         delegate().clear();
    614       }
    615     }
    616 
    617     @Override
    618     public Set<K> keySet() {
    619       synchronized (mutex) {
    620         if (keySet == null) {
    621           keySet = typePreservingSet(delegate().keySet(), mutex);
    622         }
    623         return keySet;
    624       }
    625     }
    626 
    627     @Override
    628     public Collection<V> values() {
    629       synchronized (mutex) {
    630         if (valuesCollection == null) {
    631           valuesCollection = collection(delegate().values(), mutex);
    632         }
    633         return valuesCollection;
    634       }
    635     }
    636 
    637     @Override
    638     public Collection<Map.Entry<K, V>> entries() {
    639       synchronized (mutex) {
    640         if (entries == null) {
    641           entries = typePreservingCollection(delegate().entries(), mutex);
    642         }
    643         return entries;
    644       }
    645     }
    646 
    647     @Override
    648     public Map<K, Collection<V>> asMap() {
    649       synchronized (mutex) {
    650         if (asMap == null) {
    651           asMap = new SynchronizedAsMap<K, V>(delegate().asMap(), mutex);
    652         }
    653         return asMap;
    654       }
    655     }
    656 
    657     @Override
    658     public Multiset<K> keys() {
    659       synchronized (mutex) {
    660         if (keys == null) {
    661           keys = multiset(delegate().keys(), mutex);
    662         }
    663         return keys;
    664       }
    665     }
    666 
    667     @Override public boolean equals(Object o) {
    668       if (o == this) {
    669         return true;
    670       }
    671       synchronized (mutex) {
    672         return delegate().equals(o);
    673       }
    674     }
    675 
    676     @Override public int hashCode() {
    677       synchronized (mutex) {
    678         return delegate().hashCode();
    679       }
    680     }
    681 
    682     private static final long serialVersionUID = 0;
    683   }
    684 
    685   static <K, V> ListMultimap<K, V> listMultimap(
    686       ListMultimap<K, V> multimap, @Nullable Object mutex) {
    687     if (multimap instanceof SynchronizedListMultimap ||
    688         multimap instanceof ImmutableListMultimap) {
    689       return multimap;
    690     }
    691     return new SynchronizedListMultimap<K, V>(multimap, mutex);
    692   }
    693 
    694   private static class SynchronizedListMultimap<K, V>
    695       extends SynchronizedMultimap<K, V> implements ListMultimap<K, V> {
    696     SynchronizedListMultimap(
    697         ListMultimap<K, V> delegate, @Nullable Object mutex) {
    698       super(delegate, mutex);
    699     }
    700     @Override ListMultimap<K, V> delegate() {
    701       return (ListMultimap<K, V>) super.delegate();
    702     }
    703     @Override public List<V> get(K key) {
    704       synchronized (mutex) {
    705         return list(delegate().get(key), mutex);
    706       }
    707     }
    708     @Override public List<V> removeAll(Object key) {
    709       synchronized (mutex) {
    710         return delegate().removeAll(key); // copy not synchronized
    711       }
    712     }
    713     @Override public List<V> replaceValues(
    714         K key, Iterable<? extends V> values) {
    715       synchronized (mutex) {
    716         return delegate().replaceValues(key, values); // copy not synchronized
    717       }
    718     }
    719     private static final long serialVersionUID = 0;
    720   }
    721 
    722   static <K, V> SetMultimap<K, V> setMultimap(
    723       SetMultimap<K, V> multimap, @Nullable Object mutex) {
    724     if (multimap instanceof SynchronizedSetMultimap ||
    725         multimap instanceof ImmutableSetMultimap) {
    726       return multimap;
    727     }
    728     return new SynchronizedSetMultimap<K, V>(multimap, mutex);
    729   }
    730 
    731   private static class SynchronizedSetMultimap<K, V>
    732       extends SynchronizedMultimap<K, V> implements SetMultimap<K, V> {
    733     transient Set<Map.Entry<K, V>> entrySet;
    734 
    735     SynchronizedSetMultimap(
    736         SetMultimap<K, V> delegate, @Nullable Object mutex) {
    737       super(delegate, mutex);
    738     }
    739     @Override SetMultimap<K, V> delegate() {
    740       return (SetMultimap<K, V>) super.delegate();
    741     }
    742     @Override public Set<V> get(K key) {
    743       synchronized (mutex) {
    744         return set(delegate().get(key), mutex);
    745       }
    746     }
    747     @Override public Set<V> removeAll(Object key) {
    748       synchronized (mutex) {
    749         return delegate().removeAll(key); // copy not synchronized
    750       }
    751     }
    752     @Override public Set<V> replaceValues(
    753         K key, Iterable<? extends V> values) {
    754       synchronized (mutex) {
    755         return delegate().replaceValues(key, values); // copy not synchronized
    756       }
    757     }
    758     @Override public Set<Map.Entry<K, V>> entries() {
    759       synchronized (mutex) {
    760         if (entrySet == null) {
    761           entrySet = set(delegate().entries(), mutex);
    762         }
    763         return entrySet;
    764       }
    765     }
    766     private static final long serialVersionUID = 0;
    767   }
    768 
    769   static <K, V> SortedSetMultimap<K, V> sortedSetMultimap(
    770       SortedSetMultimap<K, V> multimap, @Nullable Object mutex) {
    771     if (multimap instanceof SynchronizedSortedSetMultimap) {
    772       return multimap;
    773     }
    774     return new SynchronizedSortedSetMultimap<K, V>(multimap, mutex);
    775   }
    776 
    777   private static class SynchronizedSortedSetMultimap<K, V>
    778       extends SynchronizedSetMultimap<K, V> implements SortedSetMultimap<K, V> {
    779     SynchronizedSortedSetMultimap(
    780         SortedSetMultimap<K, V> delegate, @Nullable Object mutex) {
    781       super(delegate, mutex);
    782     }
    783     @Override SortedSetMultimap<K, V> delegate() {
    784       return (SortedSetMultimap<K, V>) super.delegate();
    785     }
    786     @Override public SortedSet<V> get(K key) {
    787       synchronized (mutex) {
    788         return sortedSet(delegate().get(key), mutex);
    789       }
    790     }
    791     @Override public SortedSet<V> removeAll(Object key) {
    792       synchronized (mutex) {
    793         return delegate().removeAll(key); // copy not synchronized
    794       }
    795     }
    796     @Override public SortedSet<V> replaceValues(
    797         K key, Iterable<? extends V> values) {
    798       synchronized (mutex) {
    799         return delegate().replaceValues(key, values); // copy not synchronized
    800       }
    801     }
    802     @Override
    803     public Comparator<? super V> valueComparator() {
    804       synchronized (mutex) {
    805         return delegate().valueComparator();
    806       }
    807     }
    808     private static final long serialVersionUID = 0;
    809   }
    810 
    811   private static <E> Collection<E> typePreservingCollection(
    812       Collection<E> collection, @Nullable Object mutex) {
    813     if (collection instanceof SortedSet) {
    814       return sortedSet((SortedSet<E>) collection, mutex);
    815     }
    816     if (collection instanceof Set) {
    817       return set((Set<E>) collection, mutex);
    818     }
    819     if (collection instanceof List) {
    820       return list((List<E>) collection, mutex);
    821     }
    822     return collection(collection, mutex);
    823   }
    824 
    825   private static <E> Set<E> typePreservingSet(
    826       Set<E> set, @Nullable Object mutex) {
    827     if (set instanceof SortedSet) {
    828       return sortedSet((SortedSet<E>) set, mutex);
    829     } else {
    830       return set(set, mutex);
    831     }
    832   }
    833 
    834   private static class SynchronizedAsMapEntries<K, V>
    835       extends SynchronizedSet<Map.Entry<K, Collection<V>>> {
    836     SynchronizedAsMapEntries(
    837         Set<Map.Entry<K, Collection<V>>> delegate, @Nullable Object mutex) {
    838       super(delegate, mutex);
    839     }
    840 
    841     @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() {
    842       // Must be manually synchronized.
    843       final Iterator<Map.Entry<K, Collection<V>>> iterator = super.iterator();
    844       return new ForwardingIterator<Map.Entry<K, Collection<V>>>() {
    845         @Override protected Iterator<Map.Entry<K, Collection<V>>> delegate() {
    846           return iterator;
    847         }
    848 
    849         @Override public Map.Entry<K, Collection<V>> next() {
    850           final Map.Entry<K, Collection<V>> entry = iterator.next();
    851           return new ForwardingMapEntry<K, Collection<V>>() {
    852             @Override protected Map.Entry<K, Collection<V>> delegate() {
    853               return entry;
    854             }
    855             @Override public Collection<V> getValue() {
    856               return typePreservingCollection(entry.getValue(), mutex);
    857             }
    858           };
    859         }
    860       };
    861     }
    862 
    863     // See Collections.CheckedMap.CheckedEntrySet for details on attacks.
    864 
    865     @Override public Object[] toArray() {
    866       synchronized (mutex) {
    867         return ObjectArrays.toArrayImpl(delegate());
    868       }
    869     }
    870     @Override public <T> T[] toArray(T[] array) {
    871       synchronized (mutex) {
    872         return ObjectArrays.toArrayImpl(delegate(), array);
    873       }
    874     }
    875     @Override public boolean contains(Object o) {
    876       synchronized (mutex) {
    877         return Maps.containsEntryImpl(delegate(), o);
    878       }
    879     }
    880     @Override public boolean containsAll(Collection<?> c) {
    881       synchronized (mutex) {
    882         return Collections2.containsAllImpl(delegate(), c);
    883       }
    884     }
    885     @Override public boolean equals(Object o) {
    886       if (o == this) {
    887         return true;
    888       }
    889       synchronized (mutex) {
    890         return Sets.equalsImpl(delegate(), o);
    891       }
    892     }
    893     @Override public boolean remove(Object o) {
    894       synchronized (mutex) {
    895         return Maps.removeEntryImpl(delegate(), o);
    896       }
    897     }
    898     @Override public boolean removeAll(Collection<?> c) {
    899       synchronized (mutex) {
    900         return Iterators.removeAll(delegate().iterator(), c);
    901       }
    902     }
    903     @Override public boolean retainAll(Collection<?> c) {
    904       synchronized (mutex) {
    905         return Iterators.retainAll(delegate().iterator(), c);
    906       }
    907     }
    908 
    909     private static final long serialVersionUID = 0;
    910   }
    911 
    912   @VisibleForTesting
    913   static <K, V> Map<K, V> map(Map<K, V> map, @Nullable Object mutex) {
    914     return new SynchronizedMap<K, V>(map, mutex);
    915   }
    916 
    917   private static class SynchronizedMap<K, V> extends SynchronizedObject
    918       implements Map<K, V> {
    919     transient Set<K> keySet;
    920     transient Collection<V> values;
    921     transient Set<Map.Entry<K, V>> entrySet;
    922 
    923     SynchronizedMap(Map<K, V> delegate, @Nullable Object mutex) {
    924       super(delegate, mutex);
    925     }
    926 
    927     @SuppressWarnings("unchecked")
    928     @Override Map<K, V> delegate() {
    929       return (Map<K, V>) super.delegate();
    930     }
    931 
    932     @Override
    933     public void clear() {
    934       synchronized (mutex) {
    935         delegate().clear();
    936       }
    937     }
    938 
    939     @Override
    940     public boolean containsKey(Object key) {
    941       synchronized (mutex) {
    942         return delegate().containsKey(key);
    943       }
    944     }
    945 
    946     @Override
    947     public boolean containsValue(Object value) {
    948       synchronized (mutex) {
    949         return delegate().containsValue(value);
    950       }
    951     }
    952 
    953     @Override
    954     public Set<Map.Entry<K, V>> entrySet() {
    955       synchronized (mutex) {
    956         if (entrySet == null) {
    957           entrySet = set(delegate().entrySet(), mutex);
    958         }
    959         return entrySet;
    960       }
    961     }
    962 
    963     @Override
    964     public V get(Object key) {
    965       synchronized (mutex) {
    966         return delegate().get(key);
    967       }
    968     }
    969 
    970     @Override
    971     public boolean isEmpty() {
    972       synchronized (mutex) {
    973         return delegate().isEmpty();
    974       }
    975     }
    976 
    977     @Override
    978     public Set<K> keySet() {
    979       synchronized (mutex) {
    980         if (keySet == null) {
    981           keySet = set(delegate().keySet(), mutex);
    982         }
    983         return keySet;
    984       }
    985     }
    986 
    987     @Override
    988     public V put(K key, V value) {
    989       synchronized (mutex) {
    990         return delegate().put(key, value);
    991       }
    992     }
    993 
    994     @Override
    995     public void putAll(Map<? extends K, ? extends V> map) {
    996       synchronized (mutex) {
    997         delegate().putAll(map);
    998       }
    999     }
   1000 
   1001     @Override
   1002     public V remove(Object key) {
   1003       synchronized (mutex) {
   1004         return delegate().remove(key);
   1005       }
   1006     }
   1007 
   1008     @Override
   1009     public int size() {
   1010       synchronized (mutex) {
   1011         return delegate().size();
   1012       }
   1013     }
   1014 
   1015     @Override
   1016     public Collection<V> values() {
   1017       synchronized (mutex) {
   1018         if (values == null) {
   1019           values = collection(delegate().values(), mutex);
   1020         }
   1021         return values;
   1022       }
   1023     }
   1024 
   1025     @Override public boolean equals(Object o) {
   1026       if (o == this) {
   1027         return true;
   1028       }
   1029       synchronized (mutex) {
   1030         return delegate().equals(o);
   1031       }
   1032     }
   1033 
   1034     @Override public int hashCode() {
   1035       synchronized (mutex) {
   1036         return delegate().hashCode();
   1037       }
   1038     }
   1039 
   1040     private static final long serialVersionUID = 0;
   1041   }
   1042 
   1043   static <K, V> SortedMap<K, V> sortedMap(
   1044       SortedMap<K, V> sortedMap, @Nullable Object mutex) {
   1045     return new SynchronizedSortedMap<K, V>(sortedMap, mutex);
   1046   }
   1047 
   1048   static class SynchronizedSortedMap<K, V> extends SynchronizedMap<K, V>
   1049       implements SortedMap<K, V> {
   1050 
   1051     SynchronizedSortedMap(SortedMap<K, V> delegate, @Nullable Object mutex) {
   1052       super(delegate, mutex);
   1053     }
   1054 
   1055     @Override SortedMap<K, V> delegate() {
   1056       return (SortedMap<K, V>) super.delegate();
   1057     }
   1058 
   1059     @Override public Comparator<? super K> comparator() {
   1060       synchronized (mutex) {
   1061         return delegate().comparator();
   1062       }
   1063     }
   1064 
   1065     @Override public K firstKey() {
   1066       synchronized (mutex) {
   1067         return delegate().firstKey();
   1068       }
   1069     }
   1070 
   1071     @Override public SortedMap<K, V> headMap(K toKey) {
   1072       synchronized (mutex) {
   1073         return sortedMap(delegate().headMap(toKey), mutex);
   1074       }
   1075     }
   1076 
   1077     @Override public K lastKey() {
   1078       synchronized (mutex) {
   1079         return delegate().lastKey();
   1080       }
   1081     }
   1082 
   1083     @Override public SortedMap<K, V> subMap(K fromKey, K toKey) {
   1084       synchronized (mutex) {
   1085         return sortedMap(delegate().subMap(fromKey, toKey), mutex);
   1086       }
   1087     }
   1088 
   1089     @Override public SortedMap<K, V> tailMap(K fromKey) {
   1090       synchronized (mutex) {
   1091         return sortedMap(delegate().tailMap(fromKey), mutex);
   1092       }
   1093     }
   1094 
   1095     private static final long serialVersionUID = 0;
   1096   }
   1097 
   1098   static <K, V> BiMap<K, V> biMap(BiMap<K, V> bimap, @Nullable Object mutex) {
   1099     if (bimap instanceof SynchronizedBiMap ||
   1100         bimap instanceof ImmutableBiMap) {
   1101       return bimap;
   1102     }
   1103     return new SynchronizedBiMap<K, V>(bimap, mutex, null);
   1104   }
   1105 
   1106   @VisibleForTesting static class SynchronizedBiMap<K, V>
   1107       extends SynchronizedMap<K, V> implements BiMap<K, V>, Serializable {
   1108     private transient Set<V> valueSet;
   1109     private transient BiMap<V, K> inverse;
   1110 
   1111     private SynchronizedBiMap(BiMap<K, V> delegate, @Nullable Object mutex,
   1112         @Nullable BiMap<V, K> inverse) {
   1113       super(delegate, mutex);
   1114       this.inverse = inverse;
   1115     }
   1116 
   1117     @Override BiMap<K, V> delegate() {
   1118       return (BiMap<K, V>) super.delegate();
   1119     }
   1120 
   1121     @Override public Set<V> values() {
   1122       synchronized (mutex) {
   1123         if (valueSet == null) {
   1124           valueSet = set(delegate().values(), mutex);
   1125         }
   1126         return valueSet;
   1127       }
   1128     }
   1129 
   1130     @Override
   1131     public V forcePut(K key, V value) {
   1132       synchronized (mutex) {
   1133         return delegate().forcePut(key, value);
   1134       }
   1135     }
   1136 
   1137     @Override
   1138     public BiMap<V, K> inverse() {
   1139       synchronized (mutex) {
   1140         if (inverse == null) {
   1141           inverse
   1142               = new SynchronizedBiMap<V, K>(delegate().inverse(), mutex, this);
   1143         }
   1144         return inverse;
   1145       }
   1146     }
   1147 
   1148     private static final long serialVersionUID = 0;
   1149   }
   1150 
   1151   private static class SynchronizedAsMap<K, V>
   1152       extends SynchronizedMap<K, Collection<V>> {
   1153     transient Set<Map.Entry<K, Collection<V>>> asMapEntrySet;
   1154     transient Collection<Collection<V>> asMapValues;
   1155 
   1156     SynchronizedAsMap(Map<K, Collection<V>> delegate, @Nullable Object mutex) {
   1157       super(delegate, mutex);
   1158     }
   1159 
   1160     @Override public Collection<V> get(Object key) {
   1161       synchronized (mutex) {
   1162         Collection<V> collection = super.get(key);
   1163         return (collection == null) ? null
   1164             : typePreservingCollection(collection, mutex);
   1165       }
   1166     }
   1167 
   1168     @Override public Set<Map.Entry<K, Collection<V>>> entrySet() {
   1169       synchronized (mutex) {
   1170         if (asMapEntrySet == null) {
   1171           asMapEntrySet = new SynchronizedAsMapEntries<K, V>(
   1172               delegate().entrySet(), mutex);
   1173         }
   1174         return asMapEntrySet;
   1175       }
   1176     }
   1177 
   1178     @Override public Collection<Collection<V>> values() {
   1179       synchronized (mutex) {
   1180         if (asMapValues == null) {
   1181           asMapValues
   1182               = new SynchronizedAsMapValues<V>(delegate().values(), mutex);
   1183         }
   1184         return asMapValues;
   1185       }
   1186     }
   1187 
   1188     @Override public boolean containsValue(Object o) {
   1189       // values() and its contains() method are both synchronized.
   1190       return values().contains(o);
   1191     }
   1192 
   1193     private static final long serialVersionUID = 0;
   1194   }
   1195 
   1196   private static class SynchronizedAsMapValues<V>
   1197       extends SynchronizedCollection<Collection<V>> {
   1198     SynchronizedAsMapValues(
   1199         Collection<Collection<V>> delegate, @Nullable Object mutex) {
   1200       super(delegate, mutex);
   1201     }
   1202 
   1203     @Override public Iterator<Collection<V>> iterator() {
   1204       // Must be manually synchronized.
   1205       final Iterator<Collection<V>> iterator = super.iterator();
   1206       return new ForwardingIterator<Collection<V>>() {
   1207         @Override protected Iterator<Collection<V>> delegate() {
   1208           return iterator;
   1209         }
   1210         @Override public Collection<V> next() {
   1211           return typePreservingCollection(iterator.next(), mutex);
   1212         }
   1213       };
   1214     }
   1215 
   1216     private static final long serialVersionUID = 0;
   1217   }
   1218 }
   1219