xpcom/glue/nsDeque.h

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