1/* 2 * Copyright (C) 2007, 2008 Apple Inc. All rights reserved. 3 * Copyright (C) 2009 Google Inc. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of 15 * its contributors may be used to endorse or promote products derived 16 * from this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 21 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30#ifndef WTF_Deque_h 31#define WTF_Deque_h 32 33// FIXME: Could move what Vector and Deque share into a separate file. 34// Deque doesn't actually use Vector. 35 36#include <iterator> 37#include "wtf/PassTraits.h" 38#include "wtf/Vector.h" 39 40namespace WTF { 41 42 template<typename T, size_t inlineCapacity> class DequeIteratorBase; 43 template<typename T, size_t inlineCapacity> class DequeIterator; 44 template<typename T, size_t inlineCapacity> class DequeConstIterator; 45 46 template<typename T, size_t inlineCapacity = 0> 47 class Deque { 48 WTF_MAKE_FAST_ALLOCATED; 49 public: 50 typedef DequeIterator<T, inlineCapacity> iterator; 51 typedef DequeConstIterator<T, inlineCapacity> const_iterator; 52 typedef std::reverse_iterator<iterator> reverse_iterator; 53 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 54 typedef PassTraits<T> Pass; 55 typedef typename PassTraits<T>::PassType PassType; 56 57 Deque(); 58 Deque(const Deque<T, inlineCapacity>&); 59 Deque& operator=(const Deque<T, inlineCapacity>&); 60 ~Deque(); 61 62 void swap(Deque<T, inlineCapacity>&); 63 64 size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; } 65 bool isEmpty() const { return m_start == m_end; } 66 67 iterator begin() { return iterator(this, m_start); } 68 iterator end() { return iterator(this, m_end); } 69 const_iterator begin() const { return const_iterator(this, m_start); } 70 const_iterator end() const { return const_iterator(this, m_end); } 71 reverse_iterator rbegin() { return reverse_iterator(end()); } 72 reverse_iterator rend() { return reverse_iterator(begin()); } 73 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 74 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 75 76 T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; } 77 const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; } 78 PassType takeFirst(); 79 80 T& last() { ASSERT(m_start != m_end); return *(--end()); } 81 const T& last() const { ASSERT(m_start != m_end); return *(--end()); } 82 83 template<typename U> void append(const U&); 84 template<typename U> void prepend(const U&); 85 void removeFirst(); 86 void remove(iterator&); 87 void remove(const_iterator&); 88 89 void clear(); 90 91 template<typename Predicate> 92 iterator findIf(Predicate&); 93 94 private: 95 friend class DequeIteratorBase<T, inlineCapacity>; 96 97 typedef VectorBuffer<T, inlineCapacity> Buffer; 98 typedef VectorTypeOperations<T> TypeOperations; 99 typedef DequeIteratorBase<T, inlineCapacity> IteratorBase; 100 101 void remove(size_t position); 102 void invalidateIterators(); 103 void destroyAll(); 104 void checkValidity() const; 105 void checkIndexValidity(size_t) const; 106 void expandCapacityIfNeeded(); 107 void expandCapacity(); 108 109 size_t m_start; 110 size_t m_end; 111 Buffer m_buffer; 112#ifndef NDEBUG 113 mutable IteratorBase* m_iterators; 114#endif 115 }; 116 117 template<typename T, size_t inlineCapacity = 0> 118 class DequeIteratorBase { 119 protected: 120 DequeIteratorBase(); 121 DequeIteratorBase(const Deque<T, inlineCapacity>*, size_t); 122 DequeIteratorBase(const DequeIteratorBase&); 123 DequeIteratorBase& operator=(const DequeIteratorBase&); 124 ~DequeIteratorBase(); 125 126 void assign(const DequeIteratorBase& other) { *this = other; } 127 128 void increment(); 129 void decrement(); 130 131 T* before() const; 132 T* after() const; 133 134 bool isEqual(const DequeIteratorBase&) const; 135 136 private: 137 void addToIteratorsList(); 138 void removeFromIteratorsList(); 139 void checkValidity() const; 140 void checkValidity(const DequeIteratorBase&) const; 141 142 Deque<T, inlineCapacity>* m_deque; 143 size_t m_index; 144 145 friend class Deque<T, inlineCapacity>; 146 147#ifndef NDEBUG 148 mutable DequeIteratorBase* m_next; 149 mutable DequeIteratorBase* m_previous; 150#endif 151 }; 152 153 template<typename T, size_t inlineCapacity = 0> 154 class DequeIterator : public DequeIteratorBase<T, inlineCapacity> { 155 private: 156 typedef DequeIteratorBase<T, inlineCapacity> Base; 157 typedef DequeIterator<T, inlineCapacity> Iterator; 158 159 public: 160 typedef ptrdiff_t difference_type; 161 typedef T value_type; 162 typedef T* pointer; 163 typedef T& reference; 164 typedef std::bidirectional_iterator_tag iterator_category; 165 166 DequeIterator(Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { } 167 168 DequeIterator(const Iterator& other) : Base(other) { } 169 DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; } 170 171 T& operator*() const { return *Base::after(); } 172 T* operator->() const { return Base::after(); } 173 174 bool operator==(const Iterator& other) const { return Base::isEqual(other); } 175 bool operator!=(const Iterator& other) const { return !Base::isEqual(other); } 176 177 Iterator& operator++() { Base::increment(); return *this; } 178 // postfix ++ intentionally omitted 179 Iterator& operator--() { Base::decrement(); return *this; } 180 // postfix -- intentionally omitted 181 }; 182 183 template<typename T, size_t inlineCapacity = 0> 184 class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity> { 185 private: 186 typedef DequeIteratorBase<T, inlineCapacity> Base; 187 typedef DequeConstIterator<T, inlineCapacity> Iterator; 188 typedef DequeIterator<T, inlineCapacity> NonConstIterator; 189 190 public: 191 typedef ptrdiff_t difference_type; 192 typedef T value_type; 193 typedef const T* pointer; 194 typedef const T& reference; 195 typedef std::bidirectional_iterator_tag iterator_category; 196 197 DequeConstIterator(const Deque<T, inlineCapacity>* deque, size_t index) : Base(deque, index) { } 198 199 DequeConstIterator(const Iterator& other) : Base(other) { } 200 DequeConstIterator(const NonConstIterator& other) : Base(other) { } 201 DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; } 202 DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; } 203 204 const T& operator*() const { return *Base::after(); } 205 const T* operator->() const { return Base::after(); } 206 207 bool operator==(const Iterator& other) const { return Base::isEqual(other); } 208 bool operator!=(const Iterator& other) const { return !Base::isEqual(other); } 209 210 Iterator& operator++() { Base::increment(); return *this; } 211 // postfix ++ intentionally omitted 212 Iterator& operator--() { Base::decrement(); return *this; } 213 // postfix -- intentionally omitted 214 }; 215 216#ifdef NDEBUG 217 template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkValidity() const { } 218 template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::checkIndexValidity(size_t) const { } 219 template<typename T, size_t inlineCapacity> inline void Deque<T, inlineCapacity>::invalidateIterators() { } 220#else 221 template<typename T, size_t inlineCapacity> 222 void Deque<T, inlineCapacity>::checkValidity() const 223 { 224 // In this implementation a capacity of 1 would confuse append() and 225 // other places that assume the index after capacity - 1 is 0. 226 ASSERT(m_buffer.capacity() != 1); 227 228 if (!m_buffer.capacity()) { 229 ASSERT(!m_start); 230 ASSERT(!m_end); 231 } else { 232 ASSERT(m_start < m_buffer.capacity()); 233 ASSERT(m_end < m_buffer.capacity()); 234 } 235 } 236 237 template<typename T, size_t inlineCapacity> 238 void Deque<T, inlineCapacity>::checkIndexValidity(size_t index) const 239 { 240 ASSERT_UNUSED(index, index <= m_buffer.capacity()); 241 if (m_start <= m_end) { 242 ASSERT(index >= m_start); 243 ASSERT(index <= m_end); 244 } else { 245 ASSERT(index >= m_start || index <= m_end); 246 } 247 } 248 249 template<typename T, size_t inlineCapacity> 250 void Deque<T, inlineCapacity>::invalidateIterators() 251 { 252 IteratorBase* next; 253 for (IteratorBase* p = m_iterators; p; p = next) { 254 next = p->m_next; 255 p->m_deque = 0; 256 p->m_next = 0; 257 p->m_previous = 0; 258 } 259 m_iterators = 0; 260 } 261#endif 262 263 template<typename T, size_t inlineCapacity> 264 inline Deque<T, inlineCapacity>::Deque() 265 : m_start(0) 266 , m_end(0) 267#ifndef NDEBUG 268 , m_iterators(0) 269#endif 270 { 271 checkValidity(); 272 } 273 274 template<typename T, size_t inlineCapacity> 275 inline Deque<T, inlineCapacity>::Deque(const Deque<T, inlineCapacity>& other) 276 : m_start(other.m_start) 277 , m_end(other.m_end) 278 , m_buffer(other.m_buffer.capacity()) 279#ifndef NDEBUG 280 , m_iterators(0) 281#endif 282 { 283 const T* otherBuffer = other.m_buffer.buffer(); 284 if (m_start <= m_end) 285 TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start); 286 else { 287 TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer()); 288 TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start); 289 } 290 } 291 292 template<typename T, size_t inlineCapacity> 293 void deleteAllValues(const Deque<T, inlineCapacity>& collection) 294 { 295 typedef typename Deque<T, inlineCapacity>::const_iterator iterator; 296 iterator end = collection.end(); 297 for (iterator it = collection.begin(); it != end; ++it) 298 delete *it; 299 } 300 301 template<typename T, size_t inlineCapacity> 302 inline Deque<T, inlineCapacity>& Deque<T, inlineCapacity>::operator=(const Deque<T, inlineCapacity>& other) 303 { 304 // FIXME: This is inefficient if we're using an inline buffer and T is 305 // expensive to copy since it will copy the buffer twice instead of once. 306 Deque<T> copy(other); 307 swap(copy); 308 return *this; 309 } 310 311 template<typename T, size_t inlineCapacity> 312 inline void Deque<T, inlineCapacity>::destroyAll() 313 { 314 if (m_start <= m_end) 315 TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end); 316 else { 317 TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end); 318 TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity()); 319 } 320 } 321 322 template<typename T, size_t inlineCapacity> 323 inline Deque<T, inlineCapacity>::~Deque() 324 { 325 checkValidity(); 326 invalidateIterators(); 327 destroyAll(); 328 } 329 330 template<typename T, size_t inlineCapacity> 331 inline void Deque<T, inlineCapacity>::swap(Deque<T, inlineCapacity>& other) 332 { 333 checkValidity(); 334 other.checkValidity(); 335 invalidateIterators(); 336 std::swap(m_start, other.m_start); 337 std::swap(m_end, other.m_end); 338 m_buffer.swap(other.m_buffer); 339 checkValidity(); 340 other.checkValidity(); 341 } 342 343 template<typename T, size_t inlineCapacity> 344 inline void Deque<T, inlineCapacity>::clear() 345 { 346 checkValidity(); 347 invalidateIterators(); 348 destroyAll(); 349 m_start = 0; 350 m_end = 0; 351 m_buffer.deallocateBuffer(m_buffer.buffer()); 352 checkValidity(); 353 } 354 355 template<typename T, size_t inlineCapacity> 356 template<typename Predicate> 357 inline DequeIterator<T, inlineCapacity> Deque<T, inlineCapacity>::findIf(Predicate& predicate) 358 { 359 iterator end_iterator = end(); 360 for (iterator it = begin(); it != end_iterator; ++it) { 361 if (predicate(*it)) 362 return it; 363 } 364 return end_iterator; 365 } 366 367 template<typename T, size_t inlineCapacity> 368 inline void Deque<T, inlineCapacity>::expandCapacityIfNeeded() 369 { 370 if (m_start) { 371 if (m_end + 1 != m_start) 372 return; 373 } else if (m_end) { 374 if (m_end != m_buffer.capacity() - 1) 375 return; 376 } else if (m_buffer.capacity()) 377 return; 378 379 expandCapacity(); 380 } 381 382 template<typename T, size_t inlineCapacity> 383 void Deque<T, inlineCapacity>::expandCapacity() 384 { 385 checkValidity(); 386 size_t oldCapacity = m_buffer.capacity(); 387 T* oldBuffer = m_buffer.buffer(); 388 m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1)); 389 if (m_start <= m_end) 390 TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start); 391 else { 392 TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer()); 393 size_t newStart = m_buffer.capacity() - (oldCapacity - m_start); 394 TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart); 395 m_start = newStart; 396 } 397 m_buffer.deallocateBuffer(oldBuffer); 398 checkValidity(); 399 } 400 401 template<typename T, size_t inlineCapacity> 402 inline typename Deque<T, inlineCapacity>::PassType Deque<T, inlineCapacity>::takeFirst() 403 { 404 T oldFirst = Pass::transfer(first()); 405 removeFirst(); 406 return Pass::transfer(oldFirst); 407 } 408 409 template<typename T, size_t inlineCapacity> template<typename U> 410 inline void Deque<T, inlineCapacity>::append(const U& value) 411 { 412 checkValidity(); 413 expandCapacityIfNeeded(); 414 new (NotNull, &m_buffer.buffer()[m_end]) T(value); 415 if (m_end == m_buffer.capacity() - 1) 416 m_end = 0; 417 else 418 ++m_end; 419 checkValidity(); 420 } 421 422 template<typename T, size_t inlineCapacity> template<typename U> 423 inline void Deque<T, inlineCapacity>::prepend(const U& value) 424 { 425 checkValidity(); 426 expandCapacityIfNeeded(); 427 if (!m_start) 428 m_start = m_buffer.capacity() - 1; 429 else 430 --m_start; 431 new (NotNull, &m_buffer.buffer()[m_start]) T(value); 432 checkValidity(); 433 } 434 435 template<typename T, size_t inlineCapacity> 436 inline void Deque<T, inlineCapacity>::removeFirst() 437 { 438 checkValidity(); 439 invalidateIterators(); 440 ASSERT(!isEmpty()); 441 TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]); 442 if (m_start == m_buffer.capacity() - 1) 443 m_start = 0; 444 else 445 ++m_start; 446 checkValidity(); 447 } 448 449 template<typename T, size_t inlineCapacity> 450 inline void Deque<T, inlineCapacity>::remove(iterator& it) 451 { 452 it.checkValidity(); 453 remove(it.m_index); 454 } 455 456 template<typename T, size_t inlineCapacity> 457 inline void Deque<T, inlineCapacity>::remove(const_iterator& it) 458 { 459 it.checkValidity(); 460 remove(it.m_index); 461 } 462 463 template<typename T, size_t inlineCapacity> 464 inline void Deque<T, inlineCapacity>::remove(size_t position) 465 { 466 if (position == m_end) 467 return; 468 469 checkValidity(); 470 invalidateIterators(); 471 472 T* buffer = m_buffer.buffer(); 473 TypeOperations::destruct(&buffer[position], &buffer[position + 1]); 474 475 // Find which segment of the circular buffer contained the remove element, and only move elements in that part. 476 if (position >= m_start) { 477 TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1); 478 m_start = (m_start + 1) % m_buffer.capacity(); 479 } else { 480 TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position); 481 m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity(); 482 } 483 checkValidity(); 484 } 485 486#ifdef NDEBUG 487 template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity() const { } 488 template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase<T, inlineCapacity>&) const { } 489 template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList() { } 490 template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList() { } 491#else 492 template<typename T, size_t inlineCapacity> 493 void DequeIteratorBase<T, inlineCapacity>::checkValidity() const 494 { 495 ASSERT(m_deque); 496 m_deque->checkIndexValidity(m_index); 497 } 498 499 template<typename T, size_t inlineCapacity> 500 void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase& other) const 501 { 502 checkValidity(); 503 other.checkValidity(); 504 ASSERT(m_deque == other.m_deque); 505 } 506 507 template<typename T, size_t inlineCapacity> 508 void DequeIteratorBase<T, inlineCapacity>::addToIteratorsList() 509 { 510 if (!m_deque) 511 m_next = 0; 512 else { 513 m_next = m_deque->m_iterators; 514 m_deque->m_iterators = this; 515 if (m_next) 516 m_next->m_previous = this; 517 } 518 m_previous = 0; 519 } 520 521 template<typename T, size_t inlineCapacity> 522 void DequeIteratorBase<T, inlineCapacity>::removeFromIteratorsList() 523 { 524 if (!m_deque) { 525 ASSERT(!m_next); 526 ASSERT(!m_previous); 527 } else { 528 if (m_next) { 529 ASSERT(m_next->m_previous == this); 530 m_next->m_previous = m_previous; 531 } 532 if (m_previous) { 533 ASSERT(m_deque->m_iterators != this); 534 ASSERT(m_previous->m_next == this); 535 m_previous->m_next = m_next; 536 } else { 537 ASSERT(m_deque->m_iterators == this); 538 m_deque->m_iterators = m_next; 539 } 540 } 541 m_next = 0; 542 m_previous = 0; 543 } 544#endif 545 546 template<typename T, size_t inlineCapacity> 547 inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase() 548 : m_deque(0) 549 { 550 } 551 552 template<typename T, size_t inlineCapacity> 553 inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const Deque<T, inlineCapacity>* deque, size_t index) 554 : m_deque(const_cast<Deque<T, inlineCapacity>*>(deque)) 555 , m_index(index) 556 { 557 addToIteratorsList(); 558 checkValidity(); 559 } 560 561 template<typename T, size_t inlineCapacity> 562 inline DequeIteratorBase<T, inlineCapacity>::DequeIteratorBase(const DequeIteratorBase& other) 563 : m_deque(other.m_deque) 564 , m_index(other.m_index) 565 { 566 addToIteratorsList(); 567 checkValidity(); 568 } 569 570 template<typename T, size_t inlineCapacity> 571 inline DequeIteratorBase<T, inlineCapacity>& DequeIteratorBase<T, inlineCapacity>::operator=(const DequeIteratorBase& other) 572 { 573 other.checkValidity(); 574 removeFromIteratorsList(); 575 576 m_deque = other.m_deque; 577 m_index = other.m_index; 578 addToIteratorsList(); 579 checkValidity(); 580 return *this; 581 } 582 583 template<typename T, size_t inlineCapacity> 584 inline DequeIteratorBase<T, inlineCapacity>::~DequeIteratorBase() 585 { 586#ifndef NDEBUG 587 removeFromIteratorsList(); 588 m_deque = 0; 589#endif 590 } 591 592 template<typename T, size_t inlineCapacity> 593 inline bool DequeIteratorBase<T, inlineCapacity>::isEqual(const DequeIteratorBase& other) const 594 { 595 checkValidity(other); 596 return m_index == other.m_index; 597 } 598 599 template<typename T, size_t inlineCapacity> 600 inline void DequeIteratorBase<T, inlineCapacity>::increment() 601 { 602 checkValidity(); 603 ASSERT(m_index != m_deque->m_end); 604 ASSERT(m_deque->m_buffer.capacity()); 605 if (m_index == m_deque->m_buffer.capacity() - 1) 606 m_index = 0; 607 else 608 ++m_index; 609 checkValidity(); 610 } 611 612 template<typename T, size_t inlineCapacity> 613 inline void DequeIteratorBase<T, inlineCapacity>::decrement() 614 { 615 checkValidity(); 616 ASSERT(m_index != m_deque->m_start); 617 ASSERT(m_deque->m_buffer.capacity()); 618 if (!m_index) 619 m_index = m_deque->m_buffer.capacity() - 1; 620 else 621 --m_index; 622 checkValidity(); 623 } 624 625 template<typename T, size_t inlineCapacity> 626 inline T* DequeIteratorBase<T, inlineCapacity>::after() const 627 { 628 checkValidity(); 629 ASSERT(m_index != m_deque->m_end); 630 return &m_deque->m_buffer.buffer()[m_index]; 631 } 632 633 template<typename T, size_t inlineCapacity> 634 inline T* DequeIteratorBase<T, inlineCapacity>::before() const 635 { 636 checkValidity(); 637 ASSERT(m_index != m_deque->m_start); 638 if (!m_index) 639 return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1]; 640 return &m_deque->m_buffer.buffer()[m_index - 1]; 641 } 642 643} // namespace WTF 644 645using WTF::Deque; 646 647#endif // WTF_Deque_h 648