Tworzenie systemu bazy danych jest bardzo żmudnym zajęciem, szczególnie jeżeli w grę wchodzi brak doświadczenia. Koncepcja na budowę bazy danych zmieniała się wielokrotnie, zanim wyewoluowała do dzisiejszego kształtu, który chcę teraz zaprezentować.
Na obecną chwilę istnieją, zgodnie z informacjami zawartymi w poprzednim wpisie, dwie implementacje systemu bazodanowego. Mimo różnicy w sposobie działań wewnątrz, obie mają te same metody służące do obsługi z zewnątrz. Obie także oparte są na dwóch klasach, z których obie służą do modyfikacji bazy, jednak każda z nich ma inne zadania. Najpierw chciałbym opisać klasę...
TreeVertex
Klasa TreeVertex przechowuje informacje na temat położenia pojedynczego postu wewnątrz struktury drzewa, a także na temat treści, tytułu i daty powstania posta. Umożliwia jednak modyfikację wyłącznie tej drugiej grupy danych. Stąd jej szkielet wygląda następująco:
class Base;
class TreeVertex
{
friend class Base;
public:
// Con- and destructor
TreeVertex(int ID, TreeVertex* parent = NULL);
~TreeVertex();
// User Methods
/// Modyfing posts
void setTitle(string title);
void setText(string text);
/// Getting information
time_t getDate();
string getTitle();
string getText();
int getBranchCount();
private:
// Properties
int ID;
time_t Date;
string Title;
string Text;
vector<TreeVertex*> Children;
TreeVertex* Parent;
};
Myślę, że większość tego kodu nie wymaga omówienia, jednak pokrótce wyjaśnię zastosowanie wszystkich metod i składowych.
Linie 1 i 5 służą do zadeklarowania przyjaźni między klasami TreeVertex oraz Base, co umożliwia drugiej z nich dostęp do prywatnych składowych pierwszej. Dzięki temu klasa Base zyskuje wyłączność na ingerencję w składowe kontrolujące położenie wpisu w strukturze. Nie jest potrzebna także implementacja dodatkowych metod modyfikujących prywatne pola klasy.
Linie 9 i 10 to definicja konstruktora i destruktora klasy. Pierwszy z nich ustawia ID instancji, jej przodka, a także ustawia wartości pozostałych pól na puste. Destruktor w implementacji indeksowej nie robi nic, natomiast we wskaźnikowej wywołuje destruktory wszystkich wierzchołków w poddrzewie, którego jest korzeniem, w celu oczyszczenia pamięci. Zapobieganiem usunięcia potrzebnych postów zajmuje się jedna z niżej omawianych metod drugiej klasy.
W liniach 14 i 15 znajduje się definicja metod służących do modyfikacji tytułu i treści wpisu, natomiast od 18 do 21 linii włącznie mamy te odpowiedzialne za pobieranie niektórych danych. Linie 25-30 do prywatne pola klasy, które przechowują informacje na jej temat. Podany kod pochodzi z implementacji wskaźnikowej, stąd w liniach 29 i 30 TreeVertex*, zamieniony na int w implementacji indeksowej.
Base
Drugą klasą tworzącą obecnie system bazy danych jest klasa Base, zarządzająca strukturą drzewa, jednak nie mająca nic wspólnego z treścią wpisów. Szkielet tej klasy w obu implementacjach nieco się różni, stąd zacznę od omówienia wersji wskaźnikowej:
class Base
{
public:
Base(TreeVertex* curr = Curr);
~Base();
bool atRoot();
bool atLeaf();
TreeVertex* addEntry();
TreeVertex* addEndEntry();
TreeVertex* addBranch();
void delCurrentEntry(bool children, bool successor);
void goTo(TreeVertex* entry);
TreeVertex* moveUp();
TreeVertex* moveDown();
TreeVertex* moveSide(int id);
TreeVertex* getCurrent();
private:
static TreeVertex* Root;
static TreeVertex* Curr;
static int maxID;
};
Tutaj nie mamy definicji przyjaźni między klasami Base oraz TreeVertex, ponieważ nie jest potrzebny nam dostęp do prywatnych pól tej pierwszej z poziomu drugiej.
W linii 4. i 5. mamy definicje konstruktora i destruktora. Ten drugi nie robi nic, kod tego pierwszego znajduje się poniżej:
Base::Base(TreeVertex* curr)
{
if (!Root)
{
Root = new TreeVertex(0);
Curr = Root;
maxID = 0;
}
else
{
Curr = curr;
}
}
Jak widać, konstruktor działa dwojako: jeżeli już wcześniej istniała instancja klasy Base, to pole Root nie wskazuje na pustkę i zostanie wykonana wyłącznie linia numer 11. Przypisuje ona wskaźnikowi na obecny element argument podany konstruktorowi. Jego domyślną wartością jest obecna wartość tego wskaźnika, stąd jeżeli nie podamy żadnego argumentu, to obecny element pozostanie ten sam.
Jeżeli natomiast jest to pierwsza instancja tej klasy, to tworzony jest korzeń klasy. Dodatkowo wskaźnik na obecny element zostaje przekierowany na nowo powstały wierzchołek. Pole maxID ustawiane jest na 0 - zastosowanie tego pola zostanie omówione nieco niżej.
W liniach 6 i 7 wewnątrz szkieletu klasy Base znajdują się definicje dwóch metod pomocniczych: pierwsza z nich zwraca prawdę, jeżeli wskaźnik na obecny element jest równy wskaźnikowi na korzeń. Druga z nich zwraca prawdę, jeżeli następca obecnego wierzchołka nie istnieje, tj. Base::Curr->Children[0] == NULL
Następne 3 metody (linie 9-11) działają bardzo podobnie w obu implementacjach. Tworzą one nowy wierzchołek oraz modyfikują pola tych obiektów, które znajdują się w sąsiedztwie (są jego przodkiem, następcą lub dziećmi), tak, aby stworzyć i umieścić nowy post w odpowiednim miejscu. Pierwsza metoda lokuje wpis w obecnej linii za obecnym postem, druga na końcu linii, a trzecia tworzy nowe odgałęzienie od obecnego wpisu. Wszystkie trzy metody zwracają także wskaźnik do nowo utworzonego postu, aby móc je bezpośrednio edytować lub przeskoczyć do nich na stałe przy pomocy metody goTo()
Nadszedł czas na funkcję, której musiałem poświęcić najwięcej czasu zarówno w wersji wskaźnikowej, jak i indeksowej - delCurrentEntry(bool ch, bool s). Wynik jej działania jest identyczny w obu implementacjach, jednak cel ten jest osiągnięty zupełnie odmiennymi drogami, co wynika z różnej organizacji struktury. Zacznijmy jednak od tego jak owa funkcja powinna działać. Jak można się domyślić, usuwa ona z drzewa wpis wskazywany obecnie przez składową Curr. Przyjmuje ona jednak dwie zmienne typu bool kontrolujące usuwanie potomków (bool ch) oraz następcy (bool s). Od ich wartości zależą które wpisy zostaną usunięte - chyba oczywistym jest które znikną w którym z przypadków. Powstaje jednak problem, co zrobić z osieroconymi wpisami? Możliwości jest kilka. Ja wybrałem następującą zasadę: osierocone dzieci oraz następcy zostają dziećmi przodka usuniętego wpisu. Przykład:
Pomarańczowe strzałki oznaczają następstwo w linii, czarne odgałęzienia. Czerwony wierzchołek to obecny wpis - jeżeli żaden wierzchołek nie ma takiego koloru, to znaczy że wskaźnik pokazuje na korzeń.
Przyjąłem jeszcze jedną zasadę: jeżeli usuwany wierzchołek jest odgałęzieniem liścia, to jego następca zostaje zastępcą przodka usuniętego wierzchołka, jak na diagramie poniżej:
Przejdźmy jednak do właściwej implementacji tej metody w wersji wskaźnikowej:
void Base::delCurrentEntry(bool children, bool successor)
{
if (!children)
{
for (int i = 1; i < Curr->getBranchCount(); i++)
{
Curr->Parent->Children.push_back(Curr->Children[i]);
Curr->Children[i]->Parent = Curr->Parent;
Curr->Children[i] = NULL;
}
}
if (!successor)
{
Curr->Children[0]->Parent = Curr->Parent;
if (Curr->Parent->Children[0])
Curr->Parent->Children.push_back(Curr->Children[0]);
else
Curr->Parent->Children[0] = Curr->Children[0];
Curr->Children[0] = NULL ;
}
delete Curr;
Curr = Root;
}
Mimo że kod jest dość prosty, i w rzeczywistości krótki, to stworzenie tej funkcji zajęło mi dwa dni - ciągle dostawałem naruszenia ochrony pamięci, ewentualnie usuwało się nie to co trzeba lub drzewo wyglądało zupełnie inaczej niż powinno po tej operacji.
Przechodząc do kodu, linie 3 i 12 są warunkami sprawdzającymi, czy do funkcji zostały przekazane wartości fałszywe. Jeżeli tak, odpowiedni potomkowie są przenoszeni do przodka usuwanego posta, zgodnie z przedstawionymi wyżej zasadami. Warte uwagi są linie 9 i 19, które ustawiają wskaźniki przeniesionych już postów na NULL. Są one strażnikami zapobiegającymi usunięciu postów, które mają zostać zachowane. Dzięki temu wywoływany w 22 linijce i omówiony na początku destruktor, nie może dostać się do wpisów, które zostały przeniesione. Na końcu wskaźnik obecnego wpisu przenoszony jest do korzenia, aby zapobiec odwołaniom do zniszczonej właśnie instancji klasy.
Wracając do szkieletu klasy Base: linie 14-18 zawierają definicje metod odpowiedzialnych za nawigację po strukturze drzewa. Pierwsza z nich przestawia wskaźnik Curr na podany element, pozostałe zwracają wskaźniki (nie zmieniając nic wewnątrz klasy) kolejno na ojca, następcę, wybranego potomka obecnego postu oraz na obecny post.
Linie 21-23 to definicje statycznych składowych bazy danych, dzięki czemu można odwołać się do bazy poprzez stworzenie nowego wskaźnika na instancję tej klasy, pobranie odpowiednich informacji i zniszczenie tymczasowej instancji. Zapobiega to także tworzeniu kilku różnych baz danych. Pierwsze dwa z trzech pól są dość oczywiste i przewijały się już kilkakrotnie. Na trochę uwagi zasługuje jednak maxID. Chociaż zastosowanie tej zmiennej jest raczej oczywiste i związane jest z nadawaniem ID nowo powstałym wpisom, to należy zauważyć, że nie przechowuje ona liczebności wpisów, a ID ostatnio dodanego postu. Może wydawać się to mało istotnym szczegółem. Jednak w ten sposób łatwiej zapamiętać, że maxID nie zmienia się przy usuwaniu wpisów, co do czego mógłbym mieć wątpliwości, gdyby zmienna nazywała się entriesCount i przechowywała liczebność wpisów.
Czas na omówienie różnic między wskaźnikową a indeksową implementacją klasy Base. Kod jej szkieletu różni się niewiele od wskaźnikowego:
#define PARENT Entries[Entries[Curr].Parent]
#define CURRENT Entries[Curr]
class Base
{
public:
Base(int curr = Curr);
~Base();
bool atRoot();
bool atLeaf();
TreeVertex* addEntry();
TreeVertex* addEndEntry();
TreeVertex* addBranch();
void delEntry(int id);
void delCurrentEntry(bool children, bool successor);
void goTo(TreeVertex* entry);
TreeVertex* moveUp();
TreeVertex* moveDown();
TreeVertex* moveSide(int id);
TreeVertex* getCurrent();
private:
static int Curr;
static vector<TreeVertex> Entries;
};
Zaczynając od końca, jednak od najbardziej istotnej moim zdaniem różnicy, należy zauważyć (oprócz oczywistej zmiany wskaźnika obecnego obiektu na jego indeks, co wynika z głównego założenia tego rozwiązania), że nie ma tutaj wskaźnika ani indeksu na korzeń - znajduje się on zawsze pod indeksem 0, a także najwyższego numeru ID - jego rolę doskonale spełnia metoda size() wektora Entries (chociaż jest to sprzeczne z nieco wyżej postawionym argumentem za składową maxID). Dodatkowo pojawił się nieobecny dotąd wektor Entries, który przechowuje wszystkie wpisy.
Kolejną wynikającą z założeń różnicą jest argument konstruktora (linia 7) - wskaźnik został zastąpiony indeksem. Sam konstruktor także zmienił się nieco - ze względu na nieobecność wskaźnika na korzeń trzeba było zmienić sposób rozpoznawania czy baza danych została już zainicjalizowana. Rozwiązałem to przy pomocy indeksu Curr, któremu, jako składowej statycznej, przypisuję początkowo wartość -1, natomiast konstruktor zmienia ją na 0. Reszta konstruktora pozostała praktycznie bez zmian.
Ostatnią różnicą jest implementacja usuwania postów. Składa się ona z dwóch metod, z których jedna jest wywoływana rekurencyjnie (w implementacji wskaźnikowej rolę tę pełnił destruktor klasy TreeVertex, tutaj nie jest nawet wywoływany, stąd zmiana). Zacznijmy od funkcji delCurrentVertex(), która działa na podobnych zasadach co jej wskaźnikowy odpowiednik
void Base::delCurrentEntry(bool children, bool successor)
{
if (!children)
{
for (int i = CURRENT.Children.size()-1; i > 0; i--)
{
Entries[CURRENT.Children[i]].Parent = CURRENT.Parent;
PARENT.Children.push_back(CURRENT.Children[i]);
CURRENT.Children.pop_back();
}
}
if (!successor)
{
Entries[CURRENT.Children[0]].Parent = CURRENT.Parent;
if (PARENT.Children[0])
PARENT.Children.push_back(CURRENT.Children[0]);
else
PARENT.Children[0] = CURRENT.Children[0];
CURRENT.Children[0] = 0;
}
delEntry(Curr);
if (PARENT.Children[0] == Curr)
PARENT.Children[0] = 0;
for (int i = 1; i < PARENT.Children.size(); i++)
{
if (PARENT.Children[i] == Curr)
{
PARENT.Children[i] = PARENT.Children[PARENT.Children.size()-1];
PARENT.Children.pop_back();
break;
}
}
Curr = 0;
}
Myślę, że linie 3-20 nie wymagają komentarza, ponieważ ten fragment kodu działa niemal identycznie jak odpowiadający mu fragment w implementacji wskaźnikowej, z tą różnicą, że operuje na indeksach. W 22 linii wywoływana jest rekurencyjna funkcja delEntry(), która zostanie omówiona za chwilę. Jej wywołanie następuje w tym miejscu, ponieważ ciąg dalszy funkcji delCurrentEntry() zakłóca strukturę drzewa i uniemożliwia skuteczne usunięcie wszystkich wpisów.
Cóż jednak te kolejne linie robią? To proste - znajdują którym dzieckiem swojego przodka jest usuwany wpis. Jeżeli jest na miejscu następcy (linie 23-24), to indeks ten zamieniany jest na 0. Jeżeli natomiast jest zwykłym potomkiem, to jego indeks w wektorze dzieci jest zamieniany z indeksem na końcu tego wektora, a potem usuwany. Na końcu, tak jak w implementacji wskaźnikowej, uwaga bazy danych skupia się na korzeniu drzewa.
void Base::delEntry(int id)
{
for (int i = 0; i < Entries[id].Children.size(); i++)
if (Entries[id].Children[i])
delEntry(Entries[id].Children[i]);
while (!Entries[id].Children.empty())
Entries[id].Children.pop_back();
Entries[id].Children.push_back(0);
Entries[id].setDel();
}
Działanie tej metody jest dość proste. Linie 3-5 odpowiadają za rekurencyjne wywołanie metody dla wszystkich istniejących potomków danego postu. Później w liniach 7-9 wektor potomków jest przywracany do stanu początkowego, a metoda setDel klasy TreeVertex ustawia ID danego wpisu na -1, co będzie w przyszłości znakiem dla metody zapisującej, że dany post został usunięty i nie potrzeba zapisywać na jego temat nic oprócz rejestrowania faktu jego istnienia. Nie jest to może najlepsze rozwiązanie i dane mogą się dość porządnie fragmentować, jednak póki co żaden z lepszych pomysłów nie chciał działać poprawnie ze względu na bałagan w indeksach wektora wpisów, spowodowany przesuwaniem elementów.
Uff... Wreszcie koniec. Nie tylko tego przydługiego wpisu (mam nadzieje, że nie za bardzo zamotanego), ale także żmudnej implementacji podstawowych funkcji bazy danych, która szła mi niewyobrażalnie powoli. Tę część przeprawy bazodanowej mam już jednak na szczęście za sobą (chociaż nie wykluczam modyfikacj, szczególnie w kewstii przenoszenia osieroconych wpisów), jednak przede mną zostały wyzwania związane z tagami, zapisem i odczytem, a co za tym idzie - szyfrowaniem.
PS: Benchmarkowanie obecnej implementacji bazy danych pozostaje na jutro. Jutro wieczorem pojawi się także wpis na ten temat, jeżeli wszystko pójdzie zgodnie z planem
Brak komentarzy:
Prześlij komentarz