--- a/toolkit/components/url-classifier/src/nsUrlClassifierUtils.h
+++ b/toolkit/components/url-classifier/src/nsUrlClassifierUtils.h
@@ -139,17 +139,17 @@ public:
 
     if (!mEntries.Init())
       return PR_FALSE;
 
     return PR_TRUE;
   }
 
   PRBool Put(const nsACString &fragment) {
-    Entry *entry;
+    Entry *entry = nsnull;
     if (mEntries.Get(fragment, &entry)) {
       // Remove this entry from the list, we'll add it back
       // to the front.
       UnlinkEntry(entry);
     } else {
       if (mEntryStorage.Length() < mEntryStorage.Capacity()) {
         entry = mEntryStorage.AppendElement();
         if (!entry)
@@ -159,29 +159,31 @@ public:
         entry = mLast;
         UnlinkEntry(entry);
         mEntries.Remove(entry->mFragment);
       }
       entry->mFragment = fragment;
       mEntries.Put(fragment, entry);
     }
 
-    // Add the entry to the front of the list
-    entry->mPrev = nsnull;
-    entry->mNext = mFirst;
-    mFirst = entry;
-    if (!mLast) {
-      mLast = entry;
-    }
+    LinkEntry(entry);
 
     return PR_TRUE;
   }
 
-  PRBool Has(const nsACString &fragment) {
-    return mEntries.Get(fragment, nsnull);
+  PRBool Has(const nsACString &fragment, PRBool update = PR_TRUE) {
+    Entry *entry = nsnull;
+    PRBool exists = mEntries.Get(fragment, &entry);
+    // Move this entry to the front of the list (if it isn't already there)
+    if (update && exists && entry != mFirst) {
+      UnlinkEntry(entry);
+      LinkEntry(entry);
+    }
+
+    return exists;
   }
 
   void Clear() {
     mFirst = mLast = nsnull;
     mEntries.Clear();
     mEntryStorage.Clear();
     mEntryStorage.SetCapacity(mCapacity);
   }
@@ -194,16 +196,30 @@ private:
     Entry() : mNext(nsnull), mPrev(nsnull) {};
     ~Entry() { }
 
     Entry *mNext;
     Entry *mPrev;
     nsCString mFragment;
   };
 
+  void LinkEntry(Entry *entry)
+  {
+    // Add the entry to the front of the list
+    entry->mPrev = nsnull;
+    entry->mNext = mFirst;
+    if (mFirst) {
+      mFirst->mPrev = entry;
+    }
+    mFirst = entry;
+    if (!mLast) {
+      mLast = entry;
+    }
+  }
+
   void UnlinkEntry(Entry *entry)
   {
     if (entry->mPrev)
       entry->mPrev->mNext = entry->mNext;
     else
       mFirst = entry->mNext;
 
     if (entry->mNext)

--- a/toolkit/components/url-classifier/tests/TestUrlClassifierUtils.cpp
+++ b/toolkit/components/url-classifier/tests/TestUrlClassifierUtils.cpp
@@ -298,25 +298,56 @@ void TestLongHostname()
   PRIntervalTime clockEnd = PR_IntervalNow();
 
   CheckEquals(in, out);
 
   printf("CanonicalizeHostname on long string (%dms)\n",
          PR_IntervalToMilliseconds(clockEnd - clockStart));
 }
 
+void TestFragmentSet()
+{
+  nsUrlClassifierFragmentSet set;
+  set.Init(3);
+
+  set.Put(NS_LITERAL_CSTRING("a"));
+  set.Put(NS_LITERAL_CSTRING("b"));
+  set.Put(NS_LITERAL_CSTRING("c"));
+
+  // At this point, adding a fourth element would push "a" off.
+  // Make sure that set.Has("a") moves it to the front of the list
+  set.Has(NS_LITERAL_CSTRING("a"));
+
+  // Now add a new item.  This should now push "b" off the list,
+  // but leave "a"
+  set.Put(NS_LITERAL_CSTRING("d"));
+
+  gTotalTests++;
+  if (set.Has(NS_LITERAL_CSTRING("a")))
+    gPassedTests++;
+  else
+    fprintf(stderr, "FAILED: set.Has(\"a\") failed.\n");
+
+  gTotalTests++;
+  if (!set.Has(NS_LITERAL_CSTRING("b")))
+    gPassedTests++;
+  else
+    fprintf(stderr, "FAILED: !set.Has(\"b\") failed.\n");
+}
+
 int main(int argc, char **argv)
 {
   NS_LogInit();
 
   TestUnescape();
   TestEnc();
   TestCanonicalize();
   TestCanonicalNum();
   TestParseIPAddress();
   TestHostname();
   TestLongHostname();
+  TestFragmentSet();
 
   printf("%d of %d tests passed\n", gPassedTests, gTotalTests);
   // Non-zero return status signals test failure to build system.
 
   return (gPassedTests != gTotalTests);
 }