xpcom/glue/nsDeque.h

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