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