Sentinel (Programmierung)

Begriff und Zweck

Ein Sentinel, Wächterknoten oder – im engeren Sinn – Wächterwert ist ein Programmierkonstrukt, das das Ende einer Sequenz markiert. Bei einer Suche wird der Sentinel so eingerichtet, dass die Schleife nach der erfolglosen Prüfung aller echten Elemente scheinbar doch ein passendes Element „findet“. Anschließend prüft das Programm, ob tatsächlich ein echtes Element oder nur der Sentinel getroffen wurde, und korrigiert das Ergebnis gegebenenfalls zu „nicht gefunden“.

Dadurch entfällt innerhalb der Suchschleife die zusätzliche Prüfung, ob das Ende der Sequenz erreicht ist. Dafür werden Vorbereitung und Auswertung außerhalb der Schleife etwas aufwendiger. Im weiteren Sinn bezeichnet Sentinel jedes besondere Objekt, das normalerweise nicht in der Sequenz vorkommt und sie beendet, beispielsweise das Nullzeichen bei Zeichenketten.

Suche mit Nullzeiger

Im Beispiel wird in einer einfach verketteten Liste nach dem Schlüsselwert search_key gesucht. Jeder Knoten enthält den ganzzahligen Schlüssel key und mit next einen Zeiger auf den nächsten Knoten. In der herkömmlichen Version beendet der Nullzeiger NULL die Liste.

Die Funktion Search beginnt beim Zeiger first und durchläuft die Liste. In jedem Schleifenschritt prüft sie erst, ob node != NULL gilt, und danach, ob node->key == search_key ist. Bei Übereinstimmung gibt sie den gefundenen Knoten zurück. Wird das Listenende erreicht, liefert sie NULL als Zeichen für „nicht gefunden“. Einfüge- und Löschoperationen müssen dafür sorgen, dass NULL stets der Terminator bleibt.

Suche mit Wächterknoten

In der Sentinel-Version beendet ein eigener Knoten Sentinel die Liste; der Zeiger sentinel zeigt auf ihn. sentinel->next verweist auf den Sentinel selbst, und eine anfangs leere Liste beginnt mit first = sentinel. Der Wächterknoten ist damit Teil der Datenstruktur, und auch hier müssen Einfügen und Löschen den festgelegten Terminator erhalten.

Vor jeder Suche setzt SearchWithSentinel den Schlüssel des Wächterknotens auf den gesuchten Wert: sentinel->key = search_key. Deshalb trifft die Schleife spätestens beim Sentinel auf den Suchwert. Innerhalb der Schleife genügt die einzige Prüfung node->key != search_key; eine gesonderte Kontrolle des Listenendes entfällt. Nach der Schleife entscheidet node != sentinel, ob ein echter Listenknoten gefunden wurde. Ist dies der Fall, wird der Knoten zurückgegeben, andernfalls NULL.

Vorteil und Nebenwirkung

Der Sentinel spart pro Schleifenschritt eine Abfrage: Die gewöhnliche Version prüft sowohl das Listenende als auch den Schlüssel, die Sentinel-Version nur den Schlüssel.

Die Vorbereitung sentinel->key = search_key verändert jedoch die Datenstruktur. Damit wird die Suche, die ohne Sentinel nur lesend wäre, zu einer modifizierenden Operation. Bei parallelem beziehungsweise konkurrentem Zugriff muss SearchWithSentinel deshalb in einem kritischen Abschnitt ausgeführt und durch ein Mutex – eine Sperre zum Schutz gemeinsam genutzter Daten – abgesichert werden. Dieser zusätzliche Aufwand kann schwerer wiegen als die eingesparte Abfrage.