wtf/Deque.h

   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 "Vector.h"
  37
  38 namespace WTF {
  39
  40     template<typename T> class DequeIteratorBase;
  41     template<typename T> class DequeIterator;
  42     template<typename T> class DequeConstIterator;
  43     template<typename T> class DequeReverseIterator;
  44     template<typename T> class DequeConstReverseIterator;
  45
  46     template<typename T>
  47     class Deque : public FastAllocBase {
  48     public:
  49         typedef DequeIterator<T> iterator;
  50         typedef DequeConstIterator<T> const_iterator;
  51         typedef DequeReverseIterator<T> reverse_iterator;
  52         typedef DequeConstReverseIterator<T> const_reverse_iterator;
  53
  54         Deque();
  55         Deque(const Deque<T>&);
  56         Deque& operator=(const Deque<T>&);
  57         ~Deque();
  58
  59         void swap(Deque<T>&);
  60
  61         size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
  62         bool isEmpty() const { return m_start == m_end; }
  63
  64         iterator begin() { return iterator(this, m_start); }
  65         iterator end() { return iterator(this, m_end); }
  66         const_iterator begin() const { return const_iterator(this, m_start); }
  67         const_iterator end() const { return const_iterator(this, m_end); }
  68         reverse_iterator rbegin() { return reverse_iterator(this, m_end); }
  69         reverse_iterator rend() { return reverse_iterator(this, m_start); }
  70         const_reverse_iterator rbegin() const { return const_reverse_iterator(this, m_end); }
  71         const_reverse_iterator rend() const { return const_reverse_iterator(this, m_start); }
  72
  73         T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
  74         const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
  75
  76         template<typename U> void append(const U&);
  77         template<typename U> void prepend(const U&);
  78         void removeFirst();
  79         void remove(iterator&);
  80         void remove(const_iterator&);
  81
  82         void clear();
  83
  84         template<typename Predicate>
  85         iterator findIf(Predicate&);
  86
  87     private:
  88         friend class DequeIteratorBase<T>;
  89
  90         typedef VectorBuffer<T, 0> Buffer;
  91         typedef VectorTypeOperations<T> TypeOperations;
  92         typedef DequeIteratorBase<T> IteratorBase;
  93
  94         void remove(size_t position);
  95         void invalidateIterators();
  96         void destroyAll();
  97         void checkValidity() const;
  98         void checkIndexValidity(size_t) const;
  99         void expandCapacityIfNeeded();
 100         void expandCapacity();
 101
 102         size_t m_start;
 103         size_t m_end;
 104         Buffer m_buffer;
 105 #ifndef NDEBUG
 106         mutable IteratorBase* m_iterators;
 107 #endif
 108     };
 109
 110     template<typename T>
 111     class DequeIteratorBase {
 112     private:
 113         typedef DequeIteratorBase<T> Base;
 114
 115     protected:
 116         DequeIteratorBase();
 117         DequeIteratorBase(const Deque<T>*, size_t);
 118         DequeIteratorBase(const Base&);
 119         Base& operator=(const Base&);
 120         ~DequeIteratorBase();
 121
 122         void assign(const Base& other) { *this = other; }
 123
 124         void increment();
 125         void decrement();
 126
 127         T* before() const;
 128         T* after() const;
 129
 130         bool isEqual(const Base&) const;
 131
 132     private:
 133         void addToIteratorsList();
 134         void removeFromIteratorsList();
 135         void checkValidity() const;
 136         void checkValidity(const Base&) const;
 137
 138         Deque<T>* m_deque;
 139         size_t m_index;
 140
 141         friend class Deque<T>;
 142
 143 #ifndef NDEBUG
 144         mutable DequeIteratorBase* m_next;
 145         mutable DequeIteratorBase* m_previous;
 146 #endif
 147     };
 148
 149     template<typename T>
 150     class DequeIterator : public DequeIteratorBase<T> {
 151     private:
 152         typedef DequeIteratorBase<T> Base;
 153         typedef DequeIterator<T> Iterator;
 154
 155     public:
 156         DequeIterator(Deque<T>* deque, size_t index) : Base(deque, index) { }
 157
 158         DequeIterator(const Iterator& other) : Base(other) { }
 159         DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
 160
 161         T& operator*() const { return *Base::after(); }
 162         T* operator->() const { return Base::after(); }
 163
 164         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
 165         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 166
 167         Iterator& operator++() { Base::increment(); return *this; }
 168         // postfix ++ intentionally omitted
 169         Iterator& operator--() { Base::decrement(); return *this; }
 170         // postfix -- intentionally omitted
 171     };
 172
 173     template<typename T>
 174     class DequeConstIterator : public DequeIteratorBase<T> {
 175     private:
 176         typedef DequeIteratorBase<T> Base;
 177         typedef DequeConstIterator<T> Iterator;
 178         typedef DequeIterator<T> NonConstIterator;
 179
 180     public:
 181         DequeConstIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
 182
 183         DequeConstIterator(const Iterator& other) : Base(other) { }
 184         DequeConstIterator(const NonConstIterator& other) : Base(other) { }
 185         DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
 186         DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
 187
 188         const T& operator*() const { return *Base::after(); }
 189         const T* operator->() const { return Base::after(); }
 190
 191         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
 192         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 193
 194         Iterator& operator++() { Base::increment(); return *this; }
 195         // postfix ++ intentionally omitted
 196         Iterator& operator--() { Base::decrement(); return *this; }
 197         // postfix -- intentionally omitted
 198     };
 199
 200     template<typename T>
 201     class DequeReverseIterator : public DequeIteratorBase<T> {
 202     private:
 203         typedef DequeIteratorBase<T> Base;
 204         typedef DequeReverseIterator<T> Iterator;
 205
 206     public:
 207         DequeReverseIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
 208
 209         DequeReverseIterator(const Iterator& other) : Base(other) { }
 210         DequeReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
 211
 212         T& operator*() const { return *Base::before(); }
 213         T* operator->() const { return Base::before(); }
 214
 215         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
 216         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 217
 218         Iterator& operator++() { Base::decrement(); return *this; }
 219         // postfix ++ intentionally omitted
 220         Iterator& operator--() { Base::increment(); return *this; }
 221         // postfix -- intentionally omitted
 222     };
 223
 224     template<typename T>
 225     class DequeConstReverseIterator : public DequeIteratorBase<T> {
 226     private:
 227         typedef DequeIteratorBase<T> Base;
 228         typedef DequeConstReverseIterator<T> Iterator;
 229         typedef DequeReverseIterator<T> NonConstIterator;
 230
 231     public:
 232         DequeConstReverseIterator(const Deque<T>* deque, size_t index) : Base(deque, index) { }
 233
 234         DequeConstReverseIterator(const Iterator& other) : Base(other) { }
 235         DequeConstReverseIterator(const NonConstIterator& other) : Base(other) { }
 236         DequeConstReverseIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
 237         DequeConstReverseIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }
 238
 239         const T& operator*() const { return *Base::before(); }
 240         const T* operator->() const { return Base::before(); }
 241
 242         bool operator==(const Iterator& other) const { return Base::isEqual(other); }
 243         bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
 244
 245         Iterator& operator++() { Base::decrement(); return *this; }
 246         // postfix ++ intentionally omitted
 247         Iterator& operator--() { Base::increment(); return *this; }
 248         // postfix -- intentionally omitted
 249     };
 250
 251 #ifdef NDEBUG
 252     template<typename T> inline void Deque<T>::checkValidity() const { }
 253     template<typename T> inline void Deque<T>::checkIndexValidity(size_t) const { }
 254     template<typename T> inline void Deque<T>::invalidateIterators() { }
 255 #else
 256     template<typename T>
 257     void Deque<T>::checkValidity() const
 258     {
 259         if (!m_buffer.capacity()) {
 260             ASSERT(!m_start);
 261             ASSERT(!m_end);
 262         } else {
 263             ASSERT(m_start < m_buffer.capacity());
 264             ASSERT(m_end < m_buffer.capacity());
 265         }
 266     }
 267
 268     template<typename T>
 269     void Deque<T>::checkIndexValidity(size_t index) const
 270     {
 271         ASSERT(index <= m_buffer.capacity());
 272         if (m_start <= m_end) {
 273             ASSERT(index >= m_start);
 274             ASSERT(index <= m_end);
 275         } else {
 276             ASSERT(index >= m_start || index <= m_end);
 277         }
 278     }
 279
 280     template<typename T>
 281     void Deque<T>::invalidateIterators()
 282     {
 283         IteratorBase* next;
 284         for (IteratorBase* p = m_iterators; p; p = next) {
 285             next = p->m_next;
 286             p->m_deque = 0;
 287             p->m_next = 0;
 288             p->m_previous = 0;
 289         }
 290         m_iterators = 0;
 291     }
 292 #endif
 293
 294     template<typename T>
 295     inline Deque<T>::Deque()
 296         : m_start(0)
 297         , m_end(0)
 298 #ifndef NDEBUG
 299         , m_iterators(0)
 300 #endif
 301     {
 302         checkValidity();
 303     }
 304
 305     template<typename T>
 306     inline Deque<T>::Deque(const Deque<T>& other)
 307         : m_start(other.m_start)
 308         , m_end(other.m_end)
 309         , m_buffer(other.m_buffer.capacity())
 310 #ifndef NDEBUG
 311         , m_iterators(0)
 312 #endif
 313     {
 314         const T* otherBuffer = other.m_buffer.buffer();
 315         if (m_start <= m_end)
 316             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
 317         else {
 318             TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
 319             TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
 320         }
 321     }
 322
 323     template<typename T>
 324     void deleteAllValues(const Deque<T>& collection)
 325     {
 326         typedef typename Deque<T>::const_iterator iterator;
 327         iterator end = collection.end();
 328         for (iterator it = collection.begin(); it != end; ++it)
 329             delete *it;
 330     }
 331
 332     template<typename T>
 333     inline Deque<T>& Deque<T>::operator=(const Deque<T>& other)
 334     {
 335         Deque<T> copy(other);
 336         swap(copy);
 337         return *this;
 338     }
 339
 340     template<typename T>
 341     inline void Deque<T>::destroyAll()
 342     {
 343         if (m_start <= m_end)
 344             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
 345         else {
 346             TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
 347             TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
 348         }
 349     }
 350
 351     template<typename T>
 352     inline Deque<T>::~Deque()
 353     {
 354         checkValidity();
 355         invalidateIterators();
 356         destroyAll();
 357     }
 358
 359     template<typename T>
 360     inline void Deque<T>::swap(Deque<T>& other)
 361     {
 362         checkValidity();
 363         other.checkValidity();
 364         invalidateIterators();
 365         std::swap(m_start, other.m_start);
 366         std::swap(m_end, other.m_end);
 367         m_buffer.swap(other.m_buffer);
 368         checkValidity();
 369         other.checkValidity();
 370     }
 371
 372     template<typename T>
 373     inline void Deque<T>::clear()
 374     {
 375         checkValidity();
 376         invalidateIterators();
 377         destroyAll();
 378         m_start = 0;
 379         m_end = 0;
 380         checkValidity();
 381     }
 382
 383     template<typename T>
 384     template<typename Predicate>
 385     inline DequeIterator<T> Deque<T>::findIf(Predicate& predicate)
 386     {
 387         iterator end_iterator = end();
 388         for (iterator it = begin(); it != end_iterator; ++it) {
 389             if (predicate(*it))
 390                 return it;
 391         }
 392         return end_iterator;
 393     }
 394
 395     template<typename T>
 396     inline void Deque<T>::expandCapacityIfNeeded()
 397     {
 398         if (m_start) {
 399             if (m_end + 1 != m_start)
 400                 return;
 401         } else if (m_end) {
 402             if (m_end != m_buffer.capacity() - 1)
 403                 return;
 404         } else if (m_buffer.capacity())
 405             return;
 406
 407         expandCapacity();
 408     }
 409
 410     template<typename T>
 411     void Deque<T>::expandCapacity()
 412     {
 413         checkValidity();
 414         size_t oldCapacity = m_buffer.capacity();
 415         size_t newCapacity = max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1);
 416         T* oldBuffer = m_buffer.buffer();
 417         m_buffer.allocateBuffer(newCapacity);
 418         if (m_start <= m_end)
 419             TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
 420         else {
 421             TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
 422             size_t newStart = newCapacity - (oldCapacity - m_start);
 423             TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
 424             m_start = newStart;
 425         }
 426         m_buffer.deallocateBuffer(oldBuffer);
 427         checkValidity();
 428     }
 429
 430     template<typename T> template<typename U>
 431     inline void Deque<T>::append(const U& value)
 432     {
 433         checkValidity();
 434         expandCapacityIfNeeded();
 435         new (&m_buffer.buffer()[m_end]) T(value);
 436         if (m_end == m_buffer.capacity() - 1)
 437             m_end = 0;
 438         else
 439             ++m_end;
 440         checkValidity();
 441     }
 442
 443     template<typename T> template<typename U>
 444     inline void Deque<T>::prepend(const U& value)
 445     {
 446         checkValidity();
 447         expandCapacityIfNeeded();
 448         if (!m_start)
 449             m_start = m_buffer.capacity() - 1;
 450         else
 451             --m_start;
 452         new (&m_buffer.buffer()[m_start]) T(value);
 453         checkValidity();
 454     }
 455
 456     template<typename T>
 457     inline void Deque<T>::removeFirst()
 458     {
 459         checkValidity();
 460         invalidateIterators();
 461         ASSERT(!isEmpty());
 462         TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
 463         if (m_start == m_buffer.capacity() - 1)
 464             m_start = 0;
 465         else
 466             ++m_start;
 467         checkValidity();
 468     }
 469
 470     template<typename T>
 471     inline void Deque<T>::remove(iterator& it)
 472     {
 473         it.checkValidity();
 474         remove(it.m_index);
 475     }
 476
 477     template<typename T>
 478     inline void Deque<T>::remove(const_iterator& it)
 479     {
 480         it.checkValidity();
 481         remove(it.m_index);
 482     }
 483
 484     template<typename T>
 485     inline void Deque<T>::remove(size_t position)
 486     {
 487         if (position == m_end)
 488             return;
 489
 490         checkValidity();
 491         invalidateIterators();
 492
 493         T* buffer = m_buffer.buffer();
 494         TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
 495
 496         // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
 497         if (position >= m_start) {
 498             TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
 499             m_start = (m_start + 1) % m_buffer.capacity();
 500         } else {
 501             TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
 502             m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
 503         }
 504         checkValidity();
 505     }
 506
 507 #ifdef NDEBUG
 508     template<typename T> inline void DequeIteratorBase<T>::checkValidity() const { }
 509     template<typename T> inline void DequeIteratorBase<T>::checkValidity(const DequeIteratorBase<T>&) const { }
 510     template<typename T> inline void DequeIteratorBase<T>::addToIteratorsList() { }
 511     template<typename T> inline void DequeIteratorBase<T>::removeFromIteratorsList() { }
 512 #else
 513     template<typename T>
 514     void DequeIteratorBase<T>::checkValidity() const
 515     {
 516         ASSERT(m_deque);
 517         m_deque->checkIndexValidity(m_index);
 518     }
 519
 520     template<typename T>
 521     void DequeIteratorBase<T>::checkValidity(const Base& other) const
 522     {
 523         checkValidity();
 524         other.checkValidity();
 525         ASSERT(m_deque == other.m_deque);
 526     }
 527
 528     template<typename T>
 529     void DequeIteratorBase<T>::addToIteratorsList()
 530     {
 531         if (!m_deque)
 532             m_next = 0;
 533         else {
 534             m_next = m_deque->m_iterators;
 535             m_deque->m_iterators = this;
 536             if (m_next)
 537                 m_next->m_previous = this;
 538         }
 539         m_previous = 0;
 540     }
 541
 542     template<typename T>
 543     void DequeIteratorBase<T>::removeFromIteratorsList()
 544     {
 545         if (!m_deque) {
 546             ASSERT(!m_next);
 547             ASSERT(!m_previous);
 548         } else {
 549             if (m_next) {
 550                 ASSERT(m_next->m_previous == this);
 551                 m_next->m_previous = m_previous;
 552             }
 553             if (m_previous) {
 554                 ASSERT(m_deque->m_iterators != this);
 555                 ASSERT(m_previous->m_next == this);
 556                 m_previous->m_next = m_next;
 557             } else {
 558                 ASSERT(m_deque->m_iterators == this);
 559                 m_deque->m_iterators = m_next;
 560             }
 561         }
 562         m_next = 0;
 563         m_previous = 0;
 564     }
 565 #endif
 566
 567     template<typename T>
 568     inline DequeIteratorBase<T>::DequeIteratorBase()
 569         : m_deque(0)
 570     {
 571     }
 572
 573     template<typename T>
 574     inline DequeIteratorBase<T>::DequeIteratorBase(const Deque<T>* deque, size_t index)
 575         : m_deque(const_cast<Deque<T>*>(deque))
 576         , m_index(index)
 577     {
 578         addToIteratorsList();
 579         checkValidity();
 580     }
 581
 582     template<typename T>
 583     inline DequeIteratorBase<T>::DequeIteratorBase(const Base& other)
 584         : m_deque(other.m_deque)
 585         , m_index(other.m_index)
 586     {
 587         addToIteratorsList();
 588         checkValidity();
 589     }
 590
 591     template<typename T>
 592     inline DequeIteratorBase<T>& DequeIteratorBase<T>::operator=(const Base& other)
 593     {
 594         checkValidity();
 595         other.checkValidity();
 596         removeFromIteratorsList();
 597
 598         m_deque = other.m_deque;
 599         m_index = other.m_index;
 600         addToIteratorsList();
 601         checkValidity();
 602         return *this;
 603     }
 604
 605     template<typename T>
 606     inline DequeIteratorBase<T>::~DequeIteratorBase()
 607     {
 608 #ifndef NDEBUG
 609         removeFromIteratorsList();
 610         m_deque = 0;
 611 #endif
 612     }
 613
 614     template<typename T>
 615     inline bool DequeIteratorBase<T>::isEqual(const Base& other) const
 616     {
 617         checkValidity(other);
 618         return m_index == other.m_index;
 619     }
 620
 621     template<typename T>
 622     inline void DequeIteratorBase<T>::increment()
 623     {
 624         checkValidity();
 625         ASSERT(m_index != m_deque->m_end);
 626         ASSERT(m_deque->m_buffer.capacity());
 627         if (m_index == m_deque->m_buffer.capacity() - 1)
 628             m_index = 0;
 629         else
 630             ++m_index;
 631         checkValidity();
 632     }
 633
 634     template<typename T>
 635     inline void DequeIteratorBase<T>::decrement()
 636     {
 637         checkValidity();
 638         ASSERT(m_index != m_deque->m_start);
 639         ASSERT(m_deque->m_buffer.capacity());
 640         if (!m_index)
 641             m_index = m_deque->m_buffer.capacity() - 1;
 642         else
 643             --m_index;
 644         checkValidity();
 645     }
 646
 647     template<typename T>
 648     inline T* DequeIteratorBase<T>::after() const
 649     {
 650         checkValidity();
 651         ASSERT(m_index != m_deque->m_end);
 652         return &m_deque->m_buffer.buffer()[m_index];
 653     }
 654
 655     template<typename T>
 656     inline T* DequeIteratorBase<T>::before() const
 657     {
 658         checkValidity();
 659         ASSERT(m_index != m_deque->m_start);
 660         if (!m_index)
 661             return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
 662         return &m_deque->m_buffer.buffer()[m_index - 1];
 663     }
 664
 665 } // namespace WTF
 666
 667 using WTF::Deque;
 668
 669 #endif // WTF_Deque_h