The Tor Browser / file comparison

comparison: xpcom/glue/nsDeque.h

xpcom/glue/nsDeque.h

changeset 0
6474c204b198
equal deleted inserted replaced
-1:000000000000 0:abf541b61620
1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5
6 /**
7 * MODULE NOTES:
8 *
9 * The Deque is a very small, very efficient container object
10 * than can hold elements of type void*, offering the following features:
11 * Its interface supports pushing and popping of elements.
12 * It can iterate (via an interator class) its elements.
13 * When full, it can efficiently resize dynamically.
14 *
15 *
16 * NOTE: The only bit of trickery here is that this deque is
17 * built upon a ring-buffer. Like all ring buffers, the first
18 * element may not be at index[0]. The mOrigin member determines
19 * where the first child is. This point is quietly hidden from
20 * customers of this class.
21 *
22 */
23
24 #ifndef _NSDEQUE
25 #define _NSDEQUE
26
27 #include "nscore.h"
28 #include "nsDebug.h"
29 #include "mozilla/Attributes.h"
30 #include "mozilla/fallible.h"
31 #include "mozilla/MemoryReporting.h"
32
33 /**
34 * The nsDequeFunctor class is used when you want to create
35 * callbacks between the deque and your generic code.
36 * Use these objects in a call to ForEach();
37 *
38 */
39
40 class nsDequeFunctor{
41 public:
42 virtual void* operator()(void* anObject)=0;
43 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
60 class nsDequeIterator;
61
62 class NS_COM_GLUE nsDeque {
63 friend class nsDequeIterator;
64 typedef mozilla::fallible_t fallible_t;
65 public:
66 nsDeque(nsDequeFunctor* aDeallocator = nullptr);
67 ~nsDeque();
68
69 /**
70 * Returns the number of elements currently stored in
71 * this deque.
72 *
73 * @return number of elements currently in the deque
74 */
75 inline int32_t GetSize() const {return mSize;}
76
77 /**
78 * Appends new member at the end of the deque.
79 *
80 * @param item to store in deque
81 */
82 void Push(void* aItem) {
83 if (!Push(aItem, fallible_t())) {
84 NS_ABORT_OOM(mSize);
85 }
86 }
87
88 bool Push(void* aItem, const fallible_t&) NS_WARN_UNUSED_RESULT;
89
90 /**
91 * Inserts new member at the front of the deque.
92 *
93 * @param item to store in deque
94 */
95 void PushFront(void* aItem) {
96 if (!PushFront(aItem, fallible_t())) {
97 NS_ABORT_OOM(mSize);
98 }
99 }
100
101 bool PushFront(void* aItem, const fallible_t&) NS_WARN_UNUSED_RESULT;
102
103 /**
104 * Remove and return the last item in the container.
105 *
106 * @return the item that was the last item in container
107 */
108 void* Pop();
109
110 /**
111 * Remove and return the first item in the container.
112 *
113 * @return the item that was first item in container
114 */
115 void* PopFront();
116
117 /**
118 * Retrieve the bottom item without removing it.
119 *
120 * @return the first item in container
121 */
122
123 void* Peek();
124 /**
125 * Return topmost item without removing it.
126 *
127 * @return the first item in container
128 */
129 void* PeekFront();
130
131 /**
132 * Retrieve the i'th member from the deque without removing it.
133 *
134 * @param index of desired item
135 * @return i'th element in list
136 */
137 void* ObjectAt(int aIndex) const;
138
139 /**
140 * Removes and returns the i'th member from the deque.
141 *
142 * @param index of desired item
143 * @return the element which was removed
144 */
145 void* RemoveObjectAt(int aIndex);
146
147 /**
148 * Remove all items from container without destroying them.
149 */
150 void Empty();
151
152 /**
153 * Remove and delete all items from container.
154 * Deletes are handled by the deallocator nsDequeFunctor
155 * which is specified at deque construction.
156 */
157 void Erase();
158
159 /**
160 * Creates a new iterator, pointing to the first
161 * item in the deque.
162 *
163 * @return new dequeIterator
164 */
165 nsDequeIterator Begin() const;
166
167 /**
168 * Creates a new iterator, pointing to the last
169 * item in the deque.
170 *
171 * @return new dequeIterator
172 */
173 nsDequeIterator End() const;
174
175 void* Last() const;
176
177 /**
178 * Call this method when you want to iterate all the
179 * members of the container, passing a functor along
180 * to call your code.
181 *
182 * @param aFunctor object to call for each member
183 */
184 void ForEach(nsDequeFunctor& aFunctor) const;
185
186 /**
187 * Call this method when you want to iterate all the
188 * members of the container, calling the functor you
189 * passed with each member. This process will interrupt
190 * if your function returns non 0 to this method.
191 *
192 * @param aFunctor object to call for each member
193 * @return first nonzero result of aFunctor or 0.
194 */
195 const void* FirstThat(nsDequeFunctor& aFunctor) const;
196
197 void SetDeallocator(nsDequeFunctor* aDeallocator);
198
199 size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
200 size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
201
202 protected:
203 int32_t mSize;
204 int32_t mCapacity;
205 int32_t mOrigin;
206 nsDequeFunctor* mDeallocator;
207 void* mBuffer[8];
208 void** mData;
209
210 private:
211
212 /**
213 * Copy constructor (PRIVATE)
214 *
215 * @param another deque
216 */
217 nsDeque(const nsDeque& other);
218
219 /**
220 * Deque assignment operator (PRIVATE)
221 *
222 * @param another deque
223 * @return *this
224 */
225 nsDeque& operator=(const nsDeque& anOther);
226
227 bool GrowCapacity();
228 };
229
230 /******************************************************
231 * Here comes the nsDequeIterator class...
232 ******************************************************/
233
234 class NS_COM_GLUE nsDequeIterator {
235 public:
236 /**
237 * DequeIterator is an object that knows how to iterate
238 * (forward and backward) through a Deque. Normally,
239 * you don't need to do this, but there are some special
240 * cases where it is pretty handy.
241 *
242 * One warning: the iterator is not bound to an item,
243 * it is bound to an index, so if you insert or remove
244 * from the beginning while using an iterator
245 * (which is not recommended) then the iterator will
246 * point to a different item. @see GetCurrent()
247 *
248 * Here you go.
249 *
250 * @param aQueue is the deque object to be iterated
251 * @param aIndex is the starting position for your iteration
252 */
253 nsDequeIterator(const nsDeque& aQueue, int aIndex=0);
254
255 /**
256 * Create a copy of a DequeIterator
257 *
258 * @param aCopy is another iterator to copy from
259 */
260 nsDequeIterator(const nsDequeIterator& aCopy);
261
262 /**
263 * Moves iterator to first element in the deque
264 * @return *this
265 */
266 nsDequeIterator& First();
267
268 /**
269 * Standard assignment operator for dequeiterator
270 * @param aCopy is another iterator to copy from
271 * @return *this
272 */
273 nsDequeIterator& operator=(const nsDequeIterator& aCopy);
274
275 /**
276 * preform ! operation against two iterators to test for equivalence
277 * (or lack thereof)!
278 *
279 * @param aIter is the object to be compared to
280 * @return TRUE if NOT equal.
281 */
282 bool operator!=(nsDequeIterator& aIter);
283
284 /**
285 * Compare two iterators for increasing order.
286 *
287 * @param aIter is the other iterator to be compared to
288 * @return TRUE if this object points to an element before
289 * the element pointed to by aIter.
290 * FALSE if this and aIter are not iterating over
291 * the same deque.
292 */
293 bool operator<(nsDequeIterator& aIter);
294
295 /**
296 * Compare two iterators for equivalence.
297 *
298 * @param aIter is the other iterator to be compared to
299 * @return TRUE if EQUAL
300 */
301 bool operator==(nsDequeIterator& aIter);
302
303 /**
304 * Compare two iterators for non strict decreasing order.
305 *
306 * @param aIter is the other iterator to be compared to
307 * @return TRUE if this object points to the same element, or
308 * an element after the element pointed to by aIter.
309 * FALSE if this and aIter are not iterating over
310 * the same deque.
311 */
312 bool operator>=(nsDequeIterator& aIter);
313
314 /**
315 * Pre-increment operator
316 * Iterator will advance one index towards the end.
317 *
318 * @return object_at(++index)
319 */
320 void* operator++();
321
322 /**
323 * Post-increment operator
324 * Iterator will advance one index towards the end.
325 *
326 * @param param is ignored
327 * @return object_at(mIndex++)
328 */
329 void* operator++(int);
330
331 /**
332 * Pre-decrement operator
333 * Iterator will advance one index towards the beginning.
334 *
335 * @return object_at(--index)
336 */
337 void* operator--();
338
339 /**
340 * Post-decrement operator
341 * Iterator will advance one index towards the beginning.
342 *
343 * @param param is ignored
344 * @return object_at(index--)
345 */
346 void* operator--(int);
347
348 /**
349 * Retrieve the the iterator's notion of current node.
350 *
351 * Note that the iterator floats, so you don't need to do:
352 * <code>++iter; aDeque.PopFront();</code>
353 * Unless you actually want your iterator to jump 2 positions
354 * relative to its origin.
355 *
356 * Picture: [1 2i 3 4]
357 * PopFront()
358 * Picture: [2 3i 4]
359 * Note that I still happily points to object at the second index.
360 *
361 * @return object at i'th index
362 */
363 void* GetCurrent();
364
365 /**
366 * Call this method when you want to iterate all the
367 * members of the container, passing a functor along
368 * to call your code.
369 *
370 * @param aFunctor object to call for each member
371 * @return *this
372 */
373 void ForEach(nsDequeFunctor& aFunctor) const;
374
375 /**
376 * Call this method when you want to iterate all the
377 * members of the container, calling the functor you
378 * passed with each member. This process will interrupt
379 * if your function returns non 0 to this method.
380 *
381 * @param aFunctor object to call for each member
382 * @return first nonzero result of aFunctor or 0.
383 */
384 const void* FirstThat(nsDequeFunctor& aFunctor) const;
385
386 protected:
387
388 int32_t mIndex;
389 const nsDeque& mDeque;
390 };
391 #endif

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial