Parametrize C++ splay tree with allocator.

src/zone.h

 // Copyright 2006-2008 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 187 matching lines @@
 
   static int nesting() { return nesting_; }
 
  private:
   ZoneScopeMode mode_;
   static int nesting_;
 };
 
 
 // A zone splay tree.  The config type parameter encapsulates the
-// different configurations of a concrete splay tree:
-//
-//   typedef Key: the key type
-//   typedef Value: the value type
-//   static const kNoKey: the dummy key used when no key is set
-//   static const kNoValue: the dummy value used to initialize nodes
-//   int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function
-//
+// different configurations of a concrete splay tree (see splay-tree.h).
+// The tree itself and all its elements are allocated in the Zone.
 template <typename Config>
-class ZoneSplayTree : public ZoneObject {
+class ZoneSplayTree: public SplayTree<Config, ZoneListAllocationPolicy> {
  public:
-  typedef typename Config::Key Key;
-  typedef typename Config::Value Value;
-
-  class Locator;
-
-  ZoneSplayTree() : root_(NULL) { }
-
-  // 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);
-
-  // 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);
-
-  // Find the mapping with the greatest key in this tree.
-  bool FindGreatest(Locator* locator);
-
-  // Finds the mapping with the least key greater than or equal to the
-  // given key.
-  bool FindLeastGreaterThan(const Key& key, Locator* locator);
-
-  // Find the mapping with the least key in this tree.
-  bool FindLeast(Locator* locator);
-
-  // Remove the node with the given key from the tree.
-  bool Remove(const Key& key);
-
-  bool is_empty() { return root_ == NULL; }
-
-  // Perform the splay operation for the given key. Moves the node with
-  // the given key to the top of the tree.  If no node has the given
-  // key, the last node on the search path is moved to the top of the
-  // tree.
-  void Splay(const Key& key);
-
-  class Node : public ZoneObject {
-   public:
-    Node(const Key& key, const Value& value)
-        : key_(key),
-          value_(value),
-          left_(NULL),
-          right_(NULL) { }
-    Key key() { return key_; }
-    Value value() { return value_; }
-    Node* left() { return left_; }
-    Node* right() { return right_; }
-   private:
-    friend class ZoneSplayTree;
-    friend class Locator;
-    Key key_;
-    Value value_;
-    Node* left_;
-    Node* right_;
-  };
-
-  // A locator provides access to a node in the tree without actually
-  // exposing the node.
-  class Locator {
-   public:
-    explicit Locator(Node* node) : node_(node) { }
-    Locator() : node_(NULL) { }
-    const Key& key() { return node_->key_; }
-    Value& value() { return node_->value_; }
-    void set_value(const Value& value) { node_->value_ = value; }
-    inline void bind(Node* node) { node_ = node; }
-   private:
-    Node* node_;
-  };
-
-  template <class Callback>
-  void ForEach(Callback* callback);
-
- private:
-  Node* root_;
+  ZoneSplayTree()
+      : SplayTree<Config, ZoneListAllocationPolicy>() {}
+  ~ZoneSplayTree();
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_ZONE_H_