1 /* 2 * Copyright (C) 2011 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' 14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS 17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 23 * THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #include "config.h" 27 28 #include "wtf/Deque.h" 29 30 #include "wtf/HashSet.h" 31 #include "wtf/OwnPtr.h" 32 #include "wtf/PassOwnPtr.h" 33 #include <gtest/gtest.h> 34 35 namespace { 36 37 TEST(DequeTest, Basic) 38 { 39 Deque<int> intDeque; 40 EXPECT_TRUE(intDeque.isEmpty()); 41 EXPECT_EQ(0ul, intDeque.size()); 42 } 43 44 void checkNumberSequence(Deque<int>& deque, int from, int to, bool increment) 45 { 46 Deque<int>::iterator it = increment ? deque.begin() : deque.end(); 47 size_t index = increment ? 0 : deque.size(); 48 int step = from < to ? 1 : -1; 49 for (int i = from; i != to + step; i += step) { 50 if (!increment) { 51 --it; 52 --index; 53 } 54 55 EXPECT_EQ(i, *it); 56 EXPECT_EQ(i, deque[index]); 57 58 if (increment) { 59 ++it; 60 ++index; 61 } 62 } 63 EXPECT_EQ(increment ? deque.end() : deque.begin(), it); 64 EXPECT_EQ(increment ? deque.size() : 0, index); 65 } 66 67 void checkNumberSequenceReverse(Deque<int>& deque, int from, int to, bool increment) 68 { 69 Deque<int>::reverse_iterator it = increment ? deque.rbegin() : deque.rend(); 70 size_t index = increment ? 0 : deque.size(); 71 int step = from < to ? 1 : -1; 72 for (int i = from; i != to + step; i += step) { 73 if (!increment) { 74 --it; 75 --index; 76 } 77 78 EXPECT_EQ(i, *it); 79 EXPECT_EQ(i, deque.at(deque.size() - 1 - index)); 80 81 if (increment) { 82 ++it; 83 ++index; 84 } 85 } 86 EXPECT_EQ(increment ? deque.rend() : deque.rbegin(), it); 87 EXPECT_EQ(increment ? deque.size() : 0, index); 88 } 89 90 TEST(DequeTest, Reverse) 91 { 92 Deque<int> intDeque; 93 intDeque.append(10); 94 intDeque.append(11); 95 intDeque.append(12); 96 intDeque.append(13); 97 98 checkNumberSequence(intDeque, 10, 13, true); 99 checkNumberSequence(intDeque, 13, 10, false); 100 checkNumberSequenceReverse(intDeque, 13, 10, true); 101 checkNumberSequenceReverse(intDeque, 10, 13, false); 102 103 intDeque.append(14); 104 intDeque.append(15); 105 EXPECT_EQ(10, intDeque.takeFirst()); 106 EXPECT_EQ(15, intDeque.takeLast()); 107 checkNumberSequence(intDeque, 11, 14, true); 108 checkNumberSequence(intDeque, 14, 11, false); 109 checkNumberSequenceReverse(intDeque, 14, 11, true); 110 checkNumberSequenceReverse(intDeque, 11, 14, false); 111 112 for (int i = 15; i < 200; ++i) 113 intDeque.append(i); 114 checkNumberSequence(intDeque, 11, 199, true); 115 checkNumberSequence(intDeque, 199, 11, false); 116 checkNumberSequenceReverse(intDeque, 199, 11, true); 117 checkNumberSequenceReverse(intDeque, 11, 199, false); 118 119 for (int i = 0; i < 180; ++i) { 120 EXPECT_EQ(i + 11, intDeque[0]); 121 EXPECT_EQ(i + 11, intDeque.takeFirst()); 122 } 123 checkNumberSequence(intDeque, 191, 199, true); 124 checkNumberSequence(intDeque, 199, 191, false); 125 checkNumberSequenceReverse(intDeque, 199, 191, true); 126 checkNumberSequenceReverse(intDeque, 191, 199, false); 127 128 Deque<int> intDeque2; 129 swap(intDeque, intDeque2); 130 131 checkNumberSequence(intDeque2, 191, 199, true); 132 checkNumberSequence(intDeque2, 199, 191, false); 133 checkNumberSequenceReverse(intDeque2, 199, 191, true); 134 checkNumberSequenceReverse(intDeque2, 191, 199, false); 135 136 intDeque.swap(intDeque2); 137 138 checkNumberSequence(intDeque, 191, 199, true); 139 checkNumberSequence(intDeque, 199, 191, false); 140 checkNumberSequenceReverse(intDeque, 199, 191, true); 141 checkNumberSequenceReverse(intDeque, 191, 199, false); 142 143 intDeque.swap(intDeque2); 144 145 checkNumberSequence(intDeque2, 191, 199, true); 146 checkNumberSequence(intDeque2, 199, 191, false); 147 checkNumberSequenceReverse(intDeque2, 199, 191, true); 148 checkNumberSequenceReverse(intDeque2, 191, 199, false); 149 } 150 151 class DestructCounter { 152 public: 153 explicit DestructCounter(int i, int* destructNumber) 154 : m_i(i) 155 , m_destructNumber(destructNumber) 156 { } 157 158 ~DestructCounter() { ++(*m_destructNumber); } 159 int get() const { return m_i; } 160 161 private: 162 int m_i; 163 int* m_destructNumber; 164 }; 165 166 typedef WTF::Deque<OwnPtr<DestructCounter> > OwnPtrDeque; 167 168 TEST(DequeTest, OwnPtr) 169 { 170 int destructNumber = 0; 171 OwnPtrDeque deque; 172 deque.append(adoptPtr(new DestructCounter(0, &destructNumber))); 173 deque.append(adoptPtr(new DestructCounter(1, &destructNumber))); 174 EXPECT_EQ(2u, deque.size()); 175 176 OwnPtr<DestructCounter>& counter0 = deque.first(); 177 EXPECT_EQ(0, counter0->get()); 178 int counter1 = deque.last()->get(); 179 EXPECT_EQ(1, counter1); 180 EXPECT_EQ(0, destructNumber); 181 182 size_t index = 0; 183 for (OwnPtrDeque::iterator iter = deque.begin(); iter != deque.end(); ++iter) { 184 OwnPtr<DestructCounter>& refCounter = *iter; 185 EXPECT_EQ(index, static_cast<size_t>(refCounter->get())); 186 EXPECT_EQ(index, static_cast<size_t>((*refCounter).get())); 187 index++; 188 } 189 EXPECT_EQ(0, destructNumber); 190 191 OwnPtrDeque::iterator it = deque.begin(); 192 for (index = 0; index < deque.size(); ++index) { 193 OwnPtr<DestructCounter>& refCounter = *it; 194 EXPECT_EQ(index, static_cast<size_t>(refCounter->get())); 195 index++; 196 ++it; 197 } 198 EXPECT_EQ(0, destructNumber); 199 200 EXPECT_EQ(0, deque.first()->get()); 201 deque.removeFirst(); 202 EXPECT_EQ(1, deque.first()->get()); 203 EXPECT_EQ(1u, deque.size()); 204 EXPECT_EQ(1, destructNumber); 205 206 OwnPtr<DestructCounter> ownCounter1 = deque.first().release(); 207 deque.removeFirst(); 208 EXPECT_EQ(counter1, ownCounter1->get()); 209 EXPECT_EQ(0u, deque.size()); 210 EXPECT_EQ(1, destructNumber); 211 212 ownCounter1.clear(); 213 EXPECT_EQ(2, destructNumber); 214 215 size_t count = 1025; 216 destructNumber = 0; 217 for (size_t i = 0; i < count; ++i) 218 deque.prepend(adoptPtr(new DestructCounter(i, &destructNumber))); 219 220 // Deque relocation must not destruct OwnPtr element. 221 EXPECT_EQ(0, destructNumber); 222 EXPECT_EQ(count, deque.size()); 223 224 OwnPtrDeque copyDeque; 225 deque.swap(copyDeque); 226 EXPECT_EQ(0, destructNumber); 227 EXPECT_EQ(count, copyDeque.size()); 228 EXPECT_EQ(0u, deque.size()); 229 230 copyDeque.clear(); 231 EXPECT_EQ(count, static_cast<size_t>(destructNumber)); 232 } 233 234 // WrappedInt class will fail if it was memmoved or memcpyed. 235 static HashSet<void*> constructedWrappedInts; 236 class WrappedInt { 237 public: 238 WrappedInt(int i = 0) 239 : m_originalThisPtr(this) 240 , m_i(i) 241 { 242 constructedWrappedInts.add(this); 243 } 244 245 WrappedInt(const WrappedInt& other) 246 : m_originalThisPtr(this) 247 , m_i(other.m_i) 248 { 249 constructedWrappedInts.add(this); 250 } 251 252 WrappedInt& operator=(const WrappedInt& other) 253 { 254 m_i = other.m_i; 255 return *this; 256 } 257 258 ~WrappedInt() 259 { 260 EXPECT_EQ(m_originalThisPtr, this); 261 EXPECT_TRUE(constructedWrappedInts.contains(this)); 262 constructedWrappedInts.remove(this); 263 } 264 265 int get() const { return m_i; } 266 267 private: 268 void* m_originalThisPtr; 269 int m_i; 270 }; 271 272 TEST(DequeTest, SwapWithoutInlineCapacity) 273 { 274 Deque<WrappedInt> dequeA; 275 dequeA.append(WrappedInt(1)); 276 Deque<WrappedInt> dequeB; 277 dequeB.append(WrappedInt(2)); 278 279 ASSERT_EQ(dequeA.size(), dequeB.size()); 280 dequeA.swap(dequeB); 281 282 ASSERT_EQ(1u, dequeA.size()); 283 EXPECT_EQ(2, dequeA.first().get()); 284 ASSERT_EQ(1u, dequeB.size()); 285 EXPECT_EQ(1, dequeB.first().get()); 286 287 dequeA.append(WrappedInt(3)); 288 289 ASSERT_GT(dequeA.size(), dequeB.size()); 290 dequeA.swap(dequeB); 291 292 ASSERT_EQ(1u, dequeA.size()); 293 EXPECT_EQ(1, dequeA.first().get()); 294 ASSERT_EQ(2u, dequeB.size()); 295 EXPECT_EQ(2, dequeB.first().get()); 296 297 ASSERT_LT(dequeA.size(), dequeB.size()); 298 dequeA.swap(dequeB); 299 300 ASSERT_EQ(2u, dequeA.size()); 301 EXPECT_EQ(2, dequeA.first().get()); 302 ASSERT_EQ(1u, dequeB.size()); 303 EXPECT_EQ(1, dequeB.first().get()); 304 305 dequeA.append(WrappedInt(4)); 306 dequeA.swap(dequeB); 307 308 ASSERT_EQ(1u, dequeA.size()); 309 EXPECT_EQ(1, dequeA.first().get()); 310 ASSERT_EQ(3u, dequeB.size()); 311 EXPECT_EQ(2, dequeB.first().get()); 312 313 dequeB.swap(dequeA); 314 } 315 316 } // namespace 317
