Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : /**
8 : * MODULE NOTES:
9 : *
10 : * The Deque is a very small, very efficient container object
11 : * than can hold items of type void*, offering the following features:
12 : * - Its interface supports pushing, popping, and peeking of items at the back
13 : * or front, and retrieval from any position.
14 : * - It can iterate over items via a ForEach method, range-for, or an iterator
15 : * class.
16 : * - When full, it can efficiently resize dynamically.
17 : *
18 : * NOTE: The only bit of trickery here is that this deque is
19 : * built upon a ring-buffer. Like all ring buffers, the first
20 : * item may not be at index[0]. The mOrigin member determines
21 : * where the first child is. This point is quietly hidden from
22 : * customers of this class.
23 : */
24 :
25 : #ifndef _NSDEQUE
26 : #define _NSDEQUE
27 :
28 : #include "nscore.h"
29 : #include "nsDebug.h"
30 : #include "mozilla/Attributes.h"
31 : #include "mozilla/fallible.h"
32 : #include "mozilla/MemoryReporting.h"
33 :
34 : /**
35 : * The nsDequeFunctor class is used when you want to create
36 : * callbacks between the deque and your generic code.
37 : * Use these objects in a call to ForEach(), and as custom deallocators.
38 : */
39 6 : class nsDequeFunctor
40 : {
41 : public:
42 : virtual void* operator()(void* aObject) = 0;
43 3 : virtual ~nsDequeFunctor() {}
44 : };
45 :
46 : /******************************************************
47 : * Here comes the nsDeque class itself...
48 : ******************************************************/
49 :
50 : /**
51 : * The deque (double-ended queue) class is a common container type,
52 : * whose behavior mimics a line in your favorite checkout stand.
53 : * Classic CS describes the common behavior of a queue as FIFO.
54 : * A deque allows insertion and removal at both ends of
55 : * the container.
56 : *
57 : * The deque stores pointers to items.
58 : */
59 : class nsDeque
60 : {
61 : typedef mozilla::fallible_t fallible_t;
62 : public:
63 : /**
64 : * Constructs an empty deque.
65 : *
66 : * @param aDeallocator Optional deallocator functor that will be called from
67 : * Erase() and the destructor on any remaining item.
68 : * The deallocator is owned by the deque and will be
69 : * deleted at destruction time.
70 : */
71 : explicit nsDeque(nsDequeFunctor* aDeallocator = nullptr);
72 :
73 : /**
74 : * Deque destructor. Erases all items, deletes the deallocator.
75 : */
76 : ~nsDeque();
77 :
78 : /**
79 : * Returns the number of items currently stored in
80 : * this deque.
81 : *
82 : * @return number of items currently in the deque
83 : */
84 22 : inline size_t GetSize() const { return mSize; }
85 :
86 : /**
87 : * Appends new member at the end of the deque.
88 : *
89 : * @param aItem item to store in deque
90 : */
91 3 : void Push(void* aItem)
92 : {
93 3 : if (!Push(aItem, mozilla::fallible)) {
94 0 : NS_ABORT_OOM(mSize * sizeof(void*));
95 : }
96 3 : }
97 :
98 : /**
99 : * Appends new member at the end of the deque.
100 : *
101 : * @param aItem item to store in deque
102 : * @return true if succeeded, false if failed to resize deque as needed
103 : */
104 : MOZ_MUST_USE bool Push(void* aItem, const fallible_t&);
105 :
106 : /**
107 : * Inserts new member at the front of the deque.
108 : *
109 : * @param aItem item to store in deque
110 : */
111 0 : void PushFront(void* aItem)
112 : {
113 0 : if (!PushFront(aItem, mozilla::fallible)) {
114 0 : NS_ABORT_OOM(mSize * sizeof(void*));
115 : }
116 0 : }
117 :
118 : /**
119 : * Inserts new member at the front of the deque.
120 : *
121 : * @param aItem item to store in deque
122 : * @return true if succeeded, false if failed to resize deque as needed
123 : */
124 : MOZ_MUST_USE bool PushFront(void* aItem, const fallible_t&);
125 :
126 : /**
127 : * Remove and return the last item in the container.
128 : *
129 : * @return the item that was the last item in container
130 : */
131 : void* Pop();
132 :
133 : /**
134 : * Remove and return the first item in the container.
135 : *
136 : * @return the item that was first item in container
137 : */
138 : void* PopFront();
139 :
140 : /**
141 : * Retrieve the last item without removing it.
142 : *
143 : * @return the last item in container
144 : */
145 : void* Peek() const;
146 :
147 : /**
148 : * Retrieve the first item without removing it.
149 : *
150 : * @return the first item in container
151 : */
152 : void* PeekFront() const;
153 :
154 : /**
155 : * Retrieve a member from the deque without removing it.
156 : *
157 : * @param index of desired item
158 : * @return item in list, or nullptr if index is outside the deque
159 : */
160 : void* ObjectAt(size_t aIndex) const;
161 :
162 : /**
163 : * Remove and delete all items from container.
164 : * Deletes are handled by the deallocator nsDequeFunctor
165 : * which is specified at deque construction.
166 : */
167 : void Erase();
168 :
169 : /**
170 : * Call this method when you want to iterate through all
171 : * items in the container, passing a functor along
172 : * to call your code.
173 : * If the deque is modified during ForEach, iteration will continue based on
174 : * item indices; meaning that front operations may effectively skip over
175 : * items or visit some items multiple times.
176 : *
177 : * @param aFunctor object to call for each member
178 : */
179 : void ForEach(nsDequeFunctor& aFunctor) const;
180 :
181 : // This iterator assumes that the deque itself is const, i.e., it cannot be
182 : // modified while the iterator is used.
183 : // Also it is a 'const' iterator in that it provides copies of the deque's
184 : // elements, and therefore it is not possible to modify the deque's contents
185 : // by assigning to a dereference of this iterator.
186 : class ConstDequeIterator
187 : {
188 : public:
189 : ConstDequeIterator(const nsDeque& aDeque, size_t aIndex)
190 : : mDeque(aDeque)
191 : , mIndex(aIndex)
192 : {
193 : }
194 : ConstDequeIterator& operator++()
195 : {
196 : ++mIndex;
197 : return *this;
198 : }
199 : bool operator==(const ConstDequeIterator& aOther) const
200 : {
201 : return mIndex == aOther.mIndex;
202 : }
203 : bool operator!=(const ConstDequeIterator& aOther) const
204 : {
205 : return mIndex != aOther.mIndex;
206 : }
207 : void* operator*() const
208 : {
209 : // Don't allow out-of-deque dereferences.
210 : MOZ_RELEASE_ASSERT(mIndex < mDeque.GetSize());
211 : return mDeque.ObjectAt(mIndex);
212 : }
213 : private:
214 : const nsDeque& mDeque;
215 : size_t mIndex;
216 : };
217 : // If this deque is const, we can provide ConstDequeIterator's.
218 : ConstDequeIterator begin() const
219 : {
220 : return ConstDequeIterator(*this, 0);
221 : }
222 : ConstDequeIterator end() const
223 : {
224 : return ConstDequeIterator(*this, mSize);
225 : }
226 :
227 : // It is a 'const' iterator in that it provides copies of the deque's
228 : // elements, and therefore it is not possible to modify the deque's contents
229 : // by assigning to a dereference of this iterator.
230 : // If the deque is modified in other ways, this iterator will stay at the same
231 : // index, and will handle past-the-end comparisons, but not dereferencing.
232 : class ConstIterator
233 : {
234 : public:
235 : // Special index for the end iterator, to track the possibly-shifting
236 : // deque size.
237 : static const size_t EndIteratorIndex = size_t(-1);
238 :
239 : ConstIterator(const nsDeque& aDeque, size_t aIndex)
240 : : mDeque(aDeque)
241 : , mIndex(aIndex)
242 : {
243 : }
244 : ConstIterator& operator++()
245 : {
246 : // End-iterator shouldn't be modified.
247 : MOZ_ASSERT(mIndex != EndIteratorIndex);
248 : ++mIndex;
249 : return *this;
250 : }
251 : bool operator==(const ConstIterator& aOther) const
252 : {
253 : return EffectiveIndex() == aOther.EffectiveIndex();
254 : }
255 : bool operator!=(const ConstIterator& aOther) const
256 : {
257 : return EffectiveIndex() != aOther.EffectiveIndex();
258 : }
259 : void* operator*() const
260 : {
261 : // Don't allow out-of-deque dereferences.
262 : MOZ_RELEASE_ASSERT(mIndex < mDeque.GetSize());
263 : return mDeque.ObjectAt(mIndex);
264 : }
265 : private:
266 : // 0 <= index < deque.GetSize() inside the deque, deque.GetSize() otherwise.
267 : // Only used when comparing indices, not to actually access items.
268 : size_t EffectiveIndex() const
269 : {
270 : return (mIndex < mDeque.GetSize()) ? mIndex : mDeque.GetSize();
271 : }
272 :
273 : const nsDeque& mDeque;
274 : size_t mIndex; // May point outside the deque!
275 : };
276 : // If this deque is *not* const, we provide ConstIterator's that can handle
277 : // deque size changes.
278 : ConstIterator begin()
279 : {
280 : return ConstIterator(*this, 0);
281 : }
282 : ConstIterator end()
283 : {
284 : return ConstIterator(*this, ConstIterator::EndIteratorIndex);
285 : }
286 :
287 : size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
288 : size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
289 :
290 : protected:
291 : size_t mSize;
292 : size_t mCapacity;
293 : size_t mOrigin;
294 : nsDequeFunctor* mDeallocator;
295 : void* mBuffer[8];
296 : void** mData;
297 :
298 : private:
299 :
300 : /**
301 : * Copy constructor (deleted)
302 : *
303 : * @param aOther another deque
304 : */
305 : nsDeque(const nsDeque& aOther) = delete;
306 :
307 : /**
308 : * Deque assignment operator (deleted)
309 : *
310 : * @param aOther another deque
311 : * @return *this
312 : */
313 : nsDeque& operator=(const nsDeque& aOther) = delete;
314 :
315 : bool GrowCapacity();
316 : void SetDeallocator(nsDequeFunctor* aDeallocator);
317 :
318 : /**
319 : * Remove all items from container without destroying them.
320 : */
321 : void Empty();
322 : };
323 : #endif
|
