michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public michael@0: * License, v. 2.0. If a copy of the MPL was not distributed with this michael@0: * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ michael@0: michael@0: /** michael@0: * MODULE NOTES: michael@0: * michael@0: * The Deque is a very small, very efficient container object michael@0: * than can hold elements of type void*, offering the following features: michael@0: * Its interface supports pushing and popping of elements. michael@0: * It can iterate (via an interator class) its elements. michael@0: * When full, it can efficiently resize dynamically. michael@0: * michael@0: * michael@0: * NOTE: The only bit of trickery here is that this deque is michael@0: * built upon a ring-buffer. Like all ring buffers, the first michael@0: * element may not be at index[0]. The mOrigin member determines michael@0: * where the first child is. This point is quietly hidden from michael@0: * customers of this class. michael@0: * michael@0: */ michael@0: michael@0: #ifndef _NSDEQUE michael@0: #define _NSDEQUE michael@0: michael@0: #include "nscore.h" michael@0: #include "nsDebug.h" michael@0: #include "mozilla/Attributes.h" michael@0: #include "mozilla/fallible.h" michael@0: #include "mozilla/MemoryReporting.h" michael@0: michael@0: /** michael@0: * The nsDequeFunctor class is used when you want to create michael@0: * callbacks between the deque and your generic code. michael@0: * Use these objects in a call to ForEach(); michael@0: * michael@0: */ michael@0: michael@0: class nsDequeFunctor{ michael@0: public: michael@0: virtual void* operator()(void* anObject)=0; michael@0: virtual ~nsDequeFunctor() {} michael@0: }; michael@0: michael@0: /****************************************************** michael@0: * Here comes the nsDeque class itself... michael@0: ******************************************************/ michael@0: michael@0: /** michael@0: * The deque (double-ended queue) class is a common container type, michael@0: * whose behavior mimics a line in your favorite checkout stand. michael@0: * Classic CS describes the common behavior of a queue as FIFO. michael@0: * A deque allows insertion and removal at both ends of michael@0: * the container. michael@0: * michael@0: * The deque stores pointers to items. michael@0: */ michael@0: michael@0: class nsDequeIterator; michael@0: michael@0: class NS_COM_GLUE nsDeque { michael@0: friend class nsDequeIterator; michael@0: typedef mozilla::fallible_t fallible_t; michael@0: public: michael@0: nsDeque(nsDequeFunctor* aDeallocator = nullptr); michael@0: ~nsDeque(); michael@0: michael@0: /** michael@0: * Returns the number of elements currently stored in michael@0: * this deque. michael@0: * michael@0: * @return number of elements currently in the deque michael@0: */ michael@0: inline int32_t GetSize() const {return mSize;} michael@0: michael@0: /** michael@0: * Appends new member at the end of the deque. michael@0: * michael@0: * @param item to store in deque michael@0: */ michael@0: void Push(void* aItem) { michael@0: if (!Push(aItem, fallible_t())) { michael@0: NS_ABORT_OOM(mSize); michael@0: } michael@0: } michael@0: michael@0: bool Push(void* aItem, const fallible_t&) NS_WARN_UNUSED_RESULT; michael@0: michael@0: /** michael@0: * Inserts new member at the front of the deque. michael@0: * michael@0: * @param item to store in deque michael@0: */ michael@0: void PushFront(void* aItem) { michael@0: if (!PushFront(aItem, fallible_t())) { michael@0: NS_ABORT_OOM(mSize); michael@0: } michael@0: } michael@0: michael@0: bool PushFront(void* aItem, const fallible_t&) NS_WARN_UNUSED_RESULT; michael@0: michael@0: /** michael@0: * Remove and return the last item in the container. michael@0: * michael@0: * @return the item that was the last item in container michael@0: */ michael@0: void* Pop(); michael@0: michael@0: /** michael@0: * Remove and return the first item in the container. michael@0: * michael@0: * @return the item that was first item in container michael@0: */ michael@0: void* PopFront(); michael@0: michael@0: /** michael@0: * Retrieve the bottom item without removing it. michael@0: * michael@0: * @return the first item in container michael@0: */ michael@0: michael@0: void* Peek(); michael@0: /** michael@0: * Return topmost item without removing it. michael@0: * michael@0: * @return the first item in container michael@0: */ michael@0: void* PeekFront(); michael@0: michael@0: /** michael@0: * Retrieve the i'th member from the deque without removing it. michael@0: * michael@0: * @param index of desired item michael@0: * @return i'th element in list michael@0: */ michael@0: void* ObjectAt(int aIndex) const; michael@0: michael@0: /** michael@0: * Removes and returns the i'th member from the deque. michael@0: * michael@0: * @param index of desired item michael@0: * @return the element which was removed michael@0: */ michael@0: void* RemoveObjectAt(int aIndex); michael@0: michael@0: /** michael@0: * Remove all items from container without destroying them. michael@0: */ michael@0: void Empty(); michael@0: michael@0: /** michael@0: * Remove and delete all items from container. michael@0: * Deletes are handled by the deallocator nsDequeFunctor michael@0: * which is specified at deque construction. michael@0: */ michael@0: void Erase(); michael@0: michael@0: /** michael@0: * Creates a new iterator, pointing to the first michael@0: * item in the deque. michael@0: * michael@0: * @return new dequeIterator michael@0: */ michael@0: nsDequeIterator Begin() const; michael@0: michael@0: /** michael@0: * Creates a new iterator, pointing to the last michael@0: * item in the deque. michael@0: * michael@0: * @return new dequeIterator michael@0: */ michael@0: nsDequeIterator End() const; michael@0: michael@0: void* Last() const; michael@0: michael@0: /** michael@0: * Call this method when you want to iterate all the michael@0: * members of the container, passing a functor along michael@0: * to call your code. michael@0: * michael@0: * @param aFunctor object to call for each member michael@0: */ michael@0: void ForEach(nsDequeFunctor& aFunctor) const; michael@0: michael@0: /** michael@0: * Call this method when you want to iterate all the michael@0: * members of the container, calling the functor you michael@0: * passed with each member. This process will interrupt michael@0: * if your function returns non 0 to this method. michael@0: * michael@0: * @param aFunctor object to call for each member michael@0: * @return first nonzero result of aFunctor or 0. michael@0: */ michael@0: const void* FirstThat(nsDequeFunctor& aFunctor) const; michael@0: michael@0: void SetDeallocator(nsDequeFunctor* aDeallocator); michael@0: michael@0: size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const; michael@0: size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const; michael@0: michael@0: protected: michael@0: int32_t mSize; michael@0: int32_t mCapacity; michael@0: int32_t mOrigin; michael@0: nsDequeFunctor* mDeallocator; michael@0: void* mBuffer[8]; michael@0: void** mData; michael@0: michael@0: private: michael@0: michael@0: /** michael@0: * Copy constructor (PRIVATE) michael@0: * michael@0: * @param another deque michael@0: */ michael@0: nsDeque(const nsDeque& other); michael@0: michael@0: /** michael@0: * Deque assignment operator (PRIVATE) michael@0: * michael@0: * @param another deque michael@0: * @return *this michael@0: */ michael@0: nsDeque& operator=(const nsDeque& anOther); michael@0: michael@0: bool GrowCapacity(); michael@0: }; michael@0: michael@0: /****************************************************** michael@0: * Here comes the nsDequeIterator class... michael@0: ******************************************************/ michael@0: michael@0: class NS_COM_GLUE nsDequeIterator { michael@0: public: michael@0: /** michael@0: * DequeIterator is an object that knows how to iterate michael@0: * (forward and backward) through a Deque. Normally, michael@0: * you don't need to do this, but there are some special michael@0: * cases where it is pretty handy. michael@0: * michael@0: * One warning: the iterator is not bound to an item, michael@0: * it is bound to an index, so if you insert or remove michael@0: * from the beginning while using an iterator michael@0: * (which is not recommended) then the iterator will michael@0: * point to a different item. @see GetCurrent() michael@0: * michael@0: * Here you go. michael@0: * michael@0: * @param aQueue is the deque object to be iterated michael@0: * @param aIndex is the starting position for your iteration michael@0: */ michael@0: nsDequeIterator(const nsDeque& aQueue, int aIndex=0); michael@0: michael@0: /** michael@0: * Create a copy of a DequeIterator michael@0: * michael@0: * @param aCopy is another iterator to copy from michael@0: */ michael@0: nsDequeIterator(const nsDequeIterator& aCopy); michael@0: michael@0: /** michael@0: * Moves iterator to first element in the deque michael@0: * @return *this michael@0: */ michael@0: nsDequeIterator& First(); michael@0: michael@0: /** michael@0: * Standard assignment operator for dequeiterator michael@0: * @param aCopy is another iterator to copy from michael@0: * @return *this michael@0: */ michael@0: nsDequeIterator& operator=(const nsDequeIterator& aCopy); michael@0: michael@0: /** michael@0: * preform ! operation against two iterators to test for equivalence michael@0: * (or lack thereof)! michael@0: * michael@0: * @param aIter is the object to be compared to michael@0: * @return TRUE if NOT equal. michael@0: */ michael@0: bool operator!=(nsDequeIterator& aIter); michael@0: michael@0: /** michael@0: * Compare two iterators for increasing order. michael@0: * michael@0: * @param aIter is the other iterator to be compared to michael@0: * @return TRUE if this object points to an element before michael@0: * the element pointed to by aIter. michael@0: * FALSE if this and aIter are not iterating over michael@0: * the same deque. michael@0: */ michael@0: bool operator<(nsDequeIterator& aIter); michael@0: michael@0: /** michael@0: * Compare two iterators for equivalence. michael@0: * michael@0: * @param aIter is the other iterator to be compared to michael@0: * @return TRUE if EQUAL michael@0: */ michael@0: bool operator==(nsDequeIterator& aIter); michael@0: michael@0: /** michael@0: * Compare two iterators for non strict decreasing order. michael@0: * michael@0: * @param aIter is the other iterator to be compared to michael@0: * @return TRUE if this object points to the same element, or michael@0: * an element after the element pointed to by aIter. michael@0: * FALSE if this and aIter are not iterating over michael@0: * the same deque. michael@0: */ michael@0: bool operator>=(nsDequeIterator& aIter); michael@0: michael@0: /** michael@0: * Pre-increment operator michael@0: * Iterator will advance one index towards the end. michael@0: * michael@0: * @return object_at(++index) michael@0: */ michael@0: void* operator++(); michael@0: michael@0: /** michael@0: * Post-increment operator michael@0: * Iterator will advance one index towards the end. michael@0: * michael@0: * @param param is ignored michael@0: * @return object_at(mIndex++) michael@0: */ michael@0: void* operator++(int); michael@0: michael@0: /** michael@0: * Pre-decrement operator michael@0: * Iterator will advance one index towards the beginning. michael@0: * michael@0: * @return object_at(--index) michael@0: */ michael@0: void* operator--(); michael@0: michael@0: /** michael@0: * Post-decrement operator michael@0: * Iterator will advance one index towards the beginning. michael@0: * michael@0: * @param param is ignored michael@0: * @return object_at(index--) michael@0: */ michael@0: void* operator--(int); michael@0: michael@0: /** michael@0: * Retrieve the the iterator's notion of current node. michael@0: * michael@0: * Note that the iterator floats, so you don't need to do: michael@0: * ++iter; aDeque.PopFront(); michael@0: * Unless you actually want your iterator to jump 2 positions michael@0: * relative to its origin. michael@0: * michael@0: * Picture: [1 2i 3 4] michael@0: * PopFront() michael@0: * Picture: [2 3i 4] michael@0: * Note that I still happily points to object at the second index. michael@0: * michael@0: * @return object at i'th index michael@0: */ michael@0: void* GetCurrent(); michael@0: michael@0: /** michael@0: * Call this method when you want to iterate all the michael@0: * members of the container, passing a functor along michael@0: * to call your code. michael@0: * michael@0: * @param aFunctor object to call for each member michael@0: * @return *this michael@0: */ michael@0: void ForEach(nsDequeFunctor& aFunctor) const; michael@0: michael@0: /** michael@0: * Call this method when you want to iterate all the michael@0: * members of the container, calling the functor you michael@0: * passed with each member. This process will interrupt michael@0: * if your function returns non 0 to this method. michael@0: * michael@0: * @param aFunctor object to call for each member michael@0: * @return first nonzero result of aFunctor or 0. michael@0: */ michael@0: const void* FirstThat(nsDequeFunctor& aFunctor) const; michael@0: michael@0: protected: michael@0: michael@0: int32_t mIndex; michael@0: const nsDeque& mDeque; michael@0: }; michael@0: #endif