1/*
2 * Copyright (C) 2011 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.util.concurrent;
18
19import static com.google.common.collect.Iterables.concat;
20
21import com.google.common.base.Functions;
22import com.google.common.base.Supplier;
23import com.google.common.collect.ImmutableList;
24import com.google.common.collect.Lists;
25import com.google.common.collect.Maps;
26import com.google.common.collect.Ordering;
27import com.google.common.collect.Sets;
28import com.google.common.testing.GcFinalization;
29import com.google.common.testing.NullPointerTester;
30
31import junit.framework.TestCase;
32
33import java.lang.ref.WeakReference;
34import java.util.List;
35import java.util.Map;
36import java.util.Set;
37import java.util.concurrent.Semaphore;
38import java.util.concurrent.locks.Lock;
39import java.util.concurrent.locks.ReadWriteLock;
40import java.util.concurrent.locks.ReentrantLock;
41import java.util.concurrent.locks.ReentrantReadWriteLock;
42
43/**
44 * Tests for Striped.
45 *
46 * @author Dimitris Andreou
47 */
48public class StripedTest extends TestCase {
49  private static List<Striped<?>> strongImplementations() {
50    return ImmutableList.of(
51        Striped.readWriteLock(100),
52        Striped.readWriteLock(256),
53        Striped.lock(100),
54        Striped.lock(256),
55        Striped.semaphore(100, 1),
56        Striped.semaphore(256, 1));
57  }
58
59  private static final Supplier<ReadWriteLock> READ_WRITE_LOCK_SUPPLIER =
60      new Supplier<ReadWriteLock>() {
61    @Override public ReadWriteLock get() {
62      return new ReentrantReadWriteLock();
63    }
64  };
65
66  private static final Supplier<Lock> LOCK_SUPPLER = new Supplier<Lock>() {
67    @Override public Lock get() {
68      return new ReentrantLock();
69    }
70  };
71
72  private static final Supplier<Semaphore> SEMAPHORE_SUPPLER = new Supplier<Semaphore>() {
73    @Override public Semaphore get() {
74      return new Semaphore(1, false);
75    }
76  };
77
78  private static List<Striped<?>> weakImplementations() {
79    return ImmutableList.<Striped<?>>builder()
80        .add(new Striped.SmallLazyStriped<ReadWriteLock>(50, READ_WRITE_LOCK_SUPPLIER))
81        .add(new Striped.SmallLazyStriped<ReadWriteLock>(64, READ_WRITE_LOCK_SUPPLIER))
82        .add(new Striped.LargeLazyStriped<ReadWriteLock>(50, READ_WRITE_LOCK_SUPPLIER))
83        .add(new Striped.LargeLazyStriped<ReadWriteLock>(64, READ_WRITE_LOCK_SUPPLIER))
84        .add(new Striped.SmallLazyStriped<Lock>(50, LOCK_SUPPLER))
85        .add(new Striped.SmallLazyStriped<Lock>(64, LOCK_SUPPLER))
86        .add(new Striped.LargeLazyStriped<Lock>(50, LOCK_SUPPLER))
87        .add(new Striped.LargeLazyStriped<Lock>(64, LOCK_SUPPLER))
88        .add(new Striped.SmallLazyStriped<Semaphore>(50, SEMAPHORE_SUPPLER))
89        .add(new Striped.SmallLazyStriped<Semaphore>(64, SEMAPHORE_SUPPLER))
90        .add(new Striped.LargeLazyStriped<Semaphore>(50, SEMAPHORE_SUPPLER))
91        .add(new Striped.LargeLazyStriped<Semaphore>(64, SEMAPHORE_SUPPLER))
92        .build();
93  }
94
95  private static Iterable<Striped<?>> allImplementations() {
96    return concat(strongImplementations(), weakImplementations());
97  }
98
99  public void testNull() throws Exception {
100    for (Striped<?> striped : allImplementations()) {
101      new NullPointerTester().testAllPublicInstanceMethods(striped);
102    }
103  }
104
105  public void testSizes() {
106    // not bothering testing all variations, since we know they share implementations
107    assertTrue(Striped.lock(100).size() >= 100);
108    assertTrue(Striped.lock(256).size() == 256);
109    assertTrue(Striped.lazyWeakLock(100).size() >= 100);
110    assertTrue(Striped.lazyWeakLock(256).size() == 256);
111  }
112
113  public void testWeakImplementations() {
114    for (Striped<?> striped : weakImplementations()) {
115      WeakReference<Object> weakRef = new WeakReference<Object>(striped.get(new Object()));
116      GcFinalization.awaitClear(weakRef);
117    }
118  }
119
120  public void testStrongImplementations() {
121    for (Striped<?> striped : strongImplementations()) {
122      WeakReference<Object> weakRef = new WeakReference<Object>(striped.get(new Object()));
123      WeakReference<Object> garbage = new WeakReference<Object>(new Object());
124      GcFinalization.awaitClear(garbage);
125      assertNotNull(weakRef.get());
126    }
127  }
128
129  public void testMaximalWeakStripedLock() {
130    Striped<Lock> stripedLock = Striped.lazyWeakLock(Integer.MAX_VALUE);
131    for (int i = 0; i < 10000; i++) {
132      stripedLock.get(new Object()).lock();
133      // nothing special (e.g. an exception) happens
134    }
135  }
136
137  public void testBulkGetReturnsSorted() {
138    for (Striped<?> striped : allImplementations()) {
139      Map<Object, Integer> indexByLock = Maps.newHashMap();
140      for (int i = 0; i < striped.size(); i++) {
141        indexByLock.put(striped.getAt(i), i);
142      }
143
144      // ensure that bulkGet returns locks in monotonically increasing order
145      for (int objectsNum = 1; objectsNum <= striped.size() * 2; objectsNum++) {
146        Set<Object> objects = Sets.newHashSetWithExpectedSize(objectsNum);
147        for (int i = 0; i < objectsNum; i++) {
148          objects.add(new Object());
149        }
150
151        Iterable<?> locks = striped.bulkGet(objects);
152        assertTrue(Ordering.natural().onResultOf(Functions.forMap(indexByLock)).isOrdered(locks));
153
154        // check idempotency
155        Iterable<?> locks2 = striped.bulkGet(objects);
156        assertEquals(Lists.newArrayList(locks), Lists.newArrayList(locks2));
157      }
158    }
159  }
160
161  /**
162   * Checks idempotency, and that we observe the promised number of stripes.
163   */
164  public void testBasicInvariants() {
165    for (Striped<?> striped : allImplementations()) {
166      assertBasicInvariants(striped);
167    }
168  }
169
170  private static void assertBasicInvariants(Striped<?> striped) {
171    Set<Object> observed = Sets.newIdentityHashSet(); // for the sake of weakly referenced locks.
172    // this gets the stripes with #getAt(index)
173    for (int i = 0; i < striped.size(); i++) {
174      Object object = striped.getAt(i);
175      assertNotNull(object);
176      assertSame(object, striped.getAt(i)); // idempotent
177      observed.add(object);
178    }
179    assertTrue("All stripes observed", observed.size() == striped.size());
180
181    // this uses #get(key), makes sure an already observed stripe is returned
182    for (int i = 0; i < striped.size() * 100; i++) {
183      assertTrue(observed.contains(striped.get(new Object())));
184    }
185
186    try {
187      striped.getAt(-1);
188      fail();
189    } catch (RuntimeException expected) {}
190
191    try {
192      striped.getAt(striped.size());
193      fail();
194    } catch (RuntimeException expected) {}
195  }
196
197  public void testMaxSize() {
198    for (Striped<?> striped : ImmutableList.of(
199        Striped.lazyWeakLock(Integer.MAX_VALUE),
200        Striped.lazyWeakSemaphore(Integer.MAX_VALUE, Integer.MAX_VALUE),
201        Striped.lazyWeakReadWriteLock(Integer.MAX_VALUE))) {
202      for (int i = 0; i < 3; i++) {
203        // doesn't throw exception
204        striped.getAt(Integer.MAX_VALUE - i);
205      }
206    }
207  }
208}
209