Split an allocation policy into an allocator and a deallocator.

src/splay-tree.h

Index: src/splay-tree.h
diff --git a/src/splay-tree.h b/src/splay-tree.h
index 72231e4d2a120a0fe3bf98eb12e52d3336ea6217..7ed20871fab11a98fa32928a2c97d89d558e0f82 100644
--- a/src/splay-tree.h
+++ b/src/splay-tree.h
@@ -50,26 +50,35 @@ namespace internal {
 // Forward defined as
 // template <typename Config, class Allocator = FreeStoreAllocationPolicy>
 //     class SplayTree;
-template <typename Config, class Allocator>
+template <typename Config, class P>

[danno, 2012/05/25 11:03:37]

AllocationPolicy

 class SplayTree {
  public:
   typedef typename Config::Key Key;
   typedef typename Config::Value Value;
 
+  typedef typename P::Alloc Allocator;
+  typedef typename P::Dealloc Deallocator;
+
   class Locator;
 
-  SplayTree() : root_(NULL) { }
+  SplayTree(Allocator allocator = Allocator(),
+            Deallocator deallocator = Deallocator())
+      : root_(NULL), deallocator_(deallocator) { }
   ~SplayTree();
 
-  INLINE(void* operator new(size_t size)) {
-    return Allocator::New(static_cast<int>(size));
+  INLINE(void* operator new(size_t size, Allocator allocator = Allocator())) {
+    return allocator.New(static_cast<int>(size));
+  }
+  INLINE(void operator delete(void* p, size_t,
+                              Deallocator deallocator = Deallocator())) {

[danno, 2012/05/25 11:03:37]

Adding the deallocator here does something different than you think. In this
case, you cannot override the deallocator, since there is no way to pass it in a
call to delete. So either you want "return Deallocator().Delete(p), or you want
to put an "UNREACHABLE" here like you do later in the file. 

+    return deallocator.Delete(p);
   }
-  INLINE(void operator delete(void* p, size_t)) { return Allocator::Delete(p); }
 
   // Inserts the given key in this tree with the given value.  Returns
   // true if a node was inserted, otherwise false.  If found the locator
   // is enabled and provides access to the mapping for the key.
-  bool Insert(const Key& key, Locator* locator);
+  bool Insert(const Key& key, Locator* locator,
+              Allocator allocator = Allocator());
 
   // Looks up the key in this tree and returns true if it was found,
   // otherwise false.  If the node is found the locator is enabled and
@@ -112,11 +121,11 @@ class SplayTree {
           left_(NULL),
           right_(NULL) { }
 
-    INLINE(void* operator new(size_t size)) {
-      return Allocator::New(static_cast<int>(size));
+    INLINE(void* operator new(size_t size, Allocator allocator)) {
+      return allocator.New(static_cast<int>(size));
     }
     INLINE(void operator delete(void* p, size_t)) {
-      return Allocator::Delete(p);
+      UNREACHABLE();

[danno, 2012/05/25 11:03:37]

Why unreachable? Because nodes should only be allocated in Zones? Was the delete
operator never called before? I still don't see what it's a problem to
implemented this with Deallocator().Delete(p);

[sanjoy1, 2012/05/25 20:32:44]

The nodes are deleted using Deallocator::Delete, which sees a void pointer. 
Thus, the delete method of a Node should never be called.

     }
 
     Key key() { return key_; }
@@ -183,17 +192,21 @@ class SplayTree {
 
   class NodeDeleter BASE_EMBEDDED {
    public:
-    NodeDeleter() { }
-    void Call(Node* node) { delete node; }
+    explicit NodeDeleter(Deallocator deallocator) : deallocator_(deallocator) {
+    }
+    void Call(Node* node) {  deallocator_.Delete(node); }
 
    private:
+    Deallocator deallocator_;
+
     DISALLOW_COPY_AND_ASSIGN(NodeDeleter);
   };
 
   template <class Callback>
-  void ForEachNode(Callback* callback);
+  void ForEachNode(Callback* callback, Allocator allocator = Allocator());
 
   Node* root_;
+  Deallocator deallocator_;

[danno, 2012/05/25 11:03:37]

I don't think you ever need to store the Deallocator as a member. I think we
must be able to always call the Deallocator constructor with no arguments.

[sanjoy1, 2012/05/25 20:32:44]

I need to store it in case the we're using the
PreallocatedStorageAllocationPolicy and want to have the isolate around for
deletion without a TLS lookup.  Right now it does a TLS lookup.

As long as the destructor doesn't do anything funny, I think we should be able
to reinterpret_cast the void* in the object's `operator delete' to a pointer to
the object, extract the deallocator and call the Destroy (of the Deallocator
instance) method on the pointer.

 
   DISALLOW_COPY_AND_ASSIGN(SplayTree);
 };