Sentinel (programming)

from Wikipedia, the free encyclopedia

As Sentinel (pronounced sentinel ? / I ., English for Guardian ) Guardian node or guardians value (in the narrow sense) is known in the computer science , in the field of programming , a construct which terminates a sequence such that the program logic unsuccessful after a Final inspection of all real cases (with false success) on the result "found" is running. If so, the result is subsequently corrected to "not found". Audio file / audio sample

This trick reduces the number of queries within the search loop by one , namely the query for the end of the sequence - at the expense of slightly more complicated requirements and actions outside the loop.

In a broader sense (especially in the English-speaking world), every termination of a sequence by a special object that does not normally occur there, for example the zero character in character strings , is considered a sentinel.

example

In the following two C functions, Searchand SearchWithSentinelshould be in a singly linked list of type 

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

be search_keysearched for a key value - with the same search result.

Version with zero pointer

The list sllis terminated by the zero pointer NULL . 

 1 first = NULL;                 // Terminierung vor der ersten Einfügung
 2 // NB: Die (nicht gezeigten) Operationen Einfügen und Löschen haben für ...
 3 //     den immer gleichen Terminator (hier: NULL) zu sorgen.
 4 
 5 struct sll_node *Search(int search_key)
 6 {
 7     struct sll_node *node;
 8     for (node = first;
 9          node != NULL;
10          node = node->next)
11     {
12         if (node->key == search_key)
13             return node;      // gefunden
14     }
15     return NULL;              // nicht gefunden
16 }

The forloop contains the two queries (highlighted in yellow) for each loop step

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

Version with Sentinel

The pointer sentinel to the object Sentinelserves as the terminator of the linked list sll. The object Sentinelis to be prepared specifically for the loop. (In that sense, it's part of the data structure sll.) 

 1 struct sll_node Sentinel, *sentinel = &Sentinel;
 2 sentinel->next = sentinel;
 3 first = sentinel;             // Terminierung vor der ersten Einfügung
 4 // NB: Die (nicht gezeigten) Operationen Einfügen und Löschen haben für ...
 5 //     den immer gleichen Terminator (hier: Zeigerwert) zu sorgen.
 6 
 7 struct sll_node *SearchWithSentinel(int search_key)
 8 {
 9     struct sll_node *node;
10     // gezielte Präparation:
11     sentinel->key = search_key;
12 
13     for (node = first;
14          node->key != search_key;
15          node = node->next)
16     {
17     }
18     if (node != sentinel)
19         return node;          // gefunden
20     return NULL;              // nicht gefunden
21 }

The forloop contains only one query (highlighted in yellow) per loop step

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

The introduction of the Guard Node turns the search operation, which would be read-only without it , into a modifying operation (similar to insert and delete). If the data structure is accessed in parallel (competitor), the search via also belongs SearchWithSentinelin a critical section , which must be secured by a mutex . This additional effort can outweigh the saving of one query per loop step.

See also

Individual evidence

  1. ^ Kurt Mehlhorn , Peter Sanders : Algorithms and Data Structures. The Basic Toolbox . Springer, Berlin / Heidelberg 2008, ISBN 978-3-540-77977-3 , p. 63 , doi : 10.1007 / 978-3-540-77978-0 . 3 Representing Sequences by Arrays and Linked Lists
  2. ↑ A pointer , which can have the value 0, must be queried for 0 prior to dereferencing , since dereferencing otherwise leads to a crash on most operating system-machine combinations.