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