kernel/util/SplayTree.h

30 		static int Compare(const KeyType& key, const NodeType* node);
74 		Key key = Definition::GetKey(node);
75 		_Splay(key);
77 		int c = Definition::Compare(key, fRoot);
97 	Node* Remove(const Key& key)
102 		_Splay(key);
104 		if (Definition::Compare(key, fRoot) != 0)
115 			_Splay(key);
128 		Key key = Definition::GetKey(node);
129 		_Splay(key);
141 			_Splay(key);
187 	Node* Lookup(const Key& key)
192 		_Splay(key);
194 		return Definition::Compare(key, fRoot) == 0 ? fRoot : NULL;
211 	Node* PreviousDontSplay(const Key& key) const
216 			if (Definition::Compare(key, node) > 0) {
226 	Node* FindClosest(const Key& key, bool greater, bool orEqual)
231 		_Splay(key);
236 			int compare = Definition::Compare(key, node);
268 		_Splay(key) does the splay operation on the given key.
269 		If key is in the tree, then the node containing
270 		that key becomes the root. If key is not in the tree,
271 		then after the splay, key.root is either the greatest key
272 		< key in the tree, or the least key > key in the tree.
275 		a key that's larger than any in the tree, the rightmost
279 	void _Splay(const Key& key) {
291 			int c = Definition::Compare(key, t);
297 				if (Definition::Compare(key, left) < 0) {
318 				if (Definition::Compare(key, right) > 0) {
514 	Node* Remove(const Key& key)
516 		Node* node = fTree.Remove(key);
521 		if (Node* previous = fTree.PreviousDontSplay(key))
547 	Node* Lookup(const Key& key)
549 		return fTree.Lookup(key);
566 	Node* FindClosest(const Key& key, bool greater, bool orEqual)
568 		return fTree.FindClosest(key, greater, orEqual);
591 	Iterator GetIterator(const Key& key, bool greater, bool orEqual)
593 		return Iterator(this, fTree.FindClosest(key, greater, orEqual));
596 	ConstIterator GetIterator(const Key& key, bool greater, bool orEqual) const
598 		return ConstIterator(this, FindClosest(key, greater, orEqual));