AVL-Baum zum Verwalten der Datenbankpools innerhalb der Klasse PoolEx.
int ppl6::CAVLTree::Add |
( |
const void * |
value | ) |
|
|
inherited |
- Beschreibung:
- Diese Funktion fügt ein neues Element in den Baum ein. Dabei ist sichergestellt, dass der Baum stets sortiert und ausgewogen ist. Im Gegensatz zu CTree erlaub CAVLTree auch mehrere Elemente mit dem gleichen Schlüssel. Dieses Feature muss jedoch explizit durch Aufruf der Funktion CAVLTree::AllowDupes aktiviert werden.
- Parameter
-
[in] | value | Pointer auf den hinzuzufügenden Wert |
- Rückgabe
- Wurde das Element erfolgreich hinzugefügt, gibt die Funktion true (1) zurück, sonst false (0) und ein entsprechender Fehlercode wird gesetzt,
void ppl6::CAVLTree::AllowDupes |
( |
bool |
allow | ) |
|
|
inherited |
- Beschreibung:
- Mit dieser Funktion kann festgelegt werden, ob Elemente mit gleichem Schlüssel im Baum erlaubt sind. Normalerweise ist dies nicht der Fall. Dabei gilt zu beachten, dass einige Funktionen möglicherweise unerwartet funktionieren. So wird CAVLTree::Find immer nur das erste Element finden können, ebenso CAVLTree::Delete oder CAVLTree::Remove.
- Parameter
-
allow | Mit true werden Duplikate erlaubt, mit false nicht. Werden bei einem bereits gefüllten Baum nachträglich Duplikate verboten, hat dies keine Auswirkung auf bereits vorhandene Duplikate. |
void ppl6::CAVLTree::Clear |
( |
| ) |
|
|
inherited |
- Beschreibung:
- Mit dieser Funktion wird der Inhalt des Baums gelöscht und sämtlicher durch die Elemente belegter Speicher wieder freigegeben. Dazu wird für jedes Element zunächst CAVLTree::DeleteNode und dann die virtuelle Funktion CAVLTree::DestroyValue aufgerufen. Zuletzt wiird noch der duch den Knoten selbst belegte Speicher wieder freigegeben.
- Achtung
- Bei einer abgeleiteten Klasse muss diese Funktion durch den Destruktor aufgerufen werden, um sicherzustellen, dass alle Elemente gelöscht werden.
int ppl6::db::PoolTree::Compare |
( |
const void * |
value1, |
|
|
const void * |
value2 |
|
) |
| const |
|
virtual |
- Beschreibung:
- Damit Elemente sortiert in den Baum eingehangen werden können, muss eine Möglichkeit bestehen zwei Elemente zu vergleichen. Dies wird mit dieser Methode realisiert. Da jeder Baum andere Daten enthalten kann, muss die Methode für jeden Datentyp reimplementiert werden.
- Parameter
-
[in] | value1 | Pointer auf das erste Element. Der Pointer zeigt direkt auf die Daten des Knotens, nicht auf die Verwaltungsdaten des Knotens. |
[in] | value2 | Pointer auf das zweite Element. Der Pointer zeigt direkt auf die Daten des Knotens, nicht auf die Verwaltungsdaten des Knotens. |
- Rückgabe
- Die Funktion muss einen der folgenden 4 Werte zurückliefern:
- 0: Ist der Wert in
value2
identisch mit value1
, muss 0 zurückgegeben werden.
- +1: Ist der Wert in
value2
größer als der Wert in value1
, muss +1 zurückgegeben werden
- -1: Ist der Wert in
value2
kleiner als der Wert in value1
, muss -1 zurückgegeben werden
- -2: Dieser Wert wird im Fehlerfall zurückgegeben und es wird ein Fehlercode gesetzt. Die Tree-Operation muss dann ebenfalls mit einem Fehler abbrechen und diesen Fehlercode zurückgeben.
- Achtung
- Beim Vergleich zweier Strings kann die Funktion
strcmp
nicht direkt verwendet werden, da sie laut Definition Werte kleiner oder größer 0 liefert, aber nicht exakt -1 oder +1.
- Beispiel:
- Beispiel für eine Implementierung:
class MyItem
{
public:
MyItem(const char *name) {
Name=name;
}
};
{
public:
~MyTree() {
}
virtual int Compare(
const void *value1,
const void *value2) {
MyItem *i1=(MyItem*)value1;
MyItem *i2=(MyItem*)value2;
int ret=i2->Name.StrCmp(i1->Name);
if (ret<0) return -1;
if (ret>0) return 1;
return 0;
}
}
Erneute Implementation von ppl6::CAVLTree.
int ppl6::CAVLTree::Delete |
( |
const void * |
value | ) |
|
|
inherited |
- Beschreibung:
- Diese Funktion sucht zunächst ob der angegebene Wert im Baum enthalten ist und löscht anschließend das gefundene Element. Dabei ist sichergestellt, dass der Baum stets sortiert und ausgewogen ist.
- Beim Löschen des Elements wird auch die virtuelle Funktion CAVLTree::DestroyValue aufgerufen. Diese muss sicherstellen, dass der durch das Element belegte Speicher ebenfalls freigegeben wird.
- Falls das Element nur aus dem Baum entfernt werden, aber der durch das Element
- belegte Speicher erhalten bleiben soll, kann stattdessen die Funktion CAVLTree::Remove aufgerufen werden.
- Parameter
-
[in] | value | Pointer auf den zu löschenden Wert |
- Rückgabe
- Wurde das Element erfolgreich gelöscht, gibt die Funktion true (1) zurück, sonst false (0) und ein entsprechender Fehlercode wird gesetzt.
int ppl6::db::PoolTree::DestroyValue |
( |
void * |
item | ) |
const |
|
virtual |
- Beschreibung:
- Diese Funktion wird aufgerufen, wenn ein Wert aus dem Baum gelöscht werden soll, bzw. wenn der komplette Baum gelöscht wird. Da jeder Baum andere Daten enthalten kann, muss die Methode für jeden Datentyp reimplementiert werden.
- Parameter
-
item | Pointer auf die zu löschenden Daten. Der Pointer zeigt direkt auf die Daten des Knotens, nicht auf die Verwaltungsdaten des Knotens. |
- Rückgabe
- Die Funktion sollte 1 bei erfolgreichem Löschen zurückgeben, im Fehlerfall 0. Allerdings wird der Rückgabewert gegenwärtig nicht geprüft, so dass gegebenenfalls unbemerkt ein Memory-Leak entstehen kann.
Erneute Implementation von ppl6::CAVLTree.
void * ppl6::CAVLTree::Find |
( |
const void * |
value | ) |
const |
|
inherited |
- Beschreibung:
- Mit dieser Funktion wird ein Element innerhalb des Baums gesucht. Dazu wird die Funktion CTree::CompareItems verwendet.
- Parameter
-
[in] | value | Der zu suchende Wert |
- Rückgabe
- Wird das Element im Baum gefunden, gibt die Funktion einen Pointer auf den Wert des Baum-Elements zurück. Falls nicht, wird NULL zurückgegeben und der Fehlercode 421 gesetzt.
TREEITEM * ppl6::CAVLTree::FindNode |
( |
const void * |
value | ) |
const |
|
inherited |
- Beschreibung:
- Mit dieser Funktion wird der Wert
value
innerhalb des Baums gesucht und dessen Baumelement (TREEITEM) zurückgegeben.
- Parameter
-
[in] | value | Der zu suchende Wert |
- Rückgabe
- Wird der Wert im Baum gefunden, gibt die Funktion einen Pointer auf den Wert des Baum-Elements zurück. Falls nicht, wird NULL zurückgegeben und der Fehlercode 421 gesetzt.
void* ppl6::CAVLTree::FindOrAdd |
( |
const void * |
item | ) |
|
|
inherited |
void * ppl6::CAVLTree::GetCurrent |
( |
| ) |
|
|
inherited |
- Beschreibung:
- Mit dieser Funktion wird ein Pointer auf das aktuelle Element des Baums zurückgeliefert. Dabei wird der Pointer nicht verändert.
- Rückgabe
- Pointer auf das aktuelle Element des Baums oder NULL, wenn kein Element mehr vorhanden ist. In diesesm Fall wird ausserdem der Fehlercode 422 gesetzt.
void * ppl6::CAVLTree::GetCurrent |
( |
Walker & |
walk | ) |
const |
|
inherited |
void * ppl6::CAVLTree::GetFirst |
( |
| ) |
|
|
inherited |
- Beschreibung:
- Mit dieser Funktion wird ein Pointer auf das erste Element des Baums zurückgeliefert.
- Rückgabe
- Pointer auf das erste Element des Baums oder NULL, wenn der Baum leer ist
void * ppl6::CAVLTree::GetFirst |
( |
Walker & |
walk | ) |
const |
|
inherited |
void * ppl6::CAVLTree::GetLast |
( |
| ) |
|
|
inherited |
- Beschreibung:
- Mit dieser Funktion wird ein Pointer auf das letzte Element des Baums zurückgeliefert.
- Rückgabe
- Pointer auf das letzte Element des Baums oder NULL, wenn der Baum leer ist
void * ppl6::CAVLTree::GetLast |
( |
Walker & |
walk | ) |
const |
|
inherited |
void * ppl6::CAVLTree::GetNext |
( |
| ) |
|
|
inherited |
- Beschreibung:
- Mit dieser Funktion wird ein Pointer auf das nächste Element des Baums zurückgeliefert. Somit kann der Baum sortiert vorwärts durchwandert werden.
- Rückgabe
- Pointer auf das nächste Element des Baums oder NULL, wenn keine weiteren Elemente vorhanden sind. In diesesm Fall wird ausserdem der Fehlercode 422 gesetzt.
void * ppl6::CAVLTree::GetNext |
( |
Walker & |
walk | ) |
const |
|
inherited |
void * ppl6::CAVLTree::GetPrevious |
( |
| ) |
|
|
inherited |
- Beschreibung:
- Mit dieser Funktion wird ein Pointer auf das vorherige Element des Baums zurückgeliefert. Somit kann der Baum sortiert rückwärts durchwandert werden.
- Rückgabe
- Pointer auf das vorherige Element des Baums oder NULL, wenn keine weiteren Elemente vorhanden sind. In diesesm Fall wird ausserdem der Fehlercode 422 gesetzt.
void * ppl6::CAVLTree::GetPrevious |
( |
Walker & |
walk | ) |
const |
|
inherited |
int ppl6::db::PoolTree::GetValue |
( |
const void * |
item, |
|
|
CString & |
buffer |
|
) |
| const |
|
virtual |
Diese Funktion wird durch CAVLTree::PrintNodes aufgerufen, um den Inhalt des Baums anzeigen zu können. Da jeder Baum andere Daten enthalten kann, muss die Methode für jeden Datentyp reimplementiert werden. Sie bekommt als Eingabe einen Pointer item
auf die Daten des Knotens und einen String buffer
, in dem eine textuelle Darstellung des Dateninhalts abgelegt werden soll.
- Die Implementierung der Funktion ist optional.
- Parameter
-
[in] | item | Pointer auf die Daten des Knotens |
[out] | buffer | String, in dem die textuelle Darstellung der Daten erfolgen soll. |
- Rückgabe
- Bei Erfolg soll die Funktion 1 zurückgeben, im Fehlerfall 0. Wird 0 zurückgegeben, wird der Knoten nicht ausgegeben.
Erneute Implementation von ppl6::CAVLTree.
int ppl6::CAVLTree::Num |
( |
| ) |
const |
|
inherited |
- Beschreibung:
- Diese Funktion liefert die Anzahl Elemente im Baum zurück.
- Rückgabe
- Anzahl Elemente oder 0, wenn der Baum leer ist. Bei einem leeren Baum wird ausserdem der Fehlercode 347 gesetzt.
void ppl6::CAVLTree::PrintNodes |
( |
const TREEITEM * |
node = NULL | ) |
const |
|
inherited |
int ppl6::CAVLTree::Remove |
( |
const void * |
value | ) |
|
|
inherited |
- Beschreibung:
- Diese Funktion sucht zunächst ob der angegebene Wert im Baum enthalten ist und löscht anschließend das gefundene Element aus dem Baum. Dabei ist sichergestellt, dass der Baum stets sortiert und ausgewogen ist.
- Mit dieser Funktion wird das Element nur aus dem AVL-Baum entfernt, der durch das Element belegte Speicher wird jedoch nicht freigegeben. Falls dies gewünscht ist, kann stattdessen die Funktion CAVLTree::Delete aufgerufen werden.
- Parameter
-
[in] | value | Pointer auf den zu entfernenden Wert |
- Rückgabe
- Wurde das Element erfolgreich entfernt, gibt die Funktion true (1) zurück, sonst false (0) und ein entsprechender Fehlercode wird gesetzt.
void ppl6::CAVLTree::Reset |
( |
| ) |
|
|
inherited |
- Beschreibung:
- Mit dieser Funktion wird der interne Pointer zurückgesetzt, der für die Walk-Funktionen GetNext und GetPrevious verwendet wird.
void ppl6::CAVLTree::Reset |
( |
Walker & |
walk | ) |
const |
|
inherited |
- Beschreibung:
- Bei Verwendung der CAVLTree-Klasse wird üblicherweise eine eigene Klasse davon abgeleitet und mindestens die virtuelle Funktion CAVLTree::Compare, optional auch CAVLTree::DestroyValue und CAVLTree::GetValue reimplementiert. Es gibt jedoch auch die Möglichkeit CAVLTree ohne Ableitung zu verwenden. Dazu muss die eigene Klasse von CTreeController abgeleitet werden und dessen Pointer mit dieser Funktion an die CAVLTree-Klasse übergeben werden.
- Parameter
-
Die Dokumentation für diese Klasse wurde erzeugt aufgrund der Dateien:
- /jenkins/jobs/clang_ppl6/workspace/include/ppl6-db.h
- /jenkins/jobs/clang_ppl6/workspace/src/database/PoolEx.cpp