Sentinel (programming)
As Sentinel (pronounced 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".
., English for Guardian ) Guardian node or guardians value (in the narrow sense) is known in theThis 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, Search
and SearchWithSentinel
should 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_key
searched for a key value - with the same search result.
Version with zero pointer
The list sll
is 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 for
loop 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 Sentinel
serves as the terminator of the linked list sll
. The object Sentinel
is 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 for
loop 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 SearchWithSentinel
in 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
- Binary search tree # Search without duplicates (iterative and with Sentinel) Guard nodes in a binary search tree
- Sentinel lymph nodes, see sentinel lymph nodes
Individual evidence
- ^ 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
- ↑ 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.