This shouldn't be using the stdlibc++ stuff, because it's not available everywhere. (Sad, but true.) I'd suggest switching this to use nsTArray. This is currently blocking building libxul on Android.

After some discussion, joe and I agree that nsTArray should get heap functions (MakeHeap/PushHeap/PopHeap); someone just needs to implement. Cc'ing mwu, he might have some cycles to work on this.

So.. this appears to work but I have no idea really. Gonna write some tests. I wonder if it would be worth it to always add things to the heap properly through PushHeap instead of setting a dirty bit and rebuilding the heap.

New patch without the part adding heap functions, which is now in bug 537339. Otherwise mostly the same.

Adding things immediately makes us spend a bunch of time managing the heap while we're downloading images, because their weight changes a pile of times during the download. If we had some way of changing the weight of an element in the heap - which is possible in Fibonacci heaps, but not binomial, I believe - it wouldn't be necessary.

Ah I see. Would using fibonacci heaps in the future be worthwhile?

To simplify the imgLoader code, sure. But it's not performance-critical any more, thanks to the lazy update.

Some code simplified.

Comment on attachment 435024 [details] [diff] [review] Switch imgLoader.cpp to nsTArray, v2 >diff --git a/modules/libpr0n/src/imgLoader.cpp b/modules/libpr0n/src/imgLoader.cpp >+ PRUint32 index = mQueue.Length(); >+ nsRefPtr<imgCacheEntry> *elements = mQueue.Elements(); >+ >+ if (!index) >+ return; >+ >+ while (index--) { >+ if (elements[index] != entry) >+ continue; >+ mSize -= elements[index]->GetDataSize(); >+ mQueue.RemoveElementAt(index); Two separate comments: 1 - searching arrays backwards makes me sad :( 2 - We should just use nsTArray::IndexOf() instead of hand-rolling our own search method. >@@ -1289,14 +1283,11 @@ nsresult imgLoader::EvictEntries(imgCach >+ // We iterate backwards so a shift isn't required when >+ // RemoveFromCache removes the element from the queue. Can you reformat this so it's 80 characters wide? >+ imgCacheEntry *entry; >+ while ((entry = aQueueToClear.GetLast())) >+ if (!RemoveFromCache(entry)) > return NS_ERROR_FAILURE; I'd prefer something along the lines of entry = GetLast() while (entry) { do_stuff() entry = GetLast(); } >diff --git a/modules/libpr0n/src/imgLoader.h b/modules/libpr0n/src/imgLoader.h >-class imgCacheQueue [snip] >+class imgCacheQueue; Is there a reason you moved the definition of imgCacheQueue?

This no longer blocks android stuff, though I'm leaving it open since we may as well switch to our heap impl.

Unassigning myself as there is little demand for this at the moment.

We are now much less afraid of the STL than we used to be. I won't take a patch that changes this just to remove usage of STL.