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