home *** CD-ROM | disk | FTP | other *** search
/ Computer Shopper 275 / DPCS0111DVD.ISO / Toolkit / Audio-Visual / VirtualDub / Source / VirtualDub-1.9.10-src.7z / src / h / vd2 / system / vdstl.h < prev    next >
Encoding:
C/C++ Source or Header  |  2009-09-14  |  43.3 KB  |  1,611 lines
  1. //    VirtualDub - Video processing and capture application
  2. //    System library component
  3. //    Copyright (C) 1998-2007 Avery Lee, All Rights Reserved.
  4. //
  5. //    Beginning with 1.6.0, the VirtualDub system library is licensed
  6. //    differently than the remainder of VirtualDub.  This particular file is
  7. //    thus licensed as follows (the "zlib" license):
  8. //
  9. //    This software is provided 'as-is', without any express or implied
  10. //    warranty.  In no event will the authors be held liable for any
  11. //    damages arising from the use of this software.
  12. //
  13. //    Permission is granted to anyone to use this software for any purpose,
  14. //    including commercial applications, and to alter it and redistribute it
  15. //    freely, subject to the following restrictions:
  16. //
  17. //    1.    The origin of this software must not be misrepresented; you must
  18. //        not claim that you wrote the original software. If you use this
  19. //        software in a product, an acknowledgment in the product
  20. //        documentation would be appreciated but is not required.
  21. //    2.    Altered source versions must be plainly marked as such, and must
  22. //        not be misrepresented as being the original software.
  23. //    3.    This notice may not be removed or altered from any source
  24. //        distribution.
  25.  
  26. #ifndef VD2_SYSTEM_VDSTL_H
  27. #define VD2_SYSTEM_VDSTL_H
  28.  
  29. #ifdef _MSC_VER
  30.     #pragma once
  31. #endif
  32.  
  33. #include <limits.h>
  34. #include <vd2/system/vdtypes.h>
  35. #include <vd2/system/memory.h>
  36.  
  37. ///////////////////////////////////////////////////////////////////////////
  38. //
  39. //    glue
  40. //
  41. ///////////////////////////////////////////////////////////////////////////
  42.  
  43. template<class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&>
  44. struct vditerator {
  45. #if defined(VD_COMPILER_MSVC) && (VD_COMPILER_MSVC < 1310 || (defined(VD_COMPILER_MSVC_VC8_PSDK) || defined(VD_COMPILER_MSVC_VC8_DDK)))
  46.     typedef std::iterator<Category, T, Distance> type;
  47. #else
  48.     typedef std::iterator<Category, T, Distance, Pointer, Reference> type;
  49. #endif
  50. };
  51.  
  52. template<class Iterator, class T>
  53. struct vdreverse_iterator {
  54. #if defined(VD_COMPILER_MSVC) && (VD_COMPILER_MSVC < 1310 || (defined(VD_COMPILER_MSVC_VC8_PSDK) || defined(VD_COMPILER_MSVC_VC8_DDK)))
  55.     typedef std::reverse_iterator<Iterator, T> type;
  56. #else
  57.     typedef std::reverse_iterator<Iterator> type;
  58. #endif
  59. };
  60.  
  61. ///////////////////////////////////////////////////////////////////////////
  62. class vdallocator_base {
  63. protected:
  64.     void VDNORETURN throw_oom();
  65. };
  66.  
  67. template<class T>
  68. class vdallocator : public vdallocator_base {
  69. public:
  70.     typedef    size_t        size_type;
  71.     typedef    ptrdiff_t    difference_type;
  72.     typedef    T*            pointer;
  73.     typedef    const T*    const_pointer;
  74.     typedef    T&            reference;
  75.     typedef    const T&    const_reference;
  76.     typedef    T            value_type;
  77.  
  78.     template<class U> struct rebind { typedef vdallocator<U> other; };
  79.  
  80.     pointer            address(reference x) const            { return &x; }
  81.     const_pointer    address(const_reference x) const    { return &x; }
  82.  
  83.     pointer allocate(size_type n, void *p_close = 0) {
  84.         pointer p = (pointer)malloc(n*sizeof(T));
  85.  
  86.         if (!p)
  87.             throw_oom();
  88.  
  89.         return p;
  90.     }
  91.  
  92.     void deallocate(pointer p, size_type n) {
  93.         free(p);
  94.     }
  95.  
  96.     size_type        max_size() const throw()            { return ((~(size_type)0) >> 1) / sizeof(T); }
  97.  
  98.     void            construct(pointer p, const T& val)    { new((void *)p) T(val); }
  99.     void            destroy(pointer p)                    { ((T*)p)->~T(); }
  100.  
  101. #if defined(_MSC_VER) && _MSC_VER < 1300
  102.     char *            _Charalloc(size_type n)                { return rebind<char>::other::allocate(n); }
  103. #endif
  104. };
  105.  
  106. ///////////////////////////////////////////////////////////////////////////
  107.  
  108. template<class T, unsigned kDeadZone = 16>
  109. class vddebug_alloc {
  110. public:
  111.     typedef    size_t        size_type;
  112.     typedef    ptrdiff_t    difference_type;
  113.     typedef    T*            pointer;
  114.     typedef    const T*    const_pointer;
  115.     typedef    T&            reference;
  116.     typedef    const T&    const_reference;
  117.     typedef    T            value_type;
  118.  
  119.     template<class U> struct rebind { typedef vddebug_alloc<U, kDeadZone> other; };
  120.  
  121.     pointer            address(reference x) const            { return &x; }
  122.     const_pointer    address(const_reference x) const    { return &x; }
  123.  
  124.     pointer allocate(size_type n, void *p_close = 0) {
  125.         pointer p = (pointer)VDAlignedMalloc(n*sizeof(T) + 2*kDeadZone, 16);
  126.  
  127.         if (!p)
  128.             return p;
  129.  
  130.         memset((char *)p, 0xa9, kDeadZone);
  131.         memset((char *)p + kDeadZone + n*sizeof(T), 0xa9, kDeadZone);
  132.  
  133.         return (pointer)((char *)p + kDeadZone);
  134.     }
  135.  
  136.     void deallocate(pointer p, size_type n) {
  137.         char *p1 = (char *)p - kDeadZone;
  138.         char *p2 = (char *)p + n*sizeof(T);
  139.  
  140.         for(uint32 i=0; i<kDeadZone; ++i) {
  141.             VDASSERT(p1[i] == (char)0xa9);
  142.             VDASSERT(p2[i] == (char)0xa9);
  143.         }
  144.  
  145.         VDAlignedFree(p1);
  146.     }
  147.  
  148.     size_type        max_size() const throw()            { return MAX_INT - 2*kDeadZone; }
  149.  
  150.     void            construct(pointer p, const T& val)    { new((void *)p) T(val); }
  151.     void            destroy(pointer p)                    { ((T*)p)->~T(); }
  152.  
  153. #if defined(_MSC_VER) && _MSC_VER < 1300
  154.     char *            _Charalloc(size_type n)                { return rebind<char>::other::allocate(n); }
  155. #endif
  156. };
  157.  
  158. ///////////////////////////////////////////////////////////////////////////
  159.  
  160. template<class T, unsigned kAlignment = 16>
  161. class vdaligned_alloc {
  162. public:
  163.     typedef    size_t        size_type;
  164.     typedef    ptrdiff_t    difference_type;
  165.     typedef    T*            pointer;
  166.     typedef    const T*    const_pointer;
  167.     typedef    T&            reference;
  168.     typedef    const T&    const_reference;
  169.     typedef    T            value_type;
  170.  
  171.     vdaligned_alloc() {}
  172.  
  173.     template<class U, unsigned kAlignment2>
  174.     vdaligned_alloc(const vdaligned_alloc<U, kAlignment2>&) {}
  175.  
  176.     template<class U> struct rebind { typedef vdaligned_alloc<U, kAlignment> other; };
  177.  
  178.     pointer            address(reference x) const            { return &x; }
  179.     const_pointer    address(const_reference x) const    { return &x; }
  180.  
  181.     pointer            allocate(size_type n, void *p = 0)    { return (pointer)VDAlignedMalloc(n*sizeof(T), kAlignment); }
  182.     void            deallocate(pointer p, size_type n)    { VDAlignedFree(p); }
  183.     size_type        max_size() const throw()            { return INT_MAX; }
  184.  
  185.     void            construct(pointer p, const T& val)    { new((void *)p) T(val); }
  186.     void            destroy(pointer p)                    { ((T*)p)->~T(); }
  187.  
  188. #if defined(_MSC_VER) && _MSC_VER < 1300
  189.     char *            _Charalloc(size_type n)                { return rebind<char>::other::allocate(n); }
  190. #endif
  191. };
  192.  
  193. ///////////////////////////////////////////////////////////////////////////
  194. //
  195. //    vdblock
  196. //
  197. //    vdblock<T> is similar to vector<T>, except:
  198. //
  199. //    1) May only be used with POD types.
  200. //    2) No construction or destruction of elements is performed.
  201. //    3) Capacity is always equal to size, and reallocation is performed
  202. //       whenever the size changes.
  203. //    4) Contents are undefined after a reallocation.
  204. //    5) No insertion or deletion operations are provided.
  205. //
  206. ///////////////////////////////////////////////////////////////////////////
  207.  
  208. template<class T, class A = vdallocator<T> >
  209. class vdblock : protected A {
  210. public:
  211.     typedef    T                                    value_type;
  212.     typedef    typename A::pointer                    pointer;
  213.     typedef    typename A::const_pointer            const_pointer;
  214.     typedef    typename A::reference                reference;
  215.     typedef    typename A::const_reference            const_reference;
  216.     typedef    size_t                                size_type;
  217.     typedef    ptrdiff_t                            difference_type;
  218.     typedef    pointer                                iterator;
  219.     typedef    const_pointer                        const_iterator;
  220.     typedef typename vdreverse_iterator<iterator, T>::type            reverse_iterator;
  221.     typedef typename vdreverse_iterator<const_iterator, const T>::type    const_reverse_iterator;
  222.  
  223.     vdblock(const A& alloc = A()) : A(alloc), mpBlock(NULL), mSize(0) {}
  224.     vdblock(size_type s, const A& alloc = A()) : A(alloc), mpBlock(A::allocate(s, 0)), mSize(s) {}
  225.     ~vdblock() {
  226.         if (mpBlock)
  227.             A::deallocate(mpBlock, mSize);
  228.     }
  229.  
  230.     reference                operator[](size_type n)            { return mpBlock[n]; }
  231.     const_reference            operator[](size_type n) const    { return mpBlock[n]; }
  232.     reference                at(size_type n)                    { return n < mSize ? mpBlock[n] : throw std::length_error; }
  233.     const_reference            at(size_type n) const            { return n < mSize ? mpBlock[n] : throw std::length_error; }
  234.     reference                front()                            { return *mpBlock; }
  235.     const_reference            front() const                    { return *mpBlock; }
  236.     reference                back()                            { return mpBlock[mSize-1]; }
  237.     const_reference            back() const                    { return mpBlock[mSize-1]; }
  238.  
  239.     const_pointer            data() const    { return mpBlock; }
  240.     pointer                    data()            { return mpBlock; }
  241.  
  242.     const_iterator            begin() const    { return mpBlock; }
  243.     iterator                begin()            { return mpBlock; }
  244.     const_iterator            end() const        { return mpBlock + mSize; }
  245.     iterator                end()            { return mpBlock + mSize; }
  246.  
  247.     const_reverse_iterator    rbegin() const    { return const_reverse_iterator(end()); }
  248.     reverse_iterator        rbegin()        { return reverse_iterator(end()); }
  249.     const_reverse_iterator    rend() const    { return const_reverse_iterator(begin()); }
  250.     reverse_iterator        rend()            { return reverse_iterator(begin()); }
  251.  
  252.     bool                    empty() const        { return !mSize; }
  253.     size_type                size() const        { return mSize; }
  254.     size_type                capacity() const    { return mSize; }
  255.  
  256.     void clear() {
  257.         if (mpBlock)
  258.             A::deallocate(mpBlock, mSize);
  259.         mpBlock = NULL;
  260.         mSize = 0;
  261.     }
  262.  
  263.     void resize(size_type s) {
  264.         if (s != mSize) {
  265.             if (mpBlock) {
  266.                 A::deallocate(mpBlock, mSize);
  267.                 mpBlock = NULL;
  268.             }
  269.             mSize = s;
  270.             if (s)
  271.                 mpBlock = A::allocate(mSize, 0);
  272.         }
  273.     }
  274.  
  275.     void resize(size_type s, const T& value) {
  276.         if (s != mSize) {
  277.             if (mpBlock) {
  278.                 A::deallocate(mpBlock, mSize);
  279.                 mpBlock = NULL;
  280.             }
  281.             mSize = s;
  282.             if (s) {
  283.                 mpBlock = A::allocate(mSize, 0);
  284.                 std::fill(mpBlock, mpBlock+s, value);
  285.             }
  286.         }
  287.     }
  288.  
  289.     void swap(vdblock& x) {
  290.         std::swap(mpBlock, x.mpBlock);
  291.         std::swap(mSize, x.mSize);
  292.     }
  293.  
  294. protected:
  295.     typename A::pointer        mpBlock;
  296.     typename A::size_type    mSize;
  297.  
  298.     union PODType {
  299.         T x;
  300.     };
  301. };
  302.  
  303. ///////////////////////////////////////////////////////////////////////////
  304. //
  305. //    vdstructex
  306. //
  307. //    vdstructex describes an extensible format structure, such as
  308. //    BITMAPINFOHEADER or WAVEFORMATEX, without the pain-in-the-butt
  309. //    casting normally associated with one.
  310. //
  311. ///////////////////////////////////////////////////////////////////////////
  312.  
  313. template<class T>
  314. class vdstructex {
  315. public:
  316.     typedef size_t            size_type;
  317.     typedef T                value_type;
  318.  
  319.     vdstructex() : mpMemory(NULL), mSize(0) {}
  320.  
  321.     explicit vdstructex(size_t len) : mpMemory(NULL), mSize(0) {
  322.         resize(len);
  323.     }
  324.  
  325.     vdstructex(const T *pStruct, size_t len) : mSize(len), mpMemory((T*)malloc(len)) {
  326.         memcpy(mpMemory, pStruct, len);
  327.     }
  328.  
  329.     vdstructex(const vdstructex<T>& src) : mSize(src.mSize), mpMemory((T*)malloc(src.mSize)) {
  330.         memcpy(mpMemory, src.mpMemory, mSize);
  331.     }
  332.  
  333.     ~vdstructex() {
  334.         free(mpMemory);
  335.     }
  336.  
  337.     bool        empty() const        { return !mpMemory; }
  338.     size_type    size() const        { return mSize; }
  339.     T*            data() const        { return mpMemory; }
  340.  
  341.     T&    operator *() const    { return *(T *)mpMemory; }
  342.     T*    operator->() const    { return (T *)mpMemory; }
  343.  
  344.     bool operator==(const vdstructex& x) const {
  345.         return mSize == x.mSize && (!mSize || !memcmp(mpMemory, x.mpMemory, mSize));
  346.     }
  347.  
  348.     bool operator!=(const vdstructex& x) const {
  349.         return mSize != x.mSize || (mSize && memcmp(mpMemory, x.mpMemory, mSize));
  350.     }
  351.  
  352.     vdstructex<T>& operator=(const vdstructex<T>& src) {
  353.         assign(src.mpMemory, src.mSize);
  354.         return *this;
  355.     }
  356.  
  357.     void assign(const T *pStruct, size_type len) {
  358.         if (mSize != len)
  359.             resize(len);
  360.  
  361.         memcpy(mpMemory, pStruct, len);
  362.     }
  363.  
  364.     void clear() {
  365.         free(mpMemory);
  366.         mpMemory = NULL;
  367.         mSize = 0;
  368.     }
  369.  
  370.     void resize(size_type len) {
  371.         if (mSize != len)
  372.             mpMemory = (T *)realloc(mpMemory, mSize = len);
  373.     }
  374.  
  375. protected:
  376.     size_type    mSize;
  377.     T *mpMemory;
  378. };
  379.  
  380. ///////////////////////////////////////////////////////////////////////////
  381. //
  382. //    vdlist
  383. //
  384. //    vdlist<T> is similar to list<T*>, except:
  385. //
  386. //    1) The node structure must be embedded as a superclass of T.
  387. //     Thus, the client is in full control of allocation.
  388. //    2) Node pointers may be converted back into iterators in O(1).
  389. //
  390. ///////////////////////////////////////////////////////////////////////////
  391.  
  392. struct vdlist_node {
  393.     vdlist_node *mListNodeNext, *mListNodePrev;
  394. };
  395.  
  396. template<class T, class T_Nonconst>
  397. class vdlist_iterator : public vditerator<std::bidirectional_iterator_tag, T, ptrdiff_t>::type {
  398. public:
  399.     vdlist_iterator() {}
  400.     vdlist_iterator(T *p) : mp(p) {}
  401.     vdlist_iterator(const vdlist_iterator<T_Nonconst, T_Nonconst>& src) : mp(src.mp) {}
  402.  
  403.     T* operator *() const {
  404.         return static_cast<T*>(mp);
  405.     }
  406.  
  407.     bool operator==(const vdlist_iterator<T, T_Nonconst>& x) const {
  408.         return mp == x.mp;
  409.     }
  410.  
  411.     bool operator!=(const vdlist_iterator<T, T_Nonconst>& x) const {
  412.         return mp != x.mp;
  413.     }
  414.  
  415.     vdlist_iterator& operator++() {
  416.         mp = mp->mListNodeNext;
  417.         return *this;
  418.     }
  419.  
  420.     vdlist_iterator& operator--() {
  421.         mp = mp->mListNodePrev;
  422.         return *this;
  423.     }
  424.  
  425.     vdlist_iterator operator++(int) {
  426.         iterator tmp(*this);
  427.         mp = mp->mListNodeNext;
  428.         return tmp;
  429.     }
  430.  
  431.     vdlist_iterator& operator--(int) {
  432.         iterator tmp(*this);
  433.         mp = mp->mListNodePrev;
  434.         return tmp;
  435.     }
  436.  
  437.     vdlist_node *mp;
  438. };
  439.  
  440. class vdlist_base {
  441. public:
  442.     typedef    vdlist_node                        node;
  443.     typedef    size_t                            size_type;
  444.     typedef    ptrdiff_t                        difference_type;
  445.  
  446.     bool empty() const {
  447.         return mAnchor.mListNodeNext == &mAnchor;
  448.     }
  449.  
  450.     size_type size() const {
  451.         node *p = { mAnchor.mListNodeNext };
  452.         size_type s = 0;
  453.  
  454.         if (p != &mAnchor)
  455.             do {
  456.                 ++s;
  457.                 p = p->mListNodeNext;
  458.             } while(p != &mAnchor);
  459.  
  460.         return s;
  461.     }
  462.  
  463.     void clear() {
  464.         mAnchor.mListNodePrev    = &mAnchor;
  465.         mAnchor.mListNodeNext    = &mAnchor;
  466.     }
  467.  
  468.     void pop_front() {
  469.         mAnchor.mListNodeNext = mAnchor.mListNodeNext->mListNodeNext;
  470.         mAnchor.mListNodeNext->mListNodePrev = &mAnchor;
  471.     }
  472.  
  473.     void pop_back() {
  474.         mAnchor.mListNodePrev = mAnchor.mListNodePrev->mListNodePrev;
  475.         mAnchor.mListNodePrev->mListNodeNext = &mAnchor;
  476.     }
  477.  
  478.     static void unlink(vdlist_node& node) {
  479.         vdlist_node& n1 = *node.mListNodePrev;
  480.         vdlist_node& n2 = *node.mListNodeNext;
  481.  
  482.         n1.mListNodeNext = &n2;
  483.         n2.mListNodePrev = &n1;
  484.     }
  485.  
  486. protected:
  487.     node    mAnchor;
  488. };
  489.  
  490. template<class T>
  491. class vdlist : public vdlist_base {
  492. public:
  493.     typedef    T*                                value_type;
  494.     typedef    T**                                pointer;
  495.     typedef    const T**                        const_pointer;
  496.     typedef    T*&                                reference;
  497.     typedef    const T*&                        const_reference;
  498.     typedef    vdlist_iterator<T, T>                        iterator;
  499.     typedef vdlist_iterator<const T, T>                    const_iterator;
  500.     typedef typename vdreverse_iterator<iterator, T>::type            reverse_iterator;
  501.     typedef typename vdreverse_iterator<const_iterator, const T>::type    const_reverse_iterator;
  502.  
  503.     vdlist() {
  504.         mAnchor.mListNodePrev    = &mAnchor;
  505.         mAnchor.mListNodeNext    = &mAnchor;
  506.     }
  507.  
  508.     iterator begin() {
  509.         iterator it;
  510.         it.mp = mAnchor.mListNodeNext;
  511.         return it;
  512.     }
  513.  
  514.     const_iterator begin() const {
  515.         const_iterator it;
  516.         it.mp = mAnchor.mListNodeNext;
  517.         return it;
  518.     }
  519.  
  520.     iterator end() {
  521.         iterator it;
  522.         it.mp = &mAnchor;
  523.         return it;
  524.     }
  525.  
  526.     const_iterator end() const {
  527.         const_iterator it;
  528.         it.mp = &mAnchor;
  529.         return it;
  530.     }
  531.  
  532.     reverse_iterator rbegin() {
  533.         return reverse_iterator(begin());
  534.     }
  535.  
  536.     const_reverse_iterator rbegin() const {
  537.         return const_reverse_iterator(begin());
  538.     }
  539.  
  540.     reverse_iterator rend() {
  541.         return reverse_iterator(end);
  542.     }
  543.  
  544.     const_reverse_iterator rend() const {
  545.         return const_reverse_iterator(end());
  546.     }
  547.  
  548.     const value_type front() const {
  549.         return static_cast<T *>(mAnchor.mListNodeNext);
  550.     }
  551.  
  552.     const value_type back() const {
  553.         return static_cast<T *>(mAnchor.mListNodePrev);
  554.     }
  555.  
  556.     iterator find(T *p) {
  557.         iterator it;
  558.         it.mp = mAnchor.mListNodeNext;
  559.  
  560.         if (it.mp != &mAnchor)
  561.             do {
  562.                 if (it.mp == static_cast<node *>(p))
  563.                     break;
  564.  
  565.                 it.mp = it.mp->mListNodeNext;
  566.             } while(it.mp != &mAnchor);
  567.  
  568.         return it;
  569.     }
  570.  
  571.     const_iterator find(T *p) const {
  572.         const_iterator it;
  573.         it.mp = mAnchor.mListNodeNext;
  574.  
  575.         if (it.mp != &mAnchor)
  576.             do {
  577.                 if (it.mp == static_cast<node *>(p))
  578.                     break;
  579.  
  580.                 it.mp = it.mp->mListNodeNext;
  581.             } while(it.mp != &mAnchor);
  582.  
  583.         return it;
  584.     }
  585.  
  586.     iterator fast_find(T *p) {
  587.         iterator it(p);
  588.         return it;
  589.     }
  590.  
  591.     const_iterator fast_find(T *p) const {
  592.         iterator it(p);
  593.     }
  594.  
  595.     void push_front(T *p) {
  596.         node& n = *p;
  597.         n.mListNodePrev = &mAnchor;
  598.         n.mListNodeNext = mAnchor.mListNodeNext;
  599.         n.mListNodeNext->mListNodePrev = &n;
  600.         mAnchor.mListNodeNext = &n;
  601.     }
  602.  
  603.     void push_back(T *p) {
  604.         node& n = *p;
  605.         n.mListNodeNext = &mAnchor;
  606.         n.mListNodePrev = mAnchor.mListNodePrev;
  607.         n.mListNodePrev->mListNodeNext = &n;
  608.         mAnchor.mListNodePrev = &n;
  609.     }
  610.  
  611.     iterator erase(T *p) {
  612.         return erase(fast_find(p));
  613.     }
  614.  
  615.     iterator erase(iterator it) {
  616.         node& n = *it.mp;
  617.  
  618.         n.mListNodePrev->mListNodeNext = n.mListNodeNext;
  619.         n.mListNodeNext->mListNodePrev = n.mListNodePrev;
  620.  
  621.         it.mp = n.mListNodeNext;
  622.         return it;
  623.     }
  624.  
  625.     iterator erase(iterator i1, iterator i2) {
  626.         node& np = *i1.mp->mListNodePrev;
  627.         node& nn = *i2.mp;
  628.  
  629.         np.mListNodeNext = &nn;
  630.         nn.mListNodePrev = &np;
  631.  
  632.         return i2;
  633.     }
  634.  
  635.     void insert(iterator dst, T *src) {
  636.         node& ns = *src;
  637.         node& nd = *dst.mp;
  638.  
  639.         ns.mListNodeNext = &nd;
  640.         ns.mListNodePrev = nd.mListNodePrev;
  641.         nd.mListNodePrev->mListNodeNext = &ns;
  642.         nd.mListNodePrev = &ns;
  643.     }
  644.  
  645.     void insert(iterator dst, iterator i1, iterator i2) {
  646.         if (i1 != i2) {
  647.             node& np = *dst.mp->mListNodePrev;
  648.             node& nn = *dst.mp;
  649.             node& n1 = *i1.mp;
  650.             node& n2 = *i2.mp->mListNodePrev;
  651.  
  652.             np.mListNodeNext = &n1;
  653.             n1.mListNodePrev = &np;
  654.             n2.mListNodeNext = &nn;
  655.             nn.mListNodePrev = &n2;
  656.         }
  657.     }
  658.  
  659.     void splice(iterator dst, vdlist<T>& srclist) {
  660.         insert(dst, srclist.begin(), srclist.end());
  661.         srclist.clear();
  662.     }
  663.  
  664.     void splice(iterator dst, vdlist<T>& srclist, iterator src) {
  665.         T *v = *src;
  666.         srclist.erase(src);
  667.         insert(dst, v);
  668.     }
  669.  
  670.     void splice(iterator dst, vdlist<T>& srclist, iterator i1, iterator i2) {
  671.         if (dst.mp != i1.mp && dst.mp != i2.mp) {
  672.             srclist.erase(i1, i2);
  673.             insert(dst, i1, i2);
  674.         }
  675.     }
  676. };
  677.  
  678. ///////////////////////////////////////////////////////////////////////////////
  679.  
  680. #if defined(_DEBUG) && defined(_MSC_VER)
  681.     #define VD_ACCELERATE_TEMPLATES
  682. #endif
  683.  
  684. #ifndef VDTINLINE
  685.     #ifdef VD_ACCELERATE_TEMPLATES
  686.         #ifndef VDTEXTERN
  687.             #define VDTEXTERN extern
  688.         #endif
  689.  
  690.         #define VDTINLINE
  691.     #else
  692.         #define VDTINLINE inline
  693.     #endif
  694. #endif
  695.  
  696. ///////////////////////////////////////////////////////////////////////////////
  697.  
  698. template<class T>
  699. class vdspan {
  700. public:
  701.     typedef    T                    value_type;
  702.     typedef    T*                    pointer;
  703.     typedef    const T*            const_pointer;
  704.     typedef    T&                    reference;
  705.     typedef    const T&            const_reference;
  706.     typedef    size_t                size_type;
  707.     typedef    ptrdiff_t            difference_type;
  708.     typedef    pointer                iterator;
  709.     typedef const_pointer        const_iterator;
  710.     typedef typename vdreverse_iterator<iterator, T>::type            reverse_iterator;
  711.     typedef typename vdreverse_iterator<const_iterator, const T>::type    const_reverse_iterator;
  712.  
  713.     VDTINLINE vdspan();
  714.     VDTINLINE vdspan(T *p1, T *p2);
  715.     VDTINLINE vdspan(T *p1, size_type len);
  716.  
  717. public:
  718.     VDTINLINE bool                    empty() const;
  719.     VDTINLINE size_type                size() const;
  720.  
  721.     VDTINLINE pointer                data();
  722.     VDTINLINE const_pointer            data() const;
  723.  
  724.     VDTINLINE iterator                begin();
  725.     VDTINLINE const_iterator            begin() const;
  726.     VDTINLINE iterator                end();
  727.     VDTINLINE const_iterator            end() const;
  728.  
  729.     VDTINLINE reverse_iterator        rbegin();
  730.     VDTINLINE const_reverse_iterator    rbegin() const;
  731.     VDTINLINE reverse_iterator        rend();
  732.     VDTINLINE const_reverse_iterator    rend() const;
  733.  
  734.     VDTINLINE reference                front();
  735.     VDTINLINE const_reference        front() const;
  736.     VDTINLINE reference                back();
  737.     VDTINLINE const_reference        back() const;
  738.  
  739.     VDTINLINE reference                operator[](size_type n);
  740.     VDTINLINE const_reference        operator[](size_type n) const;
  741.  
  742. protected:
  743.     T *mpBegin;
  744.     T *mpEnd;
  745. };
  746.  
  747. #ifdef VD_ACCELERATE_TEMPLATES
  748.     #pragma warning(push)
  749.     #pragma warning(disable: 4231)        //  warning C4231: nonstandard extension used : 'extern' before template explicit instantiation
  750.     VDTEXTERN template vdspan<char>;
  751.     VDTEXTERN template vdspan<uint8>;
  752.     VDTEXTERN template vdspan<uint16>;
  753.     VDTEXTERN template vdspan<uint32>;
  754.     VDTEXTERN template vdspan<uint64>;
  755.     VDTEXTERN template vdspan<sint8>;
  756.     VDTEXTERN template vdspan<sint16>;
  757.     VDTEXTERN template vdspan<sint32>;
  758.     VDTEXTERN template vdspan<sint64>;
  759.     VDTEXTERN template vdspan<float>;
  760.     VDTEXTERN template vdspan<double>;
  761.     VDTEXTERN template vdspan<wchar_t>;
  762.     #pragma warning(pop)
  763. #endif
  764.  
  765. template<class T> VDTINLINE vdspan<T>::vdspan() : mpBegin(NULL), mpEnd(NULL) {}
  766. template<class T> VDTINLINE vdspan<T>::vdspan(T *p1, T *p2) : mpBegin(p1), mpEnd(p2) {}
  767. template<class T> VDTINLINE vdspan<T>::vdspan(T *p, size_type len) : mpBegin(p), mpEnd(p+len) {}
  768. template<class T> VDTINLINE bool                    vdspan<T>::empty() const { return mpBegin == mpEnd; }
  769. template<class T> VDTINLINE typename vdspan<T>::size_type            vdspan<T>::size() const { return size_type(mpEnd - mpBegin); }
  770. template<class T> VDTINLINE typename vdspan<T>::pointer                vdspan<T>::data() { return mpBegin; }
  771. template<class T> VDTINLINE typename vdspan<T>::const_pointer        vdspan<T>::data() const { return mpBegin; }
  772. template<class T> VDTINLINE typename vdspan<T>::iterator                vdspan<T>::begin() { return mpBegin; }
  773. template<class T> VDTINLINE typename vdspan<T>::const_iterator        vdspan<T>::begin() const { return mpBegin; }
  774. template<class T> VDTINLINE typename vdspan<T>::iterator                vdspan<T>::end() { return mpEnd; }
  775. template<class T> VDTINLINE typename vdspan<T>::const_iterator        vdspan<T>::end() const { return mpEnd; }
  776. template<class T> VDTINLINE typename vdspan<T>::reverse_iterator        vdspan<T>::rbegin() { return reverse_iterator(mpBegin); }
  777. template<class T> VDTINLINE typename vdspan<T>::const_reverse_iterator vdspan<T>::rbegin() const { return const_reverse_iterator(mpBegin); }
  778. template<class T> VDTINLINE typename vdspan<T>::reverse_iterator        vdspan<T>::rend() { return reverse_iterator(mpEnd); }
  779. template<class T> VDTINLINE typename vdspan<T>::const_reverse_iterator vdspan<T>::rend() const { return const_reverse_iterator(mpEnd); }
  780. template<class T> VDTINLINE typename vdspan<T>::reference            vdspan<T>::front() { return *mpBegin; }
  781. template<class T> VDTINLINE typename vdspan<T>::const_reference        vdspan<T>::front() const { return *mpBegin; }
  782. template<class T> VDTINLINE typename vdspan<T>::reference            vdspan<T>::back() { VDASSERT(mpBegin != mpEnd); return mpEnd[-1]; }
  783. template<class T> VDTINLINE typename vdspan<T>::const_reference        vdspan<T>::back() const { VDASSERT(mpBegin != mpEnd); return mpEnd[-1]; }
  784. template<class T> VDTINLINE typename vdspan<T>::reference            vdspan<T>::operator[](size_type n) { VDASSERT(n < size_type(mpEnd - mpBegin)); return mpBegin[n]; }
  785. template<class T> VDTINLINE typename vdspan<T>::const_reference        vdspan<T>::operator[](size_type n) const { VDASSERT(n < size_type(mpEnd - mpBegin)); return mpBegin[n]; }
  786.  
  787. ///////////////////////////////////////////////////////////////////////////////
  788.  
  789. template<class T>
  790. bool operator==(const vdspan<T>& x, const vdspan<T>& y) {
  791.     uint32 len = x.size();
  792.     if (len != y.size())
  793.         return false;
  794.  
  795.     const T *px = x.data();
  796.     const T *py = y.data();
  797.  
  798.     for(uint32 i=0; i<len; ++i) {
  799.         if (px[i] != py[i])
  800.             return false;
  801.     }
  802.  
  803.     return true;
  804. }
  805.  
  806. template<class T>
  807. inline bool operator!=(const vdspan<T>& x, const vdspan<T>& y) { return !(x == y); }
  808.  
  809. ///////////////////////////////////////////////////////////////////////////////
  810.  
  811. template<class T, class S, class A = vdallocator<T> >
  812. class vdfastvector_base : public vdspan<T> {
  813. public:
  814.     ~vdfastvector_base() {
  815.         if (static_cast<const S&>(m).is_deallocatable_storage(mpBegin))
  816.             m.deallocate(mpBegin, m.eos - mpBegin);
  817.     }
  818.  
  819.     size_type capacity() const { return size_type(m.eos - mpBegin); }
  820.  
  821. public:
  822.     T *alloc(size_type n) {
  823.         size_type offset = (size_type)(mpEnd - mpBegin);
  824.         resize(offset + n);
  825.         return mpBegin + offset;
  826.     }
  827.  
  828.     void assign(const T *p1, const T *p2) {
  829.         resize(p2 - p1);
  830.         memcpy(mpBegin, p1, (char *)p2 - (char *)p1);
  831.     }
  832.  
  833.     void clear() {
  834.         mpEnd = mpBegin;
  835.     }
  836.  
  837.     iterator erase(iterator it) {
  838.         VDASSERT(it - mpBegin < mpEnd - mpBegin);
  839.  
  840.         memmove(it, it+1, (char *)mpEnd - (char *)(it+1));
  841.  
  842.         --mpEnd;
  843.  
  844.         return it;
  845.     }
  846.  
  847.     iterator erase(iterator it1, iterator it2) {
  848.         VDASSERT(it1 - mpBegin <= mpEnd - mpBegin);
  849.         VDASSERT(it2 - mpBegin <= mpEnd - mpBegin);
  850.         VDASSERT(it1 <= it2);
  851.  
  852.         memmove(it1, it2, (char *)mpEnd - (char *)it2);
  853.  
  854.         mpEnd -= (it2 - it1);
  855.  
  856.         return it1;
  857.     }
  858.  
  859.     iterator insert(iterator it, const T& value) {
  860.         const T temp(value);        // copy in case value is inside container.
  861.  
  862.         if (mpEnd == m.eos) {
  863.             difference_type delta = it - mpBegin;
  864.             _reserve_always_add_one();
  865.             it = mpBegin + delta;
  866.         }
  867.  
  868.         memmove(it+1, it, sizeof(T) * (mpEnd - it));
  869.         *it = temp;
  870.         ++mpEnd;
  871.         VDASSERT(mpEnd <= m.eos);
  872.  
  873.         return it;
  874.     }
  875.  
  876.     iterator insert(iterator it, size_type n, const T& value) {
  877.         const T temp(value);        // copy in case value is inside container.
  878.  
  879.         ptrdiff_t bytesToInsert = n * sizeof(T);
  880.  
  881.         if ((char *)m.eos - (char *)mpEnd < bytesToInsert) {
  882.             difference_type delta = it - mpBegin;
  883.             _reserve_always_add(bytesToInsert);
  884.             it = mpBegin + delta;
  885.         }
  886.  
  887.         memmove((char *)it + bytesToInsert, it, (char *)mpEnd - (char *)it);
  888.         for(size_t i=0; i<n; ++i)
  889.             *it++ = temp;
  890.         mpEnd += n;
  891.         VDASSERT(mpEnd <= m.eos);
  892.         return it;
  893.     }
  894.  
  895.     iterator insert(iterator it, const T *p1, const T *p2) {
  896.         ptrdiff_t elementsToCopy = p2 - p1;
  897.         ptrdiff_t bytesToCopy = (char *)p2 - (char *)p1;
  898.  
  899.         if ((char *)m.eos - (char *)mpEnd < bytesToCopy) {
  900.             difference_type delta = it - mpBegin;
  901.             _reserve_always_add(bytesToCopy);
  902.             it = mpBegin + delta;
  903.         }
  904.  
  905.         memmove((char *)it + bytesToCopy, it, (char *)mpEnd - (char *)it);
  906.         memcpy(it, p1, bytesToCopy);
  907.         mpEnd += elementsToCopy;
  908.         VDASSERT(mpEnd <= m.eos);
  909.         return it;
  910.     }
  911.  
  912.     reference push_back() {
  913.         if (mpEnd == m.eos)
  914.             _reserve_always_add_one();
  915.  
  916.         return *mpEnd++;
  917.     }
  918.  
  919.     void push_back(const T& value) {
  920.         const T temp(value);        // copy in case value is inside container.
  921.  
  922.         if (mpEnd == m.eos)
  923.             _reserve_always_add_one();
  924.  
  925.         *mpEnd++ = temp;
  926.     }
  927.  
  928.     void pop_back() {
  929.         VDASSERT(mpBegin != mpEnd);
  930.         --mpEnd;
  931.     }
  932.  
  933.     void resize(size_type n) {
  934.         if (n*sizeof(T) > size_type((char *)m.eos - (char *)mpBegin))
  935.             _reserve_always_amortized(n);
  936.  
  937.         mpEnd = mpBegin + n;
  938.     }
  939.  
  940.     void resize(size_type n, const T& value) {
  941.         const T temp(value);
  942.  
  943.         if (n*sizeof(T) > size_type((char *)m.eos - (char *)mpBegin)) {
  944.             _reserve_always_amortized(n);
  945.         }
  946.  
  947.         const iterator newEnd(mpBegin + n);
  948.         if (newEnd > mpEnd)
  949.             std::fill(mpEnd, newEnd, temp);
  950.         mpEnd = newEnd;
  951.     }
  952.  
  953.     void reserve(size_type n) {
  954.         if (n*sizeof(T) > size_type((char *)m.eos - (char *)mpBegin))
  955.             _reserve_always(n);
  956.     }
  957.  
  958. protected:
  959. #ifdef _MSC_VER
  960.     __declspec(noinline)
  961. #endif
  962.     void _reserve_always_add_one() {
  963.         _reserve_always((m.eos - mpBegin) * 2 + 1);
  964.     }
  965.  
  966. #ifdef _MSC_VER
  967.     __declspec(noinline)
  968. #endif
  969.     void _reserve_always_add(size_type n) {
  970.         _reserve_always((m.eos - mpBegin) * 2 + n);
  971.     }
  972.  
  973. #ifdef _MSC_VER
  974.     __declspec(noinline)
  975. #endif
  976.     void _reserve_always(size_type n) {
  977.         size_type oldSize = mpEnd - mpBegin;
  978.         T *oldStorage = mpBegin;
  979.         T *newStorage = m.allocate(n, NULL);
  980.  
  981.         memcpy(newStorage, mpBegin, (char *)mpEnd - (char *)mpBegin);
  982.         if (static_cast<const S&>(m).is_deallocatable_storage(oldStorage))
  983.             m.deallocate(oldStorage, m.eos - mpBegin);
  984.         mpBegin = newStorage;
  985.         mpEnd = newStorage + oldSize;
  986.         m.eos = newStorage + n;
  987.     }
  988.  
  989. #ifdef _MSC_VER
  990.     __declspec(noinline)
  991. #endif
  992.     void _reserve_always_amortized(size_type n) {
  993.         size_type nextCapacity = (size_type)((m.eos - mpBegin)*2);
  994.  
  995.         if (nextCapacity < n)
  996.             nextCapacity = n;
  997.  
  998.         _reserve_always(nextCapacity);
  999.     }
  1000.  
  1001.     struct : A, S {
  1002.         T *eos;
  1003.     } m;
  1004.  
  1005.     union TrivialObjectConstraint {
  1006.         T m;
  1007.     };
  1008. };
  1009.  
  1010. ///////////////////////////////////////////////////////////////////////////////
  1011.  
  1012. struct vdfastvector_storage {
  1013.     bool is_deallocatable_storage(void *p) const {
  1014.         return p != 0;
  1015.     }
  1016. };
  1017.  
  1018. template<class T, class A = vdallocator<T> >
  1019. class vdfastvector : public vdfastvector_base<T, vdfastvector_storage, A> {
  1020. public:
  1021.     vdfastvector() {
  1022.         m.eos = NULL;
  1023.     }
  1024.  
  1025.     vdfastvector(size_type len) {
  1026.         mpBegin = m.allocate(len, NULL);
  1027.         mpEnd = mpBegin + len;
  1028.         m.eos = mpEnd;
  1029.     }
  1030.  
  1031.     vdfastvector(size_type len, const T& fill) {
  1032.         mpBegin = m.allocate(len, NULL);
  1033.         mpEnd = mpBegin + len;
  1034.         m.eos = mpEnd;
  1035.  
  1036.         std::fill(mpBegin, mpEnd, fill);
  1037.     }
  1038.  
  1039.     vdfastvector(const vdfastvector& x) {
  1040.         size_type n = x.mpEnd - x.mpBegin;
  1041.         mpBegin = m.allocate(n, NULL);
  1042.         mpEnd = mpBegin + n;
  1043.         m.eos = mpEnd;
  1044.         memcpy(mpBegin, x.mpBegin, sizeof(T) * n);
  1045.     }
  1046.  
  1047.     vdfastvector(const value_type *p, const value_type *q) {
  1048.         m.eos = NULL;
  1049.  
  1050.         assign(p, q);
  1051.     }
  1052.  
  1053.     vdfastvector& operator=(const vdfastvector& x) {
  1054.         if (this != &x)
  1055.             assign(x.mpBegin, x.mpEnd);
  1056.  
  1057.         return *this;
  1058.     }
  1059.  
  1060.     void swap(vdfastvector& x) {
  1061.         T *p;
  1062.  
  1063.         p = mpBegin;        mpBegin = x.mpBegin;        x.mpBegin = p;
  1064.         p = mpEnd;            mpEnd = x.mpEnd;            x.mpEnd = p;
  1065.         p = m.eos;            m.eos = x.m.eos;            x.m.eos = p;
  1066.     }
  1067. };
  1068.  
  1069. ///////////////////////////////////////////////////////////////////////////////
  1070.  
  1071. template<class T, size_t N>
  1072. struct vdfastfixedvector_storage {
  1073.     T mArray[N];
  1074.  
  1075.     bool is_deallocatable_storage(void *p) const {
  1076.         return p != mArray;
  1077.     }
  1078. };
  1079.  
  1080. template<class T, size_t N, class A = vdallocator<T> >
  1081. class vdfastfixedvector : public vdfastvector_base<T, vdfastfixedvector_storage<T, N>, A> {
  1082. public:
  1083.     vdfastfixedvector() {
  1084.         mpBegin = m.mArray;
  1085.         mpEnd = m.mArray;
  1086.         m.eos = m.mArray + N;
  1087.     }
  1088.  
  1089.     vdfastfixedvector(size_type len) {
  1090.         if (len <= N) {
  1091.             mpBegin = m.mArray;
  1092.             mpEnd = m.mArray + len;
  1093.             m.eos = m.mArray + N;
  1094.         } else {
  1095.             mpBegin = m.allocate(len, NULL);
  1096.             mpEnd = mpBegin + len;
  1097.             m.eos = mpEnd;
  1098.         }
  1099.     }
  1100.  
  1101.     vdfastfixedvector(size_type len, const T& fill) {
  1102.         mpBegin = m.allocate(len, NULL);
  1103.         mpEnd = mpBegin + len;
  1104.         m.eos = mpEnd;
  1105.  
  1106.         std::fill(mpBegin, mpEnd, fill);
  1107.     }
  1108.  
  1109.     vdfastfixedvector(const vdfastfixedvector& x) {
  1110.         size_type n = x.mpEnd - x.mpBegin;
  1111.  
  1112.         if (n <= N) {
  1113.             mpBegin = m.mArray;
  1114.             mpEnd = m.mArray + n;
  1115.             m.eos = m.mArray + N;
  1116.         } else {
  1117.             mpBegin = m.allocate(n, NULL);
  1118.             mpEnd = mpBegin + n;
  1119.             m.eos = mpEnd;
  1120.         }
  1121.  
  1122.         memcpy(mpBegin, x.mpBegin, sizeof(T) * n);
  1123.     }
  1124.  
  1125.     vdfastfixedvector(const value_type *p, const value_type *q) {
  1126.         mpBegin = m.mArray;
  1127.         mpEnd = m.mArray;
  1128.         m.eos = m.mArray + N;
  1129.  
  1130.         assign(p, q);
  1131.     }
  1132.  
  1133.     vdfastfixedvector& operator=(const vdfastfixedvector& x) {
  1134.         if (this != &x)
  1135.             assign(x.mpBegin, x.mpEnd);
  1136.  
  1137.         return *this;
  1138.     }
  1139.  
  1140.     void swap(vdfastfixedvector& x) {
  1141.         size_t this_bytes = (char *)mpEnd - (char *)mpBegin;
  1142.         size_t other_bytes = (char *)x.mpEnd - (char *)x.mpBegin;
  1143.  
  1144.         T *p;
  1145.  
  1146.         if (mpBegin == m.mArray) {
  1147.             if (x.mpBegin == x.m.mArray) {
  1148.                 if (this_bytes < other_bytes) {
  1149.                     VDSwapMemory(m.mArray, x.m.mArray, this_bytes);
  1150.                     memcpy((char *)m.mArray + this_bytes, (char *)x.m.mArray + this_bytes, other_bytes - this_bytes);
  1151.                 } else {
  1152.                     VDSwapMemory(m.mArray, x.m.mArray, other_bytes);
  1153.                     memcpy((char *)m.mArray + other_bytes, (char *)x.m.mArray + other_bytes, this_bytes - other_bytes);
  1154.                 }
  1155.  
  1156.                 mpEnd = (T *)((char *)mpBegin + other_bytes);
  1157.                 x.mpEnd = (T *)((char *)x.mpBegin + this_bytes);
  1158.             } else {
  1159.                 memcpy(x.m.mArray, mpBegin, this_bytes);
  1160.  
  1161.                 mpBegin = x.mpBegin;
  1162.                 mpEnd = x.mpEnd;
  1163.                 m.eos = x.m.eos;
  1164.  
  1165.                 x.mpBegin = x.m.mArray;
  1166.                 x.mpEnd = (T *)((char *)x.m.mArray + this_bytes);
  1167.                 x.m.eos = x.m.mArray + N;
  1168.             }
  1169.         } else {
  1170.             if (x.mpBegin == x.m.mArray) {
  1171.                 memcpy(x.m.mArray, mpBegin, other_bytes);
  1172.  
  1173.                 x.mpBegin = mpBegin;
  1174.                 x.mpEnd = mpEnd;
  1175.                 x.m.eos = m.eos;
  1176.  
  1177.                 mpBegin = m.mArray;
  1178.                 mpEnd = (T *)((char *)m.mArray + other_bytes);
  1179.                 m.eos = m.mArray + N;
  1180.             } else {
  1181.                 p = mpBegin;        mpBegin = x.mpBegin;        x.mpBegin = p;
  1182.                 p = mpEnd;            mpEnd = x.mpEnd;            x.mpEnd = p;
  1183.                 p = m.eos;            m.eos = x.m.eos;            x.m.eos = p;
  1184.             }
  1185.         }
  1186.     }
  1187. };
  1188.  
  1189. ///////////////////////////////////////////////////////////////////////////////
  1190.  
  1191. template<class T>
  1192. struct vdfastdeque_block {
  1193.     enum {
  1194.         kBlockSize = 32,
  1195.         kBlockSizeBits = 5
  1196.     };
  1197.  
  1198.     T data[kBlockSize];
  1199. };
  1200.  
  1201. template<class T, class T_Base>
  1202. class vdfastdeque_iterator {
  1203. public:
  1204.     vdfastdeque_iterator(const vdfastdeque_iterator<T_Base, T_Base>&);
  1205.     vdfastdeque_iterator(vdfastdeque_block<T_Base> **pMapEntry, uint32 index);
  1206.  
  1207.     T& operator *() const;
  1208.     T& operator ->() const;
  1209.     vdfastdeque_iterator& operator++();
  1210.     vdfastdeque_iterator operator++(int);
  1211.     vdfastdeque_iterator& operator--();
  1212.     vdfastdeque_iterator operator--(int);
  1213.  
  1214. public:
  1215.     vdfastdeque_block<T_Base> **mpMap;
  1216.     vdfastdeque_block<T_Base> *mpBlock;
  1217.     uint32 mIndex;
  1218. };
  1219.  
  1220. template<class T, class T_Base>
  1221. vdfastdeque_iterator<T, T_Base>::vdfastdeque_iterator(const vdfastdeque_iterator<T_Base, T_Base>& x)
  1222.     : mpMap(x.mpMap)
  1223.     , mpBlock(x.mpBlock)
  1224.     , mIndex(x.mIndex)
  1225. {
  1226. }
  1227.  
  1228. template<class T, class T_Base>
  1229. vdfastdeque_iterator<T, T_Base>::vdfastdeque_iterator(vdfastdeque_block<T_Base> **pMapEntry, uint32 index)
  1230.     : mpMap(pMapEntry)
  1231.     , mpBlock(mpMap ? *mpMap : NULL)
  1232.     , mIndex(index)
  1233. {
  1234. }
  1235.  
  1236. template<class T, class T_Base>
  1237. T& vdfastdeque_iterator<T, T_Base>::operator *() const {
  1238.     return mpBlock->data[mIndex];
  1239. }
  1240.  
  1241. template<class T, class T_Base>
  1242. T& vdfastdeque_iterator<T, T_Base>::operator ->() const {
  1243.     return mpBlock->data[mIndex];
  1244. }
  1245.  
  1246. template<class T, class T_Base>
  1247. vdfastdeque_iterator<T, T_Base>& vdfastdeque_iterator<T, T_Base>::operator++() {
  1248.     if (++mIndex >= vdfastdeque_block<T>::kBlockSize) {
  1249.         mIndex = 0;
  1250.         mpBlock = *++mpMap;
  1251.     }
  1252.     return *this;
  1253. }
  1254.  
  1255. template<class T, class T_Base>
  1256. vdfastdeque_iterator<T, T_Base> vdfastdeque_iterator<T, T_Base>::operator++(int) {
  1257.     vdfastdeque_iterator r(*this);
  1258.     operator++();
  1259.     return r;
  1260. }
  1261.  
  1262. template<class T, class T_Base>
  1263. vdfastdeque_iterator<T, T_Base>& vdfastdeque_iterator<T, T_Base>::operator--() {
  1264.     if (mIndex-- == 0) {
  1265.         mIndex = vdfastdeque_block<T, T_Base>::kBlockSize - 1;
  1266.         mpBlock = *--mpMap;
  1267.     }
  1268.     return *this;
  1269. }
  1270.  
  1271. template<class T, class T_Base>
  1272. vdfastdeque_iterator<T, T_Base> vdfastdeque_iterator<T, T_Base>::operator--(int) {
  1273.     vdfastdeque_iterator r(*this);
  1274.     operator--();
  1275.     return r;
  1276. }
  1277.  
  1278. template<class T, class U, class T_Base>
  1279. bool operator==(const vdfastdeque_iterator<T, T_Base>& x,const vdfastdeque_iterator<U, T_Base>& y) {
  1280.     return x.mpBlock == y.mpBlock && x.mIndex == y.mIndex;
  1281. }
  1282.  
  1283. template<class T, class U, class T_Base>
  1284. bool operator!=(const vdfastdeque_iterator<T, T_Base>& x,const vdfastdeque_iterator<U, T_Base>& y) {
  1285.     return x.mpBlock != y.mpBlock || x.mIndex != y.mIndex;
  1286. }
  1287.  
  1288. ///////////////////////////////////////////////////////////////////////////////
  1289.  
  1290. template<class T, class A = vdallocator<T> >
  1291. class vdfastdeque {
  1292. public:
  1293.     typedef    typename A::reference        reference;
  1294.     typedef    typename A::const_reference    const_reference;
  1295.     typedef    typename A::pointer            pointer;
  1296.     typedef    typename A::const_pointer    const_pointer;
  1297.     typedef    T                    value_type;
  1298.     typedef A                    allocator_type;
  1299.     typedef    size_t                size_type;
  1300.     typedef    ptrdiff_t            difference_type;
  1301.     typedef    vdfastdeque_iterator<T, T>            iterator;
  1302.     typedef vdfastdeque_iterator<const T, T>    const_iterator;
  1303.     typedef typename vdreverse_iterator<iterator, T>::type            reverse_iterator;
  1304.     typedef typename vdreverse_iterator<const_iterator, const T>::type    const_reverse_iterator;
  1305.  
  1306.     vdfastdeque();
  1307.     ~vdfastdeque();
  1308.  
  1309.     bool                empty() const;
  1310.     size_type            size() const;
  1311.  
  1312.     reference            front();
  1313.     const_reference        front() const;
  1314.     reference            back();
  1315.     const_reference        back() const;
  1316.  
  1317.     iterator            begin();
  1318.     const_iterator        begin() const;
  1319.     iterator            end();
  1320.     const_iterator        end() const;
  1321.  
  1322.     reference            operator[](size_type n);
  1323.     const_reference        operator[](size_type n) const;
  1324.  
  1325.     void                clear();
  1326.  
  1327.     reference            push_back();
  1328.     void                push_back(const_reference x);
  1329.  
  1330.     void                pop_front();
  1331.     void                pop_back();
  1332.  
  1333.     void                swap(vdfastdeque& x);
  1334.  
  1335. protected:
  1336.     void                push_back_extend();
  1337.     void                validate();
  1338.  
  1339.     typedef vdfastdeque_block<T> Block;
  1340.  
  1341.     enum {
  1342.         kBlockSize = Block::kBlockSize,
  1343.         kBlockSizeBits = Block::kBlockSizeBits
  1344.     };
  1345.  
  1346.     struct M1 : public A::rebind<Block *>::other {
  1347.         Block **mapStartAlloc;        // start of map
  1348.         Block **mapStartCommit;        // start of range of allocated blocks
  1349.         Block **mapStart;            // start of range of active blocks
  1350.         Block **mapEnd;                // end of range of active blocks
  1351.         Block **mapEndCommit;        // end of range of allocated blocks
  1352.         Block **mapEndAlloc;        // end of map
  1353.     } m;
  1354.  
  1355.     struct M2 : public A::rebind<Block>::other {
  1356.         int startIndex;
  1357.         int endIndex;
  1358.     } mTails;
  1359.  
  1360.     union TrivialObjectConstraint {
  1361.         T obj;
  1362.     };
  1363. };
  1364.  
  1365. template<class T, class A>
  1366. vdfastdeque<T, A>::vdfastdeque() {
  1367.     m.mapStartAlloc        = NULL;
  1368.     m.mapStartCommit    = NULL;
  1369.     m.mapStart            = NULL;
  1370.     m.mapEnd            = NULL;
  1371.     m.mapEndCommit        = NULL;
  1372.     m.mapEndAlloc        = NULL;
  1373.     mTails.startIndex    = 0;
  1374.     mTails.endIndex        = kBlockSize - 1;
  1375. }
  1376.  
  1377. template<class T, class A>
  1378. vdfastdeque<T,A>::~vdfastdeque() {
  1379.     while(m.mapStartCommit != m.mapEndCommit) {
  1380.         mTails.deallocate(*m.mapStartCommit++, 1);
  1381.     }
  1382.  
  1383.     if (m.mapStartAlloc)
  1384.         m.deallocate(m.mapStartAlloc, m.mapEndAlloc - m.mapStartAlloc);
  1385. }
  1386.  
  1387. template<class T, class A>
  1388. bool vdfastdeque<T,A>::empty() const {
  1389.     return size() == 0;
  1390. }
  1391.  
  1392. template<class T, class A>
  1393. typename vdfastdeque<T,A>::size_type vdfastdeque<T,A>::size() const {
  1394.     if (m.mapEnd == m.mapStart)
  1395.         return 0;
  1396.  
  1397.     return kBlockSize * ((m.mapEnd - m.mapStart) - 1) + (mTails.endIndex + 1) - mTails.startIndex;
  1398. }
  1399.  
  1400. template<class T, class A>
  1401. typename vdfastdeque<T,A>::reference vdfastdeque<T,A>::front() {
  1402.     VDASSERT(m.mapStart != m.mapEnd);
  1403.     return (*m.mapStart)->data[mTails.startIndex];
  1404. }
  1405.  
  1406. template<class T, class A>
  1407. typename vdfastdeque<T,A>::const_reference vdfastdeque<T,A>::front() const {
  1408.     VDASSERT(m.mapStart != m.mapEnd);
  1409.     return (*m.mapStart)->data[mTails.startIndex];
  1410. }
  1411.  
  1412. template<class T, class A>
  1413. typename vdfastdeque<T,A>::reference vdfastdeque<T,A>::back() {
  1414.     VDASSERT(m.mapStart != m.mapEnd);
  1415.     return m.mapEnd[-1]->data[mTails.endIndex];
  1416. }
  1417.  
  1418. template<class T, class A>
  1419. typename vdfastdeque<T,A>::const_reference vdfastdeque<T,A>::back() const {
  1420.     VDASSERT(m.mapStart != m.mapEnd);
  1421.     return m.mapEnd[-1]->data[mTails.endIndex];
  1422. }
  1423.  
  1424. template<class T, class A>
  1425. typename vdfastdeque<T,A>::iterator vdfastdeque<T,A>::begin() {
  1426.     return iterator(m.mapStart, mTails.startIndex);
  1427. }
  1428.  
  1429. template<class T, class A>
  1430. typename vdfastdeque<T,A>::const_iterator vdfastdeque<T,A>::begin() const {
  1431.     return const_iterator(m.mapStart, mTails.startIndex);
  1432. }
  1433.  
  1434. template<class T, class A>
  1435. typename vdfastdeque<T,A>::iterator vdfastdeque<T,A>::end() {
  1436.     if (mTails.endIndex == kBlockSize - 1)
  1437.         return iterator(m.mapEnd, 0);
  1438.     else
  1439.         return iterator(m.mapEnd - 1, mTails.endIndex + 1);
  1440. }
  1441.  
  1442. template<class T, class A>
  1443. typename vdfastdeque<T,A>::const_iterator vdfastdeque<T,A>::end() const {
  1444.     if (mTails.endIndex == kBlockSize - 1)
  1445.         return const_iterator(m.mapEnd, 0);
  1446.     else
  1447.         return const_iterator(m.mapEnd - 1, mTails.endIndex + 1);
  1448. }
  1449.  
  1450. template<class T, class A>
  1451. typename vdfastdeque<T,A>::reference vdfastdeque<T,A>::operator[](size_type n) {
  1452.     n += mTails.startIndex;
  1453.     return m.mapStart[n >> kBlockSizeBits]->data[n & (kBlockSize - 1)];
  1454. }
  1455.  
  1456. template<class T, class A>
  1457. typename vdfastdeque<T,A>::const_reference vdfastdeque<T,A>::operator[](size_type n) const {
  1458.     n += mTails.startIndex;
  1459.     return m.mapStart[n >> kBlockSizeBits]->data[n & (kBlockSize - 1)];
  1460. }
  1461.  
  1462. template<class T, class A>
  1463. void vdfastdeque<T,A>::clear() {
  1464.     m.mapEnd            = m.mapStart;
  1465.     mTails.startIndex    = 0;
  1466.     mTails.endIndex        = kBlockSize - 1;
  1467. }
  1468.  
  1469. template<class T, class A>
  1470. typename vdfastdeque<T,A>::reference vdfastdeque<T,A>::push_back() {
  1471.     if (mTails.endIndex >= kBlockSize - 1) {
  1472.         push_back_extend();
  1473.  
  1474.         mTails.endIndex = -1;
  1475.     }
  1476.  
  1477.     ++mTails.endIndex;
  1478.  
  1479.     VDASSERT(m.mapEnd[-1]);
  1480.     reference r = m.mapEnd[-1]->data[mTails.endIndex];
  1481.     return r;
  1482. }
  1483.  
  1484. template<class T, class A>
  1485. void vdfastdeque<T,A>::push_back(const_reference x) {
  1486.     const T x2(x);
  1487.     push_back() = x2;
  1488. }
  1489.  
  1490. template<class T, class A>
  1491. void vdfastdeque<T,A>::pop_front() {
  1492.     if (++mTails.startIndex >= kBlockSize) {
  1493.         VDASSERT(m.mapEnd != m.mapStart);
  1494.         mTails.startIndex = 0;
  1495.         ++m.mapStart;
  1496.     }
  1497. }
  1498.  
  1499. template<class T, class A>
  1500. void vdfastdeque<T,A>::pop_back() {
  1501.     if (--mTails.endIndex < 0) {
  1502.         VDASSERT(m.mapEnd != m.mapStart);
  1503.         mTails.endIndex = kBlockSize - 1;
  1504.         --m.mapEnd;
  1505.     }
  1506. }
  1507.  
  1508. template<class T, class A>
  1509. void vdfastdeque<T,A>::swap(vdfastdeque& x) {
  1510.     std::swap(m.mapStartAlloc, x.m.mapStartAlloc);
  1511.     std::swap(m.mapStartCommit, x.m.mapStartCommit);
  1512.     std::swap(m.mapStart, x.m.mapStart);
  1513.     std::swap(m.mapEnd, x.m.mapEnd);
  1514.     std::swap(m.mapEndCommit, x.m.mapEndCommit);
  1515.     std::swap(m.mapEndAlloc, x.m.mapEndAlloc);
  1516.     std::swap(mTails.startIndex, x.mTails.startIndex);
  1517.     std::swap(mTails.endIndex, x.mTails.endIndex);
  1518. }
  1519.  
  1520. /////////////////////////////////
  1521.  
  1522. template<class T, class A>
  1523. void vdfastdeque<T,A>::push_back_extend() {
  1524.     validate();
  1525.  
  1526.     // check if we need to extend the map itself
  1527.     if (m.mapEnd == m.mapEndAlloc) {
  1528.         // can we just shift the map?
  1529.         size_type currentMapSize = m.mapEndAlloc - m.mapStartAlloc;
  1530.         size_type freeAtStart = m.mapStartCommit - m.mapStartAlloc;
  1531.  
  1532.         if (freeAtStart >= 2 && (freeAtStart + freeAtStart) >= currentMapSize) {
  1533.             size_type shiftDistance = freeAtStart >> 1;
  1534.  
  1535.             VDASSERT(!m.mapStartAlloc[0]);
  1536.             memmove(m.mapStartAlloc, m.mapStartAlloc + shiftDistance, sizeof(Block *) * (currentMapSize - shiftDistance));
  1537.             memset(m.mapStartAlloc + (currentMapSize - shiftDistance), 0, shiftDistance * sizeof(Block *));
  1538.  
  1539.             // relocate pointers
  1540.             m.mapEndCommit        -= shiftDistance;
  1541.             m.mapEnd            -= shiftDistance;
  1542.             m.mapStart            -= shiftDistance;
  1543.             m.mapStartCommit    -= shiftDistance;
  1544.             validate();
  1545.         } else {
  1546.             size_type newMapSize = currentMapSize*2+1;
  1547.  
  1548.             Block **newMap = m.allocate(newMapSize);
  1549.  
  1550.             memcpy(newMap, m.mapStartAlloc, currentMapSize * sizeof(Block *));
  1551.             memset(newMap + currentMapSize, 0, (newMapSize - currentMapSize) * sizeof(Block *));
  1552.  
  1553.             // relocate pointers
  1554.             m.mapEndAlloc        = newMap + newMapSize;
  1555.             m.mapEndCommit        = newMap + (m.mapEndCommit        - m.mapStartAlloc);
  1556.             m.mapEnd            = newMap + (m.mapEnd            - m.mapStartAlloc);
  1557.             m.mapStart            = newMap + (m.mapStart            - m.mapStartAlloc);
  1558.             m.mapStartCommit    = newMap + (m.mapStartCommit    - m.mapStartAlloc);
  1559.  
  1560.             m.deallocate(m.mapStartAlloc, currentMapSize);
  1561.             m.mapStartAlloc        = newMap;
  1562.             validate();
  1563.         }
  1564.     }
  1565.  
  1566.     VDASSERT(m.mapEnd != m.mapEndAlloc);
  1567.  
  1568.     // check if we already have a block we can use
  1569.     if (*m.mapEnd) {
  1570.         ++m.mapEnd;
  1571.         validate();
  1572.         return;
  1573.     }
  1574.  
  1575.     // check if we can steal a block from the beginning
  1576.     if (m.mapStartCommit != m.mapStart) {
  1577.         VDASSERT(*m.mapStartCommit);
  1578.         if (m.mapStartCommit != m.mapEnd) {
  1579.             *m.mapEnd = *m.mapStartCommit;
  1580.             *m.mapStartCommit = NULL;
  1581.             ++m.mapStartCommit;
  1582.         }
  1583.         ++m.mapEnd;
  1584.         m.mapEndCommit = m.mapEnd;
  1585.         validate();
  1586.         return;
  1587.     }
  1588.  
  1589.     // allocate a new block
  1590.     *m.mapEnd = mTails.allocate(1);
  1591.     ++m.mapEnd;
  1592.     m.mapEndCommit = m.mapEnd;
  1593.     validate();
  1594. }
  1595.  
  1596. template<class T, class A>
  1597. void vdfastdeque<T,A>::validate() {
  1598.     VDASSERT(m.mapStartAlloc <= m.mapStartCommit);
  1599.     VDASSERT(m.mapStartCommit <= m.mapStart);
  1600.     VDASSERT(m.mapStart <= m.mapEnd);
  1601.     VDASSERT(m.mapEnd <= m.mapEndCommit);
  1602.     VDASSERT(m.mapEndCommit <= m.mapEndAlloc);
  1603.  
  1604.     VDASSERT(m.mapStartAlloc == m.mapStartCommit || !*m.mapStartAlloc);
  1605.     VDASSERT(m.mapStartCommit == m.mapEndCommit || m.mapStartCommit[0]);
  1606.     VDASSERT(m.mapStart == m.mapEnd || (m.mapStart[0] && m.mapEnd[-1]));
  1607.     VDASSERT(m.mapEndCommit == m.mapEndAlloc || !m.mapEndCommit[0]);
  1608. }
  1609.  
  1610. #endif
  1611.