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