1 
2 /*
3  * Copyright 2006 The Android Open Source Project
4  *
5  * Use of this source code is governed by a BSD-style license that can be
6  * found in the LICENSE file.
7  */
8 
9 
10 #ifndef SkDeque_DEFINED
11 #define SkDeque_DEFINED
12 
13 #include "SkTypes.h"
14 
15 /*
16  * The deque class works by blindly creating memory space of a specified element
17  * size. It manages the memory as a doubly linked list of blocks each of which
18  * can contain multiple elements. Pushes and pops add/remove blocks from the
19  * beginning/end of the list as necessary while each block tracks the used
20  * portion of its memory.
21  * One behavior to be aware of is that the pops do not immediately remove an
22  * empty block from the beginning/end of the list (Presumably so push/pop pairs
23  * on the block boundaries don't cause thrashing). This can result in the first/
24  * last element not residing in the first/last block.
25  */
26 class SK_API SkDeque : SkNoncopyable {
27 public:
28     /**
29      * elemSize specifies the size of each individual element in the deque
30      * allocCount specifies how many elements are to be allocated as a block
31      */
32     explicit SkDeque(size_t elemSize, int allocCount = 1);
33     SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount = 1);
34     ~SkDeque();
35 
empty()36     bool    empty() const { return 0 == fCount; }
count()37     int     count() const { return fCount; }
elemSize()38     size_t  elemSize() const { return fElemSize; }
39 
front()40     const void* front() const { return fFront; }
back()41     const void* back() const  { return fBack; }
42 
front()43     void* front() {
44         return (void*)((const SkDeque*)this)->front();
45     }
46 
back()47     void* back() {
48         return (void*)((const SkDeque*)this)->back();
49     }
50 
51     /**
52      * push_front and push_back return a pointer to the memory space
53      * for the new element
54      */
55     void* push_front();
56     void* push_back();
57 
58     void pop_front();
59     void pop_back();
60 
61 private:
62     struct Block;
63 
64 public:
65     class Iter {
66     public:
67         enum IterStart {
68             kFront_IterStart,
69             kBack_IterStart
70         };
71 
72         /**
73          * Creates an uninitialized iterator. Must be reset()
74          */
75         Iter();
76 
77         Iter(const SkDeque& d, IterStart startLoc);
78         void* next();
79         void* prev();
80 
81         void reset(const SkDeque& d, IterStart startLoc);
82 
83     private:
84         SkDeque::Block* fCurBlock;
85         char*           fPos;
86         size_t          fElemSize;
87     };
88 
89     // Inherit privately from Iter to prevent access to reverse iteration
90     class F2BIter : private Iter {
91     public:
F2BIter()92         F2BIter() {}
93 
94         /**
95          * Wrap Iter's 2 parameter ctor to force initialization to the
96          * beginning of the deque
97          */
F2BIter(const SkDeque & d)98         F2BIter(const SkDeque& d) : INHERITED(d, kFront_IterStart) {}
99 
100         using Iter::next;
101 
102         /**
103          * Wrap Iter::reset to force initialization to the beginning of the
104          * deque
105          */
reset(const SkDeque & d)106         void reset(const SkDeque& d) {
107             this->INHERITED::reset(d, kFront_IterStart);
108         }
109 
110     private:
111         typedef Iter INHERITED;
112     };
113 
114 private:
115     // allow unit test to call numBlocksAllocated
116     friend class DequeUnitTestHelper;
117 
118     void*   fFront;
119     void*   fBack;
120 
121     Block*  fFrontBlock;
122     Block*  fBackBlock;
123     size_t  fElemSize;
124     void*   fInitialStorage;
125     int     fCount;             // number of elements in the deque
126     int     fAllocCount;        // number of elements to allocate per block
127 
128     Block*  allocateBlock(int allocCount);
129     void    freeBlock(Block* block);
130 
131     /**
132      * This returns the number of chunk blocks allocated by the deque. It
133      * can be used to gauge the effectiveness of the selected allocCount.
134      */
135     int  numBlocksAllocated() const;
136 };
137 
138 #endif
139