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
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkNotNull;
20
21import com.google.common.annotations.GwtCompatible;
22import com.google.common.annotations.GwtIncompatible;
23import com.google.common.annotations.VisibleForTesting;
24
25import java.io.IOException;
26import java.io.ObjectOutputStream;
27import java.io.Serializable;
28import java.util.Collection;
29import java.util.Comparator;
30import java.util.Iterator;
31import java.util.List;
32import java.util.ListIterator;
33import java.util.Map;
34import java.util.RandomAccess;
35import java.util.Set;
36import java.util.SortedMap;
37import java.util.SortedSet;
38
39import 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)
55final 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