Sentinel (Programmierung)

Als Sentinel (Aussprache: , engl. für Wächter), Wächterknoten oder Wächterwert (im engeren Sinn) bezeichnet man in der Informatik, im Bereich der Programmierung, ein Konstrukt, welches eine Sequenz derart terminiert, dass die Programmlogik nach einer erfolglosen Inspektion aller echten Fälle abschließend (mit unechtem Erfolg) auf das Ergebnis »gefunden« läuft.^[1] Wenn so geschehen, wird nachträglich das Ergebnis auf »nicht gefunden« korrigiert.

Mit diesem Trick wird die Anzahl der Abfragen innerhalb der Suchschleife um eine, nämlich die Abfrage auf das Ende der Sequenz, verringert – auf Kosten geringfügig komplizierterer Erfordernisse und Aktionen außerhalb der Schleife.

Im weiteren Sinn gilt (insbesondere im englischen Sprachraum) jede Terminierung einer Sequenz durch ein normalerweise dort nicht vorkommendes spezielles Objekt, so bspw. das Nullzeichen bei Zeichenketten, als Sentinel.

Beispiel

In den beiden folgenden C-Funktionen Search und SearchWithSentinel soll in einer einfach verketteten Liste vom Typ

struct sll_node               // ein Knoten der verketteten Liste sll
{
   int key;
   struct sll_node *next;     // -> nächster Knoten oder Terminator der Liste
} sll,
*first;                       // Zeiger auf die verkettete Liste

nach einem Schlüsselwert search_key gesucht werden – bei gleichem Suchergebnis.

Version mit Nullzeiger

Die Liste sll wird terminiert durch den Nullzeiger NULL.^[2]

first = NULL;                 // Terminierung vor der ersten Einfügung
// NB: Die (nicht gezeigten) Operationen Einfügen und Löschen haben für ...
//     den immer gleichen Terminator (hier: NULL) zu sorgen.

struct sll_node *Search(int search_key)
{
    struct sll_node *node;
    for (node = first;
         node != NULL;
         node = node->next)
    {
        if (node->key == search_key)
            return node;      // gefunden
    }
    return NULL;              // nicht gefunden
}

Die for-Schleife enthält pro Schleifenschritt die zwei (gelb hinterlegten) Abfragen

• if (node != NULL) und
• if (node->key == search_key).

Version mit Sentinel

Der Zeiger sentinel zum Objekt Sentinel dient als Terminator der verketteten Liste sll. Das Objekt Sentinel ist für die Schleife gezielt zu präparieren. (In diesem Sinn ist es Teil der Datenstruktur sll.)

struct sll_node Sentinel, *sentinel = &Sentinel;
sentinel->next = sentinel;
first = sentinel;             // Terminierung vor der ersten Einfügung
// NB: Die (nicht gezeigten) Operationen Einfügen und Löschen haben für ...
//     den immer gleichen Terminator (hier: Zeigerwert) zu sorgen.

struct sll_node *SearchWithSentinel(int search_key)
{
    struct sll_node *node;
    // gezielte Präparation:
    sentinel->key = search_key;

    for (node = first;
         node->key != search_key;
         node = node->next)
    {
    }
    if (node != sentinel)
        return node;          // gefunden
    return NULL;              // nicht gefunden
}

Die for-Schleife enthält pro Schleifenschritt nur die eine (gelb hinterlegte) Abfrage

• if (node->key != search_key).

Bemerkung

Die Einführung des Wächterknotens macht aus der Operation Suchen, die ohne ihn eine Nur-Lese-Operation wäre, eine modifizierende Operation (ähnlich Einfügen und Löschen). Wird auf die Datenstruktur parallel (konkurrent) zugegriffen, dann gehört auch das Suchen per SearchWithSentinel in einen kritischen Abschnitt, der durch ein Mutex abgesichert werden muss. Dieser zusätzliche Aufwand kann schwerer wiegen als das Einsparen einer Abfrage pro Schleifenschritt.

Siehe auch

• Binärer Suchbaum#Suchen ohne Duplikate (iterativ und mit Sentinel) Wächterknoten in einem binären Suchbaum
• Sentinel-Lymphknoten, siehe Wächterlymphknoten

Einzelnachweise

1. ↑ Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin/Heidelberg 2008, ISBN 978-3-540-77977-3, S. 63, doi:10.1007/978-3-540-77978-0.  3 Representing Sequences by Arrays and Linked Lists
2. ↑ Ein Zeiger, der den Wert 0 haben kann, muss vor der Dereferenzierung ohnehin auf 0 abgefragt werden, da die Dereferenzierung sonst auf den meisten Betriebssystem-Maschinen-Kombinationen zum Crash führt.