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 */
26class SK_API SkDeque : SkNoncopyable {
27public:
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
36    bool    empty() const { return 0 == fCount; }
37    int     count() const { return fCount; }
38    size_t  elemSize() const { return fElemSize; }
39
40    const void* front() const { return fFront; }
41    const void* back() const  { return fBack; }
42
43    void* front() {
44        return (void*)((const SkDeque*)this)->front();
45    }
46
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
61private:
62    struct Block;
63
64public:
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:
92        F2BIter() {}
93
94        /**
95         * Wrap Iter's 2 parameter ctor to force initialization to the
96         * beginning of the deque
97         */
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         */
106        void reset(const SkDeque& d) {
107            this->INHERITED::reset(d, kFront_IterStart);
108        }
109
110    private:
111        typedef Iter INHERITED;
112    };
113
114private:
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