Split an allocation policy into an allocator and a deallocator.

src/splay-tree.h

 // Copyright 2010 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 32 matching lines @@
 //   static const kNoValue: the dummy value used to initialize nodes
 //   int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function
 //
 // The tree is also parameterized by an allocation policy
 // (Allocator). The policy is used for allocating lists in the C free
 // store or the zone; see zone.h.
 
 // Forward defined as
 // template <typename Config, class Allocator = FreeStoreAllocationPolicy>
 //     class SplayTree;
-template <typename Config, class Allocator>
+template <typename Config, class AllocationPolicy>
 class SplayTree {
  public:
   typedef typename Config::Key Key;
   typedef typename Config::Value Value;
 
+  typedef typename AllocationPolicy::Allocator Allocator;
+  typedef typename AllocationPolicy::Deallocator 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)) { return Allocator::Delete(p); }
+  INLINE(void operator delete(void* ptr, size_t size)) {
+    reinterpret_cast<SplayTree*>(ptr)->deallocator_.Delete(ptr);
+  }
 
   // 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
   // provides access to the mapping for the key.
   bool Find(const Key& key, Locator* locator);
 
   // Finds the mapping with the greatest key less than or equal to the
   // given key.
   bool FindGreatestLessThan(const Key& key, Locator* locator);
 
@@ skipping 22 matching lines @@
   void Splay(const Key& key);
 
   class Node {
    public:
     Node(const Key& key, const Value& value)
         : key_(key),
           value_(value),
           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/31 11:03:36]

Hmmm. This still seems dangerous. It seems to introduce unnecessary asymmetry.

     }
 
     Key key() { return key_; }
     Value value() { return value_; }
     Node* left() { return left_; }
     Node* right() { return right_; }
 
    private:
     friend class SplayTree;
     friend class Locator;
     Key key_;
     Value value_;
     Node* left_;
     Node* right_;

[danno, 2012/05/31 11:03:36]

I think the cleanest way is to make sure Deallocator is a member here.

   };
 
   // A locator provides access to a node in the tree without actually
   // exposing the node.
   class Locator BASE_EMBEDDED {
    public:
     explicit Locator(Node* node) : node_(node) { }
     Locator() : node_(NULL) { }
     const Key& key() { return node_->key_; }
     Value& value() { return node_->value_; }
@@ skipping 32 matching lines @@
     }
 
    private:
     Callback* callback_;
 
     DISALLOW_COPY_AND_ASSIGN(NodeToPairAdaptor);
   };
 
   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_;
 
   DISALLOW_COPY_AND_ASSIGN(SplayTree);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_SPLAY_TREE_H_