Line data Source code
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 : */
22 7 : nsDeque::nsDeque(nsDequeFunctor* aDeallocator)
23 : {
24 7 : MOZ_COUNT_CTOR(nsDeque);
25 7 : mDeallocator = aDeallocator;
26 7 : mOrigin = mSize = 0;
27 7 : mData = mBuffer; // don't allocate space until you must
28 7 : mCapacity = sizeof(mBuffer) / sizeof(mBuffer[0]);
29 7 : memset(mData, 0, mCapacity * sizeof(mBuffer[0]));
30 7 : }
31 :
32 : /**
33 : * Destructor
34 : */
35 6 : nsDeque::~nsDeque()
36 : {
37 3 : 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 3 : Erase();
62 3 : if (mData && mData != mBuffer) {
63 0 : free(mData);
64 : }
65 3 : mData = 0;
66 3 : SetDeallocator(0);
67 3 : }
68 :
69 : size_t
70 0 : nsDeque::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
71 : {
72 0 : size_t size = 0;
73 0 : if (mData != mBuffer) {
74 0 : size += aMallocSizeOf(mData);
75 : }
76 :
77 0 : if (mDeallocator) {
78 0 : size += aMallocSizeOf(mDeallocator);
79 : }
80 :
81 0 : return size;
82 : }
83 :
84 : size_t
85 0 : nsDeque::SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
86 : {
87 0 : 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
97 3 : nsDeque::SetDeallocator(nsDequeFunctor* aDeallocator)
98 : {
99 3 : delete mDeallocator;
100 3 : mDeallocator = aDeallocator;
101 3 : }
102 :
103 : /**
104 : * Remove all items from container without destroying them.
105 : */
106 : void
107 3 : nsDeque::Empty()
108 : {
109 3 : if (mSize && mData) {
110 0 : memset(mData, 0, mCapacity * sizeof(*mData));
111 : }
112 3 : mSize = 0;
113 3 : mOrigin = 0;
114 3 : }
115 :
116 : /**
117 : * Remove and delete all items from container
118 : */
119 : void
120 3 : nsDeque::Erase()
121 : {
122 3 : if (mDeallocator && mSize) {
123 0 : ForEach(*mDeallocator);
124 : }
125 3 : Empty();
126 3 : }
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
136 0 : nsDeque::GrowCapacity()
137 : {
138 0 : mozilla::CheckedInt<size_t> newCapacity = mCapacity;
139 0 : newCapacity *= 4;
140 :
141 0 : NS_ASSERTION(newCapacity.isValid(), "Overflow");
142 0 : if (!newCapacity.isValid()) {
143 0 : return false;
144 : }
145 :
146 : // Sanity check the new byte size.
147 0 : mozilla::CheckedInt<size_t> newByteSize = newCapacity;
148 0 : newByteSize *= sizeof(void*);
149 :
150 0 : NS_ASSERTION(newByteSize.isValid(), "Overflow");
151 0 : if (!newByteSize.isValid()) {
152 0 : return false;
153 : }
154 :
155 0 : void** temp = (void**)malloc(newByteSize.value());
156 0 : if (!temp) {
157 0 : 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 0 : memcpy(temp, mData + mOrigin, sizeof(void*) * (mCapacity - mOrigin));
166 0 : memcpy(temp + (mCapacity - mOrigin), mData, sizeof(void*) * mOrigin);
167 :
168 0 : if (mData != mBuffer) {
169 0 : free(mData);
170 : }
171 :
172 0 : mCapacity = newCapacity.value();
173 0 : mOrigin = 0; //now realign the origin...
174 0 : mData = temp;
175 :
176 0 : 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
187 3 : nsDeque::Push(void* aItem, const fallible_t&)
188 : {
189 3 : if (mSize == mCapacity && !GrowCapacity()) {
190 0 : return false;
191 : }
192 3 : mData[modulus(mOrigin + mSize, mCapacity)] = aItem;
193 3 : mSize++;
194 3 : 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
230 0 : nsDeque::PushFront(void* aItem, const fallible_t&)
231 : {
232 :
233 0 : if (mOrigin == 0) {
234 0 : mOrigin = mCapacity - 1;
235 : } else {
236 0 : mOrigin--;
237 : }
238 :
239 0 : if (mSize == mCapacity) {
240 0 : if (!GrowCapacity()) {
241 0 : return false;
242 : }
243 : /* Comments explaining this are above*/
244 0 : mData[mSize] = mData[mOrigin];
245 : }
246 0 : mData[mOrigin] = aItem;
247 0 : mSize++;
248 0 : 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*
257 3 : nsDeque::Pop()
258 : {
259 3 : void* result = 0;
260 3 : if (mSize > 0) {
261 3 : --mSize;
262 3 : size_t offset = modulus(mSize + mOrigin, mCapacity);
263 3 : result = mData[offset];
264 3 : mData[offset] = 0;
265 3 : if (!mSize) {
266 3 : mOrigin = 0;
267 : }
268 : }
269 3 : 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*
279 0 : nsDeque::PopFront()
280 : {
281 0 : void* result = 0;
282 0 : if (mSize > 0) {
283 0 : NS_ASSERTION(mOrigin < mCapacity, "Error: Bad origin");
284 0 : result = mData[mOrigin];
285 0 : mData[mOrigin++] = 0; //zero it out for debugging purposes.
286 0 : mSize--;
287 : // Cycle around if we pop off the end
288 : // and reset origin if when we pop the last element
289 0 : if (mCapacity == mOrigin || !mSize) {
290 0 : mOrigin = 0;
291 : }
292 : }
293 0 : 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*
303 1 : nsDeque::Peek() const
304 : {
305 1 : void* result = 0;
306 1 : if (mSize > 0) {
307 0 : result = mData[modulus(mSize - 1 + mOrigin, mCapacity)];
308 : }
309 1 : 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*
319 0 : nsDeque::PeekFront() const
320 : {
321 0 : void* result = 0;
322 0 : if (mSize > 0) {
323 0 : result = mData[mOrigin];
324 : }
325 0 : 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*
338 0 : nsDeque::ObjectAt(size_t aIndex) const
339 : {
340 0 : void* result = 0;
341 0 : if (aIndex < mSize) {
342 0 : result = mData[modulus(mOrigin + aIndex, mCapacity)];
343 : }
344 0 : 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
356 0 : nsDeque::ForEach(nsDequeFunctor& aFunctor) const
357 : {
358 0 : for (size_t i = 0; i < mSize; ++i) {
359 0 : aFunctor(ObjectAt(i));
360 : }
361 0 : }
|
