Skia
2DGraphicsLibrary
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
SkDeque.h
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:
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 
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 
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 
98  F2BIter(const SkDeque& d) : INHERITED(d, kFront_IterStart) {}
99 
100  using Iter::next;
101 
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 
135  int numBlocksAllocated() const;
136 };
137 
138 #endif
void reset(const SkDeque &d)
Wrap Iter::reset to force initialization to the beginning of the deque.
Definition: SkDeque.h:106
Definition: SkDeque.h:90
Definition: SkDeque.h:26
F2BIter(const SkDeque &d)
Wrap Iter's 2 parameter ctor to force initialization to the beginning of the deque.
Definition: SkDeque.h:98
Definition: SkDeque.h:65