Sentinel (Programmierung)

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

Damit wird die Anzahl der Abfragen innerhalb der Suchschleife um eine (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

// Globale Variable:
struct sll_node {                          // ein Knoten der verketteten Liste
   int key;
   struct sll_node *next;                  // end-of-list-Indikator oder -> nächten Knoten
} sll, *first;

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; // vor der ersten Einfügung
// NB: Einfügung nicht gebracht. Sie hat aber für den immer gleichen Terminator zu sorgen.

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

Die for-Schleife enthält pro Schleifenschritt die zwei Abfragen

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

Version mit Sentinel

Der global zugreifbare Zeiger sentinel zum gezielt präparierten Objekt Sentinel dient als Terminator der Liste sll.

// Globale Variable:
struct sll_node Sentinel, *sentinel = &Sentinel;
// Global:
sentinel->next = sentinel;
first = sentinel; // 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(struct sll_node *first, int search_key) {
    struct sll_node *node;
    sentinel->key = search_key;        // gezielte Präparation

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

Die for-Schleife enthält pro Schleifenschritt nur die eine Abfrage

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

Siehe auch

• Suchmethode en:Elephant in Cairo (englisch), die auf einen satirischen Essay über verschiedene Suchmethoden nach Elefanten in Afrika zurückgeht.
• Sentinel-Lymphknoten, siehe Wächterlymphknoten