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 class nsDequeFunctor { 40 public: 41 virtual void operator()(void* aObject) = 0; 42 virtual ~nsDequeFunctor() = default; 43 }; 44 45 /****************************************************** 46 * Here comes the nsDeque class itself... 47 ******************************************************/ 48 49 /** 50 * The deque (double-ended queue) class is a common container type, 51 * whose behavior mimics a line in your favorite checkout stand. 52 * Classic CS describes the common behavior of a queue as FIFO. 53 * A deque allows insertion and removal at both ends of 54 * the container. 55 * 56 * The deque stores pointers to items. 57 */ 58 class nsDeque { 59 typedef mozilla::fallible_t fallible_t; 60 61 public: 62 /** 63 * Constructs an empty deque. 64 * 65 * @param aDeallocator Optional deallocator functor that will be called from 66 * Erase() and the destructor on any remaining item. 67 * The deallocator is owned by the deque and will be 68 * deleted at destruction time. 69 */ 70 explicit nsDeque(nsDequeFunctor* aDeallocator = nullptr); 71 72 /** 73 * Deque destructor. Erases all items, deletes the deallocator. 74 */ 75 ~nsDeque(); 76 77 /** 78 * Returns the number of items currently stored in 79 * this deque. 80 * 81 * @return number of items currently in the deque 82 */ GetSize()83 inline size_t GetSize() const { return mSize; } 84 85 /** 86 * Appends new member at the end of the deque. 87 * 88 * @param aItem item to store in deque 89 */ Push(void * aItem)90 void Push(void* aItem) { 91 if (!Push(aItem, mozilla::fallible)) { 92 NS_ABORT_OOM(mSize * sizeof(void*)); 93 } 94 } 95 96 /** 97 * Appends new member at the end of the deque. 98 * 99 * @param aItem item to store in deque 100 * @return true if succeeded, false if failed to resize deque as needed 101 */ 102 [[nodiscard]] bool Push(void* aItem, const fallible_t&); 103 104 /** 105 * Inserts new member at the front of the deque. 106 * 107 * @param aItem item to store in deque 108 */ PushFront(void * aItem)109 void PushFront(void* aItem) { 110 if (!PushFront(aItem, mozilla::fallible)) { 111 NS_ABORT_OOM(mSize * sizeof(void*)); 112 } 113 } 114 115 /** 116 * Inserts new member at the front of the deque. 117 * 118 * @param aItem item to store in deque 119 * @return true if succeeded, false if failed to resize deque as needed 120 */ 121 [[nodiscard]] bool PushFront(void* aItem, const fallible_t&); 122 123 /** 124 * Remove and return the last item in the container. 125 * 126 * @return the item that was the last item in container 127 */ 128 void* Pop(); 129 130 /** 131 * Remove and return the first item in the container. 132 * 133 * @return the item that was first item in container 134 */ 135 void* PopFront(); 136 137 /** 138 * Retrieve the last item without removing it. 139 * 140 * @return the last item in container 141 */ 142 void* Peek() const; 143 144 /** 145 * Retrieve the first item without removing it. 146 * 147 * @return the first item in container 148 */ 149 void* PeekFront() const; 150 151 /** 152 * Retrieve a member from the deque without removing it. 153 * 154 * @param index of desired item 155 * @return item in list, or nullptr if index is outside the deque 156 */ 157 void* ObjectAt(size_t aIndex) const; 158 159 /** 160 * Remove and delete all items from container. 161 * Deletes are handled by the deallocator nsDequeFunctor 162 * which is specified at deque construction. 163 */ 164 void Erase(); 165 166 /** 167 * Call this method when you want to iterate through all 168 * items in the container, passing a functor along 169 * to call your code. 170 * If the deque is modified during ForEach, iteration will continue based on 171 * item indices; meaning that front operations may effectively skip over 172 * items or visit some items multiple times. 173 * 174 * @param aFunctor object to call for each member 175 */ 176 void ForEach(nsDequeFunctor& aFunctor) const; 177 178 // This iterator assumes that the deque itself is const, i.e., it cannot be 179 // modified while the iterator is used. 180 // Also it is a 'const' iterator in that it provides copies of the deque's 181 // elements, and therefore it is not possible to modify the deque's contents 182 // by assigning to a dereference of this iterator. 183 class ConstDequeIterator { 184 public: ConstDequeIterator(const nsDeque & aDeque,size_t aIndex)185 ConstDequeIterator(const nsDeque& aDeque, size_t aIndex) 186 : mDeque(aDeque), mIndex(aIndex) {} 187 ConstDequeIterator& operator++() { 188 ++mIndex; 189 return *this; 190 } 191 bool operator==(const ConstDequeIterator& aOther) const { 192 return mIndex == aOther.mIndex; 193 } 194 bool operator!=(const ConstDequeIterator& aOther) const { 195 return mIndex != aOther.mIndex; 196 } 197 void* operator*() const { 198 // Don't allow out-of-deque dereferences. 199 MOZ_RELEASE_ASSERT(mIndex < mDeque.GetSize()); 200 return mDeque.ObjectAt(mIndex); 201 } 202 203 private: 204 const nsDeque& mDeque; 205 size_t mIndex; 206 }; 207 // If this deque is const, we can provide ConstDequeIterator's. begin()208 ConstDequeIterator begin() const { return ConstDequeIterator(*this, 0); } end()209 ConstDequeIterator end() const { return ConstDequeIterator(*this, mSize); } 210 211 // It is a 'const' iterator in that it provides copies of the deque's 212 // elements, and therefore it is not possible to modify the deque's contents 213 // by assigning to a dereference of this iterator. 214 // If the deque is modified in other ways, this iterator will stay at the same 215 // index, and will handle past-the-end comparisons, but not dereferencing. 216 class ConstIterator { 217 public: 218 // Special index for the end iterator, to track the possibly-shifting 219 // deque size. 220 static const size_t EndIteratorIndex = size_t(-1); 221 ConstIterator(const nsDeque & aDeque,size_t aIndex)222 ConstIterator(const nsDeque& aDeque, size_t aIndex) 223 : mDeque(aDeque), mIndex(aIndex) {} 224 ConstIterator& operator++() { 225 // End-iterator shouldn't be modified. 226 MOZ_ASSERT(mIndex != EndIteratorIndex); 227 ++mIndex; 228 return *this; 229 } 230 bool operator==(const ConstIterator& aOther) const { 231 return EffectiveIndex() == aOther.EffectiveIndex(); 232 } 233 bool operator!=(const ConstIterator& aOther) const { 234 return EffectiveIndex() != aOther.EffectiveIndex(); 235 } 236 void* operator*() const { 237 // Don't allow out-of-deque dereferences. 238 MOZ_RELEASE_ASSERT(mIndex < mDeque.GetSize()); 239 return mDeque.ObjectAt(mIndex); 240 } 241 242 private: 243 // 0 <= index < deque.GetSize() inside the deque, deque.GetSize() otherwise. 244 // Only used when comparing indices, not to actually access items. EffectiveIndex()245 size_t EffectiveIndex() const { 246 return (mIndex < mDeque.GetSize()) ? mIndex : mDeque.GetSize(); 247 } 248 249 const nsDeque& mDeque; 250 size_t mIndex; // May point outside the deque! 251 }; 252 // If this deque is *not* const, we provide ConstIterator's that can handle 253 // deque size changes. begin()254 ConstIterator begin() { return ConstIterator(*this, 0); } end()255 ConstIterator end() { 256 return ConstIterator(*this, ConstIterator::EndIteratorIndex); 257 } 258 259 size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const; 260 size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const; 261 262 protected: 263 size_t mSize; 264 size_t mCapacity; 265 size_t mOrigin; 266 nsDequeFunctor* mDeallocator; 267 void* mBuffer[8]; 268 void** mData; 269 270 private: 271 /** 272 * Copy constructor (deleted) 273 * 274 * @param aOther another deque 275 */ 276 nsDeque(const nsDeque& aOther) = delete; 277 278 /** 279 * Deque assignment operator (deleted) 280 * 281 * @param aOther another deque 282 * @return *this 283 */ 284 nsDeque& operator=(const nsDeque& aOther) = delete; 285 286 bool GrowCapacity(); 287 void SetDeallocator(nsDequeFunctor* aDeallocator); 288 289 /** 290 * Remove all items from container without destroying them. 291 */ 292 void Empty(); 293 }; 294 #endif 295