„Sentinel (Programmierung)“ – Versionsunterschied

Als Sentinel (Aussprache: sentinel^ⓘ, engl. für Wächter), Wächter 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. 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 Form eines Terminators einer Sequenz, so auch das Nullzeichen bei Zeichenketten, als Sentinel.

Beispiel

In den beiden folgenden C-Funktionen Search und SearchWithSentinel soll in einer 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;                       // globale Variable

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

Version mit NULL

Die Liste sll wird terminiert durch den Nullwert NULL.

// Global:
first = NULL;                 // Terminierung vor der ersten Einfügung
// NB: Einfügung nicht gebracht. Sie hat aber für ...
//     den immer gleichen Terminator (hier: Nullzeiger) 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 hinterlegte) Abfragen

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

Version mit Sentinel

Der global zugreifbare Zeiger sentinel zum für die Schleife gezielt zu präparierenden Objekt Sentinel dient als Terminator der Liste sll.

// Globale Variable:
struct sll_node Sentinel, *sentinel = &Sentinel;
// Global:
sentinel->next = sentinel;
first = sentinel;             // Terminierung vor der ersten Einfügung
// NB: Einfügung nicht gebracht. Sie hat aber 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

Wird auf die Datenstruktur parallel (konkurrent) zugegriffen, dann gehört auch das Suchen per SearchWithSentinel (modifizierende Operationen wie Einfügen und Löschen sowieso) in einen kritischen Abschnitt, der durch ein Mutex abgesichert werden muss. Dieser Nachteil kann wesentlich schwerer wiegen als der marginale Vorteil durch 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