| OLD | NEW |
| 1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 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 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 51 // template <typename Config, class Allocator = FreeStoreAllocationPolicy> | 51 // template <typename Config, class Allocator = FreeStoreAllocationPolicy> |
| 52 // class SplayTree; | 52 // class SplayTree; |
| 53 template <typename Config, class AllocationPolicy> | 53 template <typename Config, class AllocationPolicy> |
| 54 class SplayTree { | 54 class SplayTree { |
| 55 public: | 55 public: |
| 56 typedef typename Config::Key Key; | 56 typedef typename Config::Key Key; |
| 57 typedef typename Config::Value Value; | 57 typedef typename Config::Value Value; |
| 58 | 58 |
| 59 class Locator; | 59 class Locator; |
| 60 | 60 |
| 61 SplayTree() : root_(NULL) { } | 61 SplayTree(AllocationPolicy allocator = AllocationPolicy()) |
| 62 : root_(NULL), allocator_(allocator) { } |
| 62 ~SplayTree(); | 63 ~SplayTree(); |
| 63 | 64 |
| 64 INLINE(void* operator new(size_t size, | 65 INLINE(void* operator new(size_t size, |
| 65 AllocationPolicy allocator = AllocationPolicy())) { | 66 AllocationPolicy allocator = AllocationPolicy())) { |
| 66 return allocator.New(static_cast<int>(size)); | 67 return allocator.New(static_cast<int>(size)); |
| 67 } | 68 } |
| 68 INLINE(void operator delete(void* p, size_t)) { | 69 INLINE(void operator delete(void* p, size_t)) { |
| 69 AllocationPolicy::Delete(p); | 70 AllocationPolicy::Delete(p); |
| 70 } | 71 } |
| 71 | 72 |
| 72 // Inserts the given key in this tree with the given value. Returns | 73 // Inserts the given key in this tree with the given value. Returns |
| 73 // true if a node was inserted, otherwise false. If found the locator | 74 // true if a node was inserted, otherwise false. If found the locator |
| 74 // is enabled and provides access to the mapping for the key. | 75 // is enabled and provides access to the mapping for the key. |
| 75 bool Insert(const Key& key, Locator* locator, | 76 bool Insert(const Key& key, Locator* locator); |
| 76 AllocationPolicy allocator = AllocationPolicy()); | |
| 77 | 77 |
| 78 // Looks up the key in this tree and returns true if it was found, | 78 // Looks up the key in this tree and returns true if it was found, |
| 79 // otherwise false. If the node is found the locator is enabled and | 79 // otherwise false. If the node is found the locator is enabled and |
| 80 // provides access to the mapping for the key. | 80 // provides access to the mapping for the key. |
| 81 bool Find(const Key& key, Locator* locator); | 81 bool Find(const Key& key, Locator* locator); |
| 82 | 82 |
| 83 // Finds the mapping with the greatest key less than or equal to the | 83 // Finds the mapping with the greatest key less than or equal to the |
| 84 // given key. | 84 // given key. |
| 85 bool FindGreatestLessThan(const Key& key, Locator* locator); | 85 bool FindGreatestLessThan(const Key& key, Locator* locator); |
| 86 | 86 |
| (...skipping 101 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 188 class NodeDeleter BASE_EMBEDDED { | 188 class NodeDeleter BASE_EMBEDDED { |
| 189 public: | 189 public: |
| 190 NodeDeleter() { } | 190 NodeDeleter() { } |
| 191 void Call(Node* node) { AllocationPolicy::Delete(node); } | 191 void Call(Node* node) { AllocationPolicy::Delete(node); } |
| 192 | 192 |
| 193 private: | 193 private: |
| 194 DISALLOW_COPY_AND_ASSIGN(NodeDeleter); | 194 DISALLOW_COPY_AND_ASSIGN(NodeDeleter); |
| 195 }; | 195 }; |
| 196 | 196 |
| 197 template <class Callback> | 197 template <class Callback> |
| 198 void ForEachNode(Callback* callback, | 198 void ForEachNode(Callback* callback); |
| 199 AllocationPolicy allocator = AllocationPolicy()); | |
| 200 | 199 |
| 201 Node* root_; | 200 Node* root_; |
| 201 AllocationPolicy allocator_; |
| 202 | 202 |
| 203 DISALLOW_COPY_AND_ASSIGN(SplayTree); | 203 DISALLOW_COPY_AND_ASSIGN(SplayTree); |
| 204 }; | 204 }; |
| 205 | 205 |
| 206 | 206 |
| 207 } } // namespace v8::internal | 207 } } // namespace v8::internal |
| 208 | 208 |
| 209 #endif // V8_SPLAY_TREE_H_ | 209 #endif // V8_SPLAY_TREE_H_ |
| OLD | NEW |