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