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 21 matching lines...) Expand all Loading... |
32 | 32 |
33 namespace v8 { | 33 namespace v8 { |
34 namespace internal { | 34 namespace internal { |
35 | 35 |
36 | 36 |
37 // A splay tree. The config type parameter encapsulates the different | 37 // A splay tree. The config type parameter encapsulates the different |
38 // configurations of a concrete splay tree: | 38 // configurations of a concrete splay tree: |
39 // | 39 // |
40 // typedef Key: the key type | 40 // typedef Key: the key type |
41 // typedef Value: the value type | 41 // typedef Value: the value type |
42 // static const Key kNoKey: the dummy key used when no key is set | 42 // static const kNoKey: the dummy key used when no key is set |
43 // static Value kNoValue(): the dummy value used to initialize nodes | 43 // static const kNoValue: the dummy value used to initialize nodes |
44 // static int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function | 44 // int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function |
45 // | 45 // |
46 // The tree is also parameterized by an allocation policy | 46 // The tree is also parameterized by an allocation policy |
47 // (Allocator). The policy is used for allocating lists in the C free | 47 // (Allocator). The policy is used for allocating lists in the C free |
48 // store or the zone; see zone.h. | 48 // store or the zone; see zone.h. |
49 | 49 |
50 // Forward defined as | 50 // Forward defined as |
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 { |
(...skipping 12 matching lines...) Expand all Loading... |
67 return allocator.New(static_cast<int>(size)); | 67 return allocator.New(static_cast<int>(size)); |
68 } | 68 } |
69 INLINE(void operator delete(void* p)) { | 69 INLINE(void operator delete(void* p)) { |
70 AllocationPolicy::Delete(p); | 70 AllocationPolicy::Delete(p); |
71 } | 71 } |
72 // Please the MSVC compiler. We should never have to execute this. | 72 // Please the MSVC compiler. We should never have to execute this. |
73 INLINE(void operator delete(void* p, AllocationPolicy policy)) { | 73 INLINE(void operator delete(void* p, AllocationPolicy policy)) { |
74 UNREACHABLE(); | 74 UNREACHABLE(); |
75 } | 75 } |
76 | 76 |
77 AllocationPolicy allocator() { return allocator_; } | |
78 | |
79 // Checks if there is a mapping for the key. | |
80 bool Contains(const Key& key); | |
81 | |
82 // Inserts the given key in this tree with the given value. Returns | 77 // Inserts the given key in this tree with the given value. Returns |
83 // true if a node was inserted, otherwise false. If found the locator | 78 // true if a node was inserted, otherwise false. If found the locator |
84 // is enabled and provides access to the mapping for the key. | 79 // is enabled and provides access to the mapping for the key. |
85 bool Insert(const Key& key, Locator* locator); | 80 bool Insert(const Key& key, Locator* locator); |
86 | 81 |
87 // Looks up the key in this tree and returns true if it was found, | 82 // Looks up the key in this tree and returns true if it was found, |
88 // otherwise false. If the node is found the locator is enabled and | 83 // otherwise false. If the node is found the locator is enabled and |
89 // provides access to the mapping for the key. | 84 // provides access to the mapping for the key. |
90 bool Find(const Key& key, Locator* locator); | 85 bool Find(const Key& key, Locator* locator); |
91 | 86 |
(...skipping 10 matching lines...) Expand all Loading... |
102 | 97 |
103 // Find the mapping with the least key in this tree. | 98 // Find the mapping with the least key in this tree. |
104 bool FindLeast(Locator* locator); | 99 bool FindLeast(Locator* locator); |
105 | 100 |
106 // Move the node from one key to another. | 101 // Move the node from one key to another. |
107 bool Move(const Key& old_key, const Key& new_key); | 102 bool Move(const Key& old_key, const Key& new_key); |
108 | 103 |
109 // Remove the node with the given key from the tree. | 104 // Remove the node with the given key from the tree. |
110 bool Remove(const Key& key); | 105 bool Remove(const Key& key); |
111 | 106 |
112 // Remove all keys from the tree. | |
113 void Clear() { ResetRoot(); } | |
114 | |
115 bool is_empty() { return root_ == NULL; } | 107 bool is_empty() { return root_ == NULL; } |
116 | 108 |
117 // Perform the splay operation for the given key. Moves the node with | 109 // Perform the splay operation for the given key. Moves the node with |
118 // the given key to the top of the tree. If no node has the given | 110 // the given key to the top of the tree. If no node has the given |
119 // key, the last node on the search path is moved to the top of the | 111 // key, the last node on the search path is moved to the top of the |
120 // tree. | 112 // tree. |
121 void Splay(const Key& key); | 113 void Splay(const Key& key); |
122 | 114 |
123 class Node { | 115 class Node { |
124 public: | 116 public: |
(...skipping 92 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
217 Node* root_; | 209 Node* root_; |
218 AllocationPolicy allocator_; | 210 AllocationPolicy allocator_; |
219 | 211 |
220 DISALLOW_COPY_AND_ASSIGN(SplayTree); | 212 DISALLOW_COPY_AND_ASSIGN(SplayTree); |
221 }; | 213 }; |
222 | 214 |
223 | 215 |
224 } } // namespace v8::internal | 216 } } // namespace v8::internal |
225 | 217 |
226 #endif // V8_SPLAY_TREE_H_ | 218 #endif // V8_SPLAY_TREE_H_ |
OLD | NEW |