--- a/src/share/vm/gc_implementation/g1/heapRegionSet.cpp	Mon Mar 24 09:14:14 2014 -0700
+++ b/src/share/vm/gc_implementation/g1/heapRegionSet.cpp	Fri Feb 28 15:27:09 2014 +0100
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -135,9 +135,11 @@
     assert(length() > 0 && _tail != NULL, hrs_ext_msg(this, "invariant"));
     if (as_head) {
       from_list->_tail->set_next(_head);
+      _head->set_prev(from_list->_tail);
       _head = from_list->_head;
     } else {
       _tail->set_next(from_list->_head);
+      from_list->_head->set_prev(_tail);
       _tail = from_list->_tail;
     }
   }
@@ -167,6 +169,7 @@
 
     HeapRegion* next = curr->next();
     curr->set_next(NULL);
+    curr->set_prev(NULL);
     curr->set_containing_set(NULL);
     curr = next;
   }
@@ -175,6 +178,74 @@
   verify_optional();
 }
 
+void FreeRegionList::add_ordered(FreeRegionList* from_list) {
+  check_mt_safety();
+  from_list->check_mt_safety();
+
+  verify_optional();
+  from_list->verify_optional();
+
+  if (from_list->is_empty()) {
+    return;
+  }
+
+  if (is_empty()) {
+    add_as_head(from_list);
+    return;
+  }
+
+  #ifdef ASSERT
+  FreeRegionListIterator iter(from_list);
+  while (iter.more_available()) {
+    HeapRegion* hr = iter.get_next();
+    // In set_containing_set() we check that we either set the value
+    // from NULL to non-NULL or vice versa to catch bugs. So, we have
+    // to NULL it first before setting it to the value.
+    hr->set_containing_set(NULL);
+    hr->set_containing_set(this);
+  }
+  #endif // ASSERT
+
+  HeapRegion* curr_to = _head;
+  HeapRegion* curr_from = from_list->_head;
+
+  while (curr_from != NULL) {
+    while (curr_to != NULL && curr_to->hrs_index() < curr_from->hrs_index()) {
+      curr_to = curr_to->next();
+    }
+
+    if (curr_to == NULL) {
+      // The rest of the from list should be added as tail
+      _tail->set_next(curr_from);
+      curr_from->set_prev(_tail);
+      curr_from = NULL;
+    } else {
+      HeapRegion* next_from = curr_from->next();
+
+      curr_from->set_next(curr_to);
+      curr_from->set_prev(curr_to->prev());
+      if (curr_to->prev() == NULL) {
+        _head = curr_from;
+      } else {
+        curr_to->prev()->set_next(curr_from);
+      }
+      curr_to->set_prev(curr_from);
+
+      curr_from = next_from;
+    }
+  }
+
+  if (_tail->hrs_index() < from_list->_tail->hrs_index()) {
+    _tail = from_list->_tail;
+  }
+
+  _count.increment(from_list->length(), from_list->total_capacity_bytes());
+  from_list->clear();
+
+  verify_optional();
+  from_list->verify_optional();
+}
+
 void FreeRegionList::remove_all_pending(uint target_count) {
   check_mt_safety();
   assert(target_count > 1, hrs_ext_msg(this, "pre-condition"));
@@ -184,11 +255,11 @@
   DEBUG_ONLY(uint old_length = length();)
 
   HeapRegion* curr = _head;
-  HeapRegion* prev = NULL;
   uint count = 0;
   while (curr != NULL) {
     verify_region(curr);
     HeapRegion* next = curr->next();
+    HeapRegion* prev = curr->prev();
 
     if (curr->pending_removal()) {
       assert(count < target_count,
@@ -208,9 +279,14 @@
         _tail = prev;
       } else {
         assert(_tail != curr, hrs_ext_msg(this, "invariant"));
+        next->set_prev(prev);
+      }
+      if (_last = curr) {
+        _last = NULL;
       }
 
       curr->set_next(NULL);
+      curr->set_prev(NULL);
       remove(curr);
       curr->set_pending_removal(false);
 
@@ -221,8 +297,6 @@
       // carry on iterating to make sure there are not more regions
       // tagged with pending removal.
       DEBUG_ONLY(if (count == target_count) break;)
-    } else {
-      prev = curr;
     }
     curr = next;
   }
@@ -255,6 +329,7 @@
   _count = HeapRegionSetCount();
   _head = NULL;
   _tail = NULL;
+  _last = NULL;
 }
 
 void FreeRegionList::print_on(outputStream* out, bool print_contents) {
@@ -279,6 +354,9 @@
   HeapRegion* prev0 = NULL;
   uint count = 0;
   size_t capacity = 0;
+  uint last_index = 0;
+
+  guarantee(_head == NULL || _head->prev() == NULL, "_head should not have a prev");
   while (curr != NULL) {
     verify_region(curr);
 
@@ -286,6 +364,12 @@
     guarantee(count < _unrealistically_long_length,
         hrs_err_msg("[%s] the calculated length: %u seems very long, is there maybe a cycle? curr: "PTR_FORMAT" prev0: "PTR_FORMAT" " "prev1: "PTR_FORMAT" length: %u", name(), count, curr, prev0, prev1, length()));
 
+    if (curr->next() != NULL) {
+      guarantee(curr->next()->prev() == curr, "Next or prev pointers messed up");
+    }
+    guarantee(curr->hrs_index() == 0 || curr->hrs_index() > last_index, "List should be sorted");
+    last_index = curr->hrs_index();
+
     capacity += curr->capacity();
 
     prev1 = prev0;
@@ -294,7 +378,7 @@
   }
 
   guarantee(tail() == prev0, err_msg("Expected %s to end with %u but it ended with %u.", name(), tail()->hrs_index(), prev0->hrs_index()));
-
+  guarantee(_tail == NULL || _tail->next() == NULL, "_tail should not have a next");
   guarantee(length() == count, err_msg("%s count mismatch. Expected %u, actual %u.", name(), length(), count));
   guarantee(total_capacity_bytes() == capacity, err_msg("%s capacity mismatch. Expected " SIZE_FORMAT ", actual " SIZE_FORMAT,
       name(), total_capacity_bytes(), capacity));