[haiku-commits] r34526 - in haiku/trunk: headers/private/kernel/util src/system/kernel/util
- From: ingo_weinhold@xxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Sun, 6 Dec 2009 16:59:37 +0100 (CET)
Author: bonefish
Date: 2009-12-06 16:59:37 +0100 (Sun, 06 Dec 2009)
New Revision: 34526
Changeset: http://dev.haiku-os.org/changeset/34526/haiku
Added:
haiku/trunk/headers/private/kernel/util/AVLTree.h
haiku/trunk/headers/private/kernel/util/AVLTreeBase.h
haiku/trunk/src/system/kernel/util/AVLTreeBase.cpp
Removed:
haiku/trunk/src/system/kernel/util/AVLTreeMap.cpp
Modified:
haiku/trunk/headers/private/kernel/util/AVLTreeMap.h
haiku/trunk/src/system/kernel/util/Jamfile
Log:
* AVLTree:
- Renamed to AVLTreeBase and moved it into its own header/source file.
- Renamed FindClose() to FindClosest().
- Added CheckTree() method for debugging purposes. It checks the validity
of the tree.
* Added a templatized class AVLTree which doesn't offer a map-like interface
like AVLTreeMap, but rather one similar to BOpenHashMap and SplayTree. It
is more convenient to use, if one wants to store objects that already
contain the key.
Added: haiku/trunk/headers/private/kernel/util/AVLTree.h
===================================================================
--- haiku/trunk/headers/private/kernel/util/AVLTree.h
(rev 0)
+++ haiku/trunk/headers/private/kernel/util/AVLTree.h 2009-12-06 15:59:37 UTC
(rev 34526)
@@ -0,0 +1,366 @@
+/*
+ * Copyright 2003-2009, Ingo Weinhold <ingo_weinhold@xxxxxx>.
+ * Distributed under the terms of the MIT License.
+ */
+#ifndef _KERNEL_UTIL_AVL_TREE_H
+#define _KERNEL_UTIL_AVL_TREE_H
+
+
+#include <util/AVLTreeBase.h>
+
+
+/*
+ To be implemented by the definition:
+
+ typedef int Key;
+ typedef Foo Value;
+
+ AVLTreeNode* GetAVLTreeNode(Value* value) const;
+ Value* GetValue(AVLTreeNode* node) const;
+ int Compare(const Key& a, const
Value* b) const;
+ int Compare(const Value* a, const
Value* b) const;
+*/
+
+
+
+template<typename Definition>
+class AVLTree : protected AVLTreeCompare {
+private:
+ typedef typename Definition::Key Key;
+ typedef typename Definition::Value Value;
+
+public:
+ class Iterator;
+ class ConstIterator;
+
+public:
+ AVLTree();
+ AVLTree(const
Definition& definition);
+ virtual ~AVLTree();
+
+ inline int Count() const {
return fTree.Count(); }
+ inline bool IsEmpty() const { return
fTree.IsEmpty(); }
+ inline void Clear();
+
+ Value* RootNode() const;
+
+ inline Iterator GetIterator();
+ inline ConstIterator GetIterator() const;
+
+ inline Iterator GetIterator(Value* value);
+ inline ConstIterator GetIterator(Value* value) const;
+
+ Value* Find(const Key& key)
const;
+ Value* FindClosest(const Key&
key, bool less) const;
+
+ status_t Insert(Value* value,
Iterator* iterator = NULL);
+ Value* Remove(const Key& key);
+ bool Remove(Value* key);
+
+ void CheckTree() const
{ fTree.CheckTree(); }
+
+protected:
+ // AVLTreeCompare
+ virtual int CompareKeyNode(const
void* key,
+ const
AVLTreeNode* node);
+ virtual int CompareNodes(const
AVLTreeNode* node1,
+ const
AVLTreeNode* node2);
+
+ // definition shortcuts
+ inline AVLTreeNode* _GetAVLTreeNode(Value* value) const;
+ inline Value* _GetValue(const AVLTreeNode*
node) const;
+ inline int _Compare(const Key& a,
const Value* b);
+ inline int _Compare(const Value*
a, const Value* b);
+
+protected:
+ friend class Iterator;
+ friend class ConstIterator;
+
+ AVLTreeBase fTree;
+ Definition fDefinition;
+
+public:
+ // (need to implement it here, otherwise gcc 2.95.3 chokes)
+ class Iterator : public ConstIterator {
+ public:
+ inline Iterator()
+ :
+ ConstIterator()
+ {
+ }
+
+ inline Iterator(const Iterator& other)
+ :
+ ConstIterator(other)
+ {
+ }
+
+ inline void Remove()
+ {
+ if (AVLTreeNode* node =
ConstIterator::fTreeIterator.Remove()) {
+ AVLTree<Definition>* parent
+ = const_cast<AVLTree<Definition>*>(
+ ConstIterator::fParent);
+ }
+ }
+
+ private:
+ inline Iterator(AVLTree<Definition>* parent,
+ const AVLTreeIterator& treeIterator)
+ : ConstIterator(parent, treeIterator)
+ {
+ }
+
+ friend class AVLTree<Definition>;
+ };
+};
+
+
+template<typename Definition>
+class AVLTree<Definition>::ConstIterator {
+public:
+ inline ConstIterator()
+ :
+ fParent(NULL),
+ fTreeIterator()
+ {
+ }
+
+ inline ConstIterator(const ConstIterator& other)
+ :
+ fParent(other.fParent),
+ fTreeIterator(other.fTreeIterator)
+ {
+ }
+
+ inline bool HasCurrent() const
+ {
+ return fTreeIterator.Current();
+ }
+
+ inline Value* Current()
+ {
+ if (AVLTreeNode* node = fTreeIterator.Current())
+ return fParent->_GetValue(node);
+ return NULL;
+ }
+
+ inline bool HasNext() const
+ {
+ return fTreeIterator.HasNext();
+ }
+
+ inline Value* Next()
+ {
+ if (AVLTreeNode* node = fTreeIterator.Next())
+ return fParent->_GetValue(node);
+ return NULL;
+ }
+
+ inline Value* Previous()
+ {
+ if (AVLTreeNode* node = fTreeIterator.Previous())
+ return fParent->_GetValue(node);
+ return NULL;
+ }
+
+ inline ConstIterator& operator=(const ConstIterator& other)
+ {
+ fParent = other.fParent;
+ fTreeIterator = other.fTreeIterator;
+ return *this;
+ }
+
+protected:
+ inline ConstIterator(const AVLTree<Definition>* parent,
+ const AVLTreeIterator& treeIterator)
+ {
+ fParent = parent;
+ fTreeIterator = treeIterator;
+ }
+
+ friend class AVLTree<Definition>;
+
+ const AVLTree<Definition>* fParent;
+ AVLTreeIterator fTreeIterator;
+};
+
+
+template<typename Definition>
+AVLTree<Definition>::AVLTree()
+ :
+ fTree(this),
+ fDefinition()
+{
+}
+
+
+template<typename Definition>
+AVLTree<Definition>::AVLTree(const Definition& definition)
+ :
+ fTree(this),
+ fDefinition(definition)
+{
+}
+
+
+template<typename Definition>
+AVLTree<Definition>::~AVLTree()
+{
+}
+
+
+template<typename Definition>
+inline void
+AVLTree<Definition>::Clear()
+{
+ fTree.MakeEmpty();
+}
+
+
+template<typename Definition>
+inline typename AVLTree<Definition>::Value*
+AVLTree<Definition>::RootNode() const
+{
+ if (AVLTreeNode* root = fTree.Root())
+ return _GetValue(root);
+ return NULL;
+}
+
+
+template<typename Definition>
+inline typename AVLTree<Definition>::Iterator
+AVLTree<Definition>::GetIterator()
+{
+ return Iterator(this, fTree.GetIterator());
+}
+
+
+template<typename Definition>
+inline typename AVLTree<Definition>::ConstIterator
+AVLTree<Definition>::GetIterator() const
+{
+ return ConstIterator(this, fTree.GetIterator());
+}
+
+
+template<typename Definition>
+inline typename AVLTree<Definition>::Iterator
+AVLTree<Definition>::GetIterator(Value* value)
+{
+ return Iterator(this, fTree.GetIterator(_GetAVLTreeNode(value)));
+}
+
+
+template<typename Definition>
+inline typename AVLTree<Definition>::ConstIterator
+AVLTree<Definition>::GetIterator(Value* value) const
+{
+ return ConstIterator(this, fTree.GetIterator(_GetAVLTreeNode(value)));
+}
+
+
+template<typename Definition>
+typename AVLTree<Definition>::Value*
+AVLTree<Definition>::Find(const Key& key) const
+{
+ if (AVLTreeNode* node = fTree.Find(&key))
+ return _GetValue(node);
+ return NULL;
+}
+
+
+template<typename Definition>
+typename AVLTree<Definition>::Value*
+AVLTree<Definition>::FindClosest(const Key& key, bool less) const
+{
+ if (AVLTreeNode* node = fTree.FindClosest(&key, less))
+ return _GetValue(node);
+ return NULL;
+}
+
+
+template<typename Definition>
+status_t
+AVLTree<Definition>::Insert(Value* value, Iterator* iterator)
+{
+ AVLTreeNode* node = _GetAVLTreeNode(value);
+ status_t error = fTree.Insert(node);
+ if (error != B_OK)
+ return error;
+
+ if (iterator != NULL)
+ *iterator = Iterator(this, fTree.GetIterator(node));
+
+ return B_OK;
+}
+
+
+template<typename Definition>
+typename AVLTree<Definition>::Value*
+AVLTree<Definition>::Remove(const Key& key)
+{
+ AVLTreeNode* node = fTree.Remove(&key);
+ return node != NULL ? _GetValue(node) : NULL;
+}
+
+
+template<typename Definition>
+bool
+AVLTree<Definition>::Remove(Value* value)
+{
+ return fTree.Remove(_GetAVLTreeNode(value));
+}
+
+
+template<typename Definition>
+int
+AVLTree<Definition>::CompareKeyNode(const void* key,
+ const AVLTreeNode* node)
+{
+ return _Compare(*(const Key*)key, _GetValue(node));
+}
+
+
+template<typename Definition>
+int
+AVLTree<Definition>::CompareNodes(const AVLTreeNode* node1,
+ const AVLTreeNode* node2)
+{
+ return _Compare(_GetValue(node1), _GetValue(node2));
+}
+
+
+template<typename Definition>
+inline AVLTreeNode*
+AVLTree<Definition>::_GetAVLTreeNode(Value* value) const
+{
+ return fDefinition.GetAVLTreeNode(value);
+}
+
+
+template<typename Definition>
+inline typename AVLTree<Definition>::Value*
+AVLTree<Definition>::_GetValue(const AVLTreeNode* node) const
+{
+ return fDefinition.GetValue(const_cast<AVLTreeNode*>(node));
+}
+
+
+template<typename Definition>
+inline int
+AVLTree<Definition>::_Compare(const Key& a, const Value* b)
+{
+ return fDefinition.Compare(a, b);
+}
+
+
+template<typename Definition>
+inline int
+AVLTree<Definition>::_Compare(const Value* a, const Value* b)
+{
+ return fDefinition.Compare(a, b);
+}
+
+
+#endif // _KERNEL_UTIL_AVL_TREE_H
Added: haiku/trunk/headers/private/kernel/util/AVLTreeBase.h
===================================================================
--- haiku/trunk/headers/private/kernel/util/AVLTreeBase.h
(rev 0)
+++ haiku/trunk/headers/private/kernel/util/AVLTreeBase.h 2009-12-06
15:59:37 UTC (rev 34526)
@@ -0,0 +1,205 @@
+/*
+ * Copyright 2003-2009, Ingo Weinhold <ingo_weinhold@xxxxxx>.
+ * Distributed under the terms of the MIT License.
+ */
+#ifndef _KERNEL_UTIL_AVL_TREE_BASE_H
+#define _KERNEL_UTIL_AVL_TREE_BASE_H
+
+
+#include <SupportDefs.h>
+
+
+class AVLTreeIterator;
+
+
+struct AVLTreeNode {
+ AVLTreeNode* parent;
+ AVLTreeNode* left;
+ AVLTreeNode* right;
+ int balance_factor;
+};
+
+
+class AVLTreeCompare {
+public:
+ virtual ~AVLTreeCompare();
+
+ virtual int CompareKeyNode(const
void* key,
+ const
AVLTreeNode* node) = 0;
+ virtual int CompareNodes(const
AVLTreeNode* node1,
+ const
AVLTreeNode* node2) = 0;
+};
+
+
+class AVLTreeBase {
+public:
+
AVLTreeBase(AVLTreeCompare* compare);
+ ~AVLTreeBase();
+
+ inline int Count() const {
return fNodeCount; }
+ inline bool IsEmpty() const { return
(fNodeCount == 0); }
+ void MakeEmpty();
+
+ inline AVLTreeNode* Root() const { return fRoot; }
+
+ AVLTreeNode* LeftMost(AVLTreeNode* node)
const;
+ AVLTreeNode* RightMost(AVLTreeNode* node)
const;
+
+ AVLTreeNode* Previous(AVLTreeNode* node)
const;
+ AVLTreeNode* Next(AVLTreeNode* node) const;
+
+ inline AVLTreeIterator GetIterator() const;
+ inline AVLTreeIterator GetIterator(AVLTreeNode* node) const;
+
+ AVLTreeNode* Find(const void* key) const;
+ AVLTreeNode* FindClosest(const void* key,
bool less) const;
+
+ status_t Insert(AVLTreeNode*
element);
+ AVLTreeNode* Remove(const void* key);
+ bool Remove(AVLTreeNode*
element);
+
+ void CheckTree() const;
+
+private:
+ enum {
+ NOT_FOUND = -3,
+ DUPLICATE = -2,
+ NO_MEMORY = -1,
+ OK = 0,
+ HEIGHT_CHANGED = 1,
+
+ LEFT = -1,
+ BALANCED = 0,
+ RIGHT = 1,
+ };
+
+ // rotations
+ void
_RotateRight(AVLTreeNode** nodeP);
+ void
_RotateLeft(AVLTreeNode** nodeP);
+
+ // insert
+ int
_BalanceInsertLeft(AVLTreeNode** node);
+ int
_BalanceInsertRight(AVLTreeNode** node);
+ int
_Insert(AVLTreeNode* nodeToInsert);
+
+ // remove
+ int
_BalanceRemoveLeft(AVLTreeNode** node);
+ int
_BalanceRemoveRight(AVLTreeNode** node);
+ int
_RemoveRightMostChild(AVLTreeNode** node,
+
AVLTreeNode** foundNode);
+ int
_Remove(AVLTreeNode* node);
+
+ int
_CheckTree(AVLTreeNode* parent,
+
AVLTreeNode* node, int& _nodeCount) const;
+
+ AVLTreeNode* fRoot;
+ int fNodeCount;
+ AVLTreeCompare* fCompare;
+};
+
+
+// AVLTreeIterator
+class AVLTreeIterator {
+public:
+ inline AVLTreeIterator()
+ :
+ fParent(NULL),
+ fCurrent(NULL),
+ fNext(NULL)
+ {
+ }
+
+ inline AVLTreeIterator(const AVLTreeIterator& other)
+ :
+ fParent(other.fParent),
+ fCurrent(other.fCurrent),
+ fNext(other.fNext)
+ {
+ }
+
+ inline AVLTreeNode* Current() const
+ {
+ return fCurrent;
+ }
+
+ inline bool HasNext() const
+ {
+ return fNext;
+ }
+
+ inline AVLTreeNode* Next()
+ {
+ fCurrent = fNext;
+
+ if (fNext)
+ fNext = fParent->Next(fNext);
+
+ return fCurrent;
+ }
+
+ inline AVLTreeNode* Previous()
+ {
+ if (fCurrent) {
+ fNext = fCurrent;
+ fCurrent = fParent->Previous(fCurrent);
+ } else if (fNext)
+ fCurrent = fParent->Previous(fNext);
+
+ return fCurrent;
+ }
+
+ inline AVLTreeNode* Remove()
+ {
+ if (!fCurrent)
+ return NULL;
+
+ AVLTreeNode* node = fCurrent;
+ fCurrent = NULL;
+
+ return (const_cast<AVLTreeBase*>(fParent)->Remove(node) ? node
: NULL);
+ }
+
+ inline AVLTreeIterator& operator=(const AVLTreeIterator& other)
+ {
+ fParent = other.fParent;
+ fCurrent = other.fCurrent;
+ fNext = other.fNext;
+ return *this;
+ }
+
+private:
+ inline AVLTreeIterator(const AVLTreeBase* parent, AVLTreeNode* current,
+ AVLTreeNode* next)
+ :
+ fParent(parent),
+ fCurrent(current),
+ fNext(next)
+ {
+ }
+
+protected:
+ friend class AVLTreeBase;
+
+ const AVLTreeBase* fParent;
+ AVLTreeNode* fCurrent;
+ AVLTreeNode* fNext;
+};
+
+
+// GetIterator
+inline AVLTreeIterator
+AVLTreeBase::GetIterator() const
+{
+ return AVLTreeIterator(this, NULL, LeftMost(fRoot));
+}
+
+
+// GetIterator
+inline AVLTreeIterator
+AVLTreeBase::GetIterator(AVLTreeNode* node) const
+{
+ return AVLTreeIterator(this, node, Next(node));
+}
+
+
+#endif // _KERNEL_UTIL_AVL_TREE_BASE_H
Modified: haiku/trunk/headers/private/kernel/util/AVLTreeMap.h
===================================================================
--- haiku/trunk/headers/private/kernel/util/AVLTreeMap.h 2009-12-06
15:47:34 UTC (rev 34525)
+++ haiku/trunk/headers/private/kernel/util/AVLTreeMap.h 2009-12-06
15:59:37 UTC (rev 34526)
@@ -1,211 +1,15 @@
/*
- * Copyright 2003-2007, Ingo Weinhold <bonefish@xxxxxxxxxxxxxxx>.
+ * Copyright 2003-2009, Ingo Weinhold <ingo_weinhold@xxxxxx>.
* Distributed under the terms of the MIT License.
*/
-#ifndef _AVL_TREE_MAP_H
-#define _AVL_TREE_MAP_H
+#ifndef _KERNEL_UTIL_AVL_TREE_MAP_H
+#define _KERNEL_UTIL_AVL_TREE_MAP_H
-#include <OS.h>
-#include <util/kernel_cpp.h>
-
#include <util/MallocFreeAllocator.h>
+#include <util/AVLTreeBase.h>
-// maximal height of a tree
-static const int kMaxAVLTreeHeight = 32;
-
-class AVLTreeIterator;
-
-
-// AVLTreeNode
-struct AVLTreeNode {
- AVLTreeNode* parent;
- AVLTreeNode* left;
- AVLTreeNode* right;
- int balance_factor;
-};
-
-
-// AVLTreeCompare
-class AVLTreeCompare {
-public:
- virtual ~AVLTreeCompare();
-
- virtual int CompareKeyNode(const
void* key,
- const
AVLTreeNode* node) = 0;
- virtual int CompareNodes(const
AVLTreeNode* node1,
- const
AVLTreeNode* node2) = 0;
-};
-
-
-// AVLTree
-class AVLTree {
-public:
-
AVLTree(AVLTreeCompare* compare);
- ~AVLTree();
-
- inline int Count() const {
return fNodeCount; }
- inline bool IsEmpty() const { return
(fNodeCount == 0); }
- void MakeEmpty();
-
- inline AVLTreeNode* Root() const { return fRoot; }
-
- AVLTreeNode* LeftMost(AVLTreeNode* node)
const;
- AVLTreeNode* RightMost(AVLTreeNode* node)
const;
-
- AVLTreeNode* Previous(AVLTreeNode* node)
const;
- AVLTreeNode* Next(AVLTreeNode* node) const;
-
- inline AVLTreeIterator GetIterator() const;
- inline AVLTreeIterator GetIterator(AVLTreeNode* node) const;
-
- AVLTreeNode* Find(const void* key);
- AVLTreeNode* FindClose(const void* key, bool
less);
-
- status_t Insert(AVLTreeNode*
element);
- AVLTreeNode* Remove(const void* key);
- bool Remove(AVLTreeNode*
element);
-
-private:
- enum {
- NOT_FOUND = -3,
- DUPLICATE = -2,
- NO_MEMORY = -1,
- OK = 0,
- HEIGHT_CHANGED = 1,
-
- LEFT = -1,
- BALANCED = 0,
- RIGHT = 1,
- };
-
- // rotations
- void
_RotateRight(AVLTreeNode** nodeP);
- void
_RotateLeft(AVLTreeNode** nodeP);
-
- // insert
- int
_BalanceInsertLeft(AVLTreeNode** node);
- int
_BalanceInsertRight(AVLTreeNode** node);
- int
_Insert(AVLTreeNode* nodeToInsert);
-
- // remove
- int
_BalanceRemoveLeft(AVLTreeNode** node);
- int
_BalanceRemoveRight(AVLTreeNode** node);
- int
_RemoveRightMostChild(AVLTreeNode** node,
-
AVLTreeNode** foundNode);
- int
_Remove(AVLTreeNode* node);
-
- AVLTreeNode* fRoot;
- int fNodeCount;
- AVLTreeCompare* fCompare;
-};
-
-
-// AVLTreeIterator
-class AVLTreeIterator {
-public:
- inline AVLTreeIterator()
- : fParent(NULL),
- fCurrent(NULL),
- fNext(NULL)
- {
- }
-
- inline AVLTreeIterator(const AVLTreeIterator& other)
- : fParent(other.fParent),
- fCurrent(other.fCurrent),
- fNext(other.fNext)
- {
- }
-
- inline AVLTreeNode* Current() const
- {
- return fCurrent;
- }
-
- inline bool HasNext() const
- {
- return fNext;
- }
-
- inline AVLTreeNode* Next()
- {
- fCurrent = fNext;
-
- if (fNext)
- fNext = fParent->Next(fNext);
-
- return fCurrent;
- }
-
- inline AVLTreeNode* Previous()
- {
- if (fCurrent) {
- fNext = fCurrent;
- fCurrent = fParent->Previous(fCurrent);
- } else if (fNext)
- fCurrent = fParent->Previous(fNext);
-
- return fCurrent;
- }
-
- inline AVLTreeNode* Remove()
- {
- if (!fCurrent)
- return NULL;
-
- AVLTreeNode* node = fCurrent;
- fCurrent = NULL;
-
- return (const_cast<AVLTree*>(fParent)->Remove(node) ? node :
NULL);
- }
-
- inline AVLTreeIterator& operator=(const AVLTreeIterator& other)
- {
- fParent = other.fParent;
- fCurrent = other.fCurrent;
- fNext = other.fNext;
- return *this;
- }
-
-private:
- inline AVLTreeIterator(const AVLTree* parent, AVLTreeNode* current,
- AVLTreeNode* next)
- : fParent(parent),
- fCurrent(current),
- fNext(next)
- {
- }
-
-protected:
- friend class AVLTree;
-
- const AVLTree* fParent;
- AVLTreeNode* fCurrent;
- AVLTreeNode* fNext;
-};
-
-
-// GetIterator
-inline AVLTreeIterator
-AVLTree::GetIterator() const
-{
- return AVLTreeIterator(this, NULL, LeftMost(fRoot));
-}
-
-
-// GetIterator
-inline AVLTreeIterator
-AVLTree::GetIterator(AVLTreeNode* node) const
-{
- return AVLTreeIterator(this, node, Next(node));
-}
-
-
-// #pragma mark - AVLTreeMap and friends
-
-
// strategies
namespace AVLTreeMapStrategy {
// key orders
@@ -299,7 +103,7 @@
friend class Iterator;
friend class ConstIterator;
- AVLTree fTree;
+ AVLTreeBase fTree;
NodeStrategy fStrategy;
public:
@@ -518,7 +322,7 @@
typename _AVL_TREE_MAP_CLASS_NAME::Iterator
_AVL_TREE_MAP_CLASS_NAME::FindClose(const Key& key, bool less)
{
- if (AVLTreeNode* node = fTree.FindClose(&key, less))
+ if (AVLTreeNode* node = fTree.FindClosest(&key, less))
return Iterator(this, fTree.GetIterator(node));
return Iterator();
}
@@ -776,4 +580,4 @@
};
}
-#endif // _AVL_TREE_MAP_H
+#endif // _KERNEL_UTIL_AVL_TREE_MAP_H
Copied: haiku/trunk/src/system/kernel/util/AVLTreeBase.cpp (from rev 34463,
haiku/trunk/src/system/kernel/util/AVLTreeMap.cpp)
===================================================================
--- haiku/trunk/src/system/kernel/util/AVLTreeBase.cpp
(rev 0)
+++ haiku/trunk/src/system/kernel/util/AVLTreeBase.cpp 2009-12-06 15:59:37 UTC
(rev 34526)
@@ -0,0 +1,629 @@
+/*
+ * Copyright 2003-2009, Ingo Weinhold <ingo_weinhold@xxxxxx>.
+ * Distributed under the terms of the MIT License.
+ */
+
+
+#include <util/AVLTreeBase.h>
+
+#include <algorithm>
+
+#include <KernelExport.h>
+
+
+#ifdef _KERNEL_MODE
+# define CHECK_FAILED(message...) panic(message)
+#else
+# include <stdio.h>
+# include <OS.h>
+# define CHECK_FAILED(message...) \
+ do {
\
+ fprintf(stderr, message);
\
+ fprintf(stderr, "\n");
\
+ debugger("AVLTreeBase check failed"); \
+ } while (false)
+#endif
+
+
+// maximal height of a tree
+static const int kMaxAVLTreeHeight = 32;
+
+
+// #pragma mark - AVLTreeCompare
+
+
+AVLTreeCompare::~AVLTreeCompare()
+{
+}
+
+
+// #pragma mark - AVLTreeBase
+
+
+AVLTreeBase::AVLTreeBase(AVLTreeCompare* compare)
+ : fRoot(NULL),
+ fNodeCount(0),
+ fCompare(compare)
+{
+}
+
+
+AVLTreeBase::~AVLTreeBase()
+{
+}
+
+
+void
+AVLTreeBase::MakeEmpty()
+{
+ fRoot = NULL;
+ fNodeCount = 0;
+}
+
+
+AVLTreeNode*
+AVLTreeBase::LeftMost(AVLTreeNode* node) const
+{
+ if (node) {
+ while (node->left)
+ node = node->left;
+ }
+
+ return node;
+}
+
+
+AVLTreeNode*
+AVLTreeBase::RightMost(AVLTreeNode* node) const
+{
+ if (node) {
+ while (node->right)
+ node = node->right;
+ }
+
+ return node;
+}
+
+
+AVLTreeNode*
+AVLTreeBase::Previous(AVLTreeNode* node) const
+{
+ if (node) {
+ // The previous node cannot be in the right subtree.
+ if (node->left) {
+ // We have a left subtree, so go to the right-most node.
+ node = node->left;
+ while (node->right)
+ node = node->right;
+ } else {
+ // No left subtree: Backtrack our path and stop, where
we
+ // took the right branch.
+ AVLTreeNode* previous;
+ do {
+ previous = node;
+ node = node->parent;
+ } while (node && previous == node->left);
+ }
+ }
+
+ return node;
+}
+
+
+AVLTreeNode*
+AVLTreeBase::Next(AVLTreeNode* node) const
+{
+ if (node) {
+ // The next node cannot be in the left subtree.
+ if (node->right) {
+ // We have a right subtree, so go to the left-most node.
+ node = node->right;
+ while (node->left)
+ node = node->left;
+ } else {
+ // No right subtree: Backtrack our path and stop, where
we
+ // took the left branch.
+ AVLTreeNode* previous;
+ do {
+ previous = node;
+ node = node->parent;
+ } while (node && previous == node->right);
+ }
+ }
+
+ return node;
+}
+
+
+AVLTreeNode*
+AVLTreeBase::Find(const void* key) const
+{
+ AVLTreeNode* node = fRoot;
+
+ while (node) {
+ int cmp = fCompare->CompareKeyNode(key, node);
+ if (cmp == 0)
+ return node;
+
+ if (cmp < 0)
+ node = node->left;
+ else
+ node = node->right;
+ }
+
+ return NULL;
+}
+
+
+AVLTreeNode*
+AVLTreeBase::FindClosest(const void* key, bool less) const
+{
+ AVLTreeNode* node = fRoot;
+ AVLTreeNode* parent = NULL;
+
+ while (node) {
+ int cmp = fCompare->CompareKeyNode(key, node);
+ if (cmp == 0)
+ break;
[... truncated: 477 lines follow ...]
Other related posts:
- » [haiku-commits] r34526 - in haiku/trunk: headers/private/kernel/util src/system/kernel/util - ingo_weinhold
