The Tor Browser / file comparison

comparison: xpcom/glue/nsVoidArray.cpp

xpcom/glue/nsVoidArray.cpp

branch
TOR_BUG_9701
changeset 8
97036ab72558
equal deleted inserted replaced
-1:000000000000 0:e3c11d387719
1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0)) -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5
6 #include "mozilla/MathAlgorithms.h"
7 #include "mozilla/MemoryReporting.h"
8 #include <stdlib.h>
9
10 #include "nsVoidArray.h"
11 #include "nsQuickSort.h"
12 #include "nsISupportsImpl.h" // for nsTraceRefcnt
13 #include "nsAlgorithm.h"
14
15 /**
16 * Grow the array by at least this many elements at a time.
17 */
18 static const int32_t kMinGrowArrayBy = 8;
19 static const int32_t kMaxGrowArrayBy = 1024;
20
21 /**
22 * This is the threshold (in bytes) of the mImpl struct, past which
23 * we'll force the array to grow geometrically
24 */
25 static const int32_t kLinearThreshold = 24 * sizeof(void *);
26
27 /**
28 * Compute the number of bytes requires for the mImpl struct that will
29 * hold |n| elements.
30 */
31 #define SIZEOF_IMPL(n_) (sizeof(Impl) + sizeof(void *) * ((n_) - 1))
32
33 /**
34 * Compute the number of elements that an mImpl struct of |n| bytes
35 * will hold.
36 */
37 #define CAPACITYOF_IMPL(n_) ((((n_) - sizeof(Impl)) / sizeof(void *)) + 1)
38
39 #if DEBUG_VOIDARRAY
40 #define MAXVOID 10
41
42 class VoidStats {
43 public:
44 VoidStats();
45 ~VoidStats();
46
47 };
48
49 static int sizesUsed; // number of the elements of the arrays used
50 static int sizesAlloced[MAXVOID]; // sizes of the allocations. sorted
51 static int NumberOfSize[MAXVOID]; // number of this allocation size (1 per array)
52 static int AllocedOfSize[MAXVOID]; // number of this allocation size (each size for array used)
53 static int MaxAuto[MAXVOID]; // AutoArrays that maxed out at this size
54 static int GrowInPlace[MAXVOID]; // arrays this size that grew in-place via realloc
55
56 // these are per-allocation
57 static int MaxElements[2000]; // # of arrays that maxed out at each size.
58
59 // statistics macros
60 #define ADD_TO_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
61 { \
62 if (sizesAlloced[i] == (int)(size)) \
63 { ((x)[i])++; break; } \
64 } \
65 if (i >= sizesUsed && sizesUsed < MAXVOID) \
66 { sizesAlloced[sizesUsed] = (size); \
67 ((x)[sizesUsed++])++; break; \
68 } \
69 } while (0)
70
71 #define SUB_FROM_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
72 { \
73 if (sizesAlloced[i] == (int)(size)) \
74 { ((x)[i])--; break; } \
75 } \
76 } while (0)
77
78
79 VoidStats::VoidStats()
80 {
81 sizesUsed = 1;
82 sizesAlloced[0] = 0;
83 }
84
85 VoidStats::~VoidStats()
86 {
87 int i;
88 for (i = 0; i < sizesUsed; i++)
89 {
90 printf("Size %d:\n",sizesAlloced[i]);
91 printf("\tNumber of VoidArrays this size (max): %d\n",NumberOfSize[i]-MaxAuto[i]);
92 printf("\tNumber of AutoVoidArrays this size (max): %d\n",MaxAuto[i]);
93 printf("\tNumber of allocations this size (total): %d\n",AllocedOfSize[i]);
94 printf("\tNumber of GrowsInPlace this size (total): %d\n",GrowInPlace[i]);
95 }
96 printf("Max Size of VoidArray:\n");
97 for (i = 0; i < (int)(sizeof(MaxElements)/sizeof(MaxElements[0])); i++)
98 {
99 if (MaxElements[i])
100 printf("\t%d: %d\n",i,MaxElements[i]);
101 }
102 }
103
104 // Just so constructor/destructor's get called
105 VoidStats gVoidStats;
106 #endif
107
108 void
109 nsVoidArray::SetArray(Impl *newImpl, int32_t aSize, int32_t aCount)
110 {
111 // old mImpl has been realloced and so we don't free/delete it
112 NS_PRECONDITION(newImpl, "can't set size");
113 mImpl = newImpl;
114 mImpl->mCount = aCount;
115 mImpl->mSize = aSize;
116 }
117
118 // This does all allocation/reallocation of the array.
119 // It also will compact down to N - good for things that might grow a lot
120 // at times, but usually are smaller, like JS deferred GC releases.
121 bool nsVoidArray::SizeTo(int32_t aSize)
122 {
123 uint32_t oldsize = GetArraySize();
124
125 if (aSize == (int32_t) oldsize)
126 return true; // no change
127
128 if (aSize <= 0)
129 {
130 // free the array if allocated
131 if (mImpl)
132 {
133 free(reinterpret_cast<char *>(mImpl));
134 mImpl = nullptr;
135 }
136 return true;
137 }
138
139 if (mImpl)
140 {
141 // We currently own an array impl. Resize it appropriately.
142 if (aSize < mImpl->mCount)
143 {
144 // XXX Note: we could also just resize to mCount
145 return true; // can't make it that small, ignore request
146 }
147
148 char* bytes = (char *) realloc(mImpl,SIZEOF_IMPL(aSize));
149 Impl* newImpl = reinterpret_cast<Impl*>(bytes);
150 if (!newImpl)
151 return false;
152
153 #if DEBUG_VOIDARRAY
154 if (mImpl == newImpl)
155 ADD_TO_STATS(GrowInPlace,oldsize);
156 ADD_TO_STATS(AllocedOfSize,SIZEOF_IMPL(aSize));
157 if (aSize > mMaxSize)
158 {
159 ADD_TO_STATS(NumberOfSize,SIZEOF_IMPL(aSize));
160 if (oldsize)
161 SUB_FROM_STATS(NumberOfSize,oldsize);
162 mMaxSize = aSize;
163 if (mIsAuto)
164 {
165 ADD_TO_STATS(MaxAuto,SIZEOF_IMPL(aSize));
166 SUB_FROM_STATS(MaxAuto,oldsize);
167 }
168 }
169 #endif
170 SetArray(newImpl, aSize, newImpl->mCount);
171 return true;
172 }
173
174 if ((uint32_t) aSize < oldsize) {
175 // No point in allocating if it won't free the current Impl anyway.
176 return true;
177 }
178
179 // just allocate an array
180 // allocate the exact size requested
181 char* bytes = (char *) malloc(SIZEOF_IMPL(aSize));
182 Impl* newImpl = reinterpret_cast<Impl*>(bytes);
183 if (!newImpl)
184 return false;
185
186 #if DEBUG_VOIDARRAY
187 ADD_TO_STATS(AllocedOfSize,SIZEOF_IMPL(aSize));
188 if (aSize > mMaxSize)
189 {
190 ADD_TO_STATS(NumberOfSize,SIZEOF_IMPL(aSize));
191 if (oldsize && !mImpl)
192 SUB_FROM_STATS(NumberOfSize,oldsize);
193 mMaxSize = aSize;
194 }
195 #endif
196 if (mImpl)
197 {
198 #if DEBUG_VOIDARRAY
199 ADD_TO_STATS(MaxAuto,SIZEOF_IMPL(aSize));
200 SUB_FROM_STATS(MaxAuto,0);
201 SUB_FROM_STATS(NumberOfSize,0);
202 mIsAuto = true;
203 #endif
204 // We must be growing an nsAutoVoidArray - copy since we didn't
205 // realloc.
206 memcpy(newImpl->mArray, mImpl->mArray,
207 mImpl->mCount * sizeof(mImpl->mArray[0]));
208 }
209
210 SetArray(newImpl, aSize, mImpl ? mImpl->mCount : 0);
211 // no memset; handled later in ReplaceElementAt if needed
212 return true;
213 }
214
215 bool nsVoidArray::GrowArrayBy(int32_t aGrowBy)
216 {
217 // We have to grow the array. Grow by kMinGrowArrayBy slots if we're
218 // smaller than kLinearThreshold bytes, or a power of two if we're
219 // larger. This is much more efficient with most memory allocators,
220 // especially if it's very large, or of the allocator is binned.
221 if (aGrowBy < kMinGrowArrayBy)
222 aGrowBy = kMinGrowArrayBy;
223
224 uint32_t newCapacity = GetArraySize() + aGrowBy; // Minimum increase
225 uint32_t newSize = SIZEOF_IMPL(newCapacity);
226
227 if (newSize >= (uint32_t) kLinearThreshold)
228 {
229 // newCount includes enough space for at least kMinGrowArrayBy new
230 // slots. Select the next power-of-two size in bytes above or
231 // equal to that.
232 // Also, limit the increase in size to about a VM page or two.
233 if (GetArraySize() >= kMaxGrowArrayBy)
234 {
235 newCapacity = GetArraySize() + XPCOM_MAX(kMaxGrowArrayBy,aGrowBy);
236 newSize = SIZEOF_IMPL(newCapacity);
237 }
238 else
239 {
240 newSize = mozilla::CeilingLog2(newSize);
241 newCapacity = CAPACITYOF_IMPL(1u << newSize);
242 }
243 }
244 // frees old mImpl IF this succeeds
245 if (!SizeTo(newCapacity))
246 return false;
247
248 return true;
249 }
250
251 nsVoidArray::nsVoidArray()
252 : mImpl(nullptr)
253 {
254 MOZ_COUNT_CTOR(nsVoidArray);
255 #if DEBUG_VOIDARRAY
256 mMaxCount = 0;
257 mMaxSize = 0;
258 mIsAuto = false;
259 ADD_TO_STATS(NumberOfSize,0);
260 MaxElements[0]++;
261 #endif
262 }
263
264 nsVoidArray::nsVoidArray(int32_t aCount)
265 : mImpl(nullptr)
266 {
267 MOZ_COUNT_CTOR(nsVoidArray);
268 #if DEBUG_VOIDARRAY
269 mMaxCount = 0;
270 mMaxSize = 0;
271 mIsAuto = false;
272 MaxElements[0]++;
273 #endif
274 SizeTo(aCount);
275 }
276
277 nsVoidArray& nsVoidArray::operator=(const nsVoidArray& other)
278 {
279 int32_t otherCount = other.Count();
280 int32_t maxCount = GetArraySize();
281 if (otherCount)
282 {
283 if (otherCount > maxCount)
284 {
285 // frees old mImpl IF this succeeds
286 if (!GrowArrayBy(otherCount-maxCount))
287 return *this; // XXX The allocation failed - don't do anything
288
289 memcpy(mImpl->mArray, other.mImpl->mArray, otherCount * sizeof(mImpl->mArray[0]));
290 mImpl->mCount = otherCount;
291 }
292 else
293 {
294 // the old array can hold the new array
295 memcpy(mImpl->mArray, other.mImpl->mArray, otherCount * sizeof(mImpl->mArray[0]));
296 mImpl->mCount = otherCount;
297 // if it shrank a lot, compact it anyways
298 if ((otherCount*2) < maxCount && maxCount > 100)
299 {
300 Compact(); // shrank by at least 50 entries
301 }
302 }
303 #if DEBUG_VOIDARRAY
304 if (mImpl->mCount > mMaxCount &&
305 mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
306 {
307 MaxElements[mImpl->mCount]++;
308 MaxElements[mMaxCount]--;
309 mMaxCount = mImpl->mCount;
310 }
311 #endif
312 }
313 else
314 {
315 // Why do we drop the buffer here when we don't in Clear()?
316 SizeTo(0);
317 }
318
319 return *this;
320 }
321
322 nsVoidArray::~nsVoidArray()
323 {
324 MOZ_COUNT_DTOR(nsVoidArray);
325 if (mImpl)
326 free(reinterpret_cast<char*>(mImpl));
327 }
328
329 bool nsVoidArray::SetCount(int32_t aNewCount)
330 {
331 NS_ASSERTION(aNewCount >= 0,"SetCount(negative index)");
332 if (aNewCount < 0)
333 return false;
334
335 if (aNewCount == 0)
336 {
337 Clear();
338 return true;
339 }
340
341 if (uint32_t(aNewCount) > uint32_t(GetArraySize()))
342 {
343 int32_t oldCount = Count();
344 int32_t growDelta = aNewCount - oldCount;
345
346 // frees old mImpl IF this succeeds
347 if (!GrowArrayBy(growDelta))
348 return false;
349 }
350
351 if (aNewCount > mImpl->mCount)
352 {
353 // Make sure that new entries added to the array by this
354 // SetCount are cleared to 0. Some users of this assume that.
355 // This code means we don't have to memset when we allocate an array.
356 memset(&mImpl->mArray[mImpl->mCount], 0,
357 (aNewCount - mImpl->mCount) * sizeof(mImpl->mArray[0]));
358 }
359
360 mImpl->mCount = aNewCount;
361
362 #if DEBUG_VOIDARRAY
363 if (mImpl->mCount > mMaxCount &&
364 mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
365 {
366 MaxElements[mImpl->mCount]++;
367 MaxElements[mMaxCount]--;
368 mMaxCount = mImpl->mCount;
369 }
370 #endif
371
372 return true;
373 }
374
375 int32_t nsVoidArray::IndexOf(void* aPossibleElement) const
376 {
377 if (mImpl)
378 {
379 void** ap = mImpl->mArray;
380 void** end = ap + mImpl->mCount;
381 while (ap < end)
382 {
383 if (*ap == aPossibleElement)
384 {
385 return ap - mImpl->mArray;
386 }
387 ap++;
388 }
389 }
390 return -1;
391 }
392
393 bool nsVoidArray::InsertElementAt(void* aElement, int32_t aIndex)
394 {
395 int32_t oldCount = Count();
396 NS_ASSERTION(aIndex >= 0,"InsertElementAt(negative index)");
397 if (uint32_t(aIndex) > uint32_t(oldCount))
398 {
399 // An invalid index causes the insertion to fail
400 // Invalid indexes are ones that add more than one entry to the
401 // array (i.e., they can append).
402 return false;
403 }
404
405 if (oldCount >= GetArraySize())
406 {
407 if (!GrowArrayBy(1))
408 return false;
409 }
410 // else the array is already large enough
411
412 int32_t slide = oldCount - aIndex;
413 if (0 != slide)
414 {
415 // Slide data over to make room for the insertion
416 memmove(mImpl->mArray + aIndex + 1, mImpl->mArray + aIndex,
417 slide * sizeof(mImpl->mArray[0]));
418 }
419
420 mImpl->mArray[aIndex] = aElement;
421 mImpl->mCount++;
422
423 #if DEBUG_VOIDARRAY
424 if (mImpl->mCount > mMaxCount &&
425 mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
426 {
427 MaxElements[mImpl->mCount]++;
428 MaxElements[mMaxCount]--;
429 mMaxCount = mImpl->mCount;
430 }
431 #endif
432
433 return true;
434 }
435
436 bool nsVoidArray::InsertElementsAt(const nsVoidArray& other, int32_t aIndex)
437 {
438 int32_t oldCount = Count();
439 int32_t otherCount = other.Count();
440
441 NS_ASSERTION(aIndex >= 0,"InsertElementsAt(negative index)");
442 if (uint32_t(aIndex) > uint32_t(oldCount))
443 {
444 // An invalid index causes the insertion to fail
445 // Invalid indexes are ones that are more than one entry past the end of
446 // the array (i.e., they can append).
447 return false;
448 }
449
450 if (oldCount + otherCount > GetArraySize())
451 {
452 if (!GrowArrayBy(otherCount))
453 return false;;
454 }
455 // else the array is already large enough
456
457 int32_t slide = oldCount - aIndex;
458 if (0 != slide)
459 {
460 // Slide data over to make room for the insertion
461 memmove(mImpl->mArray + aIndex + otherCount, mImpl->mArray + aIndex,
462 slide * sizeof(mImpl->mArray[0]));
463 }
464
465 for (int32_t i = 0; i < otherCount; i++)
466 {
467 // copy all the elements (destroys aIndex)
468 mImpl->mArray[aIndex++] = other.mImpl->mArray[i];
469 mImpl->mCount++;
470 }
471
472 #if DEBUG_VOIDARRAY
473 if (mImpl->mCount > mMaxCount &&
474 mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
475 {
476 MaxElements[mImpl->mCount]++;
477 MaxElements[mMaxCount]--;
478 mMaxCount = mImpl->mCount;
479 }
480 #endif
481
482 return true;
483 }
484
485 bool nsVoidArray::ReplaceElementAt(void* aElement, int32_t aIndex)
486 {
487 NS_ASSERTION(aIndex >= 0,"ReplaceElementAt(negative index)");
488 if (aIndex < 0)
489 return false;
490
491 // Unlike InsertElementAt, ReplaceElementAt can implicitly add more
492 // than just the one element to the array.
493 if (uint32_t(aIndex) >= uint32_t(GetArraySize()))
494 {
495 int32_t oldCount = Count();
496 int32_t requestedCount = aIndex + 1;
497 int32_t growDelta = requestedCount - oldCount;
498
499 // frees old mImpl IF this succeeds
500 if (!GrowArrayBy(growDelta))
501 return false;
502 }
503
504 mImpl->mArray[aIndex] = aElement;
505 if (aIndex >= mImpl->mCount)
506 {
507 // Make sure that any entries implicitly added to the array by this
508 // ReplaceElementAt are cleared to 0. Some users of this assume that.
509 // This code means we don't have to memset when we allocate an array.
510 if (aIndex > mImpl->mCount) // note: not >=
511 {
512 // For example, if mCount is 2, and we do a ReplaceElementAt for
513 // element[5], then we need to set three entries ([2], [3], and [4])
514 // to 0.
515 memset(&mImpl->mArray[mImpl->mCount], 0,
516 (aIndex - mImpl->mCount) * sizeof(mImpl->mArray[0]));
517 }
518
519 mImpl->mCount = aIndex + 1;
520
521 #if DEBUG_VOIDARRAY
522 if (mImpl->mCount > mMaxCount &&
523 mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
524 {
525 MaxElements[mImpl->mCount]++;
526 MaxElements[mMaxCount]--;
527 mMaxCount = mImpl->mCount;
528 }
529 #endif
530 }
531
532 return true;
533 }
534
535 // useful for doing LRU arrays
536 bool nsVoidArray::MoveElement(int32_t aFrom, int32_t aTo)
537 {
538 void *tempElement;
539
540 if (aTo == aFrom)
541 return true;
542
543 NS_ASSERTION(aTo >= 0 && aFrom >= 0,"MoveElement(negative index)");
544 if (aTo >= Count() || aFrom >= Count())
545 {
546 // can't extend the array when moving an element. Also catches mImpl = null
547 return false;
548 }
549 tempElement = mImpl->mArray[aFrom];
550
551 if (aTo < aFrom)
552 {
553 // Moving one element closer to the head; the elements inbetween move down
554 memmove(mImpl->mArray + aTo + 1, mImpl->mArray + aTo,
555 (aFrom-aTo) * sizeof(mImpl->mArray[0]));
556 mImpl->mArray[aTo] = tempElement;
557 }
558 else // already handled aFrom == aTo
559 {
560 // Moving one element closer to the tail; the elements inbetween move up
561 memmove(mImpl->mArray + aFrom, mImpl->mArray + aFrom + 1,
562 (aTo-aFrom) * sizeof(mImpl->mArray[0]));
563 mImpl->mArray[aTo] = tempElement;
564 }
565
566 return true;
567 }
568
569 void nsVoidArray::RemoveElementsAt(int32_t aIndex, int32_t aCount)
570 {
571 int32_t oldCount = Count();
572 NS_ASSERTION(aIndex >= 0,"RemoveElementsAt(negative index)");
573 if (uint32_t(aIndex) >= uint32_t(oldCount))
574 {
575 return;
576 }
577 // Limit to available entries starting at aIndex
578 if (aCount + aIndex > oldCount)
579 aCount = oldCount - aIndex;
580
581 // We don't need to move any elements if we're removing the
582 // last element in the array
583 if (aIndex < (oldCount - aCount))
584 {
585 memmove(mImpl->mArray + aIndex, mImpl->mArray + aIndex + aCount,
586 (oldCount - (aIndex + aCount)) * sizeof(mImpl->mArray[0]));
587 }
588
589 mImpl->mCount -= aCount;
590 return;
591 }
592
593 bool nsVoidArray::RemoveElement(void* aElement)
594 {
595 int32_t theIndex = IndexOf(aElement);
596 if (theIndex != -1)
597 {
598 RemoveElementAt(theIndex);
599 return true;
600 }
601
602 return false;
603 }
604
605 void nsVoidArray::Clear()
606 {
607 if (mImpl)
608 {
609 mImpl->mCount = 0;
610 }
611 }
612
613 void nsVoidArray::Compact()
614 {
615 if (mImpl)
616 {
617 // XXX NOTE: this is quite inefficient in many cases if we're only
618 // compacting by a little, but some callers care more about memory use.
619 int32_t count = Count();
620 if (GetArraySize() > count)
621 {
622 SizeTo(Count());
623 }
624 }
625 }
626
627 // Needed because we want to pass the pointer to the item in the array
628 // to the comparator function, not a pointer to the pointer in the array.
629 struct VoidArrayComparatorContext {
630 nsVoidArrayComparatorFunc mComparatorFunc;
631 void* mData;
632 };
633
634 static int
635 VoidArrayComparator(const void* aElement1, const void* aElement2, void* aData)
636 {
637 VoidArrayComparatorContext* ctx = static_cast<VoidArrayComparatorContext*>(aData);
638 return (*ctx->mComparatorFunc)(*static_cast<void* const*>(aElement1),
639 *static_cast<void* const*>(aElement2),
640 ctx->mData);
641 }
642
643 void nsVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
644 {
645 if (mImpl && mImpl->mCount > 1)
646 {
647 VoidArrayComparatorContext ctx = {aFunc, aData};
648 NS_QuickSort(mImpl->mArray, mImpl->mCount, sizeof(mImpl->mArray[0]),
649 VoidArrayComparator, &ctx);
650 }
651 }
652
653 bool nsVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
654 {
655 int32_t index = -1;
656 bool running = true;
657
658 if (mImpl) {
659 while (running && (++index < mImpl->mCount)) {
660 running = (*aFunc)(mImpl->mArray[index], aData);
661 }
662 }
663 return running;
664 }
665
666 bool nsVoidArray::EnumerateForwards(nsVoidArrayEnumFuncConst aFunc,
667 void* aData) const
668 {
669 int32_t index = -1;
670 bool running = true;
671
672 if (mImpl) {
673 while (running && (++index < mImpl->mCount)) {
674 running = (*aFunc)(mImpl->mArray[index], aData);
675 }
676 }
677 return running;
678 }
679
680 bool nsVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
681 {
682 bool running = true;
683
684 if (mImpl)
685 {
686 int32_t index = Count();
687 while (running && (0 <= --index))
688 {
689 running = (*aFunc)(mImpl->mArray[index], aData);
690 }
691 }
692 return running;
693 }
694
695 struct SizeOfElementIncludingThisData
696 {
697 size_t mSize;
698 nsVoidArraySizeOfElementIncludingThisFunc mSizeOfElementIncludingThis;
699 mozilla::MallocSizeOf mMallocSizeOf;
700 void *mData; // the arg passed by the user
701 };
702
703 static bool
704 SizeOfElementIncludingThisEnumerator(const void *aElement, void *aData)
705 {
706 SizeOfElementIncludingThisData *d = (SizeOfElementIncludingThisData *)aData;
707 d->mSize += d->mSizeOfElementIncludingThis(aElement, d->mMallocSizeOf, d->mData);
708 return true;
709 }
710
711 size_t
712 nsVoidArray::SizeOfExcludingThis(
713 nsVoidArraySizeOfElementIncludingThisFunc aSizeOfElementIncludingThis,
714 mozilla::MallocSizeOf aMallocSizeOf, void* aData) const
715 {
716 size_t n = 0;
717 // Measure the element storage.
718 if (mImpl) {
719 n += aMallocSizeOf(mImpl);
720 }
721 // Measure things pointed to by the elements.
722 if (aSizeOfElementIncludingThis) {
723 SizeOfElementIncludingThisData data2 =
724 { 0, aSizeOfElementIncludingThis, aMallocSizeOf, aData };
725 EnumerateForwards(SizeOfElementIncludingThisEnumerator, &data2);
726 n += data2.mSize;
727 }
728 return n;
729 }
730
731 //----------------------------------------------------------------------
732 // NOTE: nsSmallVoidArray elements MUST all have the low bit as 0.
733 // This means that normally it's only used for pointers, and in particular
734 // structures or objects.
735 nsSmallVoidArray::~nsSmallVoidArray()
736 {
737 if (HasSingle())
738 {
739 // Have to null out mImpl before the nsVoidArray dtor runs.
740 mImpl = nullptr;
741 }
742 }
743
744 nsSmallVoidArray&
745 nsSmallVoidArray::operator=(nsSmallVoidArray& other)
746 {
747 int32_t count = other.Count();
748 switch (count) {
749 case 0:
750 Clear();
751 break;
752 case 1:
753 Clear();
754 AppendElement(other.ElementAt(0));
755 break;
756 default:
757 if (GetArraySize() >= count || SizeTo(count)) {
758 *AsArray() = *other.AsArray();
759 }
760 }
761
762 return *this;
763 }
764
765 int32_t
766 nsSmallVoidArray::GetArraySize() const
767 {
768 if (HasSingle()) {
769 return 1;
770 }
771
772 return AsArray()->GetArraySize();
773 }
774
775 int32_t
776 nsSmallVoidArray::Count() const
777 {
778 if (HasSingle()) {
779 return 1;
780 }
781
782 return AsArray()->Count();
783 }
784
785 void*
786 nsSmallVoidArray::FastElementAt(int32_t aIndex) const
787 {
788 NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsSmallVoidArray::FastElementAt: index out of range");
789
790 if (HasSingle()) {
791 return GetSingle();
792 }
793
794 return AsArray()->FastElementAt(aIndex);
795 }
796
797 int32_t
798 nsSmallVoidArray::IndexOf(void* aPossibleElement) const
799 {
800 if (HasSingle()) {
801 return aPossibleElement == GetSingle() ? 0 : -1;
802 }
803
804 return AsArray()->IndexOf(aPossibleElement);
805 }
806
807 bool
808 nsSmallVoidArray::InsertElementAt(void* aElement, int32_t aIndex)
809 {
810 NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
811 "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
812
813 if (aIndex == 0 && IsEmpty()) {
814 SetSingle(aElement);
815
816 return true;
817 }
818
819 if (!EnsureArray()) {
820 return false;
821 }
822
823 return AsArray()->InsertElementAt(aElement, aIndex);
824 }
825
826 bool nsSmallVoidArray::InsertElementsAt(const nsVoidArray &aOther, int32_t aIndex)
827 {
828 #ifdef DEBUG
829 for (int i = 0; i < aOther.Count(); i++) {
830 NS_ASSERTION(!(NS_PTR_TO_INT32(aOther.ElementAt(i)) & 0x1),
831 "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
832 }
833 #endif
834
835 if (aIndex == 0 && IsEmpty() && aOther.Count() == 1) {
836 SetSingle(aOther.FastElementAt(0));
837
838 return true;
839 }
840
841 if (!EnsureArray()) {
842 return false;
843 }
844
845 return AsArray()->InsertElementsAt(aOther, aIndex);
846 }
847
848 bool
849 nsSmallVoidArray::ReplaceElementAt(void* aElement, int32_t aIndex)
850 {
851 NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
852 "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
853
854 if (aIndex == 0 && (IsEmpty() || HasSingle())) {
855 SetSingle(aElement);
856
857 return true;
858 }
859
860 if (!EnsureArray()) {
861 return false;
862 }
863
864 return AsArray()->ReplaceElementAt(aElement, aIndex);
865 }
866
867 bool
868 nsSmallVoidArray::AppendElement(void* aElement)
869 {
870 NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
871 "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
872
873 if (IsEmpty()) {
874 SetSingle(aElement);
875
876 return true;
877 }
878
879 if (!EnsureArray()) {
880 return false;
881 }
882
883 return AsArray()->AppendElement(aElement);
884 }
885
886 bool
887 nsSmallVoidArray::RemoveElement(void* aElement)
888 {
889 if (HasSingle()) {
890 if (aElement == GetSingle()) {
891 mImpl = nullptr;
892 return true;
893 }
894
895 return false;
896 }
897
898 return AsArray()->RemoveElement(aElement);
899 }
900
901 void
902 nsSmallVoidArray::RemoveElementAt(int32_t aIndex)
903 {
904 if (HasSingle()) {
905 if (aIndex == 0) {
906 mImpl = nullptr;
907 }
908
909 return;
910 }
911
912 AsArray()->RemoveElementAt(aIndex);
913 }
914
915 void
916 nsSmallVoidArray::RemoveElementsAt(int32_t aIndex, int32_t aCount)
917 {
918 if (HasSingle()) {
919 if (aIndex == 0) {
920 if (aCount > 0) {
921 mImpl = nullptr;
922 }
923 }
924
925 return;
926 }
927
928 AsArray()->RemoveElementsAt(aIndex, aCount);
929 }
930
931 void
932 nsSmallVoidArray::Clear()
933 {
934 if (HasSingle()) {
935 mImpl = nullptr;
936 }
937 else {
938 AsArray()->Clear();
939 }
940 }
941
942 bool
943 nsSmallVoidArray::SizeTo(int32_t aMin)
944 {
945 if (!HasSingle()) {
946 return AsArray()->SizeTo(aMin);
947 }
948
949 if (aMin <= 0) {
950 mImpl = nullptr;
951
952 return true;
953 }
954
955 if (aMin == 1) {
956 return true;
957 }
958
959 void* single = GetSingle();
960 mImpl = nullptr;
961 if (!AsArray()->SizeTo(aMin)) {
962 SetSingle(single);
963
964 return false;
965 }
966
967 AsArray()->AppendElement(single);
968
969 return true;
970 }
971
972 void
973 nsSmallVoidArray::Compact()
974 {
975 if (!HasSingle()) {
976 AsArray()->Compact();
977 }
978 }
979
980 void
981 nsSmallVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
982 {
983 if (!HasSingle()) {
984 AsArray()->Sort(aFunc,aData);
985 }
986 }
987
988 bool
989 nsSmallVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
990 {
991 if (HasSingle()) {
992 return (*aFunc)(GetSingle(), aData);
993 }
994 return AsArray()->EnumerateForwards(aFunc,aData);
995 }
996
997 bool
998 nsSmallVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
999 {
1000 if (HasSingle()) {
1001 return (*aFunc)(GetSingle(), aData);
1002 }
1003 return AsArray()->EnumerateBackwards(aFunc,aData);
1004 }
1005
1006 bool
1007 nsSmallVoidArray::EnsureArray()
1008 {
1009 if (!HasSingle()) {
1010 return true;
1011 }
1012
1013 void* single = GetSingle();
1014 mImpl = nullptr;
1015 if (!AsArray()->AppendElement(single)) {
1016 SetSingle(single);
1017
1018 return false;
1019 }
1020
1021 return true;
1022 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial