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