kernel/util/AVLTreeBase.h

19 struct AVLTreeNode {
20 	AVLTreeNode*	parent;
21 	AVLTreeNode*	left;
22 	AVLTreeNode*	right;
32 									const AVLTreeNode* node) = 0;
33 	virtual	int					CompareNodes(const AVLTreeNode* node1,
34 									const AVLTreeNode* node2) = 0;
47 	inline	AVLTreeNode*		Root() const	{ return fRoot; }
49 	inline	AVLTreeNode*		LeftMost() const;
50 			AVLTreeNode*		LeftMost(AVLTreeNode* node) const;
51 	inline	AVLTreeNode*		RightMost() const;
52 			AVLTreeNode*		RightMost(AVLTreeNode* node) const;
54 			AVLTreeNode*		Previous(AVLTreeNode* node) const;
55 			AVLTreeNode*		Next(AVLTreeNode* node) const;
58 	inline	AVLTreeIterator		GetIterator(AVLTreeNode* node) const;
60 			AVLTreeNode*		Find(const void* key) const;
61 			AVLTreeNode*		FindClosest(const void* key, bool less) const;
63 			status_t			Insert(AVLTreeNode* element);
64 			AVLTreeNode*		Remove(const void* key);
65 			bool				Remove(AVLTreeNode* element);
83 			void				_RotateRight(AVLTreeNode** nodeP);
84 			void				_RotateLeft(AVLTreeNode** nodeP);
87 			int					_BalanceInsertLeft(AVLTreeNode** node);
88 			int					_BalanceInsertRight(AVLTreeNode** node);
89 			int					_Insert(AVLTreeNode* nodeToInsert);
92 			int					_BalanceRemoveLeft(AVLTreeNode** node);
93 			int					_BalanceRemoveRight(AVLTreeNode** node);
94 			int					_RemoveRightMostChild(AVLTreeNode** node,
95 									AVLTreeNode** foundNode);
96 			int					_Remove(AVLTreeNode* node);
98 			int					_CheckTree(AVLTreeNode* parent,
99 									AVLTreeNode* node, int& _nodeCount) const;
101 			AVLTreeNode*		fRoot;
126 	inline AVLTreeNode* Current() const
136 	inline AVLTreeNode* Next()
146 	inline AVLTreeNode* Previous()
157 	inline AVLTreeNode* Remove()
162 		AVLTreeNode* node = fCurrent;
177 	inline AVLTreeIterator(const AVLTreeBase* parent, AVLTreeNode* current,
178 			AVLTreeNode* next)
190 	AVLTreeNode*		fCurrent;
191 	AVLTreeNode*		fNext;
195 inline AVLTreeNode*
202 inline AVLTreeNode*
219 AVLTreeBase::GetIterator(AVLTreeNode* node) const