The Tor Browser / file comparison

comparison: xpcom/ds/nsSupportsArray.cpp

xpcom/ds/nsSupportsArray.cpp

changeset 0
6474c204b198
equal deleted inserted replaced
-1:000000000000 0:ce7a61ffeaa8
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/. */
5
6 #include <string.h>
7 #include "mozilla/MathAlgorithms.h"
8 #include "nsSupportsArray.h"
9 #include "nsSupportsArrayEnumerator.h"
10 #include "nsIObjectInputStream.h"
11 #include "nsIObjectOutputStream.h"
12
13 #if DEBUG_SUPPORTSARRAY
14 #define MAXSUPPORTS 20
15
16 class SupportsStats {
17 public:
18 SupportsStats();
19 ~SupportsStats();
20
21 };
22
23 static int sizesUsed; // number of the elements of the arrays used
24 static int sizesAlloced[MAXSUPPORTS]; // sizes of the allocations. sorted
25 static int NumberOfSize[MAXSUPPORTS]; // number of this allocation size (1 per array)
26 static int AllocedOfSize[MAXSUPPORTS]; // number of this allocation size (each size for array used)
27 static int GrowInPlace[MAXSUPPORTS];
28
29 // these are per-allocation
30 static int MaxElements[3000];
31
32 // very evil
33 #define ADD_TO_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
34 { \
35 if (sizesAlloced[i] == (int)(size)) \
36 { ((x)[i])++; break; } \
37 } \
38 if (i >= sizesUsed && sizesUsed < MAXSUPPORTS) \
39 { sizesAlloced[sizesUsed] = (size); \
40 ((x)[sizesUsed++])++; break; \
41 } \
42 } while (0);
43
44 #define SUB_FROM_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
45 { \
46 if (sizesAlloced[i] == (int)(size)) \
47 { ((x)[i])--; break; } \
48 } \
49 } while (0);
50
51
52 SupportsStats::SupportsStats()
53 {
54 sizesUsed = 1;
55 sizesAlloced[0] = 0;
56 }
57
58 SupportsStats::~SupportsStats()
59 {
60 int i;
61 for (i = 0; i < sizesUsed; i++)
62 {
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]);
67 }
68 printf("Max Size of SupportsArray:\n");
69 for (i = 0; i < (int)(sizeof(MaxElements)/sizeof(MaxElements[0])); i++)
70 {
71 if (MaxElements[i])
72 printf("\t%d: %d\n",i,MaxElements[i]);
73 }
74 }
75
76 // Just so constructor/destructor get called
77 SupportsStats gSupportsStats;
78 #endif
79
80 nsresult
81 nsQueryElementAt::operator()( const nsIID& aIID, void** aResult ) const
82 {
83 nsresult status = mCollection
84 ? mCollection->QueryElementAt(mIndex, aIID, aResult)
85 : NS_ERROR_NULL_POINTER;
86
87 if ( mErrorPtr )
88 *mErrorPtr = status;
89
90 return status;
91 }
92
93 static const int32_t kGrowArrayBy = 8;
94 static const int32_t kLinearThreshold = 16 * sizeof(nsISupports *);
95
96 nsSupportsArray::nsSupportsArray()
97 {
98 mArray = mAutoArray;
99 mArraySize = kAutoArraySize;
100 mCount = 0;
101 #if DEBUG_SUPPORTSARRAY
102 mMaxCount = 0;
103 mMaxSize = 0;
104 ADD_TO_STATS(NumberOfSize,kAutoArraySize*sizeof(mArray[0]));
105 MaxElements[0]++;
106 #endif
107 }
108
109 nsSupportsArray::~nsSupportsArray()
110 {
111 DeleteArray();
112 }
113
114 void nsSupportsArray::GrowArrayBy(int32_t aGrowBy)
115 {
116 // We have to grow the array. Grow by kGrowArrayBy slots if we're smaller
117 // than kLinearThreshold bytes, or a power of two if we're larger.
118 // This is much more efficient with most memory allocators, especially
119 // if it's very large, or of the allocator is binned.
120 if (aGrowBy < kGrowArrayBy)
121 aGrowBy = kGrowArrayBy;
122
123 uint32_t newCount = mArraySize + aGrowBy; // Minimum increase
124 uint32_t newSize = sizeof(mArray[0]) * newCount;
125
126 if (newSize >= (uint32_t) kLinearThreshold)
127 {
128 // newCount includes enough space for at least kGrowArrayBy new slots.
129 // Select the next power-of-two size in bytes above that if newSize is
130 // not a power of two.
131 if (newSize & (newSize - 1))
132 newSize = 1u << mozilla::CeilingLog2(newSize);
133
134 newCount = newSize / sizeof(mArray[0]);
135 }
136 // XXX This would be far more efficient in many allocators if we used
137 // XXX PR_Realloc(), etc
138 nsISupports** oldArray = mArray;
139
140 mArray = new nsISupports*[newCount];
141 mArraySize = newCount;
142
143 #if DEBUG_SUPPORTSARRAY
144 if (oldArray == mArray) // can't happen without use of realloc
145 ADD_TO_STATS(GrowInPlace,mCount);
146 ADD_TO_STATS(AllocedOfSize,mArraySize*sizeof(mArray[0]));
147 if (mArraySize > mMaxSize)
148 {
149 ADD_TO_STATS(NumberOfSize,mArraySize*sizeof(mArray[0]));
150 if (oldArray != &(mAutoArray[0]))
151 SUB_FROM_STATS(NumberOfSize,mCount*sizeof(mArray[0]));
152 mMaxSize = mArraySize;
153 }
154 #endif
155 if (oldArray) { // need to move old data
156 if (0 < mCount) {
157 ::memcpy(mArray, oldArray, mCount * sizeof(nsISupports*));
158 }
159 if (oldArray != &(mAutoArray[0])) {
160 delete[] oldArray;
161 }
162 }
163 }
164
165 nsresult
166 nsSupportsArray::Create(nsISupports *aOuter, REFNSIID aIID, void **aResult)
167 {
168 if (aOuter)
169 return NS_ERROR_NO_AGGREGATION;
170
171 nsCOMPtr<nsISupportsArray> it = new nsSupportsArray();
172
173 return it->QueryInterface(aIID, aResult);
174 }
175
176 NS_IMPL_ISUPPORTS(nsSupportsArray, nsISupportsArray, nsICollection, nsISerializable)
177
178 NS_IMETHODIMP
179 nsSupportsArray::Read(nsIObjectInputStream *aStream)
180 {
181 nsresult rv;
182
183 uint32_t newArraySize;
184 rv = aStream->Read32(&newArraySize);
185
186 if (newArraySize <= kAutoArraySize) {
187 if (mArray != mAutoArray) {
188 delete[] mArray;
189 mArray = mAutoArray;
190 }
191 newArraySize = kAutoArraySize;
192 }
193 else {
194 if (newArraySize <= mArraySize) {
195 // Keep non-default-size mArray, it's more than big enough.
196 newArraySize = mArraySize;
197 }
198 else {
199 nsISupports** array = new nsISupports*[newArraySize];
200 if (mArray != mAutoArray)
201 delete[] mArray;
202 mArray = array;
203 }
204 }
205 mArraySize = newArraySize;
206
207 rv = aStream->Read32(&mCount);
208 if (NS_FAILED(rv)) return rv;
209
210 NS_ASSERTION(mCount <= mArraySize, "overlarge mCount!");
211 if (mCount > mArraySize)
212 mCount = mArraySize;
213
214 for (uint32_t i = 0; i < mCount; i++) {
215 rv = aStream->ReadObject(true, &mArray[i]);
216 if (NS_FAILED(rv)) return rv;
217 }
218
219 return NS_OK;
220 }
221
222 NS_IMETHODIMP
223 nsSupportsArray::Write(nsIObjectOutputStream *aStream)
224 {
225 nsresult rv;
226
227 rv = aStream->Write32(mArraySize);
228 if (NS_FAILED(rv)) return rv;
229
230 rv = aStream->Write32(mCount);
231 if (NS_FAILED(rv)) return rv;
232
233 for (uint32_t i = 0; i < mCount; i++) {
234 rv = aStream->WriteObject(mArray[i], true);
235 if (NS_FAILED(rv)) return rv;
236 }
237
238 return NS_OK;
239 }
240
241 void nsSupportsArray::DeleteArray(void)
242 {
243 Clear();
244 if (mArray != &(mAutoArray[0])) {
245 delete[] mArray;
246 mArray = mAutoArray;
247 mArraySize = kAutoArraySize;
248 }
249 }
250
251
252 NS_IMETHODIMP_(bool)
253 nsSupportsArray::Equals(const nsISupportsArray* aOther)
254 {
255 if (aOther) {
256 uint32_t countOther;
257 nsISupportsArray* other = const_cast<nsISupportsArray*>(aOther);
258 nsresult rv = other->Count(&countOther);
259 if (NS_FAILED( rv ))
260 return false;
261
262 if (mCount == countOther) {
263 uint32_t index = mCount;
264 nsCOMPtr<nsISupports> otherElem;
265 while (index--) {
266 if (NS_FAILED(other->GetElementAt(index, getter_AddRefs(otherElem))))
267 return false;
268 if (mArray[index] != otherElem)
269 return false;
270 }
271 return true;
272 }
273 }
274 return false;
275 }
276
277 NS_IMETHODIMP
278 nsSupportsArray::GetElementAt(uint32_t aIndex, nsISupports **aOutPtr)
279 {
280 *aOutPtr = nullptr;
281 if (aIndex < mCount) {
282 NS_IF_ADDREF(*aOutPtr = mArray[aIndex]);
283 }
284 return NS_OK;
285 }
286
287 NS_IMETHODIMP_(int32_t)
288 nsSupportsArray::IndexOf(const nsISupports* aPossibleElement)
289 {
290 return IndexOfStartingAt(aPossibleElement, 0);
291 }
292
293 NS_IMETHODIMP_(int32_t)
294 nsSupportsArray::IndexOfStartingAt(const nsISupports* aPossibleElement,
295 uint32_t aStartIndex)
296 {
297 if (aStartIndex < mCount) {
298 const nsISupports** start = (const nsISupports**)mArray; // work around goofy compiler behavior
299 const nsISupports** ep = (start + aStartIndex);
300 const nsISupports** end = (start + mCount);
301 while (ep < end) {
302 if (aPossibleElement == *ep) {
303 return (ep - start);
304 }
305 ep++;
306 }
307 }
308 return -1;
309 }
310
311 NS_IMETHODIMP_(int32_t)
312 nsSupportsArray::LastIndexOf(const nsISupports* aPossibleElement)
313 {
314 if (0 < mCount) {
315 const nsISupports** start = (const nsISupports**)mArray; // work around goofy compiler behavior
316 const nsISupports** ep = (start + mCount);
317 while (start <= --ep) {
318 if (aPossibleElement == *ep) {
319 return (ep - start);
320 }
321 }
322 }
323 return -1;
324 }
325
326 NS_IMETHODIMP_(bool)
327 nsSupportsArray::InsertElementAt(nsISupports* aElement, uint32_t aIndex)
328 {
329 if (aIndex <= mCount) {
330 if (mArraySize < (mCount + 1)) {
331 // need to grow the array
332 GrowArrayBy(1);
333 }
334
335 // Could be slightly more efficient if GrowArrayBy knew about the
336 // split, but the difference is trivial.
337 uint32_t slide = (mCount - aIndex);
338 if (0 < slide) {
339 ::memmove(mArray + aIndex + 1, mArray + aIndex, slide * sizeof(nsISupports*));
340 }
341
342 mArray[aIndex] = aElement;
343 NS_IF_ADDREF(aElement);
344 mCount++;
345
346 #if DEBUG_SUPPORTSARRAY
347 if (mCount > mMaxCount &&
348 mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
349 {
350 MaxElements[mCount]++;
351 MaxElements[mMaxCount]--;
352 mMaxCount = mCount;
353 }
354 #endif
355 return true;
356 }
357 return false;
358 }
359
360 NS_IMETHODIMP_(bool)
361 nsSupportsArray::InsertElementsAt(nsISupportsArray* aElements, uint32_t aIndex)
362 {
363 if (!aElements) {
364 return false;
365 }
366 uint32_t countElements;
367 if (NS_FAILED( aElements->Count( &countElements ) ))
368 return false;
369
370 if (aIndex <= mCount) {
371 if (mArraySize < (mCount + countElements)) {
372 // need to grow the array
373 GrowArrayBy(countElements);
374 }
375
376 // Could be slightly more efficient if GrowArrayBy knew about the
377 // split, but the difference is trivial.
378 uint32_t slide = (mCount - aIndex);
379 if (0 < slide) {
380 ::memmove(mArray + aIndex + countElements, mArray + aIndex,
381 slide * sizeof(nsISupports*));
382 }
383
384 for (uint32_t i = 0; i < countElements; ++i, ++mCount) {
385 // use GetElementAt to copy and do AddRef for us
386 if (NS_FAILED( aElements->GetElementAt( i, mArray + aIndex + i) ))
387 return false;
388 }
389
390 #if DEBUG_SUPPORTSARRAY
391 if (mCount > mMaxCount &&
392 mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
393 {
394 MaxElements[mCount]++;
395 MaxElements[mMaxCount]--;
396 mMaxCount = mCount;
397 }
398 #endif
399 return true;
400 }
401 return false;
402 }
403
404 NS_IMETHODIMP_(bool)
405 nsSupportsArray::ReplaceElementAt(nsISupports* aElement, uint32_t aIndex)
406 {
407 if (aIndex < mCount) {
408 NS_IF_ADDREF(aElement); // addref first in case it's the same object!
409 NS_IF_RELEASE(mArray[aIndex]);
410 mArray[aIndex] = aElement;
411 return true;
412 }
413 return false;
414 }
415
416 NS_IMETHODIMP_(bool)
417 nsSupportsArray::RemoveElementsAt(uint32_t aIndex, uint32_t aCount)
418 {
419 if (aIndex + aCount <= mCount) {
420 for (uint32_t i = 0; i < aCount; i++)
421 NS_IF_RELEASE(mArray[aIndex+i]);
422 mCount -= aCount;
423 int32_t slide = (mCount - aIndex);
424 if (0 < slide) {
425 ::memmove(mArray + aIndex, mArray + aIndex + aCount,
426 slide * sizeof(nsISupports*));
427 }
428 return true;
429 }
430 return false;
431 }
432
433 NS_IMETHODIMP_(bool)
434 nsSupportsArray::RemoveElement(const nsISupports* aElement, uint32_t aStartIndex)
435 {
436 int32_t theIndex = IndexOfStartingAt(aElement,aStartIndex);
437 if (theIndex >= 0)
438 return RemoveElementAt(theIndex);
439
440 return false;
441 }
442
443 NS_IMETHODIMP_(bool)
444 nsSupportsArray::RemoveLastElement(const nsISupports* aElement)
445 {
446 int32_t theIndex = LastIndexOf(aElement);
447 if (theIndex >= 0)
448 return RemoveElementAt(theIndex);
449
450 return false;
451 }
452
453 NS_IMETHODIMP_(bool)
454 nsSupportsArray::MoveElement(int32_t aFrom, int32_t aTo)
455 {
456 nsISupports *tempElement;
457
458 if (aTo == aFrom)
459 return true;
460
461 if (aTo < 0 || aFrom < 0 ||
462 (uint32_t) aTo >= mCount || (uint32_t) aFrom >= mCount)
463 {
464 // can't extend the array when moving an element. Also catches mImpl = null
465 return false;
466 }
467 tempElement = mArray[aFrom];
468
469 if (aTo < aFrom)
470 {
471 // Moving one element closer to the head; the elements inbetween move down
472 ::memmove(mArray + aTo + 1, mArray + aTo,
473 (aFrom-aTo) * sizeof(mArray[0]));
474 mArray[aTo] = tempElement;
475 }
476 else // already handled aFrom == aTo
477 {
478 // Moving one element closer to the tail; the elements inbetween move up
479 ::memmove(mArray + aFrom, mArray + aFrom + 1,
480 (aTo-aFrom) * sizeof(mArray[0]));
481 mArray[aTo] = tempElement;
482 }
483
484 return true;
485 }
486
487 NS_IMETHODIMP
488 nsSupportsArray::Clear(void)
489 {
490 if (0 < mCount) {
491 do {
492 --mCount;
493 NS_IF_RELEASE(mArray[mCount]);
494 } while (0 != mCount);
495 }
496 return NS_OK;
497 }
498
499 NS_IMETHODIMP
500 nsSupportsArray::Compact(void)
501 {
502 #if DEBUG_SUPPORTSARRAY
503 uint32_t oldArraySize = mArraySize;
504 #endif
505 if ((mArraySize != mCount) && (kAutoArraySize < mArraySize)) {
506 nsISupports** oldArray = mArray;
507 if (mCount <= kAutoArraySize) {
508 mArray = mAutoArray;
509 mArraySize = kAutoArraySize;
510 }
511 else {
512 mArray = new nsISupports*[mCount];
513 if (!mArray) {
514 mArray = oldArray;
515 return NS_OK;
516 }
517 mArraySize = mCount;
518 }
519 #if DEBUG_SUPPORTSARRAY
520 if (oldArray == mArray &&
521 oldArray != &(mAutoArray[0])) // can't happen without use of realloc
522 ADD_TO_STATS(GrowInPlace,oldArraySize);
523 if (oldArray != &(mAutoArray[0]))
524 ADD_TO_STATS(AllocedOfSize,mArraySize*sizeof(mArray[0]));
525 #endif
526 ::memcpy(mArray, oldArray, mCount * sizeof(nsISupports*));
527 delete[] oldArray;
528 }
529 return NS_OK;
530 }
531
532 NS_IMETHODIMP_(bool)
533 nsSupportsArray::SizeTo(int32_t aSize)
534 {
535 #if DEBUG_SUPPORTSARRAY
536 uint32_t oldArraySize = mArraySize;
537 #endif
538 NS_ASSERTION(aSize >= 0, "negative aSize!");
539
540 // XXX for aSize < mCount we could resize to mCount
541 if (mArraySize == (uint32_t) aSize || (uint32_t) aSize < mCount)
542 return true; // nothing to do
543
544 // switch back to autoarray if possible
545 nsISupports** oldArray = mArray;
546 if ((uint32_t) aSize <= kAutoArraySize) {
547 mArray = mAutoArray;
548 mArraySize = kAutoArraySize;
549 }
550 else {
551 mArray = new nsISupports*[aSize];
552 if (!mArray) {
553 mArray = oldArray;
554 return false;
555 }
556 mArraySize = aSize;
557 }
558 #if DEBUG_SUPPORTSARRAY
559 if (oldArray == mArray &&
560 oldArray != &(mAutoArray[0])) // can't happen without use of realloc
561 ADD_TO_STATS(GrowInPlace,oldArraySize);
562 if (oldArray != &(mAutoArray[0]))
563 ADD_TO_STATS(AllocedOfSize,mArraySize*sizeof(mArray[0]));
564 #endif
565 ::memcpy(mArray, oldArray, mCount * sizeof(nsISupports*));
566 if (oldArray != mAutoArray)
567 delete[] oldArray;
568
569 return true;
570 }
571
572 NS_IMETHODIMP
573 nsSupportsArray::Enumerate(nsIEnumerator* *result)
574 {
575 nsSupportsArrayEnumerator* e = new nsSupportsArrayEnumerator(this);
576 if (!e)
577 return NS_ERROR_OUT_OF_MEMORY;
578 *result = e;
579 NS_ADDREF(e);
580 return NS_OK;
581 }
582
583 NS_IMETHODIMP
584 nsSupportsArray::Clone(nsISupportsArray** aResult)
585 {
586 nsCOMPtr<nsISupportsArray> newArray;
587 nsresult rv = NS_NewISupportsArray(getter_AddRefs(newArray));
588 if (NS_WARN_IF(NS_FAILED(rv)))
589 return rv;
590
591 uint32_t count = 0;
592 Count(&count);
593 for (uint32_t i = 0; i < count; i++) {
594 if (!newArray->InsertElementAt(mArray[i], i)) {
595 return NS_ERROR_OUT_OF_MEMORY;
596 }
597 }
598
599 newArray.forget(aResult);
600 return NS_OK;
601 }
602
603 nsresult
604 NS_NewISupportsArray(nsISupportsArray** aInstancePtrResult)
605 {
606 nsresult rv;
607 rv = nsSupportsArray::Create(nullptr, NS_GET_IID(nsISupportsArray),
608 (void**)aInstancePtrResult);
609 return rv;
610 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial