/src/mozilla-central/xpcom/ds/nsDeque.cpp

Source (jump to first uncovered line)
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "nsDeque.h"
#include "nsISupportsImpl.h"
#include <string.h>
#ifdef DEBUG_rickg
#include <stdio.h>
#endif

#include "mozilla/CheckedInt.h"

#define modulus(x,y) ((x)%(y))

/**
 * Standard constructor
 * @param deallocator, called by Erase and ~nsDeque
 */
nsDeque::nsDeque(nsDequeFunctor* aDeallocator)
{
  MOZ_COUNT_CTOR(nsDeque);
  mDeallocator = aDeallocator;
  mOrigin = mSize = 0;
  mData = mBuffer; // don't allocate space until you must
  mCapacity = sizeof(mBuffer) / sizeof(mBuffer[0]);
  memset(mData, 0, mCapacity * sizeof(mBuffer[0]));
}

/**
 * Destructor
 */
nsDeque::~nsDeque()
{
  MOZ_COUNT_DTOR(nsDeque);

#ifdef DEBUG_rickg
  char buffer[30];
  printf("Capacity: %i\n", mCapacity);

  static int mCaps[15] = {0};
  switch (mCapacity) {
    case 4:     mCaps[0]++; break;
    case 8:     mCaps[1]++; break;
    case 16:    mCaps[2]++; break;
    case 32:    mCaps[3]++; break;
    case 64:    mCaps[4]++; break;
    case 128:   mCaps[5]++; break;
    case 256:   mCaps[6]++; break;
    case 512:   mCaps[7]++; break;
    case 1024:  mCaps[8]++; break;
    case 2048:  mCaps[9]++; break;
    case 4096:  mCaps[10]++; break;
    default:
      break;
  }
#endif

  Erase();
  if (mData && mData != mBuffer) {
    free(mData);
  }
  mData = 0;
  SetDeallocator(0);
}

size_t
nsDeque::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
{
  size_t size = 0;
  if (mData != mBuffer) {
    size += aMallocSizeOf(mData);
  }

  if (mDeallocator) {
    size += aMallocSizeOf(mDeallocator);
  }

  return size;
}

size_t
nsDeque::SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
{
  return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf);
}

/**
 * Set the functor to be called by Erase()
 * The deque owns the functor.
 *
 * @param   aDeallocator functor object for use by Erase()
 */
void
nsDeque::SetDeallocator(nsDequeFunctor* aDeallocator)
{
  delete mDeallocator;
  mDeallocator = aDeallocator;
}

/**
 * Remove all items from container without destroying them.
 */
void
nsDeque::Empty()
{
  if (mSize && mData) {
    memset(mData, 0, mCapacity * sizeof(*mData));
  }
  mSize = 0;
  mOrigin = 0;
}

/**
 * Remove and delete all items from container
 */
void
nsDeque::Erase()
{
  if (mDeallocator && mSize) {
    ForEach(*mDeallocator);
  }
  Empty();
}

/**
 * This method quadruples the size of the deque
 * Elements in the deque are resequenced so that elements
 * in the deque are stored sequentially
 *
 * @return  whether growing succeeded
 */
bool
nsDeque::GrowCapacity()
{
  mozilla::CheckedInt<size_t> newCapacity = mCapacity;
  newCapacity *= 4;

  NS_ASSERTION(newCapacity.isValid(), "Overflow");
  if (!newCapacity.isValid()) {
    return false;
  }

  // Sanity check the new byte size.
  mozilla::CheckedInt<size_t> newByteSize = newCapacity;
  newByteSize *= sizeof(void*);

  NS_ASSERTION(newByteSize.isValid(), "Overflow");
  if (!newByteSize.isValid()) {
    return false;
  }

  void** temp = (void**)malloc(newByteSize.value());
  if (!temp) {
    return false;
  }

  //Here's the interesting part: You can't just move the elements
  //directly (in situ) from the old buffer to the new one.
  //Since capacity has changed, the old origin doesn't make
  //sense anymore. It's better to resequence the elements now.

  memcpy(temp, mData + mOrigin, sizeof(void*) * (mCapacity - mOrigin));
  memcpy(temp + (mCapacity - mOrigin), mData, sizeof(void*) * mOrigin);

  if (mData != mBuffer) {
    free(mData);
  }

  mCapacity = newCapacity.value();
  mOrigin = 0; //now realign the origin...
  mData = temp;

  return true;
}

/**
 * This method adds an item to the end of the deque.
 * This operation has the potential to cause the
 * underlying buffer to resize.
 *
 * @param   aItem: new item to be added to deque
 */
bool
nsDeque::Push(void* aItem, const fallible_t&)
{
  if (mSize == mCapacity && !GrowCapacity()) {
    return false;
  }
  mData[modulus(mOrigin + mSize, mCapacity)] = aItem;
  mSize++;
  return true;
}

/**
 * This method adds an item to the front of the deque.
 * This operation has the potential to cause the
 * underlying buffer to resize.
 *
 * --Commments for GrowCapacity() case
 * We've grown and shifted which means that the old
 * final element in the deque is now the first element
 * in the deque.  This is temporary.
 * We haven't inserted the new element at the front.
 *
 * To continue with the idea of having the front at zero
 * after a grow, we move the old final item (which through
 * the voodoo of mOrigin-- is now the first) to its final
 * position which is conveniently the old length.
 *
 * Note that this case only happens when the deque is full.
 * [And that pieces of this magic only work if the deque is full.]
 * picture:
 *   [ABCDEFGH] @[mOrigin:3]:D.
 * Task: PushFront("Z")
 * shift mOrigin so, @[mOrigin:2]:C
 * stretch and rearrange: (mOrigin:0)
 *   [CDEFGHAB ________ ________ ________]
 * copy: (The second C is currently out of bounds)
 *   [CDEFGHAB C_______ ________ ________]
 * later we will insert Z:
 *   [ZDEFGHAB C_______ ________ ________]
 * and increment size: 9. (C is no longer out of bounds)
 * --
 * @param   aItem: new item to be added to deque
 */
bool
nsDeque::PushFront(void* aItem, const fallible_t&)
{

  if (mOrigin == 0) {
    mOrigin = mCapacity - 1;
  } else {
    mOrigin--;
  }

  if (mSize == mCapacity) {
    if (!GrowCapacity()) {
      return false;
    }
    /* Comments explaining this are above*/
    mData[mSize] = mData[mOrigin];
  }
  mData[mOrigin] = aItem;
  mSize++;
  return true;
}

/**
 * Remove and return the last item in the container.
 *
 * @return  ptr to last item in container
 */
void*
nsDeque::Pop()
{
  void* result = 0;
  if (mSize > 0) {
    --mSize;
    size_t offset = modulus(mSize + mOrigin, mCapacity);
    result = mData[offset];
    mData[offset] = 0;
    if (!mSize) {
      mOrigin = 0;
    }
  }
  return result;
}

/**
 * This method gets called you want to remove and return
 * the first member in the container.
 *
 * @return  last item in container
 */
void*
nsDeque::PopFront()
{
  void* result = 0;
  if (mSize > 0) {
    NS_ASSERTION(mOrigin < mCapacity, "Error: Bad origin");
    result = mData[mOrigin];
    mData[mOrigin++] = 0;   //zero it out for debugging purposes.
    mSize--;
    // Cycle around if we pop off the end
    // and reset origin if when we pop the last element
    if (mCapacity == mOrigin || !mSize) {
      mOrigin = 0;
    }
  }
  return result;
}

/**
 * This method gets called you want to peek at the bottom
 * member without removing it.
 *
 * @return  last item in container
 */
void*
nsDeque::Peek() const
{
  void* result = 0;
  if (mSize > 0) {
    result = mData[modulus(mSize - 1 + mOrigin, mCapacity)];
  }
  return result;
}

/**
 * This method gets called you want to peek at the topmost
 * member without removing it.
 *
 * @return  last item in container
 */
void*
nsDeque::PeekFront() const
{
  void* result = 0;
  if (mSize > 0) {
    result = mData[mOrigin];
  }
  return result;
}

/**
 * Call this to retrieve the ith element from this container.
 * Keep in mind that accessing the underlying elements is
 * done in a relative fashion. Object 0 is not necessarily
 * the first element (the first element is at mOrigin).
 *
 * @param   aIndex : 0 relative offset of item you want
 * @return  void* or null
 */
void*
nsDeque::ObjectAt(size_t aIndex) const
{
  void* result = 0;
  if (aIndex < mSize) {
    result = mData[modulus(mOrigin + aIndex, mCapacity)];
  }
  return result;
}

/**
 * Call this method when you want to iterate all the
 * members of the container, passing a functor along
 * to call your code.
 *
 * @param   aFunctor object to call for each member
 * @return  *this
 */
void
nsDeque::ForEach(nsDequeFunctor& aFunctor) const
{
  for (size_t i = 0; i < mSize; ++i) {
    aFunctor(ObjectAt(i));
  }
}

Coverage Report

Created: 2018-09-25 14:53

Line	Count	Source (jump to first uncovered line)
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	0	#define modulus(x,y) ((x)%(y))
17
18		/**
19		* Standard constructor
20		* @param deallocator, called by Erase and ~nsDeque
21		*/
22		nsDeque::nsDeque(nsDequeFunctor* aDeallocator)
23	7	{
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		nsDeque::~nsDeque()
36	0	{
37	0	MOZ_COUNT_DTOR(nsDeque);
38	0
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	0	Erase();
62	0	if (mData && mData != mBuffer) {
63	0	free(mData);
64	0	}
65	0	mData = 0;
66	0	SetDeallocator(0);
67	0	}
68
69		size_t
70		nsDeque::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
71	0	{
72	0	size_t size = 0;
73	0	if (mData != mBuffer) {
74	0	size += aMallocSizeOf(mData);
75	0	}
76	0
77	0	if (mDeallocator) {
78	0	size += aMallocSizeOf(mDeallocator);
79	0	}
80	0
81	0	return size;
82	0	}
83
84		size_t
85		nsDeque::SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
86	0	{
87	0	return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf);
88	0	}
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		nsDeque::SetDeallocator(nsDequeFunctor* aDeallocator)
98	0	{
99	0	delete mDeallocator;
100	0	mDeallocator = aDeallocator;
101	0	}
102
103		/**
104		* Remove all items from container without destroying them.
105		*/
106		void
107		nsDeque::Empty()
108	0	{
109	0	if (mSize && mData) {
110	0	memset(mData, 0, mCapacity * sizeof(*mData));
111	0	}
112	0	mSize = 0;
113	0	mOrigin = 0;
114	0	}
115
116		/**
117		* Remove and delete all items from container
118		*/
119		void
120		nsDeque::Erase()
121	0	{
122	0	if (mDeallocator && mSize) {
123	0	ForEach(*mDeallocator);
124	0	}
125	0	Empty();
126	0	}
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		nsDeque::GrowCapacity()
137	0	{
138	0	mozilla::CheckedInt<size_t> newCapacity = mCapacity;
139	0	newCapacity *= 4;
140	0
141	0	NS_ASSERTION(newCapacity.isValid(), "Overflow");
142	0	if (!newCapacity.isValid()) {
143	0	return false;
144	0	}
145	0
146	0	// Sanity check the new byte size.
147	0	mozilla::CheckedInt<size_t> newByteSize = newCapacity;
148	0	newByteSize = sizeof(void);
149	0
150	0	NS_ASSERTION(newByteSize.isValid(), "Overflow");
151	0	if (!newByteSize.isValid()) {
152	0	return false;
153	0	}
154	0
155	0	void temp = (void)malloc(newByteSize.value());
156	0	if (!temp) {
157	0	return false;
158	0	}
159	0
160	0	//Here's the interesting part: You can't just move the elements
161	0	//directly (in situ) from the old buffer to the new one.
162	0	//Since capacity has changed, the old origin doesn't make
163	0	//sense anymore. It's better to resequence the elements now.
164	0
165	0	memcpy(temp, mData + mOrigin, sizeof(void) (mCapacity - mOrigin));
166	0	memcpy(temp + (mCapacity - mOrigin), mData, sizeof(void) mOrigin);
167	0
168	0	if (mData != mBuffer) {
169	0	free(mData);
170	0	}
171	0
172	0	mCapacity = newCapacity.value();
173	0	mOrigin = 0; //now realign the origin...
174	0	mData = temp;
175	0
176	0	return true;
177	0	}
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		nsDeque::Push(void* aItem, const fallible_t&)
188	0	{
189	0	if (mSize == mCapacity && !GrowCapacity()) {
190	0	return false;
191	0	}
192	0	mData[modulus(mOrigin + mSize, mCapacity)] = aItem;
193	0	mSize++;
194	0	return true;
195	0	}
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		nsDeque::PushFront(void* aItem, const fallible_t&)
231	0	{
232	0
233	0	if (mOrigin == 0) {
234	0	mOrigin = mCapacity - 1;
235	0	} else {
236	0	mOrigin--;
237	0	}
238	0
239	0	if (mSize == mCapacity) {
240	0	if (!GrowCapacity()) {
241	0	return false;
242	0	}
243	0	/* Comments explaining this are above*/
244	0	mData[mSize] = mData[mOrigin];
245	0	}
246	0	mData[mOrigin] = aItem;
247	0	mSize++;
248	0	return true;
249	0	}
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		nsDeque::Pop()
258	0	{
259	0	void* result = 0;
260	0	if (mSize > 0) {
261	0	--mSize;
262	0	size_t offset = modulus(mSize + mOrigin, mCapacity);
263	0	result = mData[offset];
264	0	mData[offset] = 0;
265	0	if (!mSize) {
266	0	mOrigin = 0;
267	0	}
268	0	}
269	0	return result;
270	0	}
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		nsDeque::PopFront()
280	0	{
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	0	// Cycle around if we pop off the end
288	0	// and reset origin if when we pop the last element
289	0	if (mCapacity == mOrigin \|\| !mSize) {
290	0	mOrigin = 0;
291	0	}
292	0	}
293	0	return result;
294	0	}
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		nsDeque::Peek() const
304	0	{
305	0	void* result = 0;
306	0	if (mSize > 0) {
307	0	result = mData[modulus(mSize - 1 + mOrigin, mCapacity)];
308	0	}
309	0	return result;
310	0	}
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		nsDeque::PeekFront() const
320	0	{
321	0	void* result = 0;
322	0	if (mSize > 0) {
323	0	result = mData[mOrigin];
324	0	}
325	0	return result;
326	0	}
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		nsDeque::ObjectAt(size_t aIndex) const
339	0	{
340	0	void* result = 0;
341	0	if (aIndex < mSize) {
342	0	result = mData[modulus(mOrigin + aIndex, mCapacity)];
343	0	}
344	0	return result;
345	0	}
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		nsDeque::ForEach(nsDequeFunctor& aFunctor) const
357	0	{
358	0	for (size_t i = 0; i < mSize; ++i) {
359	0	aFunctor(ObjectAt(i));
360	0	}
361	0	}