1 /* 2 * Copyright 2003-2009, Ingo Weinhold <ingo_weinhold@gmx.de>. 3 * Distributed under the terms of the MIT License. 4 */ 5 #ifndef _KERNEL_UTIL_AVL_TREE_BASE_H 6 #define _KERNEL_UTIL_AVL_TREE_BASE_H 7 8 9 #ifndef FS_SHELL 10 # include <SupportDefs.h> 11 #else 12 # include "fssh_api_wrapper.h" 13 #endif 14 15 16 class AVLTreeIterator; 17 18 19 struct AVLTreeNode { 20 AVLTreeNode* parent; 21 AVLTreeNode* left; 22 AVLTreeNode* right; 23 int balance_factor; 24 }; 25 26 27 class AVLTreeCompare { 28 public: 29 virtual ~AVLTreeCompare(); 30 31 virtual int CompareKeyNode(const void* key, 32 const AVLTreeNode* node) = 0; 33 virtual int CompareNodes(const AVLTreeNode* node1, 34 const AVLTreeNode* node2) = 0; 35 }; 36 37 38 class AVLTreeBase { 39 public: 40 AVLTreeBase(AVLTreeCompare* compare); 41 ~AVLTreeBase(); 42 43 inline int Count() const { return fNodeCount; } 44 inline bool IsEmpty() const { return (fNodeCount == 0); } 45 void MakeEmpty(); 46 47 inline AVLTreeNode* Root() const { return fRoot; } 48 49 inline AVLTreeNode* LeftMost() const; 50 AVLTreeNode* LeftMost(AVLTreeNode* node) const; 51 inline AVLTreeNode* RightMost() const; 52 AVLTreeNode* RightMost(AVLTreeNode* node) const; 53 54 AVLTreeNode* Previous(AVLTreeNode* node) const; 55 AVLTreeNode* Next(AVLTreeNode* node) const; 56 57 inline AVLTreeIterator GetIterator() const; 58 inline AVLTreeIterator GetIterator(AVLTreeNode* node) const; 59 60 AVLTreeNode* Find(const void* key) const; 61 AVLTreeNode* FindClosest(const void* key, bool less) const; 62 63 status_t Insert(AVLTreeNode* element); 64 AVLTreeNode* Remove(const void* key); 65 bool Remove(AVLTreeNode* element); 66 67 void CheckTree() const; 68 69 private: 70 enum { 71 NOT_FOUND = -3, 72 DUPLICATE = -2, 73 NO_MEMORY = -1, 74 OK = 0, 75 HEIGHT_CHANGED = 1, 76 77 LEFT = -1, 78 BALANCED = 0, 79 RIGHT = 1, 80 }; 81 82 // rotations 83 void _RotateRight(AVLTreeNode** nodeP); 84 void _RotateLeft(AVLTreeNode** nodeP); 85 86 // insert 87 int _BalanceInsertLeft(AVLTreeNode** node); 88 int _BalanceInsertRight(AVLTreeNode** node); 89 int _Insert(AVLTreeNode* nodeToInsert); 90 91 // remove 92 int _BalanceRemoveLeft(AVLTreeNode** node); 93 int _BalanceRemoveRight(AVLTreeNode** node); 94 int _RemoveRightMostChild(AVLTreeNode** node, 95 AVLTreeNode** foundNode); 96 int _Remove(AVLTreeNode* node); 97 98 int _CheckTree(AVLTreeNode* parent, 99 AVLTreeNode* node, int& _nodeCount) const; 100 101 AVLTreeNode* fRoot; 102 int fNodeCount; 103 AVLTreeCompare* fCompare; 104 }; 105 106 107 // AVLTreeIterator 108 class AVLTreeIterator { 109 public: 110 inline AVLTreeIterator() 111 : 112 fParent(NULL), 113 fCurrent(NULL), 114 fNext(NULL) 115 { 116 } 117 118 inline AVLTreeIterator(const AVLTreeIterator& other) 119 : 120 fParent(other.fParent), 121 fCurrent(other.fCurrent), 122 fNext(other.fNext) 123 { 124 } 125 126 inline AVLTreeNode* Current() const 127 { 128 return fCurrent; 129 } 130 131 inline bool HasNext() const 132 { 133 return fNext; 134 } 135 136 inline AVLTreeNode* Next() 137 { 138 fCurrent = fNext; 139 140 if (fNext) 141 fNext = fParent->Next(fNext); 142 143 return fCurrent; 144 } 145 146 inline AVLTreeNode* Previous() 147 { 148 if (fCurrent) { 149 fNext = fCurrent; 150 fCurrent = fParent->Previous(fCurrent); 151 } else if (fNext) 152 fCurrent = fParent->Previous(fNext); 153 154 return fCurrent; 155 } 156 157 inline AVLTreeNode* Remove() 158 { 159 if (!fCurrent) 160 return NULL; 161 162 AVLTreeNode* node = fCurrent; 163 fCurrent = NULL; 164 165 return (const_cast<AVLTreeBase*>(fParent)->Remove(node) ? node : NULL); 166 } 167 168 inline AVLTreeIterator& operator=(const AVLTreeIterator& other) 169 { 170 fParent = other.fParent; 171 fCurrent = other.fCurrent; 172 fNext = other.fNext; 173 return *this; 174 } 175 176 private: 177 inline AVLTreeIterator(const AVLTreeBase* parent, AVLTreeNode* current, 178 AVLTreeNode* next) 179 : 180 fParent(parent), 181 fCurrent(current), 182 fNext(next) 183 { 184 } 185 186 protected: 187 friend class AVLTreeBase; 188 189 const AVLTreeBase* fParent; 190 AVLTreeNode* fCurrent; 191 AVLTreeNode* fNext; 192 }; 193 194 195 inline AVLTreeNode* 196 AVLTreeBase::LeftMost() const 197 { 198 return LeftMost(fRoot); 199 } 200 201 202 inline AVLTreeNode* 203 AVLTreeBase::RightMost() const 204 { 205 return RightMost(fRoot); 206 } 207 208 209 // GetIterator 210 inline AVLTreeIterator 211 AVLTreeBase::GetIterator() const 212 { 213 return AVLTreeIterator(this, NULL, LeftMost()); 214 } 215 216 217 // GetIterator 218 inline AVLTreeIterator 219 AVLTreeBase::GetIterator(AVLTreeNode* node) const 220 { 221 return AVLTreeIterator(this, node, Next(node)); 222 } 223 224 225 #endif // _KERNEL_UTIL_AVL_TREE_BASE_H 226