new file mode 100644
--- /dev/null
+++ b/docshell/test/unit/test_bug442584.js
@@ -0,0 +1,34 @@
+var prefetch = Cc["@mozilla.org/prefetch-service;1"].
+               getService(Ci.nsIPrefetchService);
+var ios = Cc["@mozilla.org/network/io-service;1"].
+          getService(Ci.nsIIOService);
+var prefs = Cc["@mozilla.org/preferences-service;1"].
+            getService(Ci.nsIPrefBranch);
+
+function run_test() {
+  // Fill up the queue
+  prefs.setBoolPref("network.prefetch-next", true);
+  for (var i = 0; i < 5; i++) {
+    var uri = ios.newURI("http://localhost/" + i, null, null);
+    prefetch.prefetchURI(uri, uri, null, true);
+  }
+
+  // Make sure the queue has items in it...
+  var queue = prefetch.enumerateQueue(true, false);
+  do_check_true(queue.hasMoreElements());
+
+  // Now disable the pref to force the queue to empty...
+  prefs.setBoolPref("network.prefetch-next", false);
+  queue = prefetch.enumerateQueue(true, false);
+  do_check_false(queue.hasMoreElements());
+
+  // Now reenable the pref, and add more items to the queue.
+  prefs.setBoolPref("network.prefetch-next", true);
+  for (var i = 0; i < 5; i++) {
+    var uri = ios.newURI("http://localhost/" + i, null, null);
+    prefetch.prefetchURI(uri, uri, null, true);
+  }
+  queue = prefetch.enumerateQueue(true, false);
+  do_check_true(queue.hasMoreElements());
+}
+

--- a/uriloader/prefetch/nsPrefetchService.cpp
+++ b/uriloader/prefetch/nsPrefetchService.cpp
@@ -152,38 +152,38 @@ nsPrefetchQueueEnumerator::GetNext(nsISu
 
 //-----------------------------------------------------------------------------
 // nsPrefetchQueueEnumerator <private>
 //-----------------------------------------------------------------------------
 
 void
 nsPrefetchQueueEnumerator::Increment()
 {
-    do {
-        if (!mStarted) {
-            // If the service is currently serving a request, it won't be
-            // in the pending queue, so we return it first.  If it isn't,
-            // we'll just start with the pending queue.
-            mStarted = PR_TRUE;
-            mCurrent = mService->GetCurrentNode();
-            if (!mCurrent)
-                mCurrent = mService->GetQueueHead();
-        }
-        else if (mCurrent) {
-            if (mCurrent == mService->GetCurrentNode()) {
-                // If we just returned the node being processed by the service,
-                // start with the pending queue
-                mCurrent = mService->GetQueueHead();
-            }
-            else {
-                // Otherwise just advance to the next item in the queue
-                mCurrent = mCurrent->mNext;
-            }
-        }
-    } while (mCurrent);
+  if (!mStarted) {
+    // If the service is currently serving a request, it won't be in
+    // the pending queue, so we return it first.  If it isn't, we'll
+    // just start with the pending queue.
+    mStarted = PR_TRUE;
+    mCurrent = mService->GetCurrentNode();
+    if (!mCurrent)
+      mCurrent = mService->GetQueueHead();
+    return;
+  }
+
+  if (mCurrent) {
+    if (mCurrent == mService->GetCurrentNode()) {
+      // If we just returned the node being processed by the service,
+      // start with the pending queue
+      mCurrent = mService->GetQueueHead();
+    }
+    else {
+      // Otherwise just advance to the next item in the queue
+      mCurrent = mCurrent->mNext;
+    }
+  }
 }
 
 //-----------------------------------------------------------------------------
 // nsPrefetchQueueEnumerator::nsISupports
 //-----------------------------------------------------------------------------
 
 NS_IMPL_ISUPPORTS1(nsPrefetchQueueEnumerator, nsISimpleEnumerator)
 
@@ -581,29 +581,20 @@ nsPrefetchService::DequeueNode(nsPrefetc
         mQueueTail = nsnull;
 
     return NS_OK;
 }
 
 void
 nsPrefetchService::EmptyQueue()
 {
-    nsPrefetchNode *prev = 0;
-    nsPrefetchNode *node = mQueueHead;
-
-    while (node) {
-        nsPrefetchNode *next = node->mNext;
-        if (prev)
-            prev->mNext = next;
-        else
-            mQueueHead = next;
-        NS_RELEASE(node);
-
-        node = next;
-    }
+    do {
+        nsRefPtr<nsPrefetchNode> node;
+        DequeueNode(getter_AddRefs(node));
+    } while (mQueueHead);
 }
 
 void
 nsPrefetchService::StartPrefetching()
 {
     //
     // at initialization time we might miss the first DOCUMENT START
     // notification, so we have to be careful to avoid letting our
@@ -946,16 +937,17 @@ NS_IMETHODIMP
 nsPrefetchService::Observe(nsISupports     *aSubject,
                            const char      *aTopic,
                            const PRUnichar *aData)
 {
     LOG(("nsPrefetchService::Observe [topic=%s]\n", aTopic));
 
     if (!strcmp(aTopic, NS_XPCOM_SHUTDOWN_OBSERVER_ID)) {
         StopPrefetching();
+        EmptyQueue();
         mDisabled = PR_TRUE;
     }
     else if (!strcmp(aTopic, NS_PREFBRANCH_PREFCHANGE_TOPIC_ID)) {
         nsCOMPtr<nsIPrefBranch> prefs(do_QueryInterface(aSubject));
         PRBool enabled;
         nsresult rv = prefs->GetBoolPref(PREFETCH_PREF, &enabled);
         if (NS_SUCCEEDED(rv) && enabled) {
             if (mDisabled) {
@@ -963,16 +955,17 @@ nsPrefetchService::Observe(nsISupports  
                 mDisabled = PR_FALSE;
                 AddProgressListener();
             }
         } 
         else {
             if (!mDisabled) {
                 LOG(("disabling prefetching\n"));
                 StopPrefetching();
+                EmptyQueue();
                 mDisabled = PR_TRUE;
                 RemoveProgressListener();
             }
         }
     }
 
     return NS_OK;
 }