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