Make GlobalHandle::NodeBlock deletable

src/global-handles.h

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 138 matching lines @@
 
   // Returns the current number of weak handles to global objects.
   // These handles are also included in NumberOfWeakHandles().
   int NumberOfGlobalObjectWeakHandles();
 
   // Returns the current number of handles to global objects.
   int global_handles_count() const {
     return number_of_global_handles_;
   }
 
+  // Returns the current number of allocated blocks
+  int block_count() const { return number_of_blocks_; }
+
   // Clear the weakness of a global handle.
   static void ClearWeakness(Object** location);
 
   // Clear the weakness of a global handle.
   static void MarkIndependent(Object** location);
 
   // Mark the reference to this object externaly unreachable.
   static void MarkPartiallyDependent(Object** location);
 
   static bool IsIndependent(Object** location);
@@ skipping 99 matching lines @@
   void RemoveImplicitRefGroups();
 
   // Tear down the global handle structure.
   void TearDown();
 
   Isolate* isolate() { return isolate_; }
 
 #ifdef DEBUG
   void PrintStats();
   void Print();
+  void VerifyBlockInvariants();
 #endif
 
  private:
   explicit GlobalHandles(Isolate* isolate);
 
+  void SortBlocks(bool shouldPrune);
+
   // Migrates data from the internal representation (object_group_connections_,
   // retainer_infos_ and implicit_ref_connections_) to the public and more
   // efficient representation (object_groups_ and implicit_ref_groups_).
   void ComputeObjectGroupsAndImplicitReferences();
 
   // v8::internal::List is inefficient even for small number of elements, if we
   // don't assign any initial capacity.
   static const int kObjectGroupConnectionsCapacity = 20;
 
   // Internal node structures.
   class Node;
   class NodeBlock;
   class NodeIterator;
+  class BlockListIterator;
+  // Base class for NodeBlock
+  class BlockList {
+   public:
+    BlockList();
+    ~BlockList() { ASSERT(IsDetached()); }
+    void Detach();
+    void InsertAsHead(BlockList* block) {
+      ASSERT(IsAnchor());
+      InsertAsNext(block);
+    }
+    void InsertAsTail(BlockList* block) {
+      ASSERT(IsAnchor());
+      prev_block_->InsertAsNext(block);
+    }
+    inline bool IsAnchor() { return first_free_ == NULL && used_nodes_ == 0; }
+    inline bool IsDetached() {
+      ASSERT_EQ(prev_block_ == this, next_block_ == this);
+      return prev_block_ == this;
+    }
+    bool HasAtLeastLength(int length);
+    bool IsUnused() { return used_nodes_ == 0; }
+    int used_nodes() const { return used_nodes_; }
+    BlockList* next() { return next_block_; }
+    BlockList* prev() { return prev_block_; }
+#ifdef DEBUG
+    int LengthOfFreeList();
+#endif
+    static void SortBlocks(GlobalHandles* global_handles, bool prune);
+
+   protected:
+    BlockList* prev_block_;
+    BlockList* next_block_;
+    Node* first_free_;
+    int used_nodes_;
+
+   private:
+    // Needed for quicksort
+    static int CompareBlocks(const void* a, const void* b);
+    void InsertAsNext(BlockList* block);
+    DISALLOW_COPY_AND_ASSIGN(BlockList);
+  };
 
   Isolate* isolate_;
 
+  // Field always containing the number of blocks allocated.
+  int number_of_blocks_;
   // Field always containing the number of handles to global objects.
   int number_of_global_handles_;
 
-  // List of all allocated node blocks.
-  NodeBlock* first_block_;
+  // Anchors for doubly linked lists of blocks
+  BlockList full_blocks_;
+  BlockList non_full_blocks_;
 
-  // List of node blocks with used nodes.
-  NodeBlock* first_used_block_;
-
-  // Free list of nodes.
-  Node* first_free_;
+  // An array of all the anchors held by GlobalHandles.
+  // This simplifies iteration across all blocks.
+  static const int kAllAnchorsSize = 2;
+  BlockList*  all_anchors_[kAllAnchorsSize];
 
   // Contains all nodes holding new space objects. Note: when the list
   // is accessed, some of the objects may have been promoted already.
   List<Node*> new_space_nodes_;
 
   int post_gc_processing_count_;
 
   // Object groups and implicit references, public and more efficient
   // representation.
   List<ObjectGroup*> object_groups_;
   List<ImplicitRefGroup*> implicit_ref_groups_;
 
   // Object groups and implicit references, temporary representation while
   // constructing the groups.
   List<ObjectGroupConnection> object_group_connections_;
   List<ObjectGroupRetainerInfo> retainer_infos_;
   List<ObjectGroupConnection> implicit_ref_connections_;
 
   friend class Isolate;
 
   DISALLOW_COPY_AND_ASSIGN(GlobalHandles);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_GLOBAL_HANDLES_H_