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 |