kernel/util/SplayTree.h

18 	cheaply iteratable (requires another pointer per node).
27 		static const KeyType& GetKey(const NodeType* node);
28 		static SplayTreeLink<NodeType>* GetLink(NodeType* node);
30 		static int Compare(const KeyType& key, const NodeType* node);
33 		static NodeType** GetListLink(NodeType* node);
61 		\param node the item to insert.
63 	bool Insert(Node* node)
65 		Link* nodeLink = Definition::GetLink(node);
68 			fRoot = node;
74 		Key key = Definition::GetKey(node);
93 		fRoot = node;
108 		Node* node = fRoot;
119 		return node;
124 		\param node the item to remove.
126 	bool Remove(Node* node)
128 		Key key = Definition::GetKey(node);
131 		if (node != fRoot)
156 		Node* node = fRoot;
158 		while (Node* left = Definition::GetLink(node)->left)
159 			node = left;
161 		_Splay(Definition::GetKey(node));
163 		return node;
174 		Node* node = fRoot;
176 		while (Node* right = Definition::GetLink(node)->right)
177 			node = right;
179 		_Splay(Definition::GetKey(node));
181 		return node;
214 		Node* node = fRoot;
215 		while (node != NULL) {
216 			if (Definition::Compare(key, node) > 0) {
217 				closestNode = node;
218 				node = Definition::GetLink(node)->right;
220 				node = Definition::GetLink(node)->left;
234 		Node* node = fRoot;
235 		while (node != NULL) {
236 			int compare = Definition::Compare(key, node);
238 				return node;
242 					closestNode = node;
243 					node = Definition::GetLink(node)->left;
245 					node = Definition::GetLink(node)->right;
248 					closestNode = node;
249 					node = Definition::GetLink(node)->right;
251 					node = Definition::GetLink(node)->left;
269 		If key is in the tree, then the node containing
276 		node of the tree becomes the root. This property is used
467 			Node* node = fNext;
470 			return node;
497 	bool Insert(Node* node)
499 		if (!fTree.Insert(node))
503 		if (Node* previous = fTree.PreviousDontSplay(Definition::GetKey(node)))
508 		*Definition::GetListLink(node) = *previousNext;
509 		*previousNext = node;
516 		Node* node = fTree.Remove(key);
517 		if (node == NULL)
526 		*previousNext = *Definition::GetListLink(node);
528 		return node;
531 	bool Remove(Node* node)
533 		if (!fTree.Remove(node))
537 		if (Node* previous = fTree.PreviousDontSplay(Definition::GetKey(node)))
542 		*previousNext = *Definition::GetListLink(node);