Spis treści

Listy dwukierunkowe

Wprowadzenie

Lista jest najprostszą dynamiczną strukturą danych. Tablica jest co prawda jeszcze prostsza, ale nie jest dynamiczna. Dodanie elementu do tablicy wymaga ponownej rezerwacji pamięci i skopiowania całej starej zawartości, podobnie usunięcie elementu. Wstawianie elementów do listy i usuwanie ich z niej jest bardzo szybką operacją, a jej złożoność obliczeniowa nie zwiększa się ze wzrostem długości listy. Z tego względu lista jest podstawową strukturą danych używaną w exec.library – kernelu MorphOS-a. Można wręcz powiedzieć, że Exec jest zbudowany na listach. Listy są też szeroko stosowane w pozostałych częściach systemu do zarządzania oknami, ekranami, urządzeniami, dyskami, czcionkami, bibliotekami i tak dalej. Oczywiście również aplikacje używają list do zarządzania danymi dynamicznymi. Wiele bardziej złożonych struktur danych bazuje na listach. Z tych wszystkich powodów opanowanie list dwukierunkowych, oraz konkretnej ich odmiany używanej w MorphOS-ie jest sprawą zasadniczą dla każdego programisty pracującego z tym systemem.

Listy podzielić można na „natrętne” i „nienatrętne”. Lista natrętna, to taka, która wymaga od każdego elementu, aby zawierał w sobie część zwaną węzłem (ang. node) listy. Lista nienatrętna tworzy węzły samodzielnie. Oba rodzaje list mają swoje zalety. Listy systemowe są natrętne. Dlaczego? Dodanie elementu do listy nienatrętnej oznacza rezerwację pamięci na jego węzeł. Listy systemowe są często używane na dość niskich poziomach systemu, na przykład w obsłudze przerwań, przełączaniu procesów, czy sterownikach urządzeń. Wywoływanie systemowego alokatora pamięci z takich miejsc jest nie do zaakceptowania. Obsługa błędów również zamieniłaby się w koszmar (każda rezerwacja pamięci może się nie udać...). W niektórych zastosowaniach systemowych listy muszą być także bardzo szybkie. Przydział pamięci jest złożoną operacją i nie można oczekiwać, że zostanie wykonany w kilku taktach procesora. Oczywiście w wyższych warstwach systemu natrętność ma więcej wad niż zalet. Na przykład elementu listy natrętnej nie można dodać do więcej niż jednej listy jednocześnie. Stąd wysokopoziomowe elementy systemu (np. klasa List MUI) są nienatrętne.

Od zwykłej listy do listy systemowej

Najprostszą listą jest lista jednokierunkowa. Węzeł każdego elementu składa się tylko ze wskaźnika na następny element. Lista jako całość jest określona przez wskaźnik na pierwszy element. Listy jednokierunkowe są jednak stosowane tylko w specyficznych przypadkach. Co prawda wstawianie elementu na początek takiej listy jest bardzo łatwe, o tyle wstawianie na końcu wymaga przejścia wzdłuż całej listy dla odnalezienia jej ostatniego elementu. Czas wykonania takiej operacji rośnie proporcjonalnie do długości listy. Nie jest również możliwe przeglądanie takiej listy w kierunku od końca do początku. Dlatego listy dwukierunkowe są znacznie bardziej popularne. Listy systemowe są dwukierunkowe. Każdy węzeł zawiera dwa wskaźniki: do elementu następnego i do elementu poprzedniego. W pierwszym elemencie wskaźnik do elementu poprzedniego jest zerowy (NULL). Podobnie w ostatnim elemencie wskaźnik na element następny jest NULL-em. Gdy użytkownik listy przechowuje wskaźniki na pierwszy i ostatni element, ma symetryczny dostęp do obu końców listy.


Prosta lista dwukierunkowa. Węzeł składa się ze wskaźników „następny” i „poprzedni”.

Pomysł jest jak widać prosty, niestety trzeba go trochę skomplikować. Jak wcześniej wspomniałem, użytkownik listy utrzymuje dostęp do niej przez pamiętanie wskaźników na pierwszy i ostatni element. Jeden z tych wskaźników ulega modyfikacji za każdym razem gdy dodawany jest element na początku, albo na końcu listy. Co się jednak stanie, gdy lista ma wielu użytkowników, nie „wiedzących” o sobie nawzajem? Wstawienie lub usinięcie elementu na początku lub końcu listy wymagałoby modyfikacji wskaźnika u wszystkich użytkowników listy. Rozwiązaniem tego problemu jest wprowadzenie dwóch sztucznych elementów listy: głowy (ang. head) i ogona (ang. tail). Te dwa elementy nie zawierają danych, składają się tylko z węzła. Ich lokalizacja nie zmienia się przez cały czas istnienia listy, więc mogą być używane jako „kotwice” wspólne dla wszystkich użytkowników listy. Teraz wstawianie elementu na początek listy jest w istocie wstawianiem go między głowę listy i były pierwszy element. Podobnie wstawianie elementu na koniec, to wstawianie go między element uprzednio ostatni, a ogon listy. Adresy głowy i ogona pozostają stałe i mogą być współdzielone między użytkownikami.


Lista dwukierunkowa z elementami sztucznymi: głową i ogonem.

W liście systemowej głowa i ogon są połączone w jednej strukturze, zwanej nagłówkiem listy (ang. header). Ponieważ listy systemowe projektowano w czasach, gdy pamięci komputerów mierzono w kilobajtach, a nie gigabajtach, projektanci dostrzegli okazję zaoszczędzenia 4 bajtów. Pole poprzedni w głowie listy zawsze zawiera NULL. Pole następny w ogonie listy też zawsze zawiera NULL. W związku z tym oba te pola można połączyć w jedno. Dlatego nagłówek listy systemowej składa się z 3 a nie 4 wskaźników. W języku C nagłówek listy zdefiniowany jest jako struct List. Do list odwołujemy się zawsze przez wskaźnik na nagłówek.


Dwukierunkowa lista systemowa. Głowa i ogon listy połączone w nagłówek.

Elementy listy systemowej: węzeł i nagłówek

W systemie mamy zdefiniowane dwa rodzaje węzłów: pełny i minimalny. Węzeł minimalny składa się wyłącznie ze wskaźników na następny i poprzedni element listy. Dla języka C jest zdefiniowany w pliku nagłówkowym <exec/nodes.h>, w następujący sposób:

struct MinNode
{
  struct MinNode *mln_Succ;     // element następny (ang. successor)
  struct MinNode *mln_Pred;     // element poprzedni (ang. predecessor)
};

Pełny węzeł zawiera dodatkowe pola wykorzystywane w wielu listach systemu. Te pola to nazwa, typ i priorytet.

struct Node
{
  struct Node* ln_Succ;         // element następny
  struct Node* ln_Pred;         // element poprzedni
  UBYTE        ln_Type;         // typ elementu
  BYTE         ln_Pri;          // priorytet elementu
  char*        ln_Name;         // nazwa elementu
};

Dodatkowe pola mają znaczenie tylko w określonych listach utrzymywanych przez system i mogą być uważane za część danych elementu. Jeżeli zignorujemy typy języka C, pełny węzeł Node jest po prostu węzłem minimalnym MinNode z dodanymi na końcu trzema polami. Priorytet węzła może być wykorzystany do tworzenia list uporządkowanych lub kolejek. Exec.library zawiera funkcje do uporządkowanego wstawiania elementów.

Ponieważ mamy dwa rodzaje węzłów, mamy też dwa rodzaje nagłówków list. Oba są zdefiniowane w pliku <exec/lists.h>:

struct MinList
{
  struct MinNode* mlh_Head;      // wskaźnik do pierwszego prawdziwego elementu
  struct MinNode* mlh_Tail;      // połączone pola poprzedni głowy i następny ogona
  struct MinNode* mlh_TailPred;  // wskaźnik do ostatniego prawdziwego elementu
};

Pełny nagłówek zawiera dodatkowe pole typ (używane przez system) i jeden bajt wypełniający, zaokrąglający rozmiar struktury do wartości parzystej.

struct List
{
  struct Node* lh_Head;          // wskaźnik do pierwszego prawdziwego elementu
  struct Node* lh_Tail;          // połączone pola poprzedni głowy i następny ogona
  struct Node* lh_TailPred;      // wskaźnik do ostatniego prawdziwego elementu
  UBYTE        lh_Type;
  UBYTE        lh_pad;
};

Podobnie jak wyżej, po zignorowaniu typów języka C, nagłówek List to to samo, co MinList z dwoma dodatkowymi polami.

Listy systemowe są natrętne, więc każda struktura opisująca element listy musi zawierać w sobie węzeł (struktura MinNode, w razie potrzeby Node) jako pierwsze pole. Musi to być kompletny węzeł, nie wskaźnik. Oto przykład:

struct MyNode
{
  struct MinNode   Node;        // musi być na początku
  struct Whatever  Foobar;      // przykładowe dane elementu
  ULONG            Something;
  char             MoreData[10];
  /* ... */
};

Rozmiar elementu listy nie jest niczym ograniczony. Ponieważ w czasie manipulowania elementami listy dane nie są kopiowane, duże elementy są manipulowane dokładnie z taką samą prędkością jak małe.

Inicjalizacja listy, sprawdzenie czy lista jest pusta

Nagłówek listy, czy to struktura List, czy MinList musi być prawidłowo zainicjalizowana przed użyciem. Zapamiętaj:

Wyzerowanie nagłówka listy nie jest jej prawidłową inicjalizacją!

Patrząc na zamieszczone wcześniej diagramy można łatwo dojść do wniosku jak powinna wyglądać pusta lista:


Pusta lista.

Pusta lista zawiera wyłącznie głowę i ogon, jak zawsze połączone w nagłówek. Gdy w wyobraźni rozdzielimy głowę i ogon, inicjalizacja staje się oczywista:

Druga i trzecia operacja łączą się w jedną, bo wymienione pola są połączone w jedno. Poniższy kod prawidłowo inicjalizuje listę systemową. Zwróćmy uwagę na operator adresu &, często programiści zapominają o nim:
struct MinList mylist;

mylist.mlh_Head = (struct MinNode*)&mylist.mlh_Tail;
mylist.mlh_Tail = NULL;
mylist.mlh_TailPred = (struct MinNode*)&mylist.mlh_Head;

W przypadku używania pełnej struktury List inicjalizacja przebiega tak samo, jedynie rzutowania typów robione są na strukturę Node zamiast MinNode. Inicjalizacja listy jest często wykonywaną operacją, zatem plik nagłówkowy <exec/lists.h> definiuje makro NEWLIST.

Argumentem makra jest adres struktury List lub MinList, więc powyższy kod może być zastąpiony wywołaniem makra:
NEWLIST(&mylist);

Inną typową operacją jest sprawdzenie, czy lista jest pusta. Można ją wyprowadzić z diagramów. Istnieją cztery równoważne sposoby sprawdzenia, czy lista jest pusta:

if (mylist.mlh_Head->mln_Succ == NULL)                         /* lista jest pusta */
if (mylist.mlh_Head == (struct MinNode*)&mylist.mlh_Tail)      /* lista jest pusta */
if (mylist.mlh_TailPred->mln_Pred == NULL)                     /* lista jest pusta */
if (mylist.mlh_TailPred == (struct MinNode*)&mylist.mlh_Head)  /* lista jest pusta */

Makro IsListEmpty() zdefiniowane w <exec/lists.h> używa ostatniego sprawdzenia, uproszczonego dzięki temu, że adres pola mlh_Head jest tożsamy z adresem samego nagłówka (dobry kompilator tak, czy inaczej, uprości to sobie sam).

Iterator listy

Iterator listy to fragment kodu (zazwyczaj pętla), który kolejno przegląda listę element po elemencie i wykonuje jakieś operacje na elementach. Najprostszy iterator jest zwykle tworzony na bazie pętli for:

struct MyNode *n;
struct MinList *list;    // załóżmy, że lista jest poprawnie zainicjalizowana

for (n = (struct MyNode*)list->mlh_Head; n->Node.mln_Succ; n = (struct MyNode*)n->Node.mln_Succ)
{
  /* rób coś z węzłem 'n' */
}

Pierwsza część wyrażenia for ustawia wskaźnik n na pierwszy prawdzywy element listy (następny po jej głowie). Druga część to warunek zakończenia pętli. Zostaje ona przerwana, gdy pole następny aktualnego elementu zawiera NULL, co ma miejsce, gdy elementem aktualnym jest ogon listy. Pętla nie jest zatem wykonywana dla ogona, bo nie jest on „prawdziwym” elementem. Ostatnia wreszcie część wyrażenia for przesuwa wskaźnik n do następnego elementu. Można napisać symetryczny iterator do przeglądania listy wstecz, od końca do początku:

for (n = (struct MyNode*)list->mlh_TailPred; n->Node.mln_Pred; n = (struct MyNode*)n->Node.mln_Pred)
{
  /* rób coś z węzłem 'n' */
}

Tym razem wskaźnik n jest ustawiany na ostatni prawdziwy element (poprzedzający ogon), każdy obrót pętli przesuwa go do elementu poprzedzającego aktualny. Pętla kończy się, gdy pole poprzedni aktualnego elementu jest NULL-em, co zachodzi, gdy aktualnym elementem jest głowa listy. Tak więc dla samej głowy pętla nie jest wykonywana.

Plik <exec/lists.h> zawiera makro ForeachNode() tworzące pętlę for iteratora listy. Makro to jest trochę niebezpieczne, ponieważ na ślepo rzutuje typ wskaźnika węzła na struct Node* i typ wskaźnika listy na struct List*. W efekcie makro to całkowicie pomija statyczną kontrolę typów języka C. Może to prowadzić do błędów w kodzie. Znacznie bezpieczniej jest rzutować wskaźnik węzła na rzeczywisty typ elementu danej listy, tak jak to pokazałem w powyższych przykładach iteratorów. Bezpieczne makro generujące iterator powinno jako jeden z argumentów mieć typ elementów listy:

#define ForEachNode(n, T, list) for (n = (T)(list)->mlh_Head; n->Node.mln_Succ; n = (T)n->Node.mln_Succ)

Makra można używać następująco:

ForEachNode(n, struct MyNode*, list)
{
  /* rób coś z węzłem 'n' */
}

Co prawda to makro jest nieco mniej uniwersalne, bo zakłada listę minimalną (z nagłówkiem MinList), oraz zakłada, że pole węzła MinNode jest w strukturze elementu nazwane Node, jednak pozwala na wykorzystanie statycznej kontroli typów, a więc wyłapanie wielu błędów na etapie kompilacji programu. Podobne makro można zdefiniować dla iteratora przeglądającego listę wstecz. W języku C++ iteratory list systemowych mogą być zdefiniowane jako szablony.

Usuwanie elementów w iteratorze

Nieco uwagi należy zwrócić na przypadek, gdy iterator jest używany do selektywnego usunięcia niektórych elementów z listy. Początkujący programista może spróbować napisać następujący kod:

/* PRZYKŁAD ZŁEGO KODU */

ForEachNode(n, MyNode, list)
{
  if (/* jakiś warunek */)
  {
    Remove((struct Node*)n);
    FreeVec(n);
  }
}

Dlaczego ten kod jest niepoprawny? Gdy element n jest usuwany a jego pamięć zwalniana, odwołanie do n w następnym obrocie pętli jest odwołaniem się do zwolnionej pamięci. Najczęściej jej wartość pozostanie jeszcze niezmieniona. Dlatego ten błąd jest tak pospolity, łatwo go przeoczyć, jeżeli testy programu nie będą wystarczająco „ciężkie”. W dowolnym momencie system może przełączyć procesor na inny proces, który może zażądać przydziału pamięci i dostać nasz świeżo zwolniony element n, a następnie zmienić jego zawartość. Wtedy, gdy system zwróci procesor naszemu procesowi, n będzie wskazywał na bliżej nieokreślone dane, co z reguły spowoduje zawieszenie się programu. Rozwiązaniem tego problemu jest odczytanie wskaźnika na element następny po n zanim zwolnimy element n. W tym celu definiujemy dodatkowy wskaźnik:

struct MyNode *n, *n2;

for (n = (struct MyNode*)list->mlh_Head; n2 = (struct MyNode*)n->Node.mln_Succ; n = n2)
{
  if (/* jakiś warunek */)
  {
    Remove((struct Node*)n);
    FreeVec(n);
  }
}

Teraz wskaźnik na element następujący po n jest zapamiętany w n2 zanim n jest zwolniony. Przy następnym obrocie pętli iterator przesuwa się do następnego elementu i testuje koniec listy używając prawidłowej wartości wskaźnika n2 zamiast odwołania się do zwolnionej pamięci.

Sprawa jest prostsza, jeżeli chcemy bezwarunkowo usunąć wszystkie elementy listy i pozostawić ją pustą. Oczywiście nadal można użyć powyższej bezpiecznej pętli, ale jest nieco szybsza alternatywa:

while (n = (struct MyNode*)RemHead((struct List*)list)) FreeVec(n);

W pętli tej można też użyć funkcji RemTail(), bo zazwyczaj gdy opróżniamy całą listę, kolejność usuwania elementów nie ma znaczenia.

Dodawanie i usuwanie elementów

Dodanie elementu w dowolnym miejscu listy wymaga jedynie aktualizacji 4 wskaźników, niezależnie od rozmiaru elementu. Poniższy rysunek wyjaśnia przebieg operacji.


Wstawianie elementu do listy dwukierunkowej

Rysunkowi odpowiada następujący kod:

struct MyNode *n;    /* wstaw po tym elemencie */
struct MyNode *a;    /* wstaw ten element */

n->Node.mln_Succ->mln_Pred = &a.Node;   /* 1 */
a->Node.mln_Succ = n->Node.mln_Succ;    /* 2 */
a->Node.mln_Pred = &n.Node;             /* 3 */
n->Node.mln_Succ = &a.Node;             /* 4 */

Zwróćmy uwagę na kolejność operacji, która jest tu istotna. Gdyby ktoś np. zaczął od operacji nr 4, straciłby dostęp do reszty listy za punktem wstawiania.

Usuwanie elementu jest jeszcze prostsze, bo wymaga zmiany tylko dwóch wskaźników: jednego w elemencie poprzednim względem usuwanego i jednego w elemencie następnym. Oto przykład usunięcia jakiegoś elementu n:

n->Node.mln_Pred->mln_Succ = n->Node.mln_Succ;
n->Node.mln_Succ->mln_Pred = n->Node.mln_Pred;

Operacje usuwania i wstawiania elementu listy zostały w MorphOS-ie ustandaryzowane na dwa sposoby: jako funkcje biblioteki exec.library i jako makra. Funkcje nazywają się Insert() i Remove(), odpowiadające im makra to INSERT() i REMOVE(). Zarówno funkcja Insert() jak i makro INSERT() wymagają adresu nagłówka listy jako dodatkowego arguentu. Chociaż w ogólnym przypadku ten argument jest zbędny, dzięki niemu można wstawiać element na początek listy podając NULL jako pozycję wstawiania. Wstawianie na początku można też uzyskać podając adres nagłówka jako pozycję wstawiania.

Należy pamiętać o tym, że ani funkcja Remove() ani makro REMOVE() nie sprawdzają czy usuwany węzeł faktycznie znajduje się na liście. Próba „usunięcia” z listy węzła, który się na niej nie znajduje, skończy się uszkodzeniem zawatości przypadkowych adresów pamięci i zawieszeniem się co najmniej naszego programu.

Głowa i ogon

Bardzo częstą operacją jest wstawianie elementów na początek lub na koniec listy. Przykładowo struktury danych takie jak stos, czy kolejka mogą być zaimplementowane przy pomocy listy. W stosie element są dodawane na początek listy i zdejmowane też z początku. W przypadku kolejki dodajemy elementy na końcu a wyjmujemy na początku.

Istnienie w liście pseudoelementów głowy i ogona ma taką dodatkową zaletę, że operacje na obu końcach listy nie różnią się od ogólnego przypadku operacji w środku. Wystarczy zastąpić – na rysunku w poprzednim podrozdziale – element po lewej stronie głową listy, albo element po prawej jej ogonem. Uproszczenie zagadnienia polega na tym, że funkcje usuwające element z jednego z końców listy jako jedyny argument mają adres nagłówka listy. Funkcje dodające element mają oczywiście drugi argument – wstawiany węzeł. Do naszej dyspozycji jest komplet czterech operacji:

Operacje usuwające węzeł jako wynik zwracają adres usuniętego węzła, albo NULL jeżeli lista jest pusta.

Funkcje, czy makra?

Po przeczytaniu całego powyższego tekstu powinno być jasne, że większość operacji na listach jest bardzo prosta i zazwyczaj kompiluje się do kilku rozkazów procesora. Dlatego właśnie zostały zdefiniowane również jako makra. Czego więc używać? Generalnie makra są szybsze, chociaż niektóre z nich mogą być o parę bajtów dłuższe niż wywołania funkcji bibliotecznych (zwłaszcza INSERT()). Z drugiej strony nawet kilka kilobajtów dodatkowego kodu nie jest w dzisiejszych czasach problemem, a przyspieszenie programu jest zawsze w cenie. Tak więc w miejscach, gdzie prędkość ma znaczenie, zawsze lepiej użyć makr.

Kolejkowanie

Struktura pełnego węzła listy zawiera pole priorytetu elementu, o nazwie ln_Pri. Pole to jest często stosowane przez system do organizowania list lub kolejek z priorytetami (np. lista procesów). Aby utrzymać uporządkowanie listy według priorytetów potrzebna jest specjalna operacja wstawiania elementów. Operacji tej dostarcza exec.library, a zwie się ona Enqueue(). Funkcja ta bierze węzeł (musi to być pełny węzeł Node, nie minimalny MinNode), sprawdza jego priorytet, znajduje miejsce do wstawienia węzła i wstawia go. Jeżeli na liście znajdują się już elementy o takim samym priorytecie, nowy element zostaje wstawiony przed nimi. Oczywiście funkcję Enqueue() można wykorzystać w aplikacjach do własnych celów. Trzeba jednak pamiętać, że pole priorytetu ma jedynie rozmiar bajtu (ze znakiem), a funkcja staje się wolna dla długich list, ponieważ szukając pozycji wstawiania przegląda elementy jeden po drugim.