1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/include/core/SkDeque.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,138 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2006 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#ifndef SkDeque_DEFINED
1.14 +#define SkDeque_DEFINED
1.15 +
1.16 +#include "SkTypes.h"
1.17 +
1.18 +/*
1.19 + * The deque class works by blindly creating memory space of a specified element
1.20 + * size. It manages the memory as a doubly linked list of blocks each of which
1.21 + * can contain multiple elements. Pushes and pops add/remove blocks from the
1.22 + * beginning/end of the list as necessary while each block tracks the used
1.23 + * portion of its memory.
1.24 + * One behavior to be aware of is that the pops do not immediately remove an
1.25 + * empty block from the beginning/end of the list (Presumably so push/pop pairs
1.26 + * on the block boundaries don't cause thrashing). This can result in the first/
1.27 + * last element not residing in the first/last block.
1.28 + */
1.29 +class SK_API SkDeque : SkNoncopyable {
1.30 +public:
1.31 + /**
1.32 + * elemSize specifies the size of each individual element in the deque
1.33 + * allocCount specifies how many elements are to be allocated as a block
1.34 + */
1.35 + explicit SkDeque(size_t elemSize, int allocCount = 1);
1.36 + SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount = 1);
1.37 + ~SkDeque();
1.38 +
1.39 + bool empty() const { return 0 == fCount; }
1.40 + int count() const { return fCount; }
1.41 + size_t elemSize() const { return fElemSize; }
1.42 +
1.43 + const void* front() const { return fFront; }
1.44 + const void* back() const { return fBack; }
1.45 +
1.46 + void* front() {
1.47 + return (void*)((const SkDeque*)this)->front();
1.48 + }
1.49 +
1.50 + void* back() {
1.51 + return (void*)((const SkDeque*)this)->back();
1.52 + }
1.53 +
1.54 + /**
1.55 + * push_front and push_back return a pointer to the memory space
1.56 + * for the new element
1.57 + */
1.58 + void* push_front();
1.59 + void* push_back();
1.60 +
1.61 + void pop_front();
1.62 + void pop_back();
1.63 +
1.64 +private:
1.65 + struct Block;
1.66 +
1.67 +public:
1.68 + class Iter {
1.69 + public:
1.70 + enum IterStart {
1.71 + kFront_IterStart,
1.72 + kBack_IterStart
1.73 + };
1.74 +
1.75 + /**
1.76 + * Creates an uninitialized iterator. Must be reset()
1.77 + */
1.78 + Iter();
1.79 +
1.80 + Iter(const SkDeque& d, IterStart startLoc);
1.81 + void* next();
1.82 + void* prev();
1.83 +
1.84 + void reset(const SkDeque& d, IterStart startLoc);
1.85 +
1.86 + private:
1.87 + SkDeque::Block* fCurBlock;
1.88 + char* fPos;
1.89 + size_t fElemSize;
1.90 + };
1.91 +
1.92 + // Inherit privately from Iter to prevent access to reverse iteration
1.93 + class F2BIter : private Iter {
1.94 + public:
1.95 + F2BIter() {}
1.96 +
1.97 + /**
1.98 + * Wrap Iter's 2 parameter ctor to force initialization to the
1.99 + * beginning of the deque
1.100 + */
1.101 + F2BIter(const SkDeque& d) : INHERITED(d, kFront_IterStart) {}
1.102 +
1.103 + using Iter::next;
1.104 +
1.105 + /**
1.106 + * Wrap Iter::reset to force initialization to the beginning of the
1.107 + * deque
1.108 + */
1.109 + void reset(const SkDeque& d) {
1.110 + this->INHERITED::reset(d, kFront_IterStart);
1.111 + }
1.112 +
1.113 + private:
1.114 + typedef Iter INHERITED;
1.115 + };
1.116 +
1.117 +private:
1.118 + // allow unit test to call numBlocksAllocated
1.119 + friend class DequeUnitTestHelper;
1.120 +
1.121 + void* fFront;
1.122 + void* fBack;
1.123 +
1.124 + Block* fFrontBlock;
1.125 + Block* fBackBlock;
1.126 + size_t fElemSize;
1.127 + void* fInitialStorage;
1.128 + int fCount; // number of elements in the deque
1.129 + int fAllocCount; // number of elements to allocate per block
1.130 +
1.131 + Block* allocateBlock(int allocCount);
1.132 + void freeBlock(Block* block);
1.133 +
1.134 + /**
1.135 + * This returns the number of chunk blocks allocated by the deque. It
1.136 + * can be used to gauge the effectiveness of the selected allocCount.
1.137 + */
1.138 + int numBlocksAllocated() const;
1.139 +};
1.140 +
1.141 +#endif
