OLD | NEW |
1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 186 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
197 } | 197 } |
198 | 198 |
199 static int nesting() { return nesting_; } | 199 static int nesting() { return nesting_; } |
200 | 200 |
201 private: | 201 private: |
202 ZoneScopeMode mode_; | 202 ZoneScopeMode mode_; |
203 static int nesting_; | 203 static int nesting_; |
204 }; | 204 }; |
205 | 205 |
206 | 206 |
| 207 template <typename Node, class Callback> |
| 208 static void DoForEach(Node* node, Callback* callback); |
| 209 |
| 210 |
| 211 // A zone splay tree. The config type parameter encapsulates the |
| 212 // different configurations of a concrete splay tree: |
| 213 // |
| 214 // typedef Key: the key type |
| 215 // typedef Value: the value type |
| 216 // static const kNoKey: the dummy key used when no key is set |
| 217 // static const kNoValue: the dummy value used to initialize nodes |
| 218 // int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function |
| 219 // |
| 220 template <typename Config> |
| 221 class ZoneSplayTree : public ZoneObject { |
| 222 public: |
| 223 typedef typename Config::Key Key; |
| 224 typedef typename Config::Value Value; |
| 225 |
| 226 class Locator; |
| 227 |
| 228 ZoneSplayTree() : root_(NULL) { } |
| 229 |
| 230 // Inserts the given key in this tree with the given value. Returns |
| 231 // true if a node was inserted, otherwise false. If found the locator |
| 232 // is enabled and provides access to the mapping for the key. |
| 233 bool Insert(const Key& key, Locator* locator); |
| 234 |
| 235 // Looks up the key in this tree and returns true if it was found, |
| 236 // otherwise false. If the node is found the locator is enabled and |
| 237 // provides access to the mapping for the key. |
| 238 bool Find(const Key& key, Locator* locator); |
| 239 |
| 240 // Finds the mapping with the greatest key less than or equal to the |
| 241 // given key. |
| 242 bool FindGreatestLessThan(const Key& key, Locator* locator); |
| 243 |
| 244 // Find the mapping with the greatest key in this tree. |
| 245 bool FindGreatest(Locator* locator); |
| 246 |
| 247 // Finds the mapping with the least key greater than or equal to the |
| 248 // given key. |
| 249 bool FindLeastGreaterThan(const Key& key, Locator* locator); |
| 250 |
| 251 // Find the mapping with the least key in this tree. |
| 252 bool FindLeast(Locator* locator); |
| 253 |
| 254 // Remove the node with the given key from the tree. |
| 255 bool Remove(const Key& key); |
| 256 |
| 257 bool is_empty() { return root_ == NULL; } |
| 258 |
| 259 // Perform the splay operation for the given key. Moves the node with |
| 260 // the given key to the top of the tree. If no node has the given |
| 261 // key, the last node on the search path is moved to the top of the |
| 262 // tree. |
| 263 void Splay(const Key& key); |
| 264 |
| 265 class Node : public ZoneObject { |
| 266 public: |
| 267 Node(const Key& key, const Value& value) |
| 268 : key_(key), |
| 269 value_(value), |
| 270 left_(NULL), |
| 271 right_(NULL) { } |
| 272 Key key() { return key_; } |
| 273 Value value() { return value_; } |
| 274 Node* left() { return left_; } |
| 275 Node* right() { return right_; } |
| 276 private: |
| 277 friend class ZoneSplayTree; |
| 278 friend class Locator; |
| 279 Key key_; |
| 280 Value value_; |
| 281 Node* left_; |
| 282 Node* right_; |
| 283 }; |
| 284 |
| 285 // A locator provides access to a node in the tree without actually |
| 286 // exposing the node. |
| 287 class Locator { |
| 288 public: |
| 289 explicit Locator(Node* node) : node_(node) { } |
| 290 Locator() : node_(NULL) { } |
| 291 const Key& key() { return node_->key_; } |
| 292 Value& value() { return node_->value_; } |
| 293 void set_value(const Value& value) { node_->value_ = value; } |
| 294 inline void bind(Node* node) { node_ = node; } |
| 295 private: |
| 296 Node* node_; |
| 297 }; |
| 298 |
| 299 template <class Callback> |
| 300 void ForEach(Callback* c) { |
| 301 DoForEach<typename ZoneSplayTree<Config>::Node, Callback>(root_, c); |
| 302 } |
| 303 |
| 304 private: |
| 305 Node* root_; |
| 306 }; |
| 307 |
| 308 |
207 } } // namespace v8::internal | 309 } } // namespace v8::internal |
208 | 310 |
209 #endif // V8_ZONE_H_ | 311 #endif // V8_ZONE_H_ |
OLD | NEW |