xpcom/ds/nsDeque.cpp

   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 #include "nsDeque.h"
   8 #include "nsISupportsImpl.h"
   9 #include <string.h>
  10
  11 #include "mozilla/CheckedInt.h"
  12
  13 #define modulus(x, y) ((x) % (y))
  14
  15 namespace mozilla {
  16 namespace detail {
  17
  18 /**
  19  * Standard constructor
  20  * @param deallocator, called by Erase and ~nsDequeBase
  21  */
  22 nsDequeBase::nsDequeBase() {
  23   MOZ_COUNT_CTOR(nsDequeBase);
  24   mOrigin = mSize = 0;
  25   mData = mBuffer;  // don't allocate space until you must
  26   mCapacity = sizeof(mBuffer) / sizeof(mBuffer[0]);
  27   memset(mData, 0, mCapacity * sizeof(mBuffer[0]));
  28 }
  29
  30 /**
  31  * Destructor
  32  */
  33 nsDequeBase::~nsDequeBase() {
  34   MOZ_COUNT_DTOR(nsDequeBase);
  35
  36   if (mData && mData != mBuffer) {
  37     free(mData);
  38   }
  39   mData = nullptr;
  40 }
  41
  42 size_t nsDequeBase::SizeOfExcludingThis(
  43     mozilla::MallocSizeOf aMallocSizeOf) const {
  44   size_t size = 0;
  45   if (mData != mBuffer) {
  46     size += aMallocSizeOf(mData);
  47   }
  48
  49   return size;
  50 }
  51
  52 /**
  53  * Remove all items from container without destroying them.
  54  */
  55 void nsDequeBase::Empty() {
  56   if (mSize && mData) {
  57     memset(mData, 0, mCapacity * sizeof(*mData));
  58   }
  59   mSize = 0;
  60   mOrigin = 0;
  61 }
  62
  63 /**
  64  * This method quadruples the size of the deque
  65  * Elements in the deque are resequenced so that elements
  66  * in the deque are stored sequentially
  67  *
  68  * @return  whether growing succeeded
  69  */
  70 bool nsDequeBase::GrowCapacity() {
  71   mozilla::CheckedInt<size_t> newCapacity = mCapacity;
  72   newCapacity *= 4;
  73
  74   NS_ASSERTION(newCapacity.isValid(), "Overflow");
  75   if (!newCapacity.isValid()) {
  76     return false;
  77   }
  78
  79   // Sanity check the new byte size.
  80   mozilla::CheckedInt<size_t> newByteSize = newCapacity;
  81   newByteSize *= sizeof(void*);
  82
  83   NS_ASSERTION(newByteSize.isValid(), "Overflow");
  84   if (!newByteSize.isValid()) {
  85     return false;
  86   }
  87
  88   void** temp = (void**)malloc(newByteSize.value());
  89   if (!temp) {
  90     return false;
  91   }
  92
  93   // Here's the interesting part: You can't just move the elements
  94   // directly (in situ) from the old buffer to the new one.
  95   // Since capacity has changed, the old origin doesn't make
  96   // sense anymore. It's better to resequence the elements now.
  97
  98   memcpy(temp, mData + mOrigin, sizeof(void*) * (mCapacity - mOrigin));
  99   memcpy(temp + (mCapacity - mOrigin), mData, sizeof(void*) * mOrigin);
 100
 101   if (mData != mBuffer) {
 102     free(mData);
 103   }
 104
 105   mCapacity = newCapacity.value();
 106   mOrigin = 0;  // now realign the origin...
 107   mData = temp;
 108
 109   return true;
 110 }
 111
 112 /**
 113  * This method adds an item to the end of the deque.
 114  * This operation has the potential to cause the
 115  * underlying buffer to resize.
 116  *
 117  * @param   aItem: new item to be added to deque
 118  */
 119 bool nsDequeBase::Push(void* aItem, const fallible_t&) {
 120   if (mSize == mCapacity && !GrowCapacity()) {
 121     return false;
 122   }
 123   mData[modulus(mOrigin + mSize, mCapacity)] = aItem;
 124   mSize++;
 125   return true;
 126 }
 127
 128 /**
 129  * This method adds an item to the front of the deque.
 130  * This operation has the potential to cause the
 131  * underlying buffer to resize.
 132  *
 133  * --Commments for GrowCapacity() case
 134  * We've grown and shifted which means that the old
 135  * final element in the deque is now the first element
 136  * in the deque.  This is temporary.
 137  * We haven't inserted the new element at the front.
 138  *
 139  * To continue with the idea of having the front at zero
 140  * after a grow, we move the old final item (which through
 141  * the voodoo of mOrigin-- is now the first) to its final
 142  * position which is conveniently the old length.
 143  *
 144  * Note that this case only happens when the deque is full.
 145  * [And that pieces of this magic only work if the deque is full.]
 146  * picture:
 147  *   [ABCDEFGH] @[mOrigin:3]:D.
 148  * Task: PushFront("Z")
 149  * shift mOrigin so, @[mOrigin:2]:C
 150  * stretch and rearrange: (mOrigin:0)
 151  *   [CDEFGHAB ________ ________ ________]
 152  * copy: (The second C is currently out of bounds)
 153  *   [CDEFGHAB C_______ ________ ________]
 154  * later we will insert Z:
 155  *   [ZDEFGHAB C_______ ________ ________]
 156  * and increment size: 9. (C is no longer out of bounds)
 157  * --
 158  * @param   aItem: new item to be added to deque
 159  */
 160 bool nsDequeBase::PushFront(void* aItem, const fallible_t&) {
 161   if (mOrigin == 0) {
 162     mOrigin = mCapacity - 1;
 163   } else {
 164     mOrigin--;
 165   }
 166
 167   if (mSize == mCapacity) {
 168     if (!GrowCapacity()) {
 169       return false;
 170     }
 171     /* Comments explaining this are above*/
 172     mData[mSize] = mData[mOrigin];
 173   }
 174   mData[mOrigin] = aItem;
 175   mSize++;
 176   return true;
 177 }
 178
 179 /**
 180  * Remove and return the last item in the container.
 181  *
 182  * @return  ptr to last item in container
 183  */
 184 void* nsDequeBase::Pop() {
 185   void* result = nullptr;
 186   if (mSize > 0) {
 187     --mSize;
 188     size_t offset = modulus(mSize + mOrigin, mCapacity);
 189     result = mData[offset];
 190     mData[offset] = nullptr;
 191     if (!mSize) {
 192       mOrigin = 0;
 193     }
 194   }
 195   return result;
 196 }
 197
 198 /**
 199  * This method gets called you want to remove and return
 200  * the first member in the container.
 201  *
 202  * @return  last item in container
 203  */
 204 void* nsDequeBase::PopFront() {
 205   void* result = nullptr;
 206   if (mSize > 0) {
 207     NS_ASSERTION(mOrigin < mCapacity, "Error: Bad origin");
 208     result = mData[mOrigin];
 209     mData[mOrigin++] = nullptr;  // zero it out for debugging purposes.
 210     mSize--;
 211     // Cycle around if we pop off the end
 212     // and reset origin if when we pop the last element
 213     if (mCapacity == mOrigin || !mSize) {
 214       mOrigin = 0;
 215     }
 216   }
 217   return result;
 218 }
 219
 220 /**
 221  * This method gets called you want to peek at the bottom
 222  * member without removing it.
 223  *
 224  * @return  last item in container
 225  */
 226 void* nsDequeBase::Peek() const {
 227   void* result = nullptr;
 228   if (mSize > 0) {
 229     result = mData[modulus(mSize - 1 + mOrigin, mCapacity)];
 230   }
 231   return result;
 232 }
 233
 234 /**
 235  * This method gets called you want to peek at the topmost
 236  * member without removing it.
 237  *
 238  * @return  last item in container
 239  */
 240 void* nsDequeBase::PeekFront() const {
 241   void* result = nullptr;
 242   if (mSize > 0) {
 243     result = mData[mOrigin];
 244   }
 245   return result;
 246 }
 247
 248 /**
 249  * Call this to retrieve the ith element from this container.
 250  * Keep in mind that accessing the underlying elements is
 251  * done in a relative fashion. Object 0 is not necessarily
 252  * the first element (the first element is at mOrigin).
 253  *
 254  * @param   aIndex : 0 relative offset of item you want
 255  * @return  void* or null
 256  */
 257 void* nsDequeBase::ObjectAt(size_t aIndex) const {
 258   void* result = nullptr;
 259   if (aIndex < mSize) {
 260     result = mData[modulus(mOrigin + aIndex, mCapacity)];
 261   }
 262   return result;
 263 }
 264 }  // namespace detail
 265 }  // namespace mozilla