1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
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/. */
7 #include "mozilla/MathAlgorithms.h"
8 #include "nsSupportsArray.h"
9 #include "nsSupportsArrayEnumerator.h"
10 #include "nsIObjectInputStream.h"
11 #include "nsIObjectOutputStream.h"
13 #if DEBUG_SUPPORTSARRAY
14 #define MAXSUPPORTS 20
24 static int sizesUsed
; // number of the elements of the arrays used
25 static int sizesAlloced
[MAXSUPPORTS
]; // sizes of the allocations. sorted
26 static int NumberOfSize
[MAXSUPPORTS
]; // number of this allocation size (1 per array)
27 static int AllocedOfSize
[MAXSUPPORTS
]; // number of this allocation size (each size for array used)
28 static int GrowInPlace
[MAXSUPPORTS
];
30 // these are per-allocation
31 static int MaxElements
[3000];
34 #define ADD_TO_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
36 if (sizesAlloced[i] == (int)(size)) \
37 { ((x)[i])++; break; } \
39 if (i >= sizesUsed && sizesUsed < MAXSUPPORTS) \
40 { sizesAlloced[sizesUsed] = (size); \
41 ((x)[sizesUsed++])++; break; \
45 #define SUB_FROM_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
47 if (sizesAlloced[i] == (int)(size)) \
48 { ((x)[i])--; break; } \
53 SupportsStats::SupportsStats()
59 SupportsStats::~SupportsStats()
62 for (i
= 0; i
< sizesUsed
; ++i
) {
63 printf("Size %d:\n", sizesAlloced
[i
]);
64 printf("\tNumber of SupportsArrays this size (max): %d\n", NumberOfSize
[i
]);
65 printf("\tNumber of allocations this size (total): %d\n", AllocedOfSize
[i
]);
66 printf("\tNumber of GrowsInPlace this size (total): %d\n", GrowInPlace
[i
]);
68 printf("Max Size of SupportsArray:\n");
69 for (i
= 0; i
< (int)(sizeof(MaxElements
) / sizeof(MaxElements
[0])); ++i
) {
71 printf("\t%d: %d\n", i
, MaxElements
[i
]);
76 // Just so constructor/destructor get called
77 SupportsStats gSupportsStats
;
81 nsQueryElementAt::operator()(const nsIID
& aIID
, void** aResult
) const
84 mCollection
? mCollection
->QueryElementAt(mIndex
, aIID
, aResult
) :
85 NS_ERROR_NULL_POINTER
;
94 static const int32_t kGrowArrayBy
= 8;
95 static const int32_t kLinearThreshold
= 16 * sizeof(nsISupports
*);
97 nsSupportsArray::nsSupportsArray()
100 mArraySize
= kAutoArraySize
;
102 #if DEBUG_SUPPORTSARRAY
105 ADD_TO_STATS(NumberOfSize
, kAutoArraySize
* sizeof(mArray
[0]));
110 nsSupportsArray::~nsSupportsArray()
116 nsSupportsArray::GrowArrayBy(int32_t aGrowBy
)
118 // We have to grow the array. Grow by kGrowArrayBy slots if we're smaller
119 // than kLinearThreshold bytes, or a power of two if we're larger.
120 // This is much more efficient with most memory allocators, especially
121 // if it's very large, or of the allocator is binned.
122 if (aGrowBy
< kGrowArrayBy
) {
123 aGrowBy
= kGrowArrayBy
;
126 uint32_t newCount
= mArraySize
+ aGrowBy
; // Minimum increase
127 uint32_t newSize
= sizeof(mArray
[0]) * newCount
;
129 if (newSize
>= (uint32_t)kLinearThreshold
) {
130 // newCount includes enough space for at least kGrowArrayBy new slots.
131 // Select the next power-of-two size in bytes above that if newSize is
132 // not a power of two.
133 if (newSize
& (newSize
- 1)) {
134 newSize
= 1u << mozilla::CeilingLog2(newSize
);
137 newCount
= newSize
/ sizeof(mArray
[0]);
139 // XXX This would be far more efficient in many allocators if we used
140 // XXX PR_Realloc(), etc
141 nsISupports
** oldArray
= mArray
;
143 mArray
= new nsISupports
*[newCount
];
144 mArraySize
= newCount
;
146 #if DEBUG_SUPPORTSARRAY
147 if (oldArray
== mArray
) { // can't happen without use of realloc
148 ADD_TO_STATS(GrowInPlace
, mCount
);
150 ADD_TO_STATS(AllocedOfSize
, mArraySize
* sizeof(mArray
[0]));
151 if (mArraySize
> mMaxSize
) {
152 ADD_TO_STATS(NumberOfSize
, mArraySize
* sizeof(mArray
[0]));
153 if (oldArray
!= &(mAutoArray
[0])) {
154 SUB_FROM_STATS(NumberOfSize
, mCount
* sizeof(mArray
[0]));
156 mMaxSize
= mArraySize
;
159 if (oldArray
) { // need to move old data
161 ::memcpy(mArray
, oldArray
, mCount
* sizeof(nsISupports
*));
163 if (oldArray
!= &(mAutoArray
[0])) {
170 nsSupportsArray::Create(nsISupports
* aOuter
, REFNSIID aIID
, void** aResult
)
173 return NS_ERROR_NO_AGGREGATION
;
176 nsCOMPtr
<nsISupportsArray
> it
= new nsSupportsArray();
178 return it
->QueryInterface(aIID
, aResult
);
181 NS_IMPL_ISUPPORTS(nsSupportsArray
, nsISupportsArray
, nsICollection
,
185 nsSupportsArray::Read(nsIObjectInputStream
* aStream
)
189 uint32_t newArraySize
;
190 rv
= aStream
->Read32(&newArraySize
);
192 if (newArraySize
<= kAutoArraySize
) {
193 if (mArray
!= mAutoArray
) {
197 newArraySize
= kAutoArraySize
;
199 if (newArraySize
<= mArraySize
) {
200 // Keep non-default-size mArray, it's more than big enough.
201 newArraySize
= mArraySize
;
203 nsISupports
** array
= new nsISupports
*[newArraySize
];
204 if (mArray
!= mAutoArray
) {
210 mArraySize
= newArraySize
;
212 rv
= aStream
->Read32(&mCount
);
217 NS_ASSERTION(mCount
<= mArraySize
, "overlarge mCount!");
218 if (mCount
> mArraySize
) {
222 for (uint32_t i
= 0; i
< mCount
; i
++) {
223 rv
= aStream
->ReadObject(true, &mArray
[i
]);
233 nsSupportsArray::Write(nsIObjectOutputStream
* aStream
)
237 rv
= aStream
->Write32(mArraySize
);
242 rv
= aStream
->Write32(mCount
);
247 for (uint32_t i
= 0; i
< mCount
; i
++) {
248 rv
= aStream
->WriteObject(mArray
[i
], true);
258 nsSupportsArray::DeleteArray(void)
261 if (mArray
!= &(mAutoArray
[0])) {
264 mArraySize
= kAutoArraySize
;
270 nsSupportsArray::Equals(const nsISupportsArray
* aOther
)
274 nsISupportsArray
* other
= const_cast<nsISupportsArray
*>(aOther
);
275 nsresult rv
= other
->Count(&countOther
);
280 if (mCount
== countOther
) {
281 uint32_t index
= mCount
;
282 nsCOMPtr
<nsISupports
> otherElem
;
284 if (NS_FAILED(other
->GetElementAt(index
, getter_AddRefs(otherElem
)))) {
287 if (mArray
[index
] != otherElem
) {
298 nsSupportsArray::GetElementAt(uint32_t aIndex
, nsISupports
** aOutPtr
)
301 if (aIndex
< mCount
) {
302 NS_IF_ADDREF(*aOutPtr
= mArray
[aIndex
]);
307 NS_IMETHODIMP_(int32_t)
308 nsSupportsArray::IndexOf(const nsISupports
* aPossibleElement
)
310 return IndexOfStartingAt(aPossibleElement
, 0);
313 NS_IMETHODIMP_(int32_t)
314 nsSupportsArray::IndexOfStartingAt(const nsISupports
* aPossibleElement
,
315 uint32_t aStartIndex
)
317 if (aStartIndex
< mCount
) {
318 const nsISupports
** start
= (const nsISupports
**)mArray
; // work around goofy compiler behavior
319 const nsISupports
** ep
= (start
+ aStartIndex
);
320 const nsISupports
** end
= (start
+ mCount
);
322 if (aPossibleElement
== *ep
) {
331 NS_IMETHODIMP_(int32_t)
332 nsSupportsArray::LastIndexOf(const nsISupports
* aPossibleElement
)
335 const nsISupports
** start
= (const nsISupports
**)mArray
; // work around goofy compiler behavior
336 const nsISupports
** ep
= (start
+ mCount
);
337 while (start
<= --ep
) {
338 if (aPossibleElement
== *ep
) {
347 nsSupportsArray::InsertElementAt(nsISupports
* aElement
, uint32_t aIndex
)
349 if (aIndex
<= mCount
) {
350 if (mArraySize
< (mCount
+ 1)) {
351 // need to grow the array
355 // Could be slightly more efficient if GrowArrayBy knew about the
356 // split, but the difference is trivial.
357 uint32_t slide
= (mCount
- aIndex
);
359 ::memmove(mArray
+ aIndex
+ 1, mArray
+ aIndex
,
360 slide
* sizeof(nsISupports
*));
363 mArray
[aIndex
] = aElement
;
364 NS_IF_ADDREF(aElement
);
367 #if DEBUG_SUPPORTSARRAY
368 if (mCount
> mMaxCount
&&
369 mCount
< (int32_t)(sizeof(MaxElements
) / sizeof(MaxElements
[0]))) {
370 MaxElements
[mCount
]++;
371 MaxElements
[mMaxCount
]--;
381 nsSupportsArray::InsertElementsAt(nsISupportsArray
* aElements
, uint32_t aIndex
)
386 uint32_t countElements
;
387 if (NS_FAILED(aElements
->Count(&countElements
))) {
391 if (aIndex
<= mCount
) {
392 if (mArraySize
< (mCount
+ countElements
)) {
393 // need to grow the array
394 GrowArrayBy(countElements
);
397 // Could be slightly more efficient if GrowArrayBy knew about the
398 // split, but the difference is trivial.
399 uint32_t slide
= (mCount
- aIndex
);
401 ::memmove(mArray
+ aIndex
+ countElements
, mArray
+ aIndex
,
402 slide
* sizeof(nsISupports
*));
405 for (uint32_t i
= 0; i
< countElements
; ++i
, ++mCount
) {
406 // use GetElementAt to copy and do AddRef for us
407 if (NS_FAILED(aElements
->GetElementAt(i
, mArray
+ aIndex
+ i
))) {
412 #if DEBUG_SUPPORTSARRAY
413 if (mCount
> mMaxCount
&&
414 mCount
< (int32_t)(sizeof(MaxElements
) / sizeof(MaxElements
[0]))) {
415 MaxElements
[mCount
]++;
416 MaxElements
[mMaxCount
]--;
426 nsSupportsArray::ReplaceElementAt(nsISupports
* aElement
, uint32_t aIndex
)
428 if (aIndex
< mCount
) {
429 NS_IF_ADDREF(aElement
); // addref first in case it's the same object!
430 NS_IF_RELEASE(mArray
[aIndex
]);
431 mArray
[aIndex
] = aElement
;
438 nsSupportsArray::RemoveElementsAt(uint32_t aIndex
, uint32_t aCount
)
440 if (aIndex
+ aCount
<= mCount
) {
441 for (uint32_t i
= 0; i
< aCount
; i
++) {
442 NS_IF_RELEASE(mArray
[aIndex
+ i
]);
445 int32_t slide
= (mCount
- aIndex
);
447 ::memmove(mArray
+ aIndex
, mArray
+ aIndex
+ aCount
,
448 slide
* sizeof(nsISupports
*));
456 nsSupportsArray::RemoveElement(nsISupports
* aElement
)
458 int32_t theIndex
= IndexOfStartingAt(aElement
, 0);
460 return RemoveElementAt(theIndex
) ? NS_OK
: NS_ERROR_FAILURE
;
463 return NS_ERROR_FAILURE
;
467 nsSupportsArray::RemoveLastElement(const nsISupports
* aElement
)
469 int32_t theIndex
= LastIndexOf(aElement
);
471 return RemoveElementAt(theIndex
);
478 nsSupportsArray::MoveElement(int32_t aFrom
, int32_t aTo
)
480 nsISupports
* tempElement
;
486 if (aTo
< 0 || aFrom
< 0 ||
487 (uint32_t)aTo
>= mCount
|| (uint32_t)aFrom
>= mCount
) {
488 // can't extend the array when moving an element. Also catches mImpl = null
491 tempElement
= mArray
[aFrom
];
494 // Moving one element closer to the head; the elements inbetween move down
495 ::memmove(mArray
+ aTo
+ 1, mArray
+ aTo
,
496 (aFrom
- aTo
) * sizeof(mArray
[0]));
497 mArray
[aTo
] = tempElement
;
498 } else { // already handled aFrom == aTo
499 // Moving one element closer to the tail; the elements inbetween move up
500 ::memmove(mArray
+ aFrom
, mArray
+ aFrom
+ 1,
501 (aTo
- aFrom
) * sizeof(mArray
[0]));
502 mArray
[aTo
] = tempElement
;
509 nsSupportsArray::Clear(void)
514 NS_IF_RELEASE(mArray
[mCount
]);
515 } while (0 != mCount
);
521 nsSupportsArray::Compact(void)
523 #if DEBUG_SUPPORTSARRAY
524 uint32_t oldArraySize
= mArraySize
;
526 if ((mArraySize
!= mCount
) && (kAutoArraySize
< mArraySize
)) {
527 nsISupports
** oldArray
= mArray
;
528 if (mCount
<= kAutoArraySize
) {
530 mArraySize
= kAutoArraySize
;
532 mArray
= new nsISupports
*[mCount
];
539 #if DEBUG_SUPPORTSARRAY
540 if (oldArray
== mArray
&&
541 oldArray
!= &(mAutoArray
[0])) { // can't happen without use of realloc
542 ADD_TO_STATS(GrowInPlace
, oldArraySize
);
544 if (oldArray
!= &(mAutoArray
[0])) {
545 ADD_TO_STATS(AllocedOfSize
, mArraySize
* sizeof(mArray
[0]));
548 ::memcpy(mArray
, oldArray
, mCount
* sizeof(nsISupports
*));
555 nsSupportsArray::SizeTo(int32_t aSize
)
557 #if DEBUG_SUPPORTSARRAY
558 uint32_t oldArraySize
= mArraySize
;
560 NS_ASSERTION(aSize
>= 0, "negative aSize!");
562 // XXX for aSize < mCount we could resize to mCount
563 if (mArraySize
== (uint32_t)aSize
|| (uint32_t)aSize
< mCount
) {
564 return true; // nothing to do
567 // switch back to autoarray if possible
568 nsISupports
** oldArray
= mArray
;
569 if ((uint32_t)aSize
<= kAutoArraySize
) {
571 mArraySize
= kAutoArraySize
;
573 mArray
= new nsISupports
*[aSize
];
580 #if DEBUG_SUPPORTSARRAY
581 if (oldArray
== mArray
&&
582 oldArray
!= &(mAutoArray
[0])) { // can't happen without use of realloc
583 ADD_TO_STATS(GrowInPlace
, oldArraySize
);
585 if (oldArray
!= &(mAutoArray
[0])) {
586 ADD_TO_STATS(AllocedOfSize
, mArraySize
* sizeof(mArray
[0]));
589 ::memcpy(mArray
, oldArray
, mCount
* sizeof(nsISupports
*));
590 if (oldArray
!= mAutoArray
) {
598 nsSupportsArray::Enumerate(nsIEnumerator
** aResult
)
600 nsSupportsArrayEnumerator
* e
= new nsSupportsArrayEnumerator(this);
602 return NS_ERROR_OUT_OF_MEMORY
;
610 nsSupportsArray::Clone(nsISupportsArray
** aResult
)
612 nsCOMPtr
<nsISupportsArray
> newArray
;
613 nsresult rv
= NS_NewISupportsArray(getter_AddRefs(newArray
));
614 if (NS_WARN_IF(NS_FAILED(rv
))) {
620 for (uint32_t i
= 0; i
< count
; i
++) {
621 if (!newArray
->InsertElementAt(mArray
[i
], i
)) {
622 return NS_ERROR_OUT_OF_MEMORY
;
626 newArray
.forget(aResult
);
631 NS_NewISupportsArray(nsISupportsArray
** aInstancePtrResult
)
634 rv
= nsSupportsArray::Create(nullptr, NS_GET_IID(nsISupportsArray
),
635 (void**)aInstancePtrResult
);