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/. */
8 #include "nsISupportsImpl.h"
15 * 07/02/2001 09:17p 509,104 clangref.pdf from openwatcom's site
16 * Watcom C Language Reference Edition 11.0c
19 * The % symbol yields the remainder from the division of the first operand
20 * by the second operand. The operands of % must have integral type.
22 * When both operands of % are positive, the result is a positive value
23 * smaller than the second operand. When one or both operands is negative,
24 * whether the result is positive or negative is implementation-defined.
27 /* Ok, so first of all, C is underspecified. joy.
28 * The following functions do not provide a correct implementation of modulus
29 * They provide functionality for x>-y.
30 * There are risks of 2*y being greater than max int, which is part of the
31 * reason no multiplication is used and other operations are avoided.
36 * approximately equivalent to x %= y
41 * approximately equivalent to x % y
43 #define modasgn(x,y) if (x<0) x+=y; x%=y
44 #define modulus(x,y) ((x<0)?(x+y)%(y):(x)%(y))
47 * Standard constructor
48 * @param deallocator, called by Erase and ~nsDeque
50 nsDeque::nsDeque(nsDequeFunctor
* aDeallocator
)
52 MOZ_COUNT_CTOR(nsDeque
);
53 mDeallocator
= aDeallocator
;
55 mData
= mBuffer
; // don't allocate space until you must
56 mCapacity
= sizeof(mBuffer
) / sizeof(mBuffer
[0]);
57 memset(mData
, 0, mCapacity
* sizeof(mBuffer
[0]));
65 MOZ_COUNT_DTOR(nsDeque
);
69 printf("Capacity: %i\n", mCapacity
);
71 static int mCaps
[15] = {0};
73 case 4: mCaps
[0]++; break;
74 case 8: mCaps
[1]++; break;
75 case 16: mCaps
[2]++; break;
76 case 32: mCaps
[3]++; break;
77 case 64: mCaps
[4]++; break;
78 case 128: mCaps
[5]++; break;
79 case 256: mCaps
[6]++; break;
80 case 512: mCaps
[7]++; break;
81 case 1024: mCaps
[8]++; break;
82 case 2048: mCaps
[9]++; break;
83 case 4096: mCaps
[10]++; break;
90 if (mData
&& mData
!= mBuffer
) {
98 nsDeque::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const
101 if (mData
!= mBuffer
) {
102 size
+= aMallocSizeOf(mData
);
106 size
+= aMallocSizeOf(mDeallocator
);
113 nsDeque::SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const
115 return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf
);
119 * Set the functor to be called by Erase()
120 * The deque owns the functor.
122 * @param aDeallocator functor object for use by Erase()
125 nsDeque::SetDeallocator(nsDequeFunctor
* aDeallocator
)
128 mDeallocator
= aDeallocator
;
132 * Remove all items from container without destroying them.
137 if (mSize
&& mData
) {
138 memset(mData
, 0, mCapacity
* sizeof(mData
));
145 * Remove and delete all items from container
150 if (mDeallocator
&& mSize
) {
151 ForEach(*mDeallocator
);
157 * This method quadruples the size of the deque
158 * Elements in the deque are resequenced so that elements
159 * in the deque are stored sequentially
161 * @return whether growing succeeded
164 nsDeque::GrowCapacity()
166 int32_t theNewSize
= mCapacity
<< 2;
167 NS_ASSERTION(theNewSize
> mCapacity
, "Overflow");
168 if (theNewSize
<= mCapacity
) {
171 void** temp
= (void**)malloc(theNewSize
* sizeof(void*));
176 //Here's the interesting part: You can't just move the elements
177 //directly (in situ) from the old buffer to the new one.
178 //Since capacity has changed, the old origin doesn't make
179 //sense anymore. It's better to resequence the elements now.
181 memcpy(temp
, mData
+ mOrigin
, sizeof(void*) * (mCapacity
- mOrigin
));
182 memcpy(temp
+ (mCapacity
- mOrigin
), mData
, sizeof(void*) * mOrigin
);
184 if (mData
!= mBuffer
) {
188 mCapacity
= theNewSize
;
189 mOrigin
= 0; //now realign the origin...
196 * This method adds an item to the end of the deque.
197 * This operation has the potential to cause the
198 * underlying buffer to resize.
200 * @param aItem: new item to be added to deque
203 nsDeque::Push(void* aItem
, const fallible_t
&)
205 if (mSize
== mCapacity
&& !GrowCapacity()) {
208 mData
[modulus(mOrigin
+ mSize
, mCapacity
)] = aItem
;
214 * This method adds an item to the front of the deque.
215 * This operation has the potential to cause the
216 * underlying buffer to resize.
218 * --Commments for GrowCapacity() case
219 * We've grown and shifted which means that the old
220 * final element in the deque is now the first element
221 * in the deque. This is temporary.
222 * We haven't inserted the new element at the front.
224 * To continue with the idea of having the front at zero
225 * after a grow, we move the old final item (which through
226 * the voodoo of mOrigin-- is now the first) to its final
227 * position which is conveniently the old length.
229 * Note that this case only happens when the deque is full.
230 * [And that pieces of this magic only work if the deque is full.]
232 * [ABCDEFGH] @[mOrigin:3]:D.
233 * Task: PushFront("Z")
234 * shift mOrigin so, @[mOrigin:2]:C
235 * stretch and rearrange: (mOrigin:0)
236 * [CDEFGHAB ________ ________ ________]
237 * copy: (The second C is currently out of bounds)
238 * [CDEFGHAB C_______ ________ ________]
239 * later we will insert Z:
240 * [ZDEFGHAB C_______ ________ ________]
241 * and increment size: 9. (C is no longer out of bounds)
243 * @param aItem: new item to be added to deque
246 nsDeque::PushFront(void* aItem
, const fallible_t
&)
249 modasgn(mOrigin
, mCapacity
);
250 if (mSize
== mCapacity
) {
251 if (!GrowCapacity()) {
254 /* Comments explaining this are above*/
255 mData
[mSize
] = mData
[mOrigin
];
257 mData
[mOrigin
] = aItem
;
263 * Remove and return the last item in the container.
265 * @return ptr to last item in container
273 int32_t offset
= modulus(mSize
+ mOrigin
, mCapacity
);
274 result
= mData
[offset
];
284 * This method gets called you want to remove and return
285 * the first member in the container.
287 * @return last item in container
294 NS_ASSERTION(mOrigin
< mCapacity
, "Error: Bad origin");
295 result
= mData
[mOrigin
];
296 mData
[mOrigin
++] = 0; //zero it out for debugging purposes.
298 // Cycle around if we pop off the end
299 // and reset origin if when we pop the last element
300 if (mCapacity
== mOrigin
|| !mSize
) {
308 * This method gets called you want to peek at the bottom
309 * member without removing it.
311 * @return last item in container
318 result
= mData
[modulus(mSize
- 1 + mOrigin
, mCapacity
)];
324 * This method gets called you want to peek at the topmost
325 * member without removing it.
327 * @return last item in container
334 result
= mData
[mOrigin
];
340 * Call this to retrieve the ith element from this container.
341 * Keep in mind that accessing the underlying elements is
342 * done in a relative fashion. Object 0 is not necessarily
343 * the first element (the first element is at mOrigin).
345 * @param aIndex : 0 relative offset of item you want
346 * @return void* or null
349 nsDeque::ObjectAt(int32_t aIndex
) const
352 if (aIndex
>= 0 && aIndex
< mSize
) {
353 result
= mData
[modulus(mOrigin
+ aIndex
, mCapacity
)];
359 nsDeque::RemoveObjectAt(int32_t aIndex
)
361 if (aIndex
< 0 || aIndex
>= mSize
) {
364 void* result
= mData
[modulus(mOrigin
+ aIndex
, mCapacity
)];
366 // "Shuffle down" all elements in the array by 1, overwritting the element
368 for (int32_t i
= aIndex
; i
< mSize
; ++i
) {
369 mData
[modulus(mOrigin
+ i
, mCapacity
)] =
370 mData
[modulus(mOrigin
+ i
+ 1, mCapacity
)];
378 * Create and return an iterator pointing to
379 * the beginning of the queue. Note that this
380 * takes the circular buffer semantics into account.
382 * @return new deque iterator, init'ed to 1st item
385 nsDeque::Begin() const
387 return nsDequeIterator(*this, 0);
391 * Create and return an iterator pointing to
392 * the last item in the deque.
393 * Note that this takes the circular buffer semantics
396 * @return new deque iterator, init'ed to the last item
401 return nsDequeIterator(*this, mSize
- 1);
405 nsDeque::Last() const
407 return End().GetCurrent();
411 * Call this method when you want to iterate all the
412 * members of the container, passing a functor along
415 * @param aFunctor object to call for each member
419 nsDeque::ForEach(nsDequeFunctor
& aFunctor
) const
421 for (int32_t i
= 0; i
< mSize
; ++i
) {
422 aFunctor(ObjectAt(i
));
427 * Call this method when you want to iterate all the
428 * members of the container, calling the functor you
429 * passed with each member. This process will interrupt
430 * if your function returns non 0 to this method.
432 * @param aFunctor object to call for each member
433 * @return first nonzero result of aFunctor or 0.
436 nsDeque::FirstThat(nsDequeFunctor
& aFunctor
) const
438 for (int32_t i
= 0; i
< mSize
; ++i
) {
439 void* obj
= aFunctor(ObjectAt(i
));
447 /******************************************************
448 * Here comes the nsDequeIterator class...
449 ******************************************************/
452 * DequeIterator is an object that knows how to iterate (forward and backward)
453 * through a Deque. Normally, you don't need to do this, but there are some special
454 * cases where it is pretty handy, so here you go.
456 * This is a standard dequeiterator constructor
458 * @param aQueue is the deque object to be iterated
459 * @param aIndex is the starting position for your iteration
461 nsDequeIterator::nsDequeIterator(const nsDeque
& aQueue
, int aIndex
)
468 * Create a copy of a DequeIterator
470 * @param aCopy is another iterator to copy from
472 nsDequeIterator::nsDequeIterator(const nsDequeIterator
& aCopy
)
473 : mIndex(aCopy
.mIndex
)
474 , mDeque(aCopy
.mDeque
)
479 * Moves iterator to first element in deque
483 nsDequeIterator::First()
490 * Standard assignment operator for dequeiterator
492 * @param aCopy is an iterator to be copied from
496 nsDequeIterator::operator=(const nsDequeIterator
& aCopy
)
498 NS_ASSERTION(&mDeque
== &aCopy
.mDeque
,
499 "you can't change the deque that an interator is iterating over, sorry.");
500 mIndex
= aCopy
.mIndex
;
505 * preform ! operation against to iterators to test for equivalence
508 * @param aIter is the object to be compared to
509 * @return TRUE if NOT equal.
512 nsDequeIterator::operator!=(nsDequeIterator
& aIter
)
514 return !this->operator==(aIter
);
518 * Compare two iterators for increasing order.
520 * @param aIter is the other iterator to be compared to
521 * @return TRUE if this object points to an element before
522 * the element pointed to by aIter.
523 * FALSE if this and aIter are not iterating over the same deque.
526 nsDequeIterator::operator<(nsDequeIterator
& aIter
)
528 return mIndex
< aIter
.mIndex
&& &mDeque
== &aIter
.mDeque
;
532 * Compare two iterators for equivalence.
534 * @param aIter is the other iterator to be compared to
535 * @return TRUE if EQUAL
538 nsDequeIterator::operator==(nsDequeIterator
& aIter
)
540 return mIndex
== aIter
.mIndex
&& &mDeque
== &aIter
.mDeque
;
544 * Compare two iterators for non strict decreasing order.
546 * @param aIter is the other iterator to be compared to
547 * @return TRUE if this object points to the same element, or
548 * an element after the element pointed to by aIter.
549 * FALSE if this and aIter are not iterating over the same deque.
552 nsDequeIterator::operator>=(nsDequeIterator
& aIter
)
554 return mIndex
>= aIter
.mIndex
&& &mDeque
== &aIter
.mDeque
;
558 * Pre-increment operator
560 * @return object at post-incremented index
563 nsDequeIterator::operator++()
565 NS_ASSERTION(mIndex
< mDeque
.mSize
,
566 "You have reached the end of the Internet. You have seen "
567 "everything there is to see. Please go back. Now.");
568 #ifndef TIMELESS_LIGHTWEIGHT
569 if (mIndex
>= mDeque
.mSize
) {
573 return mDeque
.ObjectAt(++mIndex
);
577 * Post-increment operator
579 * @param param is ignored
580 * @return object at pre-incremented index
583 nsDequeIterator::operator++(int)
585 NS_ASSERTION(mIndex
<= mDeque
.mSize
,
586 "You have reached the end of the Internet. You have seen "
587 "everything there is to see. Please go back. Now.");
588 #ifndef TIMELESS_LIGHTWEIGHT
589 if (mIndex
> mDeque
.mSize
) {
593 return mDeque
.ObjectAt(mIndex
++);
597 * Pre-decrement operator
599 * @return object at pre-decremented index
602 nsDequeIterator::operator--()
604 NS_ASSERTION(mIndex
>= 0,
605 "You have reached the end of the Internet. You have seen "
606 "everything there is to see. Please go forward. Now.");
607 #ifndef TIMELESS_LIGHTWEIGHT
612 return mDeque
.ObjectAt(--mIndex
);
616 * Post-decrement operator
618 * @param param is ignored
619 * @return object at post-decremented index
622 nsDequeIterator::operator--(int)
624 NS_ASSERTION(mIndex
>= 0,
625 "You have reached the end of the Internet. You have seen "
626 "everything there is to see. Please go forward. Now.");
627 #ifndef TIMELESS_LIGHTWEIGHT
632 return mDeque
.ObjectAt(mIndex
--);
636 * Dereference operator
637 * Note that the iterator floats, so you don't need to do:
638 * <code>++iter; aDeque.PopFront();</code>
639 * Unless you actually want your iterator to jump 2 spaces.
641 * Picture: [1 2I 3 4]
644 * Note that I still happily points to object at the second index
646 * @return object at ith index
649 nsDequeIterator::GetCurrent()
651 NS_ASSERTION(mIndex
< mDeque
.mSize
&& mIndex
>= 0, "Current is out of bounds");
652 #ifndef TIMELESS_LIGHTWEIGHT
653 if (mIndex
>= mDeque
.mSize
|| mIndex
< 0) {
657 return mDeque
.ObjectAt(mIndex
);
661 * Call this method when you want to iterate all the
662 * members of the container, passing a functor along
665 * @param aFunctor object to call for each member
669 nsDequeIterator::ForEach(nsDequeFunctor
& aFunctor
) const
671 mDeque
.ForEach(aFunctor
);
675 * Call this method when you want to iterate all the
676 * members of the container, calling the functor you
677 * passed with each member. This process will interrupt
678 * if your function returns non 0 to this method.
680 * @param aFunctor object to call for each member
681 * @return first nonzero result of aFunctor or 0.
684 nsDequeIterator::FirstThat(nsDequeFunctor
& aFunctor
) const
686 return mDeque
.FirstThat(aFunctor
);