diff options
author | Ryan <ry@tinyclouds.org> | 2009-07-31 14:36:48 +0200 |
---|---|---|
committer | Ryan <ry@tinyclouds.org> | 2009-07-31 14:36:48 +0200 |
commit | 2ebd6921510f9efbf1ef7eb6988ccecac25ee988 (patch) | |
tree | 796b2b414a20bd2e6b4b43323ea149894115a8c3 /deps/v8/src/zone.h | |
parent | 5373c6869a8410e9a00771be09bc74cd17e9c843 (diff) | |
download | node-2ebd6921510f9efbf1ef7eb6988ccecac25ee988.tar.gz |
Upgrade V8 to 1.3.1
Diffstat (limited to 'deps/v8/src/zone.h')
-rw-r--r-- | deps/v8/src/zone.h | 102 |
1 files changed, 102 insertions, 0 deletions
diff --git a/deps/v8/src/zone.h b/deps/v8/src/zone.h index a8b26e9fd..cdbab3282 100644 --- a/deps/v8/src/zone.h +++ b/deps/v8/src/zone.h @@ -204,6 +204,108 @@ class ZoneScope BASE_EMBEDDED { }; +template <typename Node, class Callback> +static void DoForEach(Node* node, Callback* callback); + + +// 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 +// +template <typename Config> +class ZoneSplayTree : public ZoneObject { + 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* c) { + DoForEach<typename ZoneSplayTree<Config>::Node, Callback>(root_, c); + } + + private: + Node* root_; +}; + + } } // namespace v8::internal #endif // V8_ZONE_H_ |