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 AVLTreeNode* LeftMost(AVLTreeNode* node) const; 50 AVLTreeNode* RightMost(AVLTreeNode* node) const; 51 52 AVLTreeNode* Previous(AVLTreeNode* node) const; 53 AVLTreeNode* Next(AVLTreeNode* node) const; 54 55 inline AVLTreeIterator GetIterator() const; 56 inline AVLTreeIterator GetIterator(AVLTreeNode* node) const; 57 58 AVLTreeNode* Find(const void* key) const; 59 AVLTreeNode* FindClosest(const void* key, bool less) const; 60 61 status_t Insert(AVLTreeNode* element); 62 AVLTreeNode* Remove(const void* key); 63 bool Remove(AVLTreeNode* element); 64 65 void CheckTree() const; 66 67 private: 68 enum { 69 NOT_FOUND = -3, 70 DUPLICATE = -2, 71 NO_MEMORY = -1, 72 OK = 0, 73 HEIGHT_CHANGED = 1, 74 75 LEFT = -1, 76 BALANCED = 0, 77 RIGHT = 1, 78 }; 79 80 // rotations 81 void _RotateRight(AVLTreeNode** nodeP); 82 void _RotateLeft(AVLTreeNode** nodeP); 83 84 // insert 85 int _BalanceInsertLeft(AVLTreeNode** node); 86 int _BalanceInsertRight(AVLTreeNode** node); 87 int _Insert(AVLTreeNode* nodeToInsert); 88 89 // remove 90 int _BalanceRemoveLeft(AVLTreeNode** node); 91 int _BalanceRemoveRight(AVLTreeNode** node); 92 int _RemoveRightMostChild(AVLTreeNode** node, 93 AVLTreeNode** foundNode); 94 int _Remove(AVLTreeNode* node); 95 96 int _CheckTree(AVLTreeNode* parent, 97 AVLTreeNode* node, int& _nodeCount) const; 98 99 AVLTreeNode* fRoot; 100 int fNodeCount; 101 AVLTreeCompare* fCompare; 102 }; 103 104 105 // AVLTreeIterator 106 class AVLTreeIterator { 107 public: 108 inline AVLTreeIterator() 109 : 110 fParent(NULL), 111 fCurrent(NULL), 112 fNext(NULL) 113 { 114 } 115 116 inline AVLTreeIterator(const AVLTreeIterator& other) 117 : 118 fParent(other.fParent), 119 fCurrent(other.fCurrent), 120 fNext(other.fNext) 121 { 122 } 123 124 inline AVLTreeNode* Current() const 125 { 126 return fCurrent; 127 } 128 129 inline bool HasNext() const 130 { 131 return fNext; 132 } 133 134 inline AVLTreeNode* Next() 135 { 136 fCurrent = fNext; 137 138 if (fNext) 139 fNext = fParent->Next(fNext); 140 141 return fCurrent; 142 } 143 144 inline AVLTreeNode* Previous() 145 { 146 if (fCurrent) { 147 fNext = fCurrent; 148 fCurrent = fParent->Previous(fCurrent); 149 } else if (fNext) 150 fCurrent = fParent->Previous(fNext); 151 152 return fCurrent; 153 } 154 155 inline AVLTreeNode* Remove() 156 { 157 if (!fCurrent) 158 return NULL; 159 160 AVLTreeNode* node = fCurrent; 161 fCurrent = NULL; 162 163 return (const_cast<AVLTreeBase*>(fParent)->Remove(node) ? node : NULL); 164 } 165 166 inline AVLTreeIterator& operator=(const AVLTreeIterator& other) 167 { 168 fParent = other.fParent; 169 fCurrent = other.fCurrent; 170 fNext = other.fNext; 171 return *this; 172 } 173 174 private: 175 inline AVLTreeIterator(const AVLTreeBase* parent, AVLTreeNode* current, 176 AVLTreeNode* next) 177 : 178 fParent(parent), 179 fCurrent(current), 180 fNext(next) 181 { 182 } 183 184 protected: 185 friend class AVLTreeBase; 186 187 const AVLTreeBase* fParent; 188 AVLTreeNode* fCurrent; 189 AVLTreeNode* fNext; 190 }; 191 192 193 // GetIterator 194 inline AVLTreeIterator 195 AVLTreeBase::GetIterator() const 196 { 197 return AVLTreeIterator(this, NULL, LeftMost(fRoot)); 198 } 199 200 201 // GetIterator 202 inline AVLTreeIterator 203 AVLTreeBase::GetIterator(AVLTreeNode* node) const 204 { 205 return AVLTreeIterator(this, node, Next(node)); 206 } 207 208 209 #endif // _KERNEL_UTIL_AVL_TREE_BASE_H 210