Back to index

lightning-sunbird  0.9+nobinonly
nsDeque.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either of the GNU General Public License Version 2 or later (the "GPL"),
00026  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 
00038 #include "nsDeque.h"
00039 #include "nsCRT.h"
00040 #ifdef DEBUG_rickg
00041 #include <stdio.h>
00042 #endif
00043 
00057 /* Ok, so first of all, C is underspecified. joy.
00058  * The following functions do not provide a correct implementation of modulus
00059  * They provide functionality for x>-y.
00060  * There are risks of 2*y being greater than max int, which is part of the
00061  * reason no multiplication is used and other operations are avoided.
00062  *
00063  * modasgn
00064  * @param x variable
00065  * @param y expression
00066  * approximately equivalent to x %= y
00067  *
00068  * modulus
00069  * @param x expression
00070  * @param y expression
00071  * approximately equivalent to x % y
00072  */
00073 #define modasgn(x,y) if (x<0) x+=y; x%=y
00074 #define modulus(x,y) ((x<0)?(x+y)%(y):(x)%(y))
00075 
00076 MOZ_DECL_CTOR_COUNTER(nsDeque)
00077 
00078 
00082 nsDeque::nsDeque(nsDequeFunctor* aDeallocator) {
00083   MOZ_COUNT_CTOR(nsDeque);
00084   mDeallocator=aDeallocator;
00085   mOrigin=mSize=0;
00086   mData=mBuffer; // don't allocate space until you must
00087   mCapacity=sizeof(mBuffer)/sizeof(mBuffer[0]);
00088   memset(mData, 0, mCapacity*sizeof(mBuffer[0]));
00089 }
00090 
00094 nsDeque::~nsDeque() {
00095   MOZ_COUNT_DTOR(nsDeque);
00096 
00097 #ifdef DEBUG_rickg
00098   char buffer[30];
00099   printf("Capacity: %i\n", mCapacity);
00100 
00101   static int mCaps[15] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
00102   switch(mCapacity) {
00103     case 4:     mCaps[0]++; break;
00104     case 8:     mCaps[1]++; break;
00105     case 16:    mCaps[2]++; break;
00106     case 32:    mCaps[3]++; break;
00107     case 64:    mCaps[4]++; break;
00108     case 128:   mCaps[5]++; break;
00109     case 256:   mCaps[6]++; break;
00110     case 512:   mCaps[7]++; break;
00111     case 1024:  mCaps[8]++; break;
00112     case 2048:  mCaps[9]++; break;
00113     case 4096:  mCaps[10]++; break;
00114     default:
00115       break;
00116   }
00117 #endif
00118 
00119   Erase();
00120   if (mData && (mData!=mBuffer)) {
00121     delete [] mData;
00122   }
00123   mData=0;
00124   SetDeallocator(0);
00125 }
00126 
00133 void nsDeque::SetDeallocator(nsDequeFunctor* aDeallocator){
00134   if (mDeallocator) {
00135     delete mDeallocator;
00136   }
00137   mDeallocator=aDeallocator;
00138 }
00139 
00145 nsDeque& nsDeque::Empty() {
00146   if (mSize && mData) {
00147     memset(mData, 0, mCapacity*sizeof(mData));
00148   }
00149   mSize=0;
00150   mOrigin=0;
00151   return *this;
00152 }
00153 
00159 nsDeque& nsDeque::Erase() {
00160   if (mDeallocator && mSize) {
00161     ForEach(*mDeallocator);
00162   }
00163   return Empty();
00164 }
00165 
00179 PRInt32 nsDeque::GrowCapacity() {
00180   PRInt32 theNewSize=mCapacity<<2;
00181   NS_ASSERTION(theNewSize>mCapacity, "Overflow");
00182   if (theNewSize<=mCapacity)
00183     return mCapacity;
00184   void** temp=new void*[theNewSize];
00185 
00186   //Here's the interesting part: You can't just move the elements
00187   //directly (in situ) from the old buffer to the new one.
00188   //Since capacity has changed, the old origin doesn't make
00189   //sense anymore. It's better to resequence the elements now.
00190 
00191   if (temp) {
00192     PRInt32 tempi=0;
00193     PRInt32 i=0;
00194     PRInt32 j=0;
00195     for (i=mOrigin; i<mCapacity; i++) {
00196       temp[tempi++]=mData[i]; //copy the leading elements...
00197     }
00198     for (j=0;j<mOrigin;j++) {
00199       temp[tempi++]=mData[j]; //copy the trailing elements...
00200     }
00201     if (mData != mBuffer) {
00202       delete [] mData;
00203     }
00204     mCapacity=theNewSize;
00205     mOrigin=0; //now realign the origin...
00206     mData=temp;
00207   }
00208   return mCapacity;
00209 }
00210 
00219 nsDeque& nsDeque::Push(void* aItem) {
00220   if (mSize==mCapacity) {
00221     GrowCapacity();
00222   }
00223   mData[modulus(mOrigin + mSize, mCapacity)]=aItem;
00224   mSize++;
00225   return *this;
00226 }
00227 
00261 nsDeque& nsDeque::PushFront(void* aItem) {
00262   mOrigin--;
00263   modasgn(mOrigin,mCapacity);
00264   if (mSize==mCapacity) {
00265     GrowCapacity();
00266     /* Comments explaining this are above*/
00267     mData[mSize]=mData[mOrigin];
00268   }
00269   mData[mOrigin]=aItem;
00270   mSize++;
00271   return *this;
00272 }
00273 
00279 void* nsDeque::Pop() {
00280   void* result=0;
00281   if (mSize>0) {
00282     --mSize;
00283     PRInt32 offset=modulus(mSize + mOrigin, mCapacity);
00284     result=mData[offset];
00285     mData[offset]=0;
00286     if (!mSize) {
00287       mOrigin=0;
00288     }
00289   }
00290   return result;
00291 }
00292 
00299 void* nsDeque::PopFront() {
00300   void* result=0;
00301   if (mSize>0) {
00302     NS_ASSERTION(mOrigin < mCapacity, "Error: Bad origin");
00303     result=mData[mOrigin];
00304     mData[mOrigin++]=0;     //zero it out for debugging purposes.
00305     mSize--;
00306     // Cycle around if we pop off the end
00307     // and reset origin if when we pop the last element
00308     if (mCapacity==mOrigin || !mSize) {
00309       mOrigin=0;
00310     }
00311   }
00312   return result;
00313 }
00314 
00321 void* nsDeque::Peek() {
00322   void* result=0;
00323   if (mSize>0) {
00324     result = mData[modulus(mSize - 1 + mOrigin, mCapacity)];
00325   }
00326   return result;
00327 } 
00328 
00335 void* nsDeque::PeekFront() {
00336   void* result=0;
00337   if (mSize>0) {
00338     result=mData[mOrigin];
00339   }
00340   return result;
00341 }
00342 
00352 void* nsDeque::ObjectAt(PRInt32 aIndex) const {
00353   void* result=0;
00354   if ((aIndex>=0) && (aIndex<mSize)) {
00355     result=mData[modulus(mOrigin + aIndex, mCapacity)];
00356   }
00357   return result;
00358 }
00359 
00367 nsDequeIterator nsDeque::Begin() const{
00368   return nsDequeIterator(*this, 0);
00369 }
00370 
00379 nsDequeIterator nsDeque::End() const{
00380   return nsDequeIterator(*this, mSize - 1);
00381 }
00382 
00383 void* nsDeque::Last() const {
00384   return End().GetCurrent();
00385 }
00386 
00395 void nsDeque::ForEach(nsDequeFunctor& aFunctor) const{
00396   for (PRInt32 i=0; i<mSize; i++) {
00397     aFunctor(ObjectAt(i));
00398   }
00399 }
00400 
00410 const void* nsDeque::FirstThat(nsDequeFunctor& aFunctor) const{
00411   for (PRInt32 i=0; i<mSize; i++) {
00412     void* obj=aFunctor(ObjectAt(i));
00413     if (obj) {
00414       return obj;
00415     }
00416   }
00417   return 0;
00418 }
00419 
00420 /******************************************************
00421  * Here comes the nsDequeIterator class...
00422  ******************************************************/
00423 
00434 nsDequeIterator::nsDequeIterator(const nsDeque& aQueue, int aIndex)
00435 : mIndex(aIndex),
00436   mDeque(aQueue)
00437 {
00438 }
00439 
00445 nsDequeIterator::nsDequeIterator(const nsDequeIterator& aCopy)
00446 : mIndex(aCopy.mIndex),
00447   mDeque(aCopy.mDeque)
00448 {
00449 }
00450 
00455 nsDequeIterator& nsDequeIterator::First(){
00456   mIndex=0;
00457   return *this;
00458 }
00459 
00466 nsDequeIterator& nsDequeIterator::operator=(const nsDequeIterator& aCopy) {
00467   NS_ASSERTION(&mDeque==&aCopy.mDeque,"you can't change the deque that an interator is iterating over, sorry.");
00468   mIndex=aCopy.mIndex;
00469   return *this;
00470 }
00471 
00479 PRBool nsDequeIterator::operator!=(nsDequeIterator& aIter) {
00480   return PRBool(!this->operator==(aIter));
00481 }
00482 
00491 PRBool nsDequeIterator::operator<(nsDequeIterator& aIter) {
00492   return PRBool(((mIndex<aIter.mIndex) && (&mDeque==&aIter.mDeque)));
00493 }
00494 
00501 PRBool nsDequeIterator::operator==(nsDequeIterator& aIter) {
00502   return PRBool(((mIndex==aIter.mIndex) && (&mDeque==&aIter.mDeque)));
00503 }
00504 
00513 PRBool nsDequeIterator::operator>=(nsDequeIterator& aIter) {
00514   return PRBool(((mIndex>=aIter.mIndex) && (&mDeque==&aIter.mDeque)));
00515 }
00516 
00522 void* nsDequeIterator::operator++() {
00523   NS_ASSERTION(mIndex<mDeque.mSize,
00524     "You have reached the end of the Internet."\
00525     "You have seen everything there is to see. Please go back. Now."
00526   );
00527 #ifndef TIMELESS_LIGHTWEIGHT
00528   if (mIndex>=mDeque.mSize) return 0;
00529 #endif
00530   return mDeque.ObjectAt(++mIndex);
00531 }
00532 
00539 void* nsDequeIterator::operator++(int) {
00540   NS_ASSERTION(mIndex<=mDeque.mSize,
00541     "You have already reached the end of the Internet."\
00542     "You have seen everything there is to see. Please go back. Now."
00543   );
00544 #ifndef TIMELESS_LIGHTWEIGHT
00545   if (mIndex>mDeque.mSize) return 0;
00546 #endif
00547   return mDeque.ObjectAt(mIndex++);
00548 }
00549 
00555 void* nsDequeIterator::operator--() {
00556   NS_ASSERTION(mIndex>=0,
00557     "You have reached the beginning of the Internet."\
00558     "You have seen everything there is to see. Please go forward. Now."
00559   );
00560 #ifndef TIMELESS_LIGHTWEIGHT
00561   if (mIndex<0) return 0;
00562 #endif
00563   return mDeque.ObjectAt(--mIndex);
00564 }
00565 
00572 void* nsDequeIterator::operator--(int) {
00573   NS_ASSERTION(mIndex>=0,
00574     "You have already reached the beginning of the Internet."\
00575     "You have seen everything there is to see. Please go forward. Now."
00576   );
00577 #ifndef TIMELESS_LIGHTWEIGHT
00578   if (mIndex<0) return 0;
00579 #endif
00580   return mDeque.ObjectAt(mIndex--);
00581 }
00582 
00596 void* nsDequeIterator::GetCurrent() {
00597   NS_ASSERTION(mIndex<mDeque.mSize&&mIndex>=0,"Current is out of bounds");
00598 #ifndef TIMELESS_LIGHTWEIGHT
00599   if (mIndex>=mDeque.mSize||mIndex<0) return 0;
00600 #endif
00601   return mDeque.ObjectAt(mIndex);
00602 }
00603 
00612 void nsDequeIterator::ForEach(nsDequeFunctor& aFunctor) const{
00613   mDeque.ForEach(aFunctor);
00614 }
00615 
00625 const void* nsDequeIterator::FirstThat(nsDequeFunctor& aFunctor) const{
00626   return mDeque.FirstThat(aFunctor);
00627 }